DAWG

common lisp algorithm

そろそろトライとかDoubleArrayとかから少し離れたいけど、DAWG(Directed acyclic word graph)というものを知ってしまったので、(多分)もう少しだけ続ける。

DAWG

DAWGが何かというと、トライの共通する部分木をまとめたものらしい。
トライからDAWGへの変換は、次の操作を繰り返すことで行える(ように思う)。

  • 木を構成する二つの部分木を取り出す(それぞれA、Bと呼ぶ)
    • もしAとBが等しいなら、(Bの親ノードから)Bへの参照をAへの参照に置き換える

以下、lispでの例示。

;; 【木の表現方法】
;;    ノード: (list ラベル 子ノード*)
;;    ラベル: 任意のオブジェクト

;; トライ木:  :root=>a=>b=>c、:root=>b=>b=>c、:root=>1=>2=>3、の三つのキーを含む
(defvar *tree* '(:root (a (b (c))) 
                       (b (b (c))) 
                       (1 (2 (3)))))

;; :rootノードの一番目と二番目の子ノードの子ノードは、等しい   ※ 子ノード = 部分木
(cadr (second *tree*))
--> (B (C))
(tree-equal (cadr (second *tree*)) (cadr (third *tree*)))
--> T

;; DAWG
'(:root #1=(a #1=(b (c)))
           (b #1#)        
           (1 (2 (3))))

トライの場合は接頭部分のみが共有可能だけど、DAWGでは接尾部分のノードも共有できる。
そのため同一のキーセットを表現するために必要なノード数がトライに比べて少なくなる、というのが利点(だと思う)。

トライからの変換

トライからDAWGへの変換を行うcommon lisp関数の定義。

(setf *print-circle* t)

;; 変換関数
;;  - 基本的には単なるツリーのコピーと同様
;;  - ただし、以前にコピーした部分木と同じ部分木に遭遇した場合、再度コピーするのではなく、以前のコピーへの参照を返す点が異なる
;;  ※ これは、いわゆるmemoize関数をcopy-tree関数に適用した場合の動作と概ね等しい
(defun trie2dawg (trie)
  (let ((memo (make-hash-table :test #'equal)))
    (labels ((impl (trie)
               (when trie
                 (a.if #1=(gethash trie memo)
                     it
                   (destructuring-bind (label . children) trie
                     (setf #1# `(,label ,@(mapcar #'impl children))))))))
      (impl trie))))

;; 実行例
*tree*
--> (:ROOT (A (B (C))) (B (B (C))) (1 (2 (3))))

(trie2dawg *tree*)
--> (:ROOT (A #1=(B (C))) (B #1#) (1 (2 (3))))

(tree-equal *tree* (trie2dawg *tree*))
--> T  ; 木の構造的にはどちらも等価