トライとパトリシア
今回は簡単な例題として、「トライ (trie)」と「パトリシア (patricia)」というデータ構造を作ってみましょう。どちらも木構造の一種で、根 (root) から葉 (leaf) までの経路が一つの文字列に対応します。トライやパトリシアは文字列を高速に探索することができますが、それだけではなく、共通の接頭辞 (common prefix) を持つ文字列、たとえば 'abc' で始まる文字列を簡単に見つけることができます。
●トライとは？
トライは文字列の集合を表すのに都合のよいデータ構造です。トライの語源は、「検索 (retrieval)」という言葉の真ん中 (trie) に由来しています。トライは木構造の一種であり、根から葉までの経路がひとつの単語に対応します。次の図を見てください。
図 1 : 文字列の集合を表したトライ
上図は文字列の集合をトライで表現したものです。ここでは葉を $ で表しています。たとえば、葉 $6 までたどると、それは "THEN" という文字列を表しています。また、文字列 "THE" をトライから探す場合は、節を順番にたどっていって、葉 $6 に達した時点で "THE" を見つけることができます。もし、節 E の子に葉 $6 がなければ、THE はトライに存在しないことになります。
この例は文字列ですが、リスト (a b c d) やベクタ #(e f g h) などのデータも「トライ」で表すことができます。
●トライの実装方法
さて、トライの実現方法ですが、二分木と同様に子を格納するスロットを用意すれば簡単です。たとえば、英大文字と葉を示す $ がデータとすると、ひとつの節から最大 27 の子に分岐します。この場合、子を格納するスロットを CHILD とし、$ を含めてサイズが 27 のベクタを CHILD にセットすればいいでしょう。
ただし、データの種類が多くなるとベクタのサイズが大きくなるので、メモリを大量に消費してしまうのが欠点です。このため、トライを二分木のように構成する方法があります。次の図を見てください。
上図に示すように、縦に親子関係が伸びていき、横に兄弟の関係が伸びていくと考えてください。ようするに、二分木の右部分木が兄弟関係を表し、左部分木が親子の関係を表しているわけです。今回は Lisp でプログラムを作るので、子は Lisp らしくリストに格納して、それを CHILD にセットすることにしましょう。つまり、二分木ではなく「多分木」になります。この場合、トライをたどるときにリストの中から子を探す処理が必要になりますが、プログラムは簡単になります。
トライで公開するメソッドを下表に示します。
| メソッド | 機能 |
|---|---|
| trie-match tree seq | tree から seq を探索する |
| trie-put tree seq | tree に seq を追加する |
| trie-delete tree seq | tree から seq を削除する |
| trie-fold tree func init | tree の要素に畳み込みを行う |
| trie-for-each tree func | tree の要素に関数 func を適用する |
| trie-emptyp tree | tree が空の場合は #t を返す |
| trie-length tree | tree の要素数を求める |
引数 tree はトライを表します。引数 seq には列型 (sequence) のデータを渡します。メソッド trie-match は seq の有無だけではなく、seq が見つからない場合でも途中まで一致したした長さを返すことにします。
●クラスの定義
それでは CLOS でプログラムを作りましょう。最初にクラスを定義します。
リスト : トライの定義
;;; 節
(defclass node ()
((item :accessor node-item :initarg :item :initform nil)
(child :accessor node-child :initarg :child :initform nil)))
;;; トライ
(defclass trie ()
((root :accessor trie-root
:initform (make-instance 'node) ; ヘッダ
:initarg :root)
(obj= :accessor trie-obj=
:initform #'eql
:initarg :obj=)))
節はクラス NODE で表します。スロット ITEM に列型データの要素をセットし、スロット CHILD に子を格納したリストをセットします。トライのクラス名は TRIE とします。スロット ROOT にはヘッダ用の節を格納します。ヘッダの ITEM はダミーで NIL に初期化します。そして、スロット OBJ= に 2 つの引数が等しいか調べる述語をセットします。デフォルトの述語は eql です。
次に、終端 (葉) を表す節を初期化します。
リスト : 終端の初期化
;;; 終端
(defvar *term*)
;;; 終端の初期化
(defmethod initialize-instance ((obj trie) &rest initargs)
(declare (ignore initargs))
(call-next-method)
(unless (boundp '*term*)
(setf *term* (make-instance 'node))))
終端はグローバル変数 *TERM* にセットします。この処理はメソッド initialize-instance で行います。*TERM* が未束縛の場合にのみ、make-instance で NODE のインスタンスを生成して *TERM* にセットします。
●節の操作関数
次は節を操作する関数を作ります。
リスト : 節の操作関数
;;; 子を探す
(defun trie-search-child (node x obj=)
(find x (node-child node) :key #'node-item :test obj=))
;;; 子を追加する
(defun insert-child (node x)
(let ((new-node (make-instance 'node :item x)))
(push new-node (node-child node))
new-node))
;;; 終端のチェック
(defun search-terminal (node)
(consp (member *term* (node-child node))))
;;; 終端を追加する
(defun insert-terminal (node)
(push *term* (node-child node))
t)
;;; 終端を削除する
(defun delete-terminal (node)
(setf (node-child node)
(remove *term* (node-child node)))
t)
trie-search-child は節 NODE の CHILD から X を持つ子を探します。この処理は列関数 find を使うと簡単です。キーワード :key に #'node-item を指定して、節から比較するデータを取り出します。比較関数はキーワード :test で指定します。insert-child は節 NODE に X を持つ子を挿入します。make-instance で新しい節 NEW-NODE を生成し、それをスロット CHILD の先頭に追加します。
search-terminal は NODE のスロット CHILD に終端があるか調べます。真偽値 (T or NIL) を返したいので、member の返り値を consp でチェックしています。insert-terminal は NODE の子に終端を挿入します。delete-terminal は NODE の子から終端を削除します。
●データの探索
次はデータを探索するメソッド trie-match を作ります。
リスト : データの探索
(defun node-match (node seq obj=)
(dotimes (x (length seq)
(values (search-terminal node) x))
(let ((p (trie-search-child node (elt seq x) obj=)))
(if (null p)
(return (values nil x))
(setf node p)))))
(defmethod trie-match ((tree trie) (seq sequence))
(node-match (trie-root tree) seq (trie-obj= tree)))
実際の処理は関数 node-match で行います。列関数 elt で引数 SEQ の要素をひとつずつ取り出して、トライをたどっていきます。elt を使っているので、SEQ が列型データ (sequence) であれば動作します。trie-search-child で SEQ の要素と等しい子を探して変数 P にセットします。見つからなければ return で (values nil x) を返します。X がマッチングした長さになります。等しい子を見つけたら P を NODE にセットして、次の要素と比較します。SEQ の要素をすべてチェックしたら、最後に終端オブジェクトがあるか確認します。
●データの挿入
次はデータを挿入するメソッド trie-put を作ります。
リスト : データの挿入
(defun node-put (node seq obj=)
(dolist (x (coerce seq 'list))
(let ((p (trie-search-child node x obj=)))
(setf node (if p p (insert-child node x)))))
;; 終端を挿入
(unless (search-terminal node)
(insert-terminal node)))
(defmethod trie-put ((tree trie) seq)
(node-put (trie-root tree) seq (trie-obj= tree)))
引数 SEQ を coerce でリストに変換します。そして、dolist で要素をひとつずつ取り出して、トライに追加していきます。取り出した要素 X を持つ子を trie-search-child で探して変数 P にセットします。P が真の場合、X と等しい子が見つかったので、P を NODE にセットして次の要素をチェックします。
見つからない場合は insert-child を呼び出して、要素 X を格納した節を NODE の CHILD に追加します。そして、新しい節を NODE にセットします。最後に、search-terminal で終端をチェックします。もしも終端があれば、すでに SEQ はトライに含まれています。そうでなければ新しいデータなので、insert-terminal で終端を追加します。
●データの削除
次はデータを削除するメソッド trie-delete を作ります。
リスト : データの削除
(defun node-delete (node seq obj=)
(dolist (x (coerce seq 'list)
(when (search-terminal node)
(delete-terminal node)))
(let ((p (trie-search-child node x obj=)))
(if (null p)
(return)
(setf node p)))))
(defmethod trie-delete ((tree trie) seq)
(node-delete (trie-root tree) seq (trie-obj= tree)))
データの削除は SEQ に対応する葉を削除するだけです。この場合、不要になった節 (node) が残ったままになるので、メモリを余分に消費する欠点があります。今回はこの対策を行っていません。ご注意ください。興味のある方は不要になった節を取り除くようにプログラムを改造してみてください。
トライをたどる処理は今までと同じです。トライをたどれない場合は、削除するデータがないので NIL を返します。あとは、最後に search-terminal で終端をチェックし、データがあれば終端を delete-terminal で削除するだけです。
●巡回と畳み込み
次は巡回と畳み込みを行うメソッド trie-for-each と trie-fold を作ります。
リスト : 巡回
(defun node-for-each (node func a)
(if (eq *term* node)
(funcall func (reverse a))
(let ((a1 (cons (node-item node) a)))
(dolist (x (node-child node))
(node-for-each x func a1)))))
(defmethod trie-for-each ((tree trie) func)
(dolist (x (node-child (trie-root tree)))
(node-for-each x func nil)))
巡回の処理は関数 node-for-each で行います。引数 A は累積変数で、節の ITEM をリストに格納したものです。NODE が終端の場合、reverse で A を反転して関数 func に渡します。そうでなければ、節の ITEM を A に追加し、dolist で NODE の子を順番にたどります。
リスト : 畳み込み
(defun node-fold (node func seq a)
(if (eq *term* node)
(funcall func (reverse seq) a)
(let ((seq1 (cons (node-item node) seq)))
(dolist (x (node-child node) a)
(setf a (node-fold x func seq1 a))))))
(defmethod trie-fold ((tree trie) func a)
(dolist (x (node-child (trie-root tree)) a)
(setf a (node-fold x func nil a))))
畳み込みの処理は関数 node-fold で行います。引数 SEQ が節の ITEM を格納するリストで、引数 A が畳み込み用の累積変数です。NODE が終端の場合、関数 FUNC に (reverse seq) と A を渡して呼び出します。そうでなければ、節の ITEM を SEQ に追加し、dolist で NODE の子を順番にたどります。このとき、node-fold の返り値で変数 A の値を更新することを忘れないでください。最後に A の値を返します。
●共通接頭辞を持つデータの探索
最後に共通接頭辞 (common prefix) を持つデータを求めるメソッド trie-common-prefix を作ります。
リスト : 共通接頭辞を持つデータを求める
(defun node-common-prefix (node seq obj= a)
(dolist (x (coerce seq 'list)
(node-fold node #'cons (cdr a) nil))
(push x a)
(let ((p (trie-search-child node x obj=)))
(if (null p)
(return)
(setf node p)))))
(defmethod trie-common-prefix ((tree trie) seq)
(node-common-prefix (trie-root tree) seq (trie-obj= tree) nil))
実際の処理は関数 node-common-prefix で行います。引数 SEQ に接頭辞 (prefix) を渡します。引数 A には節の ITEM を格納するリストをセットします。SEQ の探索が成功したら、node-fold を呼び出して、接頭辞から下の部分木にあるデータを求めるだけです。node-fold を呼び出すとき、最初の NODE の要素が重複するので、(cdr a) で先頭要素を取り除いています。
後のメソッドは簡単なので説明は割愛いたします。詳細は プログラムリスト をお読みください。
●実行例
それでは、簡単な実行例を示します。プログラムはパッケージ TRIE にまとめておき、カレントディレクトリにあるものとします。
* (require :trie "trie.lisp")
("TRIE")
* (use-package :trie)
T
* (setq a (make-instance 'trie))
#<TRIE {100267B093}>
* (dotimes (x 10) (trie-put a (princ-to-string (random 5000000))))
NIL
* (trie-for-each a #'print)
(#\2 #\9 #\7 #\9 #\8 #\5 #\6)
(#\2 #\7 #\9 #\9 #\9)
(#\5 #\0 #\5 #\8 #\2 #\3)
(#\1 #\4 #\8 #\4 #\3 #\2 #\5)
(#\1 #\4 #\2 #\1 #\2 #\8 #\1)
(#\1 #\4 #\4 #\6 #\8 #\4)
(#\4 #\9 #\5 #\8 #\4 #\0 #\4)
(#\4 #\3 #\9 #\8 #\9 #\6 #\9)
(#\3 #\7 #\8 #\8 #\0 #\5 #\8)
(#\3 #\0 #\5 #\5 #\3 #\5 #\0)
NIL
* (trie-match a "144684")
T
6
* (trie-match a "14468")
NIL
5
* (trie-match a "142128")
NIL
6
* (trie-delete a "27999")
T
* (trie-delete a "27999")
NIL
* (trie-match a "27999")
NIL
5
* (trie-common-prefix a "14")
((#\1 #\4 #\4 #\6 #\8 #\4) (#\1 #\4 #\2 #\1 #\2 #\8 #\1)
(#\1 #\4 #\8 #\4 #\3 #\2 #\5))
正常に動作していますね。もうひとつ簡単な例として suffix trie を作成してみましょう。サフィックス (suffix : 接尾辞) とは、文字列のある位置から末尾までの文字列のことです。たとえば、文字列 "abcd" のサフィックスは abcd, bcd, cd, d の 4 つになります。このサフィックスをトライで表したものが suffix trie で、文字列の照合などに用いられるデータ構造です。このほかに、サフィックスを辞書順に並べた配列 suffix array や、suffix trie を改良した suffix tree というデータ構造もあります。
suffix trie は、サフィックスを順番にトライに追加していくだけで作成できます。次のリストを見てください。
リスト : suffix trie の作成
(defun make-suffix-trie (data)
(let ((x (make-instance 'trie)))
(dotimes (n (length data))
(trie-put x (subseq data n)))
(trie-for-each x #'print)))
とても簡単な方法ですが、データが多くなると時間がかかるのが欠点です。データ数を N とすると、実行時間は N2 に比例します。ご注意くださいませ。
それでは実行例を示します。
* (make-suffix-trie "aeadacab") (#\b) (#\c #\a #\b) (#\d #\a #\c #\a #\b) (#\e #\a #\d #\a #\c #\a #\b) (#\a #\b) (#\a #\c #\a #\b) (#\a #\d #\a #\c #\a #\b) (#\a #\e #\a #\d #\a #\c #\a #\b) NIL * (make-suffix-trie '(a e a d a c a b)) (B) (C A B) (D A C A B) (E A D A C A B) (A B) (A C A B) (A D A C A B) (A E A D A C A B) NIL
●パトリシアとは？
トライはとても便利なデータ構造ですが、節にはひとつの文字しか格納できないため、文字列の種類が多くなるとメモリを大量に消費してしまいます。このため、文字ではなく文字列を節に格納する方法があります。次の図を見てください。
図 3 : 文字列の集合を表したパトリシア
"TAIL" をトライで表すと T - A - I - L となりますが、I の子は L しかありませんね。この部分は "IL" とまとめることができます。つまり、節には部分文字列を格納するわけです。このように、トライにおいて分岐していない節をひとつにまとめたものを「パトリシア (Patricia Tree)」と呼ぶことがあります。
パトリシアの場合、データの探索は節の部分文字列を比較していくだけなので、簡単に実現できます。ところが、データの挿入はちょっとだけ複雑になります。たとえば、パトリシアが "ab" - "cdef" という状態で、ここに文字列 "abcdgh" を挿入してみましょう。
挿入する文字列の先頭 2 文字と最初の節 "ab" は一致するので、次の節 "cdef" と残りの文字列 "cdgh" を比較します。"cd" は一致しますが、それ以降で不一致になりますね。この場合、節 "cdef" を不一致の位置で分割します。つまり、節 "cdef" を "cd" - "ef" と分割し、節 "cd" に新しい節 "gh" を追加するのです。このあと、終端オブジェクトを追加すれば、パトリシアに "abcdgh" を挿入することができます。
このように、パトリシアにデータを挿入する場合、節の分割が必要になるためプログラムは複雑になります。そのかわり、パトリシアはトライに比べて節の個数を少なくすることができるので、トライよりも少ないメモリで文字列の集合を表すことができます。
●パトリシアのクラス定義
それではプログラムを作りましょう。最初にパトリシアを表すクラスを定義します。
リスト : クラス定義 (defclass patricia (trie) ())
クラス TRIE を継承してクラス PATRICIA を定義します。新しく追加するスロットはありません。メソッドは trie-match, trie-put, trie-delete, trie-common-prefix をオーバーライドします。あとのメソッドはパトリシアでもそのまま利用することができます。
●部分列のマッチング
パトリシアをプログラムする場合、部分列のマッチングを判定する処理がポイントになりますが、Common Lisp には mismatch という便利な列関数があるので簡単です。
mismatch seq1 seq2
列型データ seq1 と seq2 を要素ごとに比較し、それらの長さが等しくてすべての要素が一致すれば nil を返します。そうでなければ、不一致になった seq1 の位置を返します。mismatch は拙作のページ 列関数 で説明したキーワード :from-end, :test, :test-not, :key, :start1, :end1, :start2, :end2 を使用することができます。
簡単な例を示しましょう。
(mismatch "abc" "abc") => nil (mismatch "abcd" "abef") => 2 (mismatch "abc" "def") => 0 (mismatch "abcabcabc" "abc" :start1 3 :end1 6) => nil (mismatch "abcabcabc" "abd" :start1 3 :end1 6) => 5 (mismatch "abc" "abcde") => 3 (mismatch "abcde" "abc") => 3
●子の探索
mismatch を使うと、子を探す処理は簡単にプログラムできます。次のリストを見てください。
リスト : データと部分的に一致する子を探す
(defun patricia-search-child (node seq si obj=)
(dolist (x (node-child node))
(unless (eq x *term*)
(let ((n (mismatch (node-item x) seq :test obj= :start2 si)))
(if (or (null n) (plusp n))
;; 発見
(return (values x n)))))))
関数 patricia-search-child は、NODE の CHILD から子をひとつずつ取り出して、mismatch で DATA と比較します。引数 SI が SEQ のマッチング開始位置を表します。mismatch の返り値 N が NIL または 0 より大きければ、最低でもひとつの要素がマッチングしているので、values で NODE と N を返します。mismatch の返り値は第 1 引数で不一致になった位置を表していることに注意してください。マッチングする要素が見つからない場合は NIL を返します。
●最長一致の探索
次はパトリシアをたどる関数 node-longest-match を作ります。
リスト : node から最長一致する節を求める
(defun node-longest-match (node seq obj=)
(let ((si 0))
(loop
(multiple-value-bind (next n)
(patricia-search-child node seq si obj=)
(cond ((null next)
;; 見つからない : node (si) まで一致
(return (values node si 0)))
((null n)
;; seq と一致
(return (values next (+ si (length (node-item next))) 0)))
((< n (length (node-item next)))
;; next の途中まで一致
(return (values next (+ si n) n)))
(t
;; next と一致
(setf node next)
(incf si n)))))))
関数 node-longest-match はパトリシアをたどって、引数 SEQ と最も長く一致する位置を求めます。node-longest-match は、最後に一致した節 (node)、SEQ と一致した長さ (match)、節の ITEM と一致した長さ (sub-match) を返します。節の ITEM と全て一致した場合、sub-match の値は 0 とします。このメソッドはパトリシアを操作するメソッドから呼び出されます。
最初に SEQ の照合開始位置を表す変数 SI を 0 に初期化します。次に、patricia-search-child を呼び出して、その返り値を変数 NEXT と N で受け取ります。NEXT が偽の場合、子は見つからなかったので照合は失敗です。NODE と SI まではマッチしているので、(values node si 0) を返します。
N が偽の場合は、節 NEXT の ITEM で SEQ と照合が成功しました。NEXT と SEQ の長さと 0 を返します。SEQ の長さは (+ si (length (node-item next))) で求めることができます。N が NEXT の ITEM よりも短い場合、節 NEXT の途中で不一致になりました。NEXT と (+ si n) と N を返します。あとは NEXT の ITEM と一致した場合です。SI に N を加算して、次の子と照合します。
●データの探索
関数 node-longest-match を作れば、データの探索は簡単です。次のリストを見てください。
リスト : データの探索
(defmethod trie-match ((tree patricia) (seq sequence))
(multiple-value-bind (node match sub-match)
(node-longest-match (trie-root tree) seq (trie-obj= tree))
(cond ((and (zerop sub-match)
(= (length seq) match))
;; 終端のチェック
(values (search-terminal node) match))
(t
(values nil match)))))
node-longest-match を呼び出して、返り値を変数 NODE, MATCH, SUB-MATCH で受け取ります。SUB-MATCH が 0 で、かつ MATCH が SEQ と同じ長さであれば終端をチェックします。終端が見つかれば探索成功となります。それ以外の場合は節の途中でマッチングが終わっているので探索は失敗となります。
●データの挿入
次はデータを挿入するメソッド trie-put を作ります。
リスト : データの挿入
(defmethod trie-put ((tree patricia) (seq sequence))
(multiple-value-bind (node match sub-match)
(node-longest-match (trie-root tree) seq (trie-obj= tree))
(cond ((zerop sub-match)
(if (= (length seq) match)
;; 終端のチェック
(unless (search-terminal node)
(insert-terminal node))
;; node に新しい節を追加する
(insert-terminal (insert-child node (subseq seq match)))))
(t
;; node を分割して新しい節を追加する
(let ((new-node (make-instance 'node :item (subseq (node-item node) sub-match))))
(setf (node-item node) (subseq (node-item node) 0 sub-match))
(setf (node-child new-node) (node-child node))
(setf (node-child node) (list new-node))
(insert-terminal (if (= (length seq) match)
node
(insert-child node (subseq seq match)))))))))
node-longest-match を呼び出すところはデータの探索と同じです。SUB-MATCH が 0 の場合、NODE の子に終端または新しい節を追加します。MATCH が SEQ の長さと同じ場合は、NODE に終端を追加するだけです。そうでなければ、insert-child で NODE の子に新しい節を追加して、その節に終端を追加します。
SUB-MATCH が 0 でない場合、NODE を SUB-MATCH の位置で二分割します。このとき、新しい節 NEW-NODE に SUB-MATCH から後ろのデータを格納します。NODE の ITEM は先頭から SUB-MATCH - 1 までのデータに更新します。そして、NODE の CHILD を NEW-NODE の CHILD にセットして、NODE の CHILD を (list new-node) に更新します。これで NODE と NEW-NODE を接続することができます。
あとは、終端を挿入するだけです。MATCH が SEQ の長さと同じならば、NODE の子に終端を挿入します。そうでなければ、SEQ にはまだデータが残っているので、NODE の子に新しいデータ (subseq seq match) を挿入し、新しい節の子に終端を挿入します。
●データの削除
次はデータを削除するメソッド trie-delete を作ります。
リスト : データの削除
(defmethod trie-delete ((tree patricia) (seq sequence))
(multiple-value-bind (node match sub-match)
(node-longest-match (trie-root tree) seq (trie-obj= tree))
(when (and (zerop sub-match)
(= (length seq) match)
(search-terminal node))
(delete-terminal node))))
データの削除は簡単です。node-longest-match を呼び出して、SUB-MATCH が 0 で、MATCH が SEQ の長さと等しく、NODE の子に終端がある場合は、削除するデータが存在します。delete-terminal で終端を取り除くだけです。
●共通接頭辞を持つデータの探索
最後に共通接頭辞を持つデータを求めるメソッド trie-common-prefix を作ります。
リスト : 共通接頭辞を持つデータを求める
(defmethod trie-common-prefix ((tree patricia) (seq sequence))
(multiple-value-bind (node match sub-match)
(node-longest-match (trie-root tree) seq (trie-obj= tree))
(when (= (length seq) match)
(let ((a nil)
(seq1 (if (zerop sub-match)
(list seq)
(list (subseq (node-item node) sub-match) seq))))
(dolist (x (node-child node) a)
(setf a (node-fold x #'cons seq1 a)))))))
node-longest-match を呼び出して、MATCH が SEQ の長さと同じであれば、接頭辞が SEQ と同じデータがパトリシア内に存在します。このとき、SUB-MATCH が 0 ならば、NODE の ITEM は最後まで SEQ と一致しています。SEQ1 に (list seq) をセットします。SUB-MATCH が 0 でない場合、ITEM の途中まで一致しています。ITEM の SUB-MATCH 以降のデータを取り出して、SEQ といっしょにリストに格納して SEQ1 にセットします。あとは node-fold を呼び出すだけです。
●実行例（その２）
それでは、実際に試してみましょう。
* (setq a (make-instance 'patricia))
#<PATRICIA {10028C9813}>
* (dotimes (x 10) (trie-put a (princ-to-string (random 5000000))))
NIL
* (trie-for-each a #'print)
("663355")
("4297752")
("582826")
("3" "767693")
("3" "857146")
("1" "92345")
("1" "578724")
("2" "752823")
("2" "0" "90578")
("2" "0" "42599")
NIL
* (trie-match a "2090578")
T
7
* (trie-match a "200")
NIL
2
* (trie-delete a "582826")
T
* (trie-delete a "582826")
NIL
* (trie-match a "582826")
NIL
6
* (trie-common-prefix a "20")
(("20" "42599") ("20" "90578"))
* (trie-common-prefix a "3")
(("3" "857146") ("3" "767693"))
正常に動作していますね。もうひとつ簡単な実行例として suffix tree を作ってみましょう。suffix tree は suffix trie の改良したもので、サフィックスを順番にパトリシアに追加していくだけで作成できます。次のリストを見てください。
リスト : suffix tree の作成
(defun make-suffix-tree (data)
(let ((x (make-instance 'patricia)))
(dotimes (n (length data))
(trie-put x (subseq data n)))
(trie-for-each x #'print)))
とても簡単な方法ですが、データが多くなると時間がかかるのが欠点です。データ数を N とすると、実行時間は N2 に比例します。ご注意くださいませ。
それでは実行例を示します。
* (make-suffix-tree "aeadacab")
("b")
("cab")
("dacab")
("eadacab")
("a" "b")
("a" "cab")
("a" "dacab")
("a" "eadacab")
NIL
* (make-suffix-tree '(a e a d a c a b))
((B))
((C A B))
((D A C A B))
((E A D A C A B))
((A) (B))
((A) (C A B))
((A) (D A C A B))
((A) (E A D A C A B))
NIL
suffix trie を構成する場合、データ数を N とすると N2 に比例するメモリが必要になりますが、suffix tree は N に比例するメモリで構成することができます。また、データ数 N に比例する時間で suffix tree を構築するアルゴリズムもあります。suffix tree は suffix trie よりも省メモリなので、いろいろな文字列処理の高速化に利用することができます。近年は suffix tree よりも省メモリのデータ構造である suffix array も注目されています。
●プログラムリスト
;;;
;;; trie.lisp : トライとパトリシア
;;;
;;; Copyright (C) 2010-2020 Makoto Hiroi
;;;
(provide :trie)
(defpackage :trie (:use :cl))
(in-package :trie)
(export '(trie patricia trie-put trie-match trie-delete trie-fold
trie-for-each trie-length trie-clear trie-common-prefix))
;;; メソッドの宣言
(defgeneric trie-match (trie seq))
(defgeneric trie-put (trie seq))
(defgeneric trie-delete (trie seq))
(defgeneric trie-for-each (trie func))
(defgeneric trie-fold (trie func a))
(defgeneric trie-common-prefix (trie seq))
(defgeneric trie-length (trie))
(defgeneric trie-clear (trie))
;;; 終端
(defvar *term*)
;;;
;;; クラス定義
;;;
;;; 節
(defclass node ()
((item :accessor node-item :initarg :item :initform nil)
(child :accessor node-child :initarg :child :initform nil)))
;;;; トライ
(defclass trie ()
((root :accessor trie-root
:initform (make-instance 'node) ; ヘッダ
:initarg :root)
(obj= :accessor trie-obj=
:initform #'eql
:initarg :obj=)))
;;; 終端の初期化
(defmethod initialize-instance ((obj trie) &rest initargs)
(declare (ignore initargs))
(call-next-method)
(unless (boundp '*term*)
(setf *term* (make-instance 'node))))
;;;
;;; 節の操作関数
;;;
;;; 子を探す
(defun trie-search-child (node x obj=)
(find x (node-child node) :key #'node-item :test obj=))
;;; 子を追加する
(defun insert-child (node x)
(let ((new-node (make-instance 'node :item x)))
(push new-node (node-child node))
new-node))
;;; 終端のチェック
(defun search-terminal (node)
(consp (member *term* (node-child node))))
;;; 終端を追加する
(defun insert-terminal (node)
(push *term* (node-child node))
t)
;;; 終端を削除する
(defun delete-terminal (node)
(setf (node-child node)
(remove *term* (node-child node)))
t)
;;;
;;; メソッドの定義
;;;
;;; 探索
(defun node-match (node seq obj=)
(dotimes (x (length seq)
(values (search-terminal node) x))
(let ((p (trie-search-child node (elt seq x) obj=)))
(if (null p)
(return (values nil x))
(setf node p)))))
(defmethod trie-match ((tree trie) (seq sequence))
(node-match (trie-root tree) seq (trie-obj= tree)))
;;; 挿入
(defun node-put (node seq obj=)
(dolist (x (coerce seq 'list))
(let ((p (trie-search-child node x obj=)))
(setf node (if p p (insert-child node x)))))
;; 終端を挿入
(unless (search-terminal node)
(insert-terminal node)))
(defmethod trie-put ((tree trie) seq)
(node-put (trie-root tree) seq (trie-obj= tree)))
;;; 削除
(defun node-delete (node seq obj=)
(dolist (x (coerce seq 'list)
(when (search-terminal node)
(delete-terminal node)))
(let ((p (trie-search-child node x obj=)))
(if (null p)
(return)
(setf node p)))))
(defmethod trie-delete ((tree trie) seq)
(node-delete (trie-root tree) seq (trie-obj= tree)))
;;; 巡回
(defun node-for-each (node func a)
(if (eq *term* node)
(funcall func (reverse a))
(let ((a1 (cons (node-item node) a)))
(dolist (x (node-child node))
(node-for-each x func a1)))))
(defmethod trie-for-each ((tree trie) func)
(dolist (x (node-child (trie-root tree)))
(node-for-each x func nil)))
;;; 畳み込み
(defun node-fold (node func seq a)
(if (eq *term* node)
(funcall func (reverse seq) a)
(let ((seq1 (cons (node-item node) seq)))
(dolist (x (node-child node) a)
(setf a (node-fold x func seq1 a))))))
(defmethod trie-fold ((tree trie) func a)
(dolist (x (node-child (trie-root tree)) a)
(setf a (node-fold x func nil a))))
;;; 共通接頭辞を持つデータを求める
(defun node-common-prefix (node seq obj= a)
(dolist (x (coerce seq 'list)
(node-fold node #'cons (cdr a) nil))
(push x a)
(let ((p (trie-search-child node x obj=)))
(if (null p)
(return)
(setf node p)))))
(defmethod trie-common-prefix ((tree trie) seq)
(node-common-prefix (trie-root tree) seq (trie-obj= tree) nil))
;;; 要素数を求める
(defmethod trie-length ((tree trie))
(trie-fold tree #'(lambda (x a) (declare (ignore x)) (1+ a)) 0))
;;; クリア
(defmethod trie-clear ((tree trie))
(setf (node-child (trie-root tree)) nil))
;;;
;;; patricia tree
;;;
;;; クラス定義
(defclass patricia (trie) ())
;;; データを含む子を探す
(defun patricia-search-child (node seq si obj=)
(dolist (x (node-child node))
(unless (eq x *term*)
(let ((n (mismatch (node-item x) seq :test obj= :start2 si)))
(if (or (null n) (plusp n))
; 発見
(return (values x n)))))))
;;; node から最長一致する節を求める
(defun node-longest-match (node seq obj=)
(let ((si 0))
(loop
(multiple-value-bind (next n)
(patricia-search-child node seq si obj=)
(cond ((null next)
;; 見つからない : node (si) まで一致
(return (values node si 0)))
((null n)
;; seq と一致
(return (values next (+ si (length (node-item next))) 0)))
((< n (length (node-item next)))
;; next の途中まで一致
(return (values next (+ si n) n)))
(t
;; next と一致
(setf node next)
(incf si n)))))))
;;; データの探索
(defmethod trie-match ((tree patricia) (seq sequence))
(multiple-value-bind (node match sub-match)
(node-longest-match (trie-root tree) seq (trie-obj= tree))
(cond ((and (zerop sub-match)
(= (length seq) match))
; 終端のチェック
(values (search-terminal node) match))
(t
(values nil match)))))
;;; データの挿入
(defmethod trie-put ((tree patricia) (seq sequence))
(multiple-value-bind (node match sub-match)
(node-longest-match (trie-root tree) seq (trie-obj= tree))
(cond ((zerop sub-match)
(if (= (length seq) match)
;; 終端のチェック
(unless (search-terminal node)
(insert-terminal node))
;; node に新しい節を追加する
(insert-terminal (insert-child node (subseq seq match)))))
(t
;; node を分割して新しい節を追加する
(let ((new-node (make-instance 'node :item (subseq (node-item node) sub-match))))
(setf (node-item node) (subseq (node-item node) 0 sub-match))
(setf (node-child new-node) (node-child node))
(setf (node-child node) (list new-node))
(insert-terminal (if (= (length seq) match)
node
(insert-child node (subseq seq match)))))))))
;;; 削除
(defmethod trie-delete ((tree patricia) (seq sequence))
(multiple-value-bind (node match sub-match)
(node-longest-match (trie-root tree) seq (trie-obj= tree))
(when (and (zerop sub-match)
(= (length seq) match)
(search-terminal node))
(delete-terminal node))))
;;; 共通接頭辞を持つデータを求める
(defmethod trie-common-prefix ((tree patricia) (seq sequence))
(multiple-value-bind (node match sub-match)
(node-longest-match (trie-root tree) seq (trie-obj= tree))
(when (= (length seq) match)
(let ((a nil)
(seq1 (if (zerop sub-match)
(list seq)
(list (subseq (node-item node) sub-match) seq))))
(dolist (x (node-child node) a)
(setf a (node-fold x #'cons seq1 a)))))))