摘要:原文地址在简单字典树的实现一文中,我们以单词输入自动提示为引子,简单介绍了字典树的实现。前缀匹配本文讲述前缀匹配的字典树实现方案。在简单字典树的实现一文中,我们已经实现了字典树的基本操作,这里只需要再加上一个前缀匹配方法即可。
原文地址
在简单字典树(Trie)的实现一文中,我们以单词输入自动提示为引子,简单介绍了字典树的实现。那么,字典树到底可以用于哪些场合呢?
前缀匹配:给定字典库,输入一段字符,返回以该字符串为前缀的所有单词。
字频统计:给出一段文本,统计其中指定单词出现的频数。
前缀匹配本文讲述前缀匹配的字典树实现方案。仍然假设我们有以下单词:apps apple cook cookie cold,当我们想获得以co为前缀的单词时,只需要在字典树中依次找到c、o节点,然后搜索o节点的所有子树,取出其中的单词即可。
在简单字典树(Trie)的实现一文中,我们已经实现了字典树的基本操作,这里只需要再加上一个前缀匹配方法即可。具体流程如下,将前缀字符串标记为当前前缀,将根节点标记为当前节点,执行操作1:
当前前缀为空,对当前节点执行操作2。否则,取出当前单词的首字符,标记为X,遍历当前节点的子节点,如果X存在于子节点N中,将N标记为当前节点,将剩余字符串标记为当前单词,重复操作1;如果X不存在于子节点中,返回None。
以当前节点为根节点,进行深度优先搜索,取得当前节点所有子树下的所有单词。
实现的伪代码如下:
</>复制代码
def pre_match_op(current_word, current_node):
if current_word not empty:
X = current_word[0]
if X in current_node.child_node:
current_word = current_word[1:]
current_node = child_node
return pre_match_op(current_word, current_node)
else:
return None
else:
return pre_match_bfs("", current_node)
def pre_match_dfs(keep_char, current_node):
match_word = []
for child in current_node.child_node:
current_pre = pre_str + keep_char
if child.isword = True:
word = current_pre + child.char
match_word.append(word)
else:
pass
pre_match_dfs(current_pre, child)
return match_word
具体程序以及测试例子放在gist上,可以在这里找到。测试了一下,两千多个单词,寻找共同前缀的单词,速度还是蛮快的。
字频统计有时候我们需要统计一篇文章中一些单词出现的次数,这个时候用字典树可以很方便的解决这个问题。
在字典树的简单实现中,我们设计的节点数据结构如下:
图1. 用list实现字典树
只要对这里节点的数据结构稍作修改,就可以用于统计字频了。把原来数据结构中的标记位改为频数位,即保存该单词出现的次数。然后,再把原有字典树实现中的插入操作和查找操作稍微改动,就可以实现字频统计功能了。
插入操作:将单词标记为当前单词,将根节点标记为当前节点,执行操作1:
当前单词为空,当前节点单词出现频数加1,终止操作;否则取出当前单词的首字符记为X,遍历当前节点的子节点:如果X存在于子节点N,将剩余字符标记为当前单词,将N标记为当前节点,重复操作1,如果X不存在于当前节点的子节点中,那么进入操作2。
取出当前单词的首字符记为X,新建一个节点M存储X,M的父节点为当前节点。剩余字符串记为当前单词,如果当前单词为空,M节点单词出现频数加1,终止操作;否则,将M标记为当前节点,重复操作2。
查询操作:将单词标记为当前单词,将根节点标记为当前节点,执行操作1:
当前单词为空,返回当前节点字频数,即为该单词出现的次数。否则,取出当前单词的首字符,标记为X,遍历当前节点的子节点,如果X存在于子节点N中,将N标记为当前节点,将剩余字符串标记为当前单词,重复操作1;如果X不存在于子节点中,返回0。
实现伪代码如下,插入操作如下:
</>复制代码
def insert(word):
current_word = word
current_node = root
insert_operation_1(current_word, current_node)
def insert_operation_1(current_word, current_node):
if current_word not empty:
X = current_word[0]
if X in current_node.child:
current_word = current_word[1:]
current_node = child_node
insert_operation_1(current_word, current_node)
else:
insert_operation_2(current_word, current_node)
else:
current_node.count++
def insert_operation_2(current_word, current_node):
X = current_word[0]
M.value = x
M.father = current_node
current_node.child = M
current_word = current_word[1:]
if current_word not empty:
current_node = M
insert_operation_2(current_word, current_node)
else:
current_node.count++
查询操作:
</>复制代码
def count(word):
current_word = word
current_node = root
return find_opration(current_word, current_node)
def count_opration(current_word, current_node):
if current_word not empty:
X = current_word[0]
if X in current_node.child_node:
current_word = current_word[1:]
current_node = child_node
return find_opration(current_word, current_node)
else:
return 0
else:
return current_node.count
具体程序以及测试例子放在gist上,可以在这里找到。
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/37340.html
摘要:在树中,每个节点表示一个状态,每条边表示一个字符,从根节点到叶子节点经过的边即表示一个词条。查找一个词条最多耗费的时间只受词条长度影响,因此的查找性能是很高的,跟哈希算法的性能相当。 Last-Modified: 2019年5月10日15:25:35 参考文章 c++ 使用map实现Trie树 关键词过滤扩展,用于检查一段文本中是否出现敏感词,基于Double-Array Trie...
摘要:另一种高效实现下面介绍另一种实现,它将字典树用数组存储起来,不仅压缩了数组,而且不降低查找效率。这就是双数组字典树。 字典树的心得体会 常见的字典树实现方法 class Node{ uint node ; uint[] next; }; 或者类似如下结构 class Node{ uint node; map n...
阅读 1692·2019-08-30 12:51
阅读 684·2019-08-29 17:30
阅读 3722·2019-08-29 15:17
阅读 868·2019-08-28 18:10
阅读 1398·2019-08-26 17:08
阅读 2190·2019-08-26 12:16
阅读 3454·2019-08-26 11:47
阅读 3514·2019-08-23 16:18