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