Patricia Trieの実装する上での基礎事項

※Javaコードの実装が追いついていないので、実装でき次第追記しておきます。

Trieは辞書を参照する等で非常に便利なデータ構造なので、ちょっとメモしておく。今回はこのTrieの一種であるPatiricia Trieのお話。

基数木とも呼ばれているが、僕は基本的にPatricia trie（パトリシアトライ、パトリシア木）と呼んでいる。Trieのノードもしくはエッジが文字列に対応する事によって、余計なノードを確保せずにすむのでメモリの節約になる。

実装する上（自分はJavaを想定）での注意点を列挙した。基本的なことであるが「問題を細分化して、自分の理解可能なレベルにまで落とすこと」は非常に重要なことであるので、やってみた。

Trieからの変更点

最もナイーブな実装である「アルファベットの数だけ、配列を確保する」とメモリを浪費してしまう

何も考えずに分岐点に256個のポインターを配列として並べたらそれだけで32bitアーキテクチャーでも1024bytes。いくらなんでもこれでは富豪すぎるというものです。

algorithm - Patricia Trie (Radix Trie) を JavaScript で

これを避けるため、子ノードを動的に確保する。ただし、ソートをしない場合は子ノード探索時に全ての子ノードを線形探索する。ソートをしておけば、二分探索等はできるが、Patricia Trie構築に時間がかかる。

※ちなみに構築と探索のオーダーは、Mはそのノードにおける子ノードの個数とすると、
二分探索木の使用やソートするなら構築に、O(NlogN)、（子ノード）探索にO(logM)、
ソートしない場合は構築にO(N)、（子ノード）探索にO(M)。
ハッシュを使えば、構築にO(N)、子ノード探索にO(1)。ただし、理想的な状況下（ハッシュが衝突を起こさない等）を想定する上、その分メモリは食う。
以上から、構築、探索、メモリのトレードオフになっている。

Insertが少し面倒になる

例えばappleとappsを挿入する際に
１．appleという文字列に対応するキーを持つノード（又はエッジだが、以下ノードに統一する）をルートから挿入する。
２．appsという文字列を挿入する時：
　A.　appというノードを用意する。
　B.　leというノードと、sという文字列に対応するノードを用意して、appノードにつなぐ。

キーに対応するバリューのGetは一文字ではなく、接頭文字列になる。

これはWhile文で一致長をインクリメントすればいいだけだから、さほど難しくない。

Deleteもノードの削除と、親ノードのキー変更がいる

１．appsに対応するノードを削除する（＝デストラクタを起動？）
２．
　A.　leというノードを削除し、appのキーを持つノードのキーに「le」を追加する。
　B.　もしくはそのまま放置

雑記：

より最適化したPatricia Trieはcrit bit treeというビット列のTrieにより実装できる。これは動作が複雑で、まだ理解しきれていないので、また後日。。。あとダブル配列やLOUDSも構築、探索、メモリのトレードオフをぶち壊して、より最適に近くなるはず。詳しくはcedar - C++ implementation of efficiently-updatable double-array trieとかを参照するとライブラリ間のパフォーマンスが比較されていて良いはず。