最有力候補は、これかも。
404 Blog Not Found:algorithm - Patricia Trie (Radix Trie) を JavaScript で最近のTrie研究の傾向は、要素の動的変更が自在にできる一般向けのものではなく、一旦作成したら要素の追加と削除が困難な代わりにものすごくコンパクトになる、簡潔データ構造の応用手段の方に偏っていると素人目に感じるのですが、そろそろJudyたんのごとくハッシュテーブルとガチで闘うとか、逆に両方のいいとこどりを狙うとかという方向にも行ってくれないかなあ…
目から鱗というか、コロンブスの卵というか。
三分探索木 - Wikipedia三分探索木とはトライ木の各ノードを2分探索木として表現したデータ構造である。
これのどこが素晴らしいかは、Cや(STLやBoostなしの)C++など、動的配列を持たないプログラミング環境でTrieを実装してみれば理解できます。
Trieの問題
Trieは基数をrとした場合のr分木と見なすことができます。何も考えずにrだけ配列を確保すると…
404 Blog Not Found:algorithm - Patricia Trie (Radix Trie) を JavaScript でこうして実装してみると、Trieがコンテンツを整理するコンテナーとして実に自然であることがわかると同時に、電脳上でこれをコンパクトに実現することがなかなか大変なのも実感できます。何も考えずに分岐点に256個のポインターを配列として並べたらそれだけで32bitアーキテクチャーでも1024bytes。いくらなんでもこれでは富豪すぎるというものです。
となりますし、必要に応じて配列を拡張するというのはかなり重い処理になります。この問題はr = 2とすれば一応解決はします。
Trie - Wikipedia, the free encyclopediaBitwise tries
Bitwise tries are much the same as a normal character based trie except that individual bits are used to traverse what effectively becomes a form of binary tree. Generally, implementations use a special CPU instruction to very quickly find the first set bit in a fixed length key (e.g. GCC's __builtin_clz() intrinsic). This value is then used to index a 32 or 64 entry table which points to the first item in the bitwise trie with that number of leading zero bits. The search then proceeds by testing each subsequent bit in the key and choosing child[0] or child[1] appropriately until the item is found.
しかしこの場合、r=256(byte)なノードに対して常に8段のサブノードが存在するというわけで、工夫なしにはそれだけでポインターを8つも消費することになります。
Trieの問題は、空間に対して富豪だという点に集約されるでしょう。
二分探索木の問題
これに対して、二分探索木の問題はこうなります。
基数木 - Wikipedia平衡2分探索木では、検索・挿入・削除には O(log n) の時間がかかるが、基数木では O(k) である。一般に k ≥ log n であるから、これは利点とは見なされないが、平衡2分探索木での比較は常に文字列の比較であり、最悪で O(k) の時間がかかる。特に長い接頭部が共通な文字列を多数格納していると遅くなる。
分岐のたびに文字列全体を比較するという点で、時間に対して実は富豪であるのが平衡二分探索木というわけです。
これぞ両者のいいとこ取り
三分探索木は、この問題を実に鮮やかに解決しています。
- 無駄なノードが存在しない
- Bitwise Trieでは必ずlog2rの段数になりますが、三分探索木では実際に使われた文字数をCとしてlog2Cですみます
- 無駄な比較が存在しない
- 平衡二分探索木におけるO(k)のkが、三分探索木では常に1。
弱点は?
もちろん欠点ゼロというわけには行きません。
- Trieより実装が大変
- ノードが単純なルックアップテーブルである通常のTrieとは異なり、そこを二分探索するわけですから実装者のやることはさらに増えます。
- でもこの部分のみをモジュラーに実装するのは困難ではありません。例えば
child[ch]
でルックアップしているところをnextnode(ch)
として抽象化してしまえば残りは同じはずです。 - 二分木の弱点を抱え込む
- 二分木というのは放っといても平衡しません。例えばソート済みのデータを食わせると、そのままでは常に片側の枝が空のゴージャスな線形リストが出来上がります。それが起こらないように要素の追加と削除の都度平衡させる技術はすでに確立されて利用されていますが、自分で実装するとなるとかなり煩雑です。
- しかし三分探索木に関しては、「本物の」平衡二分探索木よりこの部分を簡素化する余地が大きそうです。例えば要素削除の際の平衡をやめてもいいですし、元の論文のようにあらかじめデータがある場合には、最初の文字をカウントして中央値を得るという方法で平衡処理をなくしています。
またおまえか!
で、この方法を最初に提案したのが誰かというと…
Ternary Search Trees | Dr Dobb'sBy Jon Bentley and Bob Sedgewick, April 01, 1998
Bentley & Sedgewick。この分野ではまさに「相棒」ですねえ。
で、元記事では文字列ソートにこれを用いているのですが、Trieを列挙した結果がそのまま基数ソートを実行した結果と同じになることを考えれば、これをそのまま連想配列の実装に用いてはならぬ理由もまるでありません。彼らがそこまで踏み込まなかったのはなぜだろう…
Dan the Ternary Searcher
このブログにコメントするにはログインが必要です。
さんログアウト
この記事には許可ユーザしかコメントができません。