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

DAWG2(3): cl-dawg

sbcl algorithm library

いろいろ途中経過を省いてDAWGシリーズ(?)の最後。
common lisp用のライブラリにまとめました、という話。
cl-dawg-0.1.0

概要

  • DAWGのcommon lisp実装
    • ただしSBCL依存
      • DAWG構築時に利用しているハッシューテーブルでSBCL拡張機能を使っているため 
  • 静的に与えられたキーセットの各キーに対して一意なIDをマッピングする
    • キーセットはソート済みである必要有り
    • ソート昇順に0から始まる値をIDとして割り振る
    • ID付与の方法はDAWG(2):ID付けで最後に考えた方法に近い
      • 各ノードに、次の兄弟以降が保持するキー数を格納しておき、ノードを辿るごとにその値、及び自分がキーの終端となっている場合は1、を加算していく*1
      • 検索キーに対応するノードに達した時点での合計値が、そのキーのID値となる*2
  • キーセットから構築されたDAWGはDoubleArray形式でファイルに保存される
  • 2〜4GBのメモリを有するマシンでサイズが数千万程度のキーセットが扱える(目安として)
    • 32bitマシン
    • Nグラムのようにキーセットの冗長性が高い場合

本当は億単位のキーセットを扱えるデータ構造を実装するつもりであったので、現状のものはサイズ的に(あと処理速度的-特に構築時-にも)必ずしも満足いくものとはなっていない。
ただ、common lispで数千万程度のキーセットが(比較的)手軽に扱えるというのは、それはそれで有用だと思うので、まとめて公開しておくことにした。
これ以上のものはまた必要になったら、その時に実装するかもしれない。当面は保留。

使用例等

使用例等。
キーセットには適当に作成した二千万個の文字四グラムを使用する。

# キーセット
$ wc -l 4gram
21139008 4gram 

$ ls -lh 4gram
-rw-r--r-- 1 user user 251M 2010-08-23 23:28 4gram

$ head -10000000 4ngram | tail
シを露出
シを頂い
シを頂き
シを頂戴
シを食っ
シを食べ
シを飲み
シを飲ん
シを飼っ
シを飼料
;;;; sbcl-1.0.40
;;;; - 起動時のオプションで"--dynamic-space-size"には"2048"を指定
(require :dawg)
--> NIL

;; キーセットファイル"4gram"から"dawg.idx"を作成
;; 進捗を表示する場合は、show-progressに非nilを渡す
(time
  (dawg:build :input "4gram" :output "dawg.idx" #|:show-progress t|#))
Evaluation took:
  205.782 seconds of real time  ; 処理時間は三分半程度。構築時の使用メモリのピークは約1.4GBだった。
  204.884804 seconds of total run time (198.132382 user, 6.752422 system)
  [ Run times consist of 91.783 seconds GC time, and 113.102 seconds non-GC time. ]
  99.56% CPU
  410,504,067,468 processor cycles
  4,626,234,952 bytes consed
--> T
# DAWGファイルのサイズ
$ ls -lh dawg.idx 
-rw-r--r-- 1 user user 197M 2010-11-01 04:04 dawg.idx
;; DAWGをロード
(defvar *dawg* (dawg:load "dawg.idx"))
--> *DAWG*

;; ID取得
(dawg:get-id "地方都市" *dawg*)
--> 14054337

(dawg:get-id "地方" *dawg*)  ; 文字四グラムなので、二文字のキーはない
--> NIL

;; 存在判定
(dawg:member? "ruby" *dawg*)
--> T

;; common prefix search
;; 文字四グラムしかないのであまり意味がない...
(dawg:each-common-prefix (id end) (#1="関東平野を散歩する" *dawg*) 
  (print (list id (subseq #1# 0 end))))
(19441291 "関東平野") 
--> T

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; キーセット内の全てのキーを検索
(time 
  (with-open-file (in "4.gram")
    (loop FOR key = (read-line in nil nil)
          WHILE key
      DO
      (assert (dawg:member? key *dawg*)))))
Evaluation took:
  14.047 seconds of real time
  14.000875 seconds of total run time (13.716857 user, 0.284018 system)
  [ Run times consist of 0.240 seconds GC time, and 13.761 seconds non-GC time. ]
  99.67% CPU
  28,023,264,669 processor cycles
  681,782,520 bytes consed
--> NIL

;; キー走査に掛かる時間
(time 
  (with-open-file (in "4gram")
    (loop FOR key = (read-line in nil nil)
          WHILE key)))
Evaluation took:
  6.976 seconds of real time
  6.964436 seconds of total run time (6.708420 user, 0.256016 system)
  [ Run times consist of 0.208 seconds GC time, and 6.757 seconds non-GC time. ]
  99.83% CPU
  13,916,195,292 processor cycles
  681,783,224 bytes consed
--> NIL

以上。

知見

ちなみに今回の実装を通して得た一番の知見は、完全なトライさえあれば、それをDoubleArrayに変換してファイルに保存するのには(比較的小さい)定数量のメモリがあれば十分だということ*3
つまりDAWGなり、他のトライのデータ構造なり、ソート済みのキーセットなり、何らかのトライの表現がメモリ上に構築できてしまえば、後はそれをDoubleArrayに変換するのは(メモリ的には)ほとんどタダということになる。
軽く試した限りでは、速度的にも(Double Arrayをメモリ上に構築して、その後まとめてファイルに書き出すのに比べて)ほとんどオーバヘッドは無さそうだった。

*1:ちなみに実装の都合により、ノードの兄弟を辿るにつれて、ラベルの値は減少していくようになっている。DAWG2(1)を参照。

*2:この方法は各ノードに付加情報(4byte)が与える必要があるため、サイズ効率的はあまり良くないが実装は楽。

*3:少なくとも自分がよく実装するタイプのDouble Arrayでは。