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

Javaで簡潔TRIE(3)

Java

さて、トライの説明を進めていきます。

前回の記事で作成したトライは以下のようなものです。

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

ここでは、トライを使った検索について説明します。
ここで、以下のような関数を導入します。

g(n, a) = m

この関数は、ノードnにいる時に、文字aが入力された場合の遷移先のノードmを返します。
ノードnから文字aで遷移できる遷移先のノードmが存在しない場合は、mとしてnullを返します。
例えば、n=1とし、a='k'とした場合、

g(1, 'k') = 19

となります。

このトライで、「kyoto」というキーを検索した時の流れは、以下のようになります。

g(1, 'k') = 19
g(19, 'y') = 20
g(20, 'o') = 21
g(21, 't') = 22
g(22, 'o') = 23

簡単ですね。

トライの重要な特徴として、キー集合に含まれるキーの数に関係なく、検索時間が、検索したいキーの長さに依存するということです。
つまり、検索したいキーの長さを|k_search|とし、キー集合に含まれるキーの数を|K|とした場合、2分探索では、

|k_search|×log(|K|)

となりますが、トライの場合、

|k_search|

となります。
つまり、キー集合Kに含まれるキーの数|K|に関係なく、高速な検索が可能となります。
ただし、g(n, a) = mが高速に求められるという前提条件があります。
実は、これがかなり重要な条件なのですが、次回以降に説明します。

さて、今まで説明に使ってきた以下のトライは、まだ完全ではありません。

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

例えば、検索したいキーが「intern」だった場合、トライの終端にまで到達しないので、キーが存在したのかどうかがわかりません。
このためにキー集合Kを少し変形します。
まず、キー集合Kの各キーの終端に、キー自身には含まれない終端記号(#)を付与します。
C言語で言うところのNULL文字っぽい感じですね。
終端記号を付与したキー集合Kは、以下のようになります。

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

このキー集合Kをトライに変換した場合、以下のようになります。

f:id:ryokkie:20120408142738p:image:w360

これにより、検索キー「intern」がキー集合Kに存在したかどうかが明確にわかります。
ただし、トライを検索する時は、「intern#」で検索します。
実際に検索してみると、以下のようになります。

g(1, 'i') = 2
g(2, 'n') = 3
g(3, 't') = 4
g(4, 'e') = 5
g(5, 'r') = 6
g(6, 'n') = 11
g(11, '#') = null

このようになり、キー「intern」が存在しないことがわかります。
ただし、「intern」という接頭辞(prefix)を持つキー(internet)が存在することはわかります。
このことから、共通接頭辞(common prefix)を持つキーを簡単に見つけることにも利用することができます。
例えば、「in」という共通の接頭辞を持つキーとして、「interest」と「internet」が存在することがわかります。

さて、次回も引き続きトライの説明を進めていきたいと思います。

広告を非表示にする