前綴匹配問題就是類似于你在某個輸入框中輸入某個字符串, 根據你的輸入猜測你要輸入的字符串, 比如說, 今天在我的firefox搜索欄里面搜索了"lighttpd"這個關鍵字, 當我再次輸入"ligh"的時候, 輸入框有一個下拉列表提示我"lighttpd".或者, 類似輸入法中的智能聯想, 輸入前面幾個字符聯想以其為前綴的其它詞組.這些都是前綴匹配技術的典型應用場合.
為了簡單起見, 我們下面的講述假設你所查找的字符串都是由小寫英文字母組成的.
前綴匹配問題最自然的想法就是采用樹, 我最開始的考慮是采用一個二叉樹, 根據字典順序排列來進行搜索.但是這個想法有一些問題, 比如"lighttpd"這個字符串, 在我匹配了最前面的"li"之后去搜索字符"g"的時候, 中間可能要跳躍過由字典順序排在'g'之前的字符, 比如'a','b'等等.也就是說, 根據前綴"li"去查找"lig"的時候, 我們不能馬上定位到"lig"的位置, 或者說, 這樣的定位不是O(1)的, 需要O(log2(n))次, 其中n為你所查找的字符距離字符'a'的距離.
為了解決這個問題, trie樹采用了另一種解決辦法, trie樹中每個節點擁有一個數組, 這個數組的數量是所有可能出現的字符的數量, 基于前面的假設這里提到的字符串全部由小寫字母組成, 那么就是26個元素,而數組的下標是按照字典排序距離字母'a'的距離:
const int num_chars = 2;
struct Trie_node
{
char* data;
Trie_node* branch[num_chars];
Trie_node();
};
假設要搜索前綴'l'開始的字符串, 那么以'a'為前綴的所有字符串的根節點就是root->branch['l' - 'a'], 其中root是樹的根節點.
搜索所有以'lg'為前綴的字符串可以類似展開, 其它的搜索前綴也可以同樣展開.
于是, 前綴匹配問題在trie樹中就可以如下展開:比如要搜索以"li"為前綴的索引, 首先根據前面的算法找到索引為"li"的節點, 則以"li"為前綴的字符串都在以這個節點為根的子節點中.實際情況中, 這樣的子節點可能是很多的, 需要根據情況進行過濾.
這里不再多闡述trie樹的數據結構,
這里有一份實現源碼和算法說明.
可以看到, trie樹對于實現查找可變字符串的索引有很高的效率, 如果要查找n個字符組成的字符串, 只需要n次操作.
同時, trie樹也節省了空間, 比如索引字符串"lig"和"ligh"共享了前面的三個字符.
其它相關文章:
http://blog.csdn.net/lwl_ls/archive/2008/05/03/2373069.aspx