読者です 読者をやめる 読者になる 読者になる

DAWG(2): ID付け

common lisp algorithm

最初に前回作成した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で実装した場合)これが原因で劇的に遅くなる、ということはないと思うけど ...。

*1:かつ、範囲は0以上キー数未満

*2:「できない」というのは正しくない。できるけど、そうしてしまうと接尾の共有可能なノードが無くなり、トライと等しくなるので意味がない、といった方が正しい。

*3:このためのコストが軽いかどうかはノードの実装方法に左右される。例えば、LOUDSでは各ノードが十数ビットで表現可能なため、葉ノードの数(これは通常32bit)のためのフィールドを追加すると、それだけで全体のサイズが何倍にも膨れてしまう。

*4:できるけど、効率が悪くてあまり意味がない