我是最差的NLPer之Trie树
传统机器学习算法如HMM、CRF、Kmeans，传统数据结构和算法如Trie树、AC自动机、动态规划，都还大有用武之地。
最近就遇到一个问题：如何做敏感词过滤。
网上查了一下资料，方案有两个：确定有限状态自动机（DFA）和AC自动机。
AC自动机又涉及Trie树和KMP算法。
这让我进一步想到NLP中常用的其他数据结构和算法：
- query纠错中的编辑距离
- ROUGE-L中的最长公共子序列
- 序列标注中的维特比算法
- word2vec中的哈弗曼树
- 海量文本求topk相似的局部敏感哈希
看来，为了摆脱一年后失业的悲惨命运，传统的数据结构和算法是不得不学了。
本文整理Trie树的python代码实现。
本来还想基于Trie树，实现搜索引擎的自动联想功能，可是想想520还是一个人过，我还是放过自己吧。
本文关注以下三方面的内容：
-
什么是Trie树
-
Trie树的时间复杂度和空间复杂度
-
Trie树的python实现
三：什么是Trie树
01
Trie树的自我介绍
大家好，我是Trie树，你们也可以叫我字典树或前缀树。
我擅长处理字符串匹配问题，即给定N条字符串的集合，我可以快速判断某条字符串是否在这个集合中。
比如字符串集合中有8个词语：
[“白天”,”白日梦”,”白发”,”白发红颜”,”黑夜”,”黑白”, “黑白颠倒”,”黑白分明”]
我们需要判断 “黑白颠倒” 这个词语是否在这个集合中。
那么我是怎么处理这个问题的呢？
首先我会以树的格式存储这8个词语，如下图。
红色节点的意思是，从上往下到这个节点，是一个词语。
以字典的格式存储，如下：
{'白': {'发': {'Exist': True, '红': {'颜': {'Exist': True}}},
'天': {'Exist': True},
'日': {'梦': {'Exist': True}}},
'黑': {'夜': {'Exist': True},
'白': {'Exist': True,
'分': {'明': {'Exist': True}},
'颠': {'倒': {'Exist': True}}}}}
查找时，我首先把 “黑白颠倒” 拆成【黑，白，颠，倒】三个字。
然后去字典中进行匹配，首先匹配中【黑】字，那么继续往下匹配，发现第一条路径的子节点为【白】，匹配中。
然后继续往下匹配，依次匹配中【颠】、【倒】，于是判断这个词语在字符串集合中。
可以看到，由于很多词有共同的前缀 【黑】，所以第一个字符匹配中【黑】之后，后面字符的匹配，我只在以【黑】开头的这棵右子树上去匹配就行，匹配的速度更快。
如果用纯粹遍历的方法，怎么查找呢？
那我还得拿 “黑白颠倒”
这个词，和以【白】字开头的四个词去比较，速度就慢了。
About The Author
