前綴匹配問題就是類似于你在某個輸入框中輸入某個字符串, 根據(jù)你的輸入猜測你要輸入的字符串, 比如說, 今天在我的firefox搜索欄里面搜索了"lighttpd"這個關(guān)鍵字, 當(dāng)我再次輸入"ligh"的時候, 輸入框有一個下拉列表提示我"lighttpd".或者, 類似輸入法中的智能聯(lián)想, 輸入前面幾個字符聯(lián)想以其為前綴的其它詞組.這些都是前綴匹配技術(shù)的典型應(yīng)用場合.

為了簡單起見, 我們下面的講述假設(shè)你所查找的字符串都是由小寫英文字母組成的.

前綴匹配問題最自然的想法就是采用樹, 我最開始的考慮是采用一個二叉樹, 根據(jù)字典順序排列來進行搜索.但是這個想法有一些問題, 比如"lighttpd"這個字符串, 在我匹配了最前面的"li"之后去搜索字符"g"的時候, 中間可能要跳躍過由字典順序排在'g'之前的字符, 比如'a','b'等等.也就是說, 根據(jù)前綴"li"去查找"lig"的時候, 我們不能馬上定位到"lig"的位置, 或者說, 這樣的定位不是O(1)的, 需要O(log2(n))次, 其中n為你所查找的字符距離字符'a'的距離.

為了解決這個問題, trie樹采用了另一種解決辦法, trie樹中每個節(jié)點擁有一個數(shù)組, 這個數(shù)組的數(shù)量是所有可能出現(xiàn)的字符的數(shù)量, 基于前面的假設(shè)這里提到的字符串全部由小寫字母組成, 那么就是26個元素,而數(shù)組的下標(biāo)是按照字典排序距離字母'a'的距離:
const int num_chars = 2;
struct Trie_node
{
    char* data;
    Trie_node* branch[num_chars];
    Trie_node();
};
假設(shè)要搜索前綴'l'開始的字符串, 那么以'a'為前綴的所有字符串的根節(jié)點就是root->branch['l' - 'a'], 其中root是樹的根節(jié)點.
搜索所有以'lg'為前綴的字符串可以類似展開, 其它的搜索前綴也可以同樣展開.

于是, 前綴匹配問題在trie樹中就可以如下展開:比如要搜索以"li"為前綴的索引, 首先根據(jù)前面的算法找到索引為"li"的節(jié)點, 則以"li"為前綴的字符串都在以這個節(jié)點為根的子節(jié)點中.實際情況中, 這樣的子節(jié)點可能是很多的, 需要根據(jù)情況進行過濾.

這里不再多闡述trie樹的數(shù)據(jù)結(jié)構(gòu), 這里有一份實現(xiàn)源碼和算法說明.

可以看到, trie樹對于實現(xiàn)查找可變字符串的索引有很高的效率, 如果要查找n個字符組成的字符串, 只需要n次操作.
同時, trie樹也節(jié)省了空間, 比如索引字符串"lig"和"ligh"共享了前面的三個字符.

其它相關(guān)文章:
http://blog.csdn.net/lwl_ls/archive/2008/05/03/2373069.aspx