DAWG(2): ID付け
最初に前回作成したtrie2dawg関数を使って、DAWGとして表現した場合の(トライに比べての)ノード数節約効果を見てみる。
# データ準備 # IPADICに登録されている単語を使用 $ export LC_ALL=C $ cut mecab-ipadic-2.7.0-20070801/*.csv -d',' -f1 | nkf -w | sort | uniq > word.list $ wc -l word.list 325871 word.list # 33万語
;;;;;;;;;;;;;;;;;;;;;; ;;; 単語リスト読み込み (with-open-file (in "word.list") (defparameter *word-list* (loop FOR word = (read-line in nil nil) WHILE word COLLECT word))) --> *WORD-LIST* (subseq *word-list* 1000 1010) --> ("あこがれれ" "あこがれろ" "あこがれん" "あこや" "あご" "あごひげ" "あさ" "あさい" "あさぅ" "あさう") ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;; 単語リストからトライ木作成 (defun mktrie (word-list) (mktrie-impl :root (mapcar #'make-string-input-stream word-list))) (defun mktrie-impl (label word-list) (when (eq label :end) (return-from mktrie-impl (list :end))) ; 終端ノード (cons label ; ノードのラベル (loop WITH prev-label = (read-label (car word-list)) ; 子ノードのリスト WITH prev-index = 0 FOR word IN (cdr word-list) FOR label = (read-label word) FOR index FROM 1 UNLESS (eql prev-label label) COLLECT ;; 子ノードのトライ木を再帰的に構築 (prog1 (mktrie-impl prev-label (subseq word-list prev-index index)) (setf prev-label label ; 次の子ノードへ prev-index index)) INTO children FINALLY (return (append children `(,(mktrie-impl prev-label (subseq word-list prev-index)))))))) (defun read-label (in) (read-char in nil :end)) ; ストリームが空の場合は:endを返す ;;;;;;;;; ;;; 作成 (progn (princ (mktrie (subseq *word-list* 1000 1010))) 'done) (ROOT (あ (こ (が (れ (れ (END)) (ろ (END)) (ん (END)))) (や (END))) (ご (END) (ひ (げ (END)))) (さ (END) (い (END)) (ぅ (END)) (う (END))))) --> ODNE ;; トライ (defparameter *trie* (mktrie *word-list*)) --> *TRIE* ;; DAWG (defparameter *dawg* (trie2dawg *trie*)) --> *DAWG* (tree-equal *trie* *dawg*) --> T
;;;;;;;;;;;;;;;;;;;; ;;; ノード数カウント (ノードへの参照数カウント?) ;; 関数定義 (defun node-count (tree &aux (memo (make-hash-table :test #'eq)) (cnt 0)) (nlet self ((node tree)) (when node (incf cnt) (unless #1=(gethash node memo) (setf #1# t) (loop FOR child IN (cdr node) DO (self child))))) cnt) ;; カウント (node-count *trie*) --> 795003 ; 80万 (node-count *dawg*) --> 326552 ; 33万
DAWGの方がトライに比べて、2/5程度のノード(参照数)でIPADICの単語セットを表現できている。
セット
単なるセット(集合)として扱う場合は、トライとDAWGとでは特に差異はない(おそらく)。
参照: nlet
;; セットに含まれているかどうかを判定する関数 (defun member? (key root-node &aux (in (make-string-input-stream key))) (nlet self ((node-label :root) (children (cdr root-node))) (if (eq node-label :end) t (loop WITH label = (read-label in) FOR (child-label . grandchildren) IN children THEREIS (and (eql label child-label) (self child-label grandchildren)))))) ;; トライ (member? "あこがれれ" *trie*) --> T (member? "あこがれれれ" *trie*) --> NIL ;; DAWG (member? "あこがれれ" *dawg*) --> T (member? "あこがれれれ" *dawg*) --> NIL
IDへのマップ(トライ)
各キー(単語)に一意*1なIDを対応付けようとすると話は少し(?)難しくなる。
まず、トライ。
こっちは簡単。
;; トライ作成関数を修正 ;; - 終端を、ラベルが:endのノードではなく、ID値にする (defun mktrie2 (keys) (mktrie2-impl :root (mapcar #'make-string-input-stream keys) (id-generator))) (defun id-generator (&aux (id 0)) (lambda () (prog1 id (incf id)))) (defun mktrie2-impl (label word-list id) (when (eq label :end) (return-from mktrie2-impl (funcall id))) ; 終端ノードをID値に変更 (cons label ; ノードのラベル (loop WITH prev-label = (read-label (car word-list)) ; 子ノードのリスト WITH prev-index = 0 FOR word IN (cdr word-list) FOR label = (read-label word) FOR index FROM 1 UNLESS (eql prev-label label) COLLECT ;; 子ノードのトライ木を再帰的に構築 (prog1 (mktrie2-impl prev-label (subseq word-list prev-index index) id) (setf prev-label label ; 次の子ノードへ prev-index index)) INTO children FINALLY (return (append children `(,(mktrie2-impl prev-label (subseq word-list prev-index) id))))))) ;; ID付きトライを作成 (progn (princ (mktrie2 (subseq *word-list* 1000 1010))) 'done) (ROOT (あ (こ (が (れ (れ 0) (ろ 1) (ん 2))) (や 3)) (ご 4 (ひ (げ 5))) (さ 6 (い 7) (ぅ 8) (う 9)))) --> DONE (defparameter *trie2* (mktrie2 *word-list*)) --> *TRIE2*
;; キーID検索関数 ;; キーが存在しない場合はnilを返す (defun trie-search (key trie &aux (in (make-string-input-stream key))) (nlet self ((children (cdr trie))) (loop WITH label = (read-label in) FOR child IN children DO (etypecase child (list (destructuring-bind (child-label . grandchildren) child (when (eql label child-label) (self grandchildren)))) (number (when (eql label :end) (return-from trie-search child))))))) ;; (trie-search "あこがれれ" *trie2*) --> 1000 (trie-search "あこがれれれ" *trie2*) --> NIL
トライの場合は、各キーがそれぞれ終端ノードを有しているので、そこにIDを格納するだけで良い。
DAWGの場合は、接尾の共通ノード(部分木)をまとめてしまっているため、このようにしてIDを保持することはできない*2。
IDへのマップ(DAWG) - 1
ではどうすれば良いか。
今回思いついたのは次のような方法。
- 各ノードに、その子孫ノードが有する終端ノード(葉ノード)の数を保持しておく
- キー検索時には、探索パスの各ノードの前方の兄弟ノードの有する葉ノードの数を合計することで、ID値を算出する
- ID値 = 探索パスを境界として、前方にある部分木の葉ノードの合計数
以下、実装。
;; 各ノードが、子孫に含まれる葉ノードの総数を保持するようにする ;; - ノードのcar部の形式は、labelから(cons label 葉ノードの数)に変更 (defun add-leaf-count (trie) (nlet self ((node trie)) (destructuring-bind (label . children) node (cond ((listp label) ; 計算済み (cdr label)) ((eq label :end) ; 葉ノード (setf (car node) (cons :end 1)) 1) (t ; 通常のノード (let ((leaf-count (loop FOR child IN children SUM (self child)))) ; 子ノードの子孫ノードが有する葉ノードの数を合計する (setf (car node) (cons label leaf-count)) leaf-count))))) trie) ;; 実行 (progn (princ (add-leaf-count (mktrie (subseq *word-list* 1000 1010)))) 'done) ((ROOT . 10) ((あ . 10) ((こ . 4) ((が . 3) ((れ . 3) ((れ . 1) ((END . 1))) ((ろ . 1) ((END . 1))) ((ん . 1) ((END . 1))))) ((や . 1) ((END . 1)))) ((ご . 2) ((END . 1)) ((ひ . 1) ((げ . 1) ((END . 1))))) ((さ . 4) ((END . 1)) ((い . 1) ((END . 1))) ((ぅ . 1) ((END . 1))) ((う . 1) ((END . 1)))))) --> DONE ;; *dawg*を更新 (setf *print-circle* t) (setf *print-length* 10) (add-leaf-count *dawg*) --> ((:ROOT . 325871) ((#\T . 1) ((#\KATAKANA_LETTER_SI . 1) ((#\KATAKANA_LETTER_SMALL_YA . 1) ((#\KATAKANA_LETTER_TU . 1) #1=((:END . 1)))))) ((#\POUND_SIGN . 1) #1#) ((#\YEN_SIGN . 1) #1#) ((#\DIAERESIS . 1) #1#) ((#\ACUTE_ACCENT . 1) #1#) ((#\MULTIPLICATION_SIGN . 1) #1#) ((#\DIVISION_SIGN . 1) #1#) ((#\GREEK_CAPITAL_LETTER_ALPHA . 1) #1#) ((#\GREEK_CAPITAL_LETTER_BETA . 1) #1#) ...)
;; キーID検索関数 ※ トライに対して使える (defun dawg-search (key dawg &aux (in (make-string-input-stream key))) (nlet self ((node dawg) (id 0)) (destructuring-bind ((node-label . _) . children) node (declare (ignore _)) (if (eq node-label :end) (return-from dawg-search id) (loop WITH label = (read-label in) FOR child IN children FOR ((child-label . leaf-count) . grandchildren) = child DO (when (eql label child-label) (self child id)) (incf id leaf-count)))))) ; 通過した子ノード(の子孫)が有する葉ノードの数(= キーの数)だけID値をインクリメント ;; 実行 (dawg-search "あこがれれ" *dawg*) --> 1000 (dawg-search "あこがれれれ" *dawg*) --> NIL
この方法の場合、各ノードにフィールドを一つ追加するだけ*3で、キーにIDをマッピング可能となる。
ただし、キーの検索方法は線形検索に制限されることになる。
IDへのマップ(DAWG) - 2
上述の制限は、検索を効率良く行う上で、結構大きな制約となる。
具体例を挙げると、DoubleArrayを使って実装することができない*4。
そこで次は、最初の案を少し修正して、探索パスの各ノードを参照するだけでID値が求められるようにしてみる。
- 各ノードには、それ以前の兄弟ノードの子孫が有する葉ノードの総数を格納する
- これは、dawg-search関数では検索時に計算していた値
- ただし、上記値を直接ノードに格納するのは駄目
- 一つのノードに対して、複数の参照元があるため、前方の兄弟ノードの葉ノードの総数は一意には定まらない
- 各ノードへの参照に一回クッション(ノード)をはさみ、そこ(そのノード)に実際のノードへの参照と前方の兄弟ノードの葉ノードの総数を格納することにする
;; 前方の兄弟ノードの葉ノードの総数を保持するノードを、各ノードの前にはさむようにする ;; nodeは、add-leaf-count関数の返り値 (defun add-preciding-leaf-count (node) (destructuring-bind ((label . _) . children) node (declare (ignore _)) (cons label (loop FOR child IN children FOR ((_ . child-leaf-count)) = child COLLECT (list count (add-preciding-leaf-count child)) ; (label . children) から (count (label . children)) に => リストのネストが一段深く SUM child-leaf-count INTO count)))) ; 前方の兄弟ノードの子孫にが有する葉ノードの総数 ;; 実行 (defvar *trie3* (add-preciding-leaf-count (add-leaf-count (mktrie *word-list*)))) --> *TRIE3* *trie3* --> (:ROOT (0 (#\T (0 (#\KATAKANA_LETTER_SI (0 (#\KATAKANA_LETTER_SMALL_YA (0 (#\KATAKANA_LETTER_TU (0 (:END)))))))))) (1 (#\POUND_SIGN (0 (:END)))) (2 (#\YEN_SIGN (0 (:END)))) (3 (#\DIAERESIS (0 (:END)))) (4 (#\ACUTE_ACCENT (0 (:END)))) (5 (#\MULTIPLICATION_SIGN (0 (:END)))) (6 (#\DIVISION_SIGN (0 (:END)))) (7 (#\GREEK_CAPITAL_LETTER_ALPHA (0 (:END)))) (8 (#\GREEK_CAPITAL_LETTER_BETA (0 (:END)))) ...) (defvar *dawg3* (trie2dawg *trie3*)) --> *DAWG3*
;; キーID検索関数 ※ DAWG専用ではない (defun dawg-search2 (key dawg &aux (in (make-string-input-stream key))) (nlet self ((node dawg) (id 0)) (destructuring-bind (node-label . children) node (if (eq node-label :end) (return-from dawg-search2 id) (loop WITH label = (read-label in) FOR (base-id child) IN children ; 加算するID値と実際のノードを取り出す FOR (child-label . grandchildren) = child DO (when (eql label child-label) (self child (+ base-id id)))))))) ;; 実行 (dawg-search2 "あこがれれ" *dawg3*) --> 1000 (dawg-search2 "あこがれれれ" *dawg3*) --> NIL
これでキーID付きのDAWGをDoubleArrayでも実装できるようになった。
ただし、この方法には、(せっかくDAWGにすることで減らした)必要なノード数が増えてしまう、というデメリットがある。
(node-count *trie*) --> 795003 ; 80万 (node-count *dawg*) --> 326552 ; 33万: *trie*の 2/5 (node-count *dawg3*) --> 507975 ; 50万: *trie*の 3/5
また、検索時に辿るノード数(参照数)が倍になってしまうのも少し問題。
(DoubleArrayで実装した場合)これが原因で劇的に遅くなる、ということはないと思うけど ...。
