随笔 - 6, 文章 - 0, 评论 - 24, 引用 - 0
数据加载中……

Trie—单词查找树

 

Trie—单词查找树

l  简介

Trie又称单词查找树、前缀树,是一种哈希树的变种。应用于字符串的统计与排序,经常被搜索引擎系统用于文本词频统计。

含有单词“tea”“tree”“A”“ZSU”的一棵Trie

l  性质

n  根节点不包含字符,除根节点外的每一个节点都只包含一个字符。

n  从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串。

n  每个节点的所有子节点包含的字符都不相同。

l  优点

n  查询快。对于长度为m的键值,最坏情况下只需花费O(m)的时间;而BST最坏情况下需要O(m log n)的时间。

n  当存储大量字符串时,Trie耗费的空间较少。因为键值并非显式存储的,而是与其他键值共享子串。

n  Trie适用于“最长前缀匹配”。

l  操作

n  初始化或清空

遍历Trie,删除所有节点,只保留根节点。

n  插入字符串

1.     设置当前节点根节点,设置当前字符为插入字符串中的首个字符;

2.     当前节点的子节点上搜索当前字符,若存在,则将当前节点设为值为当前字符的子节点;否则新建一个值为当前字符的子节点,并将当前结点设置为新创建的节点。.

3.     当前字符设置为串中的下个字符,若当前字符0,则结束;否则转2.

n  查找字符串

搜索过程与插入操作类似,当字符找不到匹配时返回假;若全部字符都存在匹配,判断最终停留的节点是否为树叶,若是,则返回真,否则返回假。

n  删除字符串

首先查找该字符串,边查询边将经过的节点压栈,若找不到,则返回假;否则依次判断栈顶节点是否为树叶,若是则删除该节点,否则返回真。

l 实现
对于字符表大小为S的字符串集,需建立一个S叉树来代表这些字符串的集合。

l  代码

trie.h


l  参考资料

英文维基 http://en.wikipedia.org/wiki/Trie

中文维基 http://zh.wikipedia.org/w/index.php?title=Trie&variant=zh-cn

posted on 2009-03-27 23:51 yuyang7 阅读(5250) 评论(5)  编辑 收藏 引用 所属分类: 数据结构

评论

# re: Trie—单词查找树  回复  更多评论   

好,不错,呵呵
2009-03-28 15:55 | 中国福利彩票

# re: Trie—单词查找树  回复  更多评论   

如果想在磁盘上存储Trie可以嘛?也许用数组实现?
比如说词典的应用。用只读的Trie存储词典索引,每个节点保存数据文件的文件偏移量。要求可以直接从磁盘上用file mapping使用词典索引。
2009-03-28 22:27 | lxu

# re: Trie—单词查找树  回复  更多评论   

@lxu
嗯,构造双数组trie (Double-Array Trie)。
2009-03-28 23:26 | yuyang7

# re: Trie—单词查找树  回复  更多评论   

谢谢,学到东西了。
不过觉得博主的代码可以优化下,重复代码的地方太多。

比如说insert的C风格部分,我觉得可以改成,

void insert(const char* str)
{
int size = strlen(str);
insert<char*>(str, str + size);
}
====================================
这样子可以减少重复代码的部分,而且也方便以后修改嘛。

另外,貌似memset(child, 0, sizeof(child))应该改成memset(child, 0, size * sizeof(child))
2009-03-31 00:04 | 黄宇

# re: Trie—单词查找树[未登录]  回复  更多评论   

同意楼上的第一点意见,实际上我是先实现了针对C风格字符串的函数,后来觉得有需要对一段区间内的字符进行查找,才添加了针对迭代器的函数,造成了代码冗余.
第二点意见我并不认同,可能楼上理解偏差了.可能楼上是想说 memset(child, 0, size * sizeof(tree_node<size>*)  的吧.
2009-03-31 11:32 | yuyang7

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理