前缀匹配问题就是类似于你在某个输入框中输入某个字符串, 根据你的输入猜测你要输入的字符串, 比如说, 今天在我的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