algorithm - Patricia Trie (Radix Trie) を JavaScript で

スマホ手袋 5本指全てタッチできる
smarttouch 5105
ミドリ安全

寒いのでこれをしたまま書きました。

• dankogai/js-trie-patricia - GitHub
• 404 Blog Not Found:Algorithm - 連想配列の実装としてのハッシュはオワコン?

Trieが連想配列の代わりになるというのを体でも納得しておきたかったので。

はじめてのTrie

というわけで早速作ってみましょう。あっけにとられるほど簡単です。ここではObject、つまり連想配列で分岐点を実現するというある意味本末転倒なことをしていますが、JSならばしかたがない。

var Trie = function() {
    if (!(this instanceof Trie)) return new Trie;
};
Trie.prototype.set = function(key, val) {
    var i, cc, node = this;
    for (var i = 0; i < key.length; i++){
        cc = key.charAt(i);
        if (!node[cc]) node[cc] = new Trie();
        node = node[cc];
    };
    node[''] = val;
    return this;
};
var t = new Trie;
'foo fool foolish foolishness bar baz'.split(' ').forEach(function(w){
    t.set(w, w.toUpperCase());
});
p(JSON.stringify(t, null, 2)); /* prettyprint */

確かにTrieの要件を満たしています。が、なにこれすかすか。見ての通り、要素が一つしか入っていないノードが山のようにあります。

Suffixをまとめる

すぐに思いつくのは、分岐がない接尾辞はひとまとめにしてしまうことです。葉にはキーの残りと値を格納します。ペアなのでここでは配列で。

var Trie = function() {
    if (!(this instanceof Trie)) return new Trie;
};
Trie.prototype.set = function(key, val) {
    var cc  = key.charAt(0),
        suf = key.substr(1);
    if (!cc || !this[cc]){ 
        this[cc] = [suf, val];
    }
    else if (this[cc] instanceof Trie) {
        this[cc].set(suf, val);
    }
    else {
        var kid = new Trie;
        kid.set(this[cc][0], this[cc][1]);
        kid.set(suf, val);
        this[cc] = kid;
    };
    return this;
};

var t = new Trie;
'foo fool foolish foolishness bar baz'.split(' ').forEach(function(w){
    t.set(w, w.toUpperCase());
});
p(JSON.stringify(t, null, 2)); /* prettyprint */

