こんにちは。 DSOC R&D グループの高橋寛治です。
Pythonの辞書オブジェクトは取り扱いやすいため、単語とIDの変換テーブルを作ったり、複合語の結合のためにデータ構造を工夫して簡易なトライ木を構築したりと、自分でコーディングすることがあるかと思います。
上記の場合は、ライブラリDAWGを使うことで省メモリかつ高速に、さらにできることが増えるかもしれません。
今回はそんな便利なライブラリの紹介をします。
辞書ライクなライブラリDAWG
DAWGはDirected Acyclic Word Graphのそれぞれの頭文字をとったものです。
日本語だと有向無閉路単語グラフでしょうか。
英語のWikipediaのページに少し詳しい説明があります。
トライ木に比べて、頂点の数がかなり少なくなるデータ構造であることが特徴のようです。
利用者側としては、省メモリかつ高速に辞書引きや共通接頭辞検索ができるライブラリであるということを押さえておくといいかと思います。
共通接頭辞検索とは、共通の接頭辞を持つキーを見つける検索のことです。
かな漢字変換システムにおける、かなと漢字の対応表を見つける箇所での利用がわかりやすい例です。
「きょういく」というかなを漢字に変換する場合を考えます。候補は「き」「きょ」「きょう」「きょうい」「きょういく」となり、それぞれに対応する漢字があります。
「きょう」で候補を定めたとすると、次は「いく」に対して「い」「いく」に対応する漢字をまた引きます。
このように共通の接頭辞に対して候補を高速に引くことがき、なおかつ省メモリで保持することができます。
DAWGのPython実装の公式ドキュメントはこちらです。
インストールは pip install DAWG
で完了します。
公式ドキュメントのUsageに書いているDAWGクラスを簡単に紹介します。
dawg.DAWG
: ユニコード文字のキーを保持し、検索が可能です
dawg.CompletionDAWG
: dawg.DAWG
のサブクラスであり、共通接頭辞検索などが可能です
dawg.BytesDAWG
: dawg.CompletionDAWG
のサブクラスであり、ユニコード文字のキーに対してbytesオブジェクトのリストを対応させます
dawg.RecordDAWG
: dawg.BytesDAWG
のサブクラスであり、 Pythonのstructでパッキングされたデータをユニコード文字のキーに対応させます
dawg.IntCompletionDAWG
: dawg.CompletionDAWG
のサブクラスであり、ユニコード文字のキーに対して、数値を対応付けます
dawg.IntDAWG
: dawg.DAWG
のサブクラスであり、ユニコード文字のキーに対して、数値を対応づけます
続きを読む