Trie木による文字検索

最近、Trie木という面白いデータ構造を知った。

文字列を登録して、その文字が存在するかどうかを調べる場合、ハッシュやブルームフィルターなどが考えられる。

しかし、ハッシュは衝突が頻繁におこると最悪計算量がO(N)まで悪化する。（Nはキーの数。）

ブルームフィルターは高速に登録、判定ができるが、擬陽性があるため厳密なチェックに使うには抵抗がある。

Trie木は、論理上ハッシュと同等の速度で文字列処理ができ（実際はTrie木の方が速い）、ブルームフィルターのような偽検出もない。

ということで、Trie木を使いましょう。

Spaghetti sourceに実装があります。

http://www.prefield.com/algorithm/string/trie.html

短くてシンプルだけど、凡人の私には理解するのに少し時間がかかりました。。（汗）

自分でかいたソースは以下。

class Trie {
public:
    Trie *next[26];

    Trie () {
        fill(next, next+26, (Trie *)0);
    }

    void insert(char *s) {
        if (*s == '\0') return;
        if (this->next[*s-'a'] == NULL)
            this->next[*s-'a'] = new Trie();
        this->next[*s-'a']->insert(s+1);
    }

    bool find(char *s) {
        if (*s == '\0') return true;
        if (this->next[*s-'a'] == NULL)
            return false;
        return this->next[*s-'a']->find(s+1);
    }
};