python自然语言处理之字典树知识总结

作者:李元静 时间:2023-12-29 01:01:21 

一、什么是字典树

在自然语言处理中,字符串集合常用字典树存储,这是一种字符串上的树形数据结构。字典树中每条边都对应一个字,从根节点往下的路径构成一个个字符串。

字典树并不直接在节点上存储字符串,而是将词语视作根节点到某节点之间的一条路径,并在终点节点上做个标记(表明到该节点就结束了)。

要查询一个单词,指需要顺着这条路径从根节点往下走。如果能走到标记的节点,则说明该字符串在集合中,否则说明不在。下图为字典树结构示例:

python自然语言处理之字典树知识总结

如上图所示,每条路径都是一个词汇,且没有子节点就可以判定该条路径结尾了。具体可以映射为下标所示:

词语路径
欢迎0-1-2
北大0-3-8
北京城0-3-4-5
北京大学0-3-4-6-7

至于字典树的实现,相信只要认真学过数据结构的读者,都能手到擒来,这里不在赘述。因为HanLP库已经提供了多种字典树。

二、DoubleArrayTrieSegment

认识DoubleArrayTrieSegment类之前,我们需要了解双数组字典书的概念。

我们都知道,在树中遍历查找之时,我们一般用二分查找,假如某一个树的节点有N个节点,那么其复杂度就为O(logN),这样查找起来一条一条树的遍历会非常的慢,所以就诞生了双数组字典树的概念。

双数组字典树(DAT)是一种状态转移复杂度为常数的数据结构。那么什么是状态呢?从确定有限状态自动机(DFA)的角度来讲,每个节点都是一个状态,状态表示当前已查询到的前缀。

从父节点到子节点的移动过程可以看作一次状态转移。在按照某个字符进行状态转移前,我们会向父节点询问该字符与子节点的映射关系(也就是一条路径一条边)。如果父节点有满足条件的边,则状态转移到子节点;否则立即失败,查询不到。当成功完成了全部转移时,我们就拿到了最后一个状态,询问该状态是否时最终状态。如果是,就查询到该词汇,否则该单词不存在于字典中。

比如我们查询首图的“北京大学”,状态开始为0,查询到北时状态为3,查询到京时状态为4,查询到大时状态为6,查询到学时状态为7,最后判断7是否还有子节点,如果没有匹配该词汇,如果有该词汇不在字典中。比如查询“北京大”就不在词汇中。

而双数组字典由base与check两个数组组成,其中base数组即节点,也是状态,分为空闲状态与占用状态,check数组为每个元素表示某个状态的前驱状态。具体公式如下:


base[s] + c = t
check[t] =  s

base树组中的s代表当前状态的下标,t代表转移状态的下标,c代表输入字符的数值


base[s] + c = t //表示一次状态转移

由于转移后状态下标为t,且父子关系是唯一的,所以可通过检验当前元素的前驱状态确定转移是否成功


check[t] = s //检验状态转移是否成功

这种算法相对于传统的Trie树二分查找的优点是,只需要一个加法一次比较即可完成一次状态转移,只花费了常数时间,下面给出了双数组Tree树的原理图(注意观察状态转移的过程)

python自然语言处理之字典树知识总结

了解了双数组字典树的原理,我们就可以来学习DoubleArrayTrieSegment,DoubleArrayTrieSegment分词器是对DAT(双数组字典树)最长匹配的封装,默认加载hanlp.properites中CoreDictionaryPath指定的词典。

对应的python代码如下:


if __name__ == "__main__":
   HanLP.Config.ShowTermNature=False#分词结果不显示词性
   segment=DoubleArrayTrieSegment()
   print(segment.seg("在来到这个世界之前,一起都很Happy"))

运行之后,得到如下图所示的结果:

python自然语言处理之字典树知识总结

当然,这是HanLP提供给我们的默认词典,如果想加载自己的词典,或者前文提到的其他开源的词典库,可以替换代码如下所示:


DoubleArrayTrieSegment(["词典1","词典2"])

但是不知道读者注意到了没有,上面的英文happy,它给我们拆成了单个的字母,但其实这是一个整体,如果这里替换成数字,也是一个一个数字,那么如何不让其拆开呢?

