大展身手的字典树
在简单字典树(Trie)的实现一文中,我们以单词输入自动提示
为引子,简单介绍了字典树的实现。那么,字典树到底可以用于哪些场合呢?
- 前缀匹配:给定字典库,输入一段字符,返回以该字符串为前缀的所有单词。
- 字频统计:给出一段文本,统计其中指定单词出现的频数。
前缀匹配
本文讲述前缀匹配的字典树实现方案。仍然假设我们有以下单词:apps apple cook cookie cold,当我们想获得以co为前缀的单词时,只需要在字典树中依次找到c、o节点,然后搜索o节点的所有子树,取出其中的单词即可。
在简单字典树(Trie)的实现一文中,我们已经实现了字典树的基本操作,这里只需要再加上一个前缀匹配方法即可。具体流程如下,将前缀字符串标记为当前前缀
,将根节点标记为当前节点
,执行操作1:
- 当前前缀为空,对当前节点执行操作2。否则,取出当前单词的首字符,标记为X,遍历当前节点的子节点,如果X存在于子节点N中,将N标记为当前节点,将剩余字符串标记为当前单词,重复操作1;如果X不存在于子节点中,返回None。
- 以当前节点为根节点,进行深度优先搜索,取得当前节点所有子树下的所有单词。
实现的伪代码如下:
1 | def pre_match_op(current_word, current_node): |
具体程序以及测试例子放在gist上,可以在这里找到。测试了一下,两千多个单词,寻找共同前缀的单词,速度还是蛮快的。
字频统计
有时候我们需要统计一篇文章中一些单词出现的次数,这个时候用字典树可以很方便的解决这个问题。在字典树的简单实现中,我们设计的节点数据结构如下:
只要对这里节点的数据结构稍作修改,就可以用于统计字频了。把原来数据结构中的标记位改为频数位
,即保存该单词出现的次数。然后,再把原有字典树实现中的插入操作和查找操作稍微改动,就可以实现字频统计功能了。
插入操作:将单词标记为
当前单词
,将根节点标记为当前节点
,执行操作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。
实现伪代码如下,插入操作如下:
1 | def insert(word): |
查询操作:
1 | def count(word): |
具体程序以及测试例子放在gist上,可以在这里找到。