概要

トライ木のアルゴリズムと実装についてかく。

トライ木とは

トライ木（プレフィックス木ともいう。英語はそれぞれ、trie、prefix tree）は文字列の集合を扱う木構造の一種。

各ノードは単一または複数の文字列あるいは数値を持ち（ノードは必ずしも値を持つ必要はない）、根ノードから葉に向かって探索して値をつなげていくことで単語を表現する。

ネットワークのレイヤーならIPアドレスの探索、アプリケーションレイヤーならhttpのルーティングに、機械学習とかの文脈であれば形態素解析といったところでトライ木の応用が見受けられる。

言葉で説明するよりもビジュアルのほうが頭に入りやすい。

メモリ効率が悪いので、メモリ効率がボトルネックとなるような場合はRadix Tree（Patricia Trie）のような文字列のプレフィックスを効率的に格納する木構造を検討したほうが良さそう。

検索キーの長さをmとしたとき、最悪計算量はO(m)となる。検索も挿入も同じである。

検索キーの挿入と検索だけ実装した。

構造体Nodeのchildrenはruneをmapのキーとしているが、stringでも問題ない気がする。

Insertのアルゴリズムは単純で、Insertしたい文字列の文字数分ループして、子ノードに一致するキーがあるかチェック、なければノードを追加するだけである。

子ノードに一致するキーがあるかどうかはGolangでは、v, ok:=map[key]のイディオムを使って書くことができる。（初心者過ぎて知らなかったせいでちょっとハマった）

SearchのアルゴリズムはInsertのアルゴリズムが書ければ理解できる。というより殆ど考え方は同じ。

トライ木の応用であるRadix Treeという木構造の実装に取り組んでいたのだが、あと一歩みたいなところで何度も躓いて挫折した。。。ちょっと遠回りしてまた再挑戦する。

GolangでTrieを使ってroutingを作ろうとしている。 https://github.com/bmf-san/bmf-go-router

トライ木はちょっとしたサジェスト機能なんかの実装とかにも使える気がするのでJavaScriptとかで実装してみたい。