我们来看一段代码:


if __name__ == "__main__":
   HanLP.Config.ShowTermNature=True
   segment=DoubleArrayTrieSegment()
   segment.enablePartOfSpeechTagging(True)
   print(segment.seg("在来到这个世界之前,一起都很Happy"))

enablePartOfSpeechTagging函数的意思是激活数字与英文识别,同时我们把ShowTermNature改为True,观察其输出的结果:

python自然语言处理之字典树知识总结

这里与我们前面自己写的算法输出一模一样,有分开的词汇以及词汇的标记属性。

三、AhoCorasickDoubleArrayTrieSegment

虽然双数组字典树能遍历大量的数据,但是如果数据比较长的,这些长的词汇又比较多的话,比如“受命于天,既寿永昌”算一个词汇,那么其处理起来时间复杂度依旧非常耗时。所以,我们就需要使用ACDAT进行遍历。

这里博主不讲解其原理,因为太长篇幅有限,感兴趣的可以专门学习树结构的处理。读者只需要知道其原理,什么时候用双数组遍历,什么时候用ACDAT遍历就行。而HanLP封装的ACDAT的实现类是AhoCorasickDoubleArrayTrieSegment。

下面,我们来实现AhoCorasickDoubleArrayTrieSegment,代码如下:


if __name__ == "__main__":
   HanLP.Config.ShowTermNature = False
   segment = JClass("com.hankcs.hanlp.seg.Other.AhoCorasickDoubleArrayTrieSegment")()
   print(segment.seg("在来到这个世界之前,一起都很井然有序"))

运行之后,效果如下:

python自然语言处理之字典树知识总结

需要注意的是,python的HanLP虽然提供了AhoCorasickDoubleArrayTrieSegment类,但是读者可以试试,替换后运行会报错,控制台会提示该类没有seg函数。而HanLP库又是基于Java开发的,所以在实际的项目中,尽量使用JClass加载Java类进行实战,因为python的HanLP库运行速度比Java慢一倍,但python的好处是相对简单,可以调用其他程序的类,所以速度这方面只要python引用Java类进行调用,其实速度一样。

来源:https://liyuanjinglyj.blog.csdn.net/article/details/114972876

标签:python,字典树,自然语言处理
0
投稿

猜你喜欢

  • js比较日期大小的方法

    2024-04-10 10:49:45
  • Python搭建HTTP服务器和FTP服务器

    2022-05-06 14:21:54
  • python实现用户登录系统

    2023-10-13 13:17:22
  • python的多线程原来可以这样解

    2021-02-22 16:12:18
  • Python的Flask框架中使用Flask-SQLAlchemy管理数据库的教程

    2024-01-21 22:23:32
  • 菜鸟课堂:详述如何提高MySQL中数据装载效率

    2009-10-23 14:29:00
  • Centos7 Python3下安装scrapy的详细步骤

    2021-12-03 10:59:26
  • Python把csv数据写入list和字典类型的变量脚本方法

    2021-05-27 22:04:20
  • Python将8位的图片转为24位的图片实现方法

    2021-07-31 12:11:42
  • 编写Python脚本把sqlAlchemy对象转换成dict的教程

    2023-02-22 07:26:47
  • JDBC-idea导入mysql连接java的jar包(mac)的方法

    2024-01-22 22:51:08
  • Python实现基于POS算法的区块链

    2023-10-30 01:47:19
  • 浅谈Python爬取网页的编码处理

    2021-02-03 19:55:56
  • Django中日期时间型字段进行年月日时分秒分组统计

    2023-01-05 02:26:09
  • python中的数据结构比较

    2023-07-20 10:58:35
  • VSCode 使用Settings Sync同步配置(最新版教程,非常简单)

    2022-10-17 08:50:47
  • 详解Python中的文件操作

    2022-08-26 03:35:18
  • Pycharm 创建 Django admin 用户名和密码的实例

    2021-02-10 01:46:46
  • vue-router之解决addRoutes使用遇到的坑

    2024-04-30 10:19:26
  • php.ini修改php上传文件大小限制的方法详解

    2023-09-11 04:03:12
  • asp之家 网络编程 m.aspxhome.com