DAWG2(3): cl-dawg
いろいろ途中経過を省いてDAWGシリーズ(?)の最後。
common lisp用のライブラリにまとめました、という話。
・cl-dawg-0.1.0
概要
- DAWGのcommon lisp実装
- 静的に与えられたキーセットの各キーに対して一意なIDをマッピングする
- キーセットはソート済みである必要有り
- ソート昇順に0から始まる値をIDとして割り振る
- ID付与の方法はDAWG(2):ID付けで最後に考えた方法に近い
- キーセットから構築された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をメモリ上に構築して、その後まとめてファイルに書き出すのに比べて)ほとんどオーバヘッドは無さそうだった。
