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

Javaで簡潔TRIE(4)

Java

さて、トライのイメージが掴めたところで、より実装に近いところを考えてみます。

まず、前回までに作成したトライを示しておきます。

キー集合Kは、以下のようなものでした。

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

また、このキー集合Kから作成したトライは以下のようになります。

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

また、ノードnにいる時に、文字aが入力された場合の遷移先のノードmを返す関数gは、以下のようになります。

g(n, a) = m

さて、このようなトライをコンピュータで実現する方法はいくつかあり、それぞれに利点と欠点があります。

以下の論文を参考に説明したいと思います。

トライとその応用
青江順一, 情報処理 34(2), 1993.

トライの実装というのは、基本的に、

g(n, a) = m

という関数を実装することと同じです。
難しく考える必要はないです。

まず、最もシンプルな実装である配列構造を説明します。
配列構造は、とてもシンプルなので、トライを実装することをイメージするのにかなり最適です。

今回のような小文字のアルファベットだけのキー集合をトライにすることを考える場合、a-zの範囲でいいため、g(n, a)関数に与えるaの範囲は、26だということがわかります。
つまり、

1 <= a <= 26

ということです。

このことから、トライの各ノードを以下のように表現できることがわかります。

f:id:ryokkie:20120416225851p:image:medium

つまり、配列の添え字をアルファベットの各文字対応させることによって、g(n, a)関数を実現します。
これは、実装上は、2次元配列で表現することができます。
2次元配列で表現した場合は、以下のようになります。

  | a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z |
1 |                                 2   15  23                                                            |
2 |                                                     3                                                 |
3 |                                                                             4                         |
4 |                 5                                                                                     |
5 |                                                                     6                                 |
6 |                 7                                   11                                                |
7 |                                                                         8                             |
...

このとき、空白部分は、nullを表現しています。

さて、この2次元配列を使ってg(n, a)関数が実現できているか試してみます。

g(1, 'a') = null

となるので、トライを辿れないことがわかります。

また、

g(1, 'i') = 2

となるので、トライが辿れることがわかります。

このように、2次元配列を使うことで、g(n, a)関数を簡単に表現できることがわかります。

さて、わざわざ説明することもないかもしれませんが、アルファベット以外のマルチバイト文字を使った場合に、2次元配列を使ったトライは、2次元配列のサイズが巨大になることがわかります。
また、アルファベットだけでキー集合が表現されていたとしても、登録するキーの数が多い場合も2次元配列のサイズが巨大になります。
ただし、g(n, a)関数の実行速度は、2次元配列を参照するだけなので、かなり高速です。
このことから、配列構造でのトライの実装は、

  • トライのサイズはかなり大きい
  • トライの探索はかなり速い

という特徴を持っていることがわかります。

さて、次回は、トライのサイズを小さくする2進木構造の実装を説明したいと思います。

広告を非表示にする