Monthly Archives: November 2020

[二]漫话中文分词:Trie前缀树

在上一篇文章当中,说到了一些匹配的算法,但是算法有了,还得需要一个高效的数据结构,不能只是通过[‘中国人’, ‘中东人’]等结构来进行存放,可以想象一下,如果有几十万的词,那么这个列表的占用的内存非常大。

Trie树,也被称为前缀树,该词源自单词retrieval,发音和try相同,Trie树可以为字典分词提供一种高效的分词数据结构,该结构本质上是一种树状数据结构,比如”中国人”、”中东人”三个字符串构造的Trie树为下图,图中能够很清楚的看见,Trie树结构能够很好的节省相同前缀单词所浪费的空间,因为这两个词都是以”中”开头,所以可以使用同一个父辈节点。

1

除此之外,Trie树还对查询的速度有一定的优化,如果以列表存放词来说,如果列表存放的词达到了20万个,那么最坏的情况是你需要匹配的词在存放于最后,那么就相当于要将这20万个词全部遍历,可想而知浪费了非常多的计算资源。

下图为基于同一份10万左右的词典,使用正向最大匹配算法在列表和Trie两种结构上进行分词的运行时间,从下图可以看出来差距非常大。

而Trie树的查找方式则是通过层层查询,而不是直接遍历词典,比如”中国人”,首先会查找第一层中是否有”中”这个字符,如果没有查询到则返回查询失败,如果有则继续查找”中”字符对应的下一层是否有”国”,如果没有则返回查询识别,如果有则继续查找”国”下一层是否有”人”,此时找到存在”人”这个节点,并且该节点标注为蓝色,表明是一个词,所以返回该字符串为一个词。
Continue reading

人工智能基础名词理解

近期在研究相关的自然语言处理,难免会涉及到相关的机器学习等知识,对于非计算机专业的人来说杠开始一脸迷茫,再经过多次的理解和请教后,有了一个大概的认知,这里做一个记录。

人工智能

人工智能是一个比较广泛的概念,这个概念实际上指的是让机器像人一样思考,其最早由计算机科学之父阿兰图灵在1950年的一篇《计算机器与智能》论文中写出“如果电脑能在5分钟能回答由人类测试者提出的一系列的问题,且超过30%回答让测试者误认为人类所答,则电脑通过测试”,这段话也直接启蒙式的开启了人工智能领域的研究。

而“人工智能”一词,第一次出现在1956年,达特茅斯大学召开的学术会议室,由人工智能之父约翰·麦卡锡首次提出。

通常人工智能被分为弱人工智能和强人工智能,前者可以让机器有一定程度的学习、理解和推理能力,后者则是由自适应能力,比如解决一些之前没有遇见过的问题,我们常在电影里看见的机器人就是一种强人工智能。

机器学习

机器学习为人工智能的一个研究分支,也可以理解为弱人工智能的一种实现,而机器学习做的事情是让机器取模拟和实现人类的学习行为,以获得新的技能和知识。

人工智能领域的先驱Arthur Samuel在1959年给出的机器学习定义为“不直接编程,却能赋予计算机提供能力的方法”,而美国工程院院士Tom Mitchell则给出了一个更明确的含义,指出“机器学习是通过某项人物的经验数据提高了在该人物上的能力”。

机器学习最基本的是利用给出的算法来解析数据,从中学习到一定规则(模式)得到经验,并利用学习到的经验对类似的问题作出预测和判断。
Continue reading

[一]漫话中文分词:最大匹配,双向最大,最小词数

中文分词是指将文本拆分为单词的过程,而结果集合连接起来是等于原始的文本,而中文分词一直作为NLP领域的比较重要的领域,而大多数的文本挖掘都是以分词为基础,但中文不同于英文,英文每个单词是用空格分隔,整体语义上相对于中文难度低很多。

而业务上一直有中文分词的需求,但是之前因为在忙于另外一个项目,所以一直没有研究。

近期稍空闲开始研究了相关的中文分词算法,发现中文分词总体算比较成熟,但是其中对于未登录词或者某个特定专业领域文本大部分算法分词的结果不尽人意,需要结合多种算法或者人工词典才能达到稍微好一点的效果。

中文分词的方式一共有两种,分别为:

  1. 词典分词:如正向最大匹配算法、反向最大匹配算法、双向最大匹配算法、最少词数法等
  2. 字标注分词:如HMM(隐马尔可夫)模型等

而这几种方式很难说出谁好谁坏,比如词典分词的方式速度非常快,但对于未登录词的识别又不太好,而HMM和Pkuseg都能识别部分未登录词,但是运行速度又降下来了,这对于在实际应用场景当中是非常致命的问题,所以最大的优解就是集各家所长,比如结巴分词就使用了词典分词算法识别能识别的词,而不能识别的则继续使用了HMM模型来处理。

词典分词

基于词典的分词算法实际上就是对于类似字典的数据结构进行查询,对于未在词典内的词识别较弱和交集型歧义理解能力也较弱,比如“结婚的和尚未结婚的”,理想的情况是”结婚/的/和/尚未/结婚/的”,而实际中则会被分词为”结婚/的/和尚/未/结婚/的”。

但好在词典分词的速度则非常快,词典分词目前已有非常成熟高效的解决方案,并且有非常多的工具来帮你实现相关的高效数据结构和查询方式,比如Trie树AC自动机,但在这里为了方便理解和记录,只采用了尽可能简单的方式来记录其几种算法的实现和原理。
Continue reading

条件概率

最近在了解朴素贝叶斯定理,发现自己对于这块的知识欠缺较多,在阅读一些关于贝叶斯文章的时候整理出来了非常多的名词,其中条件概率最为重要,所以也单独拿出一篇文章来记录。

本人不是相关专业,所以尽可能的查阅相关的资料并以自己能理解的方式进行记录,如有不专业或者问题之处,还请嘴下留情。

样本空间(Ω)

样本空间通常指实验或随机所有可能的集合,我们常在说一个概率的时候,实际上是默认忽略掉了样本空间,比如说事件A的概率,实际上指样本空间中,事件A的数量与样本空间的占比。

比如丢硬币,硬币只有正面和反面,那么硬币的样本空间则为{正面,反面},这个时候常说的正面的概率为二分之一,实际指的是正面事件的数量与样本空间的占比,也就是1/2。

再比如说丢骰子,一个骰子有6种可能,分别对应1-6不同的数值,那么丢骰子的样本空间则为{1,2,3,4,5,6},这个时候丢到5个事件概率则为数字5在样本空间出现的次数与样本空间总数的占比。

独立事件

独立事件是指不受过去已发生的事件而影响的事件,典型的例子就是抛硬币,不管你抛多少次硬币始终正面或反面的概率为0.5,而该硬币的样本空间如下:

独立事件的概率计算公式为如下:

事件发生的概率(P) = 事件在样本空间中的数量 / 样本空间的事件总数

比如用抛硬币的例子,计算正面的概率则为:

而除了单个独立事件,有些时候也会求多个独立事件的概率,而多个独立事件的概率则是每个独立事件发生的概率的积。

比如掷3次骰子都为6的概率是多少?需要注意因为掷骰子是一个独立事件,即每次掷的骰子样本空间都一样,并且没有因为第一次掷骰子的结果会影响到下一次。

骰子的样本空间为下,从中能够得到单次掷骰子为6的概率为1/6:

而这个时候只需要将三次掷骰子的概率相乘就得到了三次都为6的概率:

Continue reading