トライ (データ構造)
トライ木の典型的な応用として辞書の格納がある。例えば、携帯電話などで使われている。トライ木の利点として検索の高速性と新たなエントリの挿入やエントリの削除の容易性が活用されている。しかし、単に辞書の単語を格納するだけなら(つまり、各単語の意味などが必要とされない場合)、非輪状決定性有限オートマトンのほうがメモリ効率がよい。
トライ木はスペルチェッカなどの近似的マッチングアルゴリズムの実装にも適している。
1989年に青江順一がダブル配列を利用する方法を発表した。トライ木は決定性有限オートマトンとして解釈する事が出来るが、決定性有限オートマトンはデフォルト(default)・ベース(base)・次(next)・チェック(check)の4つの配列で表現できる。トライ木の場合はデフォルトは不要である。その上で、s から t へ c により遷移する場合は、以下の関係が成立すれば良い。
動的に要素が増えていく場合 next と check は同じように増えていくのでまとめる事が出来るが、base は同じ速度では増えていかず分裂してしまう。そこで、ダブル配列では、base と next を統合し、以下の関係が成立するように管理する。
すると、base と check だけが残り、この2つは同じ速さで増えていき、一つの構造体にまとめる事が出来る。
ある要素がトライ木に含まれているかどうか調べる際に、二重連鎖木を使った方法では、兄弟ノードはポインタ(連結リスト)をたどって行かないといけないが、ダブル配列では一発で遷移できる。
実装としては Theppitak Karoonboonyanan が libdatrie を公開している。