読者です 読者をやめる 読者になる 読者になる

Javaで簡潔TRIE(2)

Java

さて、トライ(TRIE)について、もう少し説明したいと思います。

まず、3つの文字列を持つキー集合Kを考えます。

K = { internet, interest, japan, jar, kyoto }

まず、この5つの文字列をトライではなく、ソートした状態で保持し、2分探索で求める場合を考えます。
ソートした状態は、以下のようになります。

f:id:ryokkie:20120407122834p:image:w360

番号は、分かりやすいように付与しました。
このように、ソートすることにより、2分探索によって検索することができます。
例えば、「kyoto」というキーを見つける場合は、以下のようにして見つけることができます。

f:id:ryokkie:20120407122835p:image:w360

簡単ですね。
どのような文字列の組み合わせであっても、ソート済みであれば、2分探索でキーを探索することができます。
2分探索の性能は、キー集合Kに含まれるキーの個数を|K|とした場合、おおよそlog(|K|)となります。*1
通常のケースでは、これで十分に高速です。

K =10000000とかでも現実的な時間で検索することができます。

さて、現実的な問題として、もっと高速にキーを見つけたい場合もあります。
これを実現するには、対数オーダーの性能を定数オーダーの性能に近づける必要があります。
この問題に対する一つのアプローチとして、トライがあります。
キー集合Kをトライで表現した場合、以下のようになります。

f:id:ryokkie:20120407133518p:image:w360

このように、トライは、各キーの共通接頭辞(common prefix)を併合して作られる木構造となります。
一般的に文字列を検索するのに有利なデータ構造です。

さて、次回は、このトライを使って説明を進めていきたいと思います。

*1:正確には、log(|K|)は、比較回数を表しています。文字列の比較は、単純な比較よりもコストがかかります。このことから、検索する文字列をk_searchとし、その長さを|k_search|とすると、2分探索の性能は、|k_search|×log(|K|)となります。

広告を非表示にする