Search on the blog

2011年4月24日日曜日

Trie木による文字検索

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

文字列を登録して、その文字が存在するかどうかを調べる場合、ハッシュやブルームフィルターなどが考えられる。
しかし、ハッシュは衝突が頻繁におこると最悪計算量がO(N)まで悪化する。(Nはキーの数。)
ブルームフィルターは高速に登録、判定ができるが、擬陽性があるため厳密なチェックに使うには抵抗がある。

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

ということで、Trie木を使いましょう。
Spaghetti sourceに実装があります。

短くてシンプルだけど、凡人の私には理解するのに少し時間がかかりました。。(汗)
自分でかいたソースは以下。


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);
    }
};


0 件のコメント:

コメントを投稿