テキスト処理に使われるTrie(トライ木)とLOUDSに関する概略

Trie(トライ木)を用いた検索は高速・省メモリ

Trie(= Retrieval tree, 検索木)はテキスト処理において必需品と言えるデータ構造です。辞書検索、日本語入力、サジェストの実装や、形態素解析に使われる辞書(形態素辞書)が主な用途と言えるでしょうか。Pythonの自然言語処理パッケージNLTK(Natural Language Tool Kit)でも、形態素解析にトライ木を用いています。

参考:http://www.nltk.org/book-jp/ch12.html

Trie(トライ木)とは?

例として、辞書として使われているトライ木の「A」から始まる単語を格納した部分を図示してみました。このように、探索木の各エッジに文字を割り当て、根ノードから葉ノードに至る経路(path)上の文字を拾っていった時の文字列によって辞書を表現します。この辞書には、「AGE」「AGILE」「ALIAS」「ALL」「ALT」「ALTUS」という6つの単語が含まれています。このように、経路によって定義される個々の単語をキーと呼びます。 形態素解析におけるトライ木の活用で言えば、各ノードには形態素が対応し、葉ノードまでの経路が文章を表すことになります。

なぜ辞書検索や形態素解析にトライ木が使われるかというと、大きく下記の理由によります。

  • 共通接頭辞検索(Common-Prefix Search)に適したデータ構造であること
  • 膨大な辞書データを格納する場合や、文字の種類が多い場合でも、検索が高速であること
  • 木構造を表現する際にLOUDSなどの簡潔データ構造を用いれば、省メモリで辞書を表現出来ること

LOUDSとは?

LOUDSとは、木構造をメモリ効率よく表現するための簡潔データ構造です。 Trieに使う場合のLOUDSの概念図を下図に示します。

左側の木がLOUDSによって表現されるTrieであり、右側の表がLOUDS(ビット列)及び、その付加情報としての文字です。 LOUDSとは、仮想ノード(Virtual node)を根ノードの親として用意したあと、下記の手続きで構築されるビット列を用いて、木構造を表現しようというデータ構造です。

  1. ノードが持つ子ノードの数に等しい数だけ「1」のビットを立て、そのあとに「0」のビットを立てる
  2. 仮想ノードから幅優先で木を探索し、1.の手続きを繰り返す

LOUDSは、木構造を最小に近いビット数で表現できます。また、Trieとして用いる際にも、接頭辞検索などの要求に対する処理をある程度高速に行える、バランスの良いデータ構造(簡潔データ構造)であることが知られています。

有名なところでは、Google日本語入力のオープンソース版であるMozcでは、LOUDSを用いてTrieを表現しています。 一方、工藤 拓氏(現Google)が開発した著名なオープンソース形態素解析エンジンMeCabには、ダブル配列(Double-Array)という別のデータ構造に基づくTrieが使われています。

弊社の実績 - 全文検索やSNS解析にトライ木を応用

弊社でも、トライ木(またはトライ木に類するデータ構造)が随所で活躍しています。 例えば、ある「案件情報検索サイト」の全文検索にサジェスト機能を付けた際、サジェストの表示(フロントエンドUI)はAutocompleteを用いましたが、データの辞書化と辞書検索は下記の要領で自作しました。

  1. 案件情報テキストから単語を抽出
  2. 辞書をトライ木で表現
  3. 共通接頭語検索によりサジェストを出力(出現頻度順に10個)

他には、「ある特定の語順が出現したツイートを抽出する」SNS解析システムの実装にトライ木を応用しました。 そのシステムの概略と、具体的な実装上の課題については、今後の記事で紹介していきたいと思います。

\(^▽^*) 私たちと一緒に働いてみませんか? (*^▽^)/

少しでも興味をお持ちいただけたら、お気軽に、お問い合わせください。

採用応募受付へ

(採用応募じゃなく、ただ、会ってみたいという方も、大歓迎です。)