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

Javaで簡潔TRIE(1)

Java

さて、今回からは、気分を変えて、簡潔なTRIEをJavaで作ってみたいと思います。

この「簡潔な」というのがポイントで、じゃあ、ただのTRIEって何なの?という疑問になるわけです。

TRIEというのは、木構造の一種で、正確には、トライ木と呼ばれるものです。
なぜ、トライ木をTRIEと書くのかというと、TREEとの混同を避けるためです。
ただのTREEよりも「Retrieval(検索)」の意味を強くもたせるために、Retrievalの部分文字列であるReTRIEvalを使って、TRIEと表現するようです。
このあたりの説明は、Wikipediaにも書いてあります。

概念的には、それほど難しくないと思います。
ただし、その応用範囲は広く、様々な言語の標準的な実装で使われています。
主に、文字列をキーとした連想配列を実現するのに使われることが多いようです。

その他にも、形態素解析器の辞書引きに使われるなど、応用範囲の広い基本データ構造です。

ビッグデータ時代の到来で、マシンを大量に並べてうんぬんかんぬんというのが流行です。
ただ、それらはスケーリングとしては重要ですが、各ノードでは、やはり基本データ構造を組み合わせて、性能を出すのが重要だと思います。
そういった意味でも、トライ木を勉強することは、「worthwhile」だと思います。

さて、次回は、トライについてもう少し説明をしたいと思います。

広告を非表示にする