Trie木による文字検索

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

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

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

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

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

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

Spaghetti sourceに実装があります。

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

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

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

view plainprint?

1. class Trie {  
2. public:  
3.     Trie *next[26];  
4.   
5.     Trie () {  
6.         fill(next, next+26, (Trie *)0);  
7.     }  
8.   
9.     void insert(char *s) {  
10.         if (*s == '\0') return;  
11.         if (this->next[*s-'a'] == NULL)  
12.             this->next[*s-'a'] = new Trie();  
13.         this->next[*s-'a']->insert(s+1);  
14.     }  
15.   
16.     bool find(char *s) {  
17.         if (*s == '\0') return true;  
18.         if (this->next[*s-'a'] == NULL)  
19.             return false;  
20.         return this->next[*s-'a']->find(s+1);  
21.     }  
22. };  

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