炼数成金 门户 科学探索 算法 查看内容

我是最差的NLPer之Trie树

2020-5-18 09:28| 发布者: 炼数成金_小数| 查看: 24901| 评论: 0|原作者: 邓邓最棒|来自: 叫我NLPer

摘要: 自然语言处理还不是深度学习的天下。传统机器学习算法如HMM、CRF、Kmeans,传统数据结构和算法如Trie树、AC自动机、动态规划,都还大有用武之地。最近就遇到一个问题:如何做敏感词过滤。网上查了一下资料,方案有两 ...
一 :今日吐槽
作为一个没有系统学过CS四大课程的NLPer,凭借一手百度+CTRL-C+CTRL-V的技能,混迹于技术中心,实属不易。

不要问我线程安全,问就是不会。
不要问我TCP三次握手,问就是不会。
不要问我二叉树的后序遍历,问就是不会。

知乎上有个问题:你见过最差的算法工程师能差到什么程度?

有个回答:
"我听过一个江湖潜规则,每一个大公司团队都会招一个特别不着调,水平也不行,智商也比较低的算法工程师,用来背低绩效。

当组里成员感到职业发展太难的时候,就会下意识看看那个人,这样,心里就会有莫大的安慰。

我当时下意识地看看周围的同事,发现他们都不符合这些描述。"

我也回头看了看钰轩君、费马君和其他同事,发现他们都不符合这些描述。

二:内容预告
自然语言处理还不是深度学习的天下。

传统机器学习算法如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个词语,如下图。

红色节点的意思是,从上往下到这个节点,是一个词语。


以字典的格式存储,如下:


查找时,我首先把 “黑白颠倒” 拆成【黑,白,颠,倒】三个字。

然后去字典中进行匹配,首先匹配中【黑】字,那么继续往下匹配,发现第一条路径的子节点为【白】,匹配中。

然后继续往下匹配,依次匹配中【颠】、【倒】,于是判断这个词语在字符串集合中。

可以看到,由于很多词有共同的前缀 【黑】,所以第一个字符匹配中【黑】之后,后面字符的匹配,我只在以【黑】开头的这棵右子树上去匹配就行,匹配的速度更快。

如果用纯粹遍历的方法,怎么查找呢?
那我还得拿 “黑白颠倒” 这个词,和以【白】字开头的四个词去比较,速度就慢了。

02 Trie树的特点、复杂度和适用场景
通过以上简单的例子,你大概也可以总结出我作为巨蟹座的三个特点:

根节点(ROOT)不包含字符,除根节点以外的每个节点只包含一个字符。
从根节点到特殊标记节点(红色节点),路径上经过的字符连接起来,为该特殊节点对应的完整字符串。 
每个节点的所有子节点(字符)不相同。

我坚决贯彻以空间换时间的方针政策,利用字符串的公共前缀,减少无谓的字符串比较,从而降低查询的时间复杂度。

假设字符集的总数为m(比如英文中只有26个字母),如果需要存储的字符串的较大长度为n,那么树的每个节点出度为m(即每个节点可能的子节点数量为m),Trie树的高度为n。

我的空间复杂度为O(m^n),是不是很恐怖?
但是正由于每个节点的出度为m,所以我能够每次顺着分支(最多m个)往下查找,而不需要遍历所有的字符串。

我的时间复杂度为O(n)。

也就是说,如果要查询的字符串长度为n,那么查n次,就可以查到。

每个班都有一个灵活的胖子。
我通常出现在搜索引擎系统中,用于搜索提示和词频统计,也作为AC自动机的基本数据结构,用于敏感词过滤。


四:Trie树的实现
下面就用Python来写一棵Trie树,实现插入和查找字符串的功能。

五:Trie树的白板编程

拿出一张A4纸,来一个白板编程。


最近不知道自己在干什么,这篇写得很水,各位看官就当是在看笑话吧。

声明:文章收集于网络,版权归原作者所有,为传播信息而发,如有侵权,请联系小编删除,谢谢!

欢迎加入本站公开兴趣群
高性能计算群
兴趣范围包括:并行计算,GPU计算,CUDA,MPI,OpenMP等各种流行计算框架,超级计算机,超级计算在气象,军事,航空,汽车设计,科学探索,生物,医药等各个领域里的应用
QQ群:326600878

鲜花

握手

雷人

路过

鸡蛋

相关阅读

最新评论

热门频道

  • 大数据
  • 商业智能
  • 量化投资
  • 科学探索
  • 创业

即将开课

 

GMT+8, 2020-7-9 13:53 , Processed in 0.098637 second(s), 25 queries .