連想配列はトライでしょ的な話がでていたので入門記事を書いてみた

計算機科学

なにやらDan Kogai氏の以下の記事が話題になっている様子。

404 Blog Not Found:Algorithm - 連想配列の実装としてのハッシュはオワコン?

連想配列(キーワードを投げると対応する値が返ってくるデータ構造)はハッシュテーブルで実装するのではなく、これからはトライ(trie)木を使うのがイケてる！(意訳)という内容だった。
連想配列にハッシュテーブルを使うのが良いか悪いかについては色々と意見があると思うので特にこの記事では触れない。
今回は連想配列として使えると話題のトライ木とはなんぞ、という入門的な記事にしようと思う。


トライ木が持つ機能
最初にトライが持つ以下の3つの機能について説明する。

- lookup
- common-prefix-search
- predictive-search

まずトライは連想配列として利用できる。つまりキーワードと値のペアを登録しておいて、キーワードを投げたときに対応する値を返してもらうという機能がある。この機能をトライの用語でlookupという。例えば

pine : 1
pine-apple : 2
pine-juice : 3

というキーワードと値のペアをトライに登録しておくと

lookup("pine") => {pine:1}

のように値を得ることができる。
次にcommon-prefix-searchについて説明する。これは入力キーワードに前方一致するキーワードと値のペアを得ることができる。例えば

common-prefix-search("pine-juice, please!") => {pine:1, pine-juice:3}

となる。実用的な例として、あるテキストのすべてのsuffixに対してcommon-prefix-searchをすることでテキスト中に含まれるキーワードをすべて見つける、ということができる。
最後にpredictive-searchについて説明する。これは入力キーワードではじまるキーワードと値のペアを得ることができる。例えば

predictive-search("pine-") => {pine-apple:2, pine-juice:3}

となる。実用的な例として日本語入力システムの予測変換に利用できる。


トライ木のデータ構造
トライ木の機能を実現するデータ構造としてはDouble ArrayとLOUDSの2つが有名。それぞれDouble Arrayは高速、LOUDSはデータサイズが小さいという特徴がある。
Double Arrayの解説は

の2つがわかりやすくオススメ。またWEB+DB PRESS Vol.64にも@tkng氏の解説記事がある。

LOUDSの解説は

などがあるが2/8に発売の「日本語入力を支える技術」(こちらも@tkng氏による)にLOUDSの解説があるとのこと。恐らくLOUDSについて日本語で書いてある唯一の書籍。


トライ木を用いた技術
トライは自然言語処理(Natural Language Processing)で極めて重要な意味を持つデータ構造で形態素解析器や日本語入力システムで利用されている。
具体的には有名な形態素解析器mecabではDouble Arrayのライブラリdartsが用いられている。

またGoogle日本語入力mozcではLOUDSのライブラリrx-trieが用いられている。当初はDouble Arrayを使おうとしたが日本語入力システムはメモリに常駐するアプリケーションなのでデータサイズが小さくなるLOUDSを利用することになったとのこと。


トライ木のライブラリ
DoubleArrayのライブラリとしてはdartsが、LOUDSのライブラリとしてはmarisa-trieが高性能でオススメ。まずはこれらの利用を検討すると良さそう。