コードが少し長くなりましたが、効果てきめん。しかしこれにも問題があります。正規表現で書けば f(oo(l(ish(ness)?)?)? となるこの部分、"oo"とか"ish"とかさらにまとめられないでしょうか?

やりましょう。

Suffixもまとめて、Patricia Treeのできあがり

できました。

var Trie = function() {
    if (!(this instanceof Trie)) return new Trie;
};

var preflen = function(a, b) {
    var n = 0;
    for (; n < a.length && n < b.length; n++) {
        if (a.substr(n, 1) !== b.substr(n, 1)) return n;
    }
    return n;
};

Trie.prototype.set = function(key, val) {
    var cc = key.charAt(0),
        suf = key.substr(1);
    if (!cc || !this[cc]) {
        this[cc] = [suf, val];
    }
    else if (this[cc] instanceof Trie) {
        this[cc].set(suf, val);
    }
    else {
        var pk = this[cc][0], pv = this[cc][1],
            pl = preflen(pk, suf), kid = new Trie;
        if (pl <= 1) {
            kid.set(suf, val);
            kid.set(pk, pv);
            this[cc] = kid;
        }
        else {
            if (pv instanceof Trie) {
                pv.set(suf.substr(pl), val);
            }
            else {
                kid.set(pk.substr(pl), pv);
                kid.set(suf.substr(pl), val);
                this[cc] = [suf.substr(0, pl), kid];
            }
        }
    }
    return this;
};

var t = new Trie;
'foo fool foolish foolishness bar baz'.split(' ').forEach(function(w){
    t.set(w, w.toUpperCase());
});
p(JSON.stringify(t, null, 2)); /* prettyprint */

出来上がった木もずいぶんとコンパクトになりました。

これを、パトリシア木(Patricia Tr(ee|ie))または基数木(Radix Tr(ee|ie))と呼びます。

基数木 - Wikipedia

基数木は簡単に言えばメモリ使用量を最適化したトライ木であり、トライ木で子ノードが1つしかないノードを子ノードとマージしたものである。その結果、内部ノードは必ず2つ以上の子ノードを持つことになる。通常のトライ木と異なり、辺には1つの文字だけでなく文字の並びがラベルとして付与される。これは、集合が小さい場合（特に長い文字列の集合）や長い接頭部を共有する文字列の集合などで効果を発揮する。

Canonicalな名前としてはWikipediaはRadixの方を採用していますが、Patriciaの方がずっと萌えますよね。Practical Algorithm To Retrieve Information Coded In Alphanumericの略というのが無理がないところもいい。まあJavaScriptの場合最後のAはUnicodeのUなのかも知れませんが。

実際に使うには要素をつっこむだけではなく取り出したり削除したりもしなければならないのですが、GitHubに上げたやつは、一通り連想配列としての機能を揃えています。以下でお試し下さい。

var tp = Trie.Patricia({foo:1,fool:2,foolish:3,foolishness:4}); p(tp.set('f', undefined)); p(tp.get('f')); p(tp.has('f')); p(tp.has('fo')); p(tp.del('f')); p(tp.has('f')); tp.each(function(k, v){ p(k, v); }); p(tp.keys()); p(tp.values()); p(tp.toRegExp('g')); var s = '' + tp.toRegExp(), /* for exact match */ rx = new RegExp( '^' + s.substr(1, s.length-2) + '$', 'm'); p(rx); 'foo fool foolish foolishness fools f'.split(' ').forEach(function(v){ p(v, v.match(rx)); }); p(JSON.stringify(tp.toObject())); p(tp.asJSON(null, 2)); p(tp = Trie.Patricia(tp.toObject())); /* Should we implement .clone ? */ p(tp.asJSON(null, 2));

よく見ると、二点ほど「ズル」をしています。

• 純粋な Patricia Trie は何もせずとも線形読み出しで辞書順でキーを取り出せますが、前述のとおりここでは(主にJSONにしたときの見栄えのために)ArrayではなくObjectで実装しているため、キーを取り出す段階で各Radix都度ソートしています。
• 要素の削除にあたって、分割されたPrefixをまとめなおすことはしていません。ハッシュテーブルの実装で要素を削除した際にテーブルを小さくするものが滅多にない--たいてい明示的にclearするかハッシュテーブルそのものを解放するか--ことを考えれば、これは妥当だと考えます。

現段階ではとりあえず連想配列に出来ることは全部パトリシアたんにもできるおと示す程度の実装ではありますが、一つだけ実地でも使えるかも知れない機能を追加しておきました(common prefix searchを後回しにするのどうよって我ながら思います)。

キーの文字列にexact matchするregexpを生成する機能です。

• 404 Blog Not Found:TRIE-Optimized Regexp
• 404 Blog Not Found:perl - 自動で /a|b|c/ を /[abc]/ にしてくれたら...

これのJS版ですね。

こうして実装してみると、Trieがコンテンツを整理するコンテナーとして実に自然であることがわかると同時に、電脳上でこれをコンパクトに実現することがなかなか大変なのも実感できます。何も考えずに分岐点に256個のポインターを配列として並べたらそれだけで32bitアーキテクチャーでも1024bytes。いくらなんでもこれでは富豪すぎるというものです。

だからって使う分だけメモリーを動的確保してはpushして、そこを線形探索したら、折角の本棚に本を縦積みするようなものですし。Judyのような意欲的な実装では、このあたりが一番の苦労のしどころとなっているのもうなづけます。

最近のTrie研究の傾向は、要素の動的変更が自在にできる一般向けのものではなく、一旦作成したら要素の追加と削除が困難な代わりにものすごくコンパクトになる、簡潔データ構造の応用手段の方に偏っていると素人目に感じるのですが、そろそろJudyたんのごとくハッシュテーブルとガチで闘うとか、逆に両方のいいとこどりを狙うとかという方向にも行ってくれないかなあ…

連想配列の実装が仮にハッシュテーブルからTrieになったとしても、Perl Mongers と Rubyists はやはりそれをhashと呼び続けるのだろうか。dictionaryとかmapとかって表現はなんか書生くさいし…Object?それはちょっと勘弁を。

Dan the Man with Too Many Things to Search

JS Source