基于Trie树的词语左右熵和互信息新词发现算法

郭理 张恒旭 王嘉岐 秦怀斌

摘  要： 由于大量新词的出现，使得中文文本分析产生了较大的困难，因此新词发现成为目前中文自然语言处理中的热点和难点问题。为此，文中提出了一种基于Trie树的词语左右熵和互信息新词发现算法。先根据成词规则，筛选掉文本中的停用词和非中文字符，将每个字与其右邻的字组成二元组;然后利用左右信息熵和互信息进行成词概率的计算，根据计算到的成词概率和词频筛选出新词;并且设计了三个实验，验证了算法的有效性和可行性。实验结果表明，该新词发现算法成词准确率较高，比其他新词发现算法时间效率有较大的提高，对于中文分词结果的优化起到重要的作用。

关键词： 新词发现算法; 左右熵; 互信息; Trie树; 算法设计; 对比验证

中图分类号： TN911?34; TP391.1                 文献标识码： A                     文章编号： 1004?373X（2020）06?0065?05

Trie tree based new word discovery algorithm using left?right entropy and

mutual information

GUO Li， ZHANG Hengxu， WANG Jiaqi， QIN Huaibin

（College of Information Science and Technology， Shihezi University， Shihezi 832000， China）

Abstract： The emergence of multitude of new words makes Chinese discourse analysis difficult. Therefore， the discovery of new words has become a hot and difficult problem in natural language processing of Chinese. A Trie tree based new word discovery algorithm using left?right entropy and mutual information is proposed. The disused words and non Chinese characters in the text are filtered out according to the rules of word?formation. Each word is divided into a binary group with its right neighbor， and then the probability of word?formation is calculated by means of left?right information entropy and mutual information， so as to screen out new words according to the calculated probability of word?formation and word frequency. Three experiments were designed to verify the effectiveness and feasibility of the algorithm. The experimental results show that the new word discovery algorithm has higher accuracy of word?formation， and has higher time efficiency than other new word discovery algorithms， which plays an important role in the optimization of Chinese word segmentation results.

Keywords： new word discovery algorithm; left?right entropy; mutual information; Trie tree; algorithm design; comparison validation

0  引  言

汉语言历史悠久，文化源远流长，很多地方有不同的方言，有着不同的书写习惯，这些方言大多不被包含在已有的词库中;另外，随着互联网的发展，产生了不同于传统语言的网络语言，其中包含着大量不存在于词库中的词，但是这些词却广泛存在于互联网中，并且常常是热门话题的关键词。由于中文无法像西方语言那样使用词与词间的分隔符进行分词，因此在面向中文的自然语言处理中，如何对中文文本进行分词处理就成为了一个难点。一个比较简单直接的解决方案是建立一个词库来进行中文词汇的分词处理。

一般来说，新词是指随时代发展新出现或旧词新用的词[1?2]，由于大量新词的出现，导致了中文文本分词精度低下，对中文文本分析造成了较大的困难。既有研究结果显示，60%的分词错误都由新词导致[2]，因此如何有效地识别新词并将其添加到已有词库中就成为当前中文自然语言处理中的热点和难点问题之一。

近几年研究者提出的新词发现研究方法大致可分为以下两类：

1） 基于成词规则的新词发现方法。通过构词的原理、词性和语义构建数学模型，从而对文本中的新词进行挖掘[3?4]。这种方法具有准确率高、针对性强的特点，但是后期对于成词规则的维护非常困难，并且只适用于针对的领域，通用性不强。

2） 基于统计学的新词发现算法。通过使用统计模型来对文本中的各种语料信息发现新词[2，5]。这种方法具有灵活性高、普适性强的特点，但需要对模型进行大量训练，准确率较低。

目前，多数研究者多采用两者相结合的方法进行新词发现研究[6?10]：夭荣朋等利用N元递增算法提取新词的候选项[6];欧阳柳波等利用相邻度和反规则进行新词发现研究[7];王馨等利用改进的关联规则算法和互信息得到新词[8];张华平等建造最大熵模型和二元语法分词模型[9];叶雪梅等验证了TF?IDF特征权重算法能有效提高新词发现分类器性能[10]。

1  左右信息熵和互信息

在本文提出的新词发现算法中，如果需要发现一段文本语料中的新词。首先使用该新词发现算法对文本进行中文新词发现，再将得到的词与词库进行匹配，将现有词库没有的词加入到词库中。这些后来加入到词库中的词即为算法发现的新词，通过将新词不断加入到词库，新词发现数量逐渐减少，这有利于减小后续的计算负担。要使用基于零词库的新词发现算法，在中文分词过程中，明确成词标准非常关键。本文提出的新词发现算法中的左右信息熵和互信息就是用来衡量一个字符片段是否能够称之为词的标准。

1.1  左右信息熵

熵是一种表示信息量的指标，熵越高就意味着信息含量越大，不确定性越高，越难以预测。左右信息熵是通过计算一个字符片段左边和右边的信息熵，通过信息熵的值来反映了一个词是否有丰富的左右搭配，如果达到一定阈值则可认为两个片段可以成为一个新词。以下给出计算信息熵的公式：

假设发生一件事情的概率有[Pxi]，它们发生的次数[i]分别为1，2，3。则该事件在平均情况下的信息熵为：

信息熵是用来衡量一个词的随机性的标准。[Pxi]在新词挖掘时就是一个词出现的概率，用信息熵来衡量一个文本片段的左邻字集合和右邻字集合的随机性。

1.2  互信息

在信息论相关领域中，互信息（Mutual Information）是指两个事件集合之间的相关性，是一种有用的信息度量，应用于文本处理中，词的互信息指两个词的相关程度。在传统的文本中，互信息可以用以下公式来计算：

式中：[ptk，ci]是字符[tk]與字符[ci]组合起来的字符[tkci]在文本中出现的概率;[ptk]是字符[tk]在文本中出现的概率;[pci]是字符[ci]在文本中出现的概率。

2  基于Trie树的词语左右熵和互信息新词发现算法

2.1  算法设计

本文在研究文本数据的新词发现过程中，发现原有的基于词语左右熵和互信息的新词发现算法不太理想，算法在新词发现过程中存在错分、误分等现象，且由于在文本数据中存在着大量重复的前缀，这导致使用哈希树结构的新词发现算法的时间复杂度非常高。为解决以上两个问题，本文对基于词语左右熵和互信息的新词发现算法进行了以下改进：

1） 在读入文本数据之后，对文本中的停用词加入规则，进行了相关清理，减少了停用词对新词发现结果造成的影响，使分词结果有了较大的提升。

2） 使用Trie树[11]代替哈希树使算法的时间复杂度从[On2]优化到[Onlog n]。

3） 在新词发现的最后加入基于词频的成词筛选，通过设置词频的阈值，筛选掉数据集中出现较少的词，使分词结果有了进一步的提升。

2.2  Trie树

Trie树[11]用于存储键值对，存储的键值对中键值类型往往是字符串。与二叉搜索树的区别是键值的存储位置不同，Trie树中的键值不直接存储在节点中，而是根据树中节点的位置决定。一个节点的所有后代都具有一样的前缀，即与该节点对应的字符串，且根节点往往存储空字符串，因此Trie树也称为前缀树或字典树。 通常，并非所有节点都具有对应的值，只有叶节点和一些内部节点对应的键值具有相关值。Trie树的具体结构如图1所示。

2.3  算法流程

由于对文本数据的新词发现是针对中文进行的新词发现，所以要先对文本数据进行预处理，去除文本中的所有非中文符号和常用停用词，将每个字与其右邻的字组成二元组。建立Trie树，利用左右信息熵和互信息进行成词概率的计算，根据计算到的成词概率和词频筛选出新词。算法流程如图2所示。

2.4  算法过程

1） 数据预处理。读入数据流文本，将数据流文本转化为字符流文本，转化结束后，根据成词规则过滤掉字符流文本中所有非中文字符和停用词。文本数据预处理算法如下：

输入：语料文件位置dataPath

输出：去除非中文字符和停用词之后的字符流文本text

1.orginText= new String（Files.readAllBytes（Paths.get（dataPath）））;              //读入数据流文本并转化为字符流文本

2.text= orginText.replaceAll（"[^＼＼u4E00?＼＼u9FA5]+"， ""）;

//去除所有非中文字符

3.stopword = readFile（"stopword.dict"）;          //读取停用词

4.for （eachStopword ：stopword） {

5.text = text.replaceAll（eachStopword， ""）;     //去除停用词

3.3  与其他分词器效果对比实验

实验使用SIGHAN Backoff2（2005）中微软亚洲研究院提供的 MSR 公开中文简体数据集，采用普遍使用的召回率（R） 、正确率（P）和F值来评价分词效果，定义如下：

[R=CNN×100%]

[P=CNM×100%]

[F=2PRP+R×100%]

式中： CN表示算法正确识别出的词数;N表示实际的词数;M表示分词器分出的词数。

实验分别以加入本文的新词发现算法后的LTP分词器、市场上常用的Jieba中文分词器和SnowNLP中文分词器对语料进行分词，得到的实验结果如表1所示。

表1  分词效果对比表               %

[分词器 R P F 加入新词发现后的LTP分词器 91.771 89.746 90.747 SnowNLP分詞器 84.851 80.272 82.498 Jieba分词器 80.599 80.809 80.704 ]

由表1可以看出，由于本文所使用的LTP分词器加入了新词发现功能，可以从语料中识别出词典中没有的新词并加入到词典中，从而不断更新词典，因此加入新词发现后的LTP分词器的分词效果要优于SnowNLP分词器和Jieba分词器的分词效果。

4  结  语

本文对中文文本语料新词发现方法进行了研究，提出了一种基于Trie树的词语左右熵和互信息新词发现算法。该算法先根据成词规则，筛选掉文本中的停用词和非中文字符，将每个字与其右邻的字组成二元组，通过建立Trie树索引来提升新词发现的效率，然后利用左右信息熵和互信息进行成词概率的计算，根据计算到的成词概率和词频筛选出新词。最后设计了三个实验，取得了理想的结果，实验结果表明基于Trie树的词语左右熵和互信息新词发现算法成词准确率比较高，在时间复杂度上对比其他新词发现算法有较大的降低，算法对词典要求降低，可以较好地在文本中发掘新词，并且表明新词发现对于中文分词结果的优化能起到非常重要的作用。

参考文献

[1] 万琪，于中华，陈黎，等.利用新词探测提高中文微博的情感表达抽取[J].中国科学技术大学学报，2017（1）：66?72.

[2] 李文坤，张仰森，陈若愚.基于词内部结合度和边界自由度的新词发现[J].计算机应用研究，2015，32（8）：2302?2304.

[3] 唐亮，席耀一，赵晓峰，等.基于特征相似度的跨语言事件映射[J].计算机应用，2016，36（2）：247?250.

[4] 成于思，施云涛.面向专业领域的中文分词方法[J].计算机工程与应用，2018，54（17）：35?39.

[5] 雷一鸣，刘勇，霍华.面向网络语言基于微博语料的新词发现方法[J].计算机工程与设计，2017（3）：789?794.

[6] 夭荣朋，许国艳，宋健.基于改进互信息和邻接熵的微博新词发现方法[J].计算机应用，2016，36（10）：2772?2776.

[7] 欧阳柳波，周伟光.基于位置标签与词性结合的组合词抽取方法[J].计算机应用研究，2016，33（4）：1062?1065.

[8] 王馨，王煜，王亮.基于新词发现的网络新闻热点排名[J].图书情报工作，2015（6）：68?74.

[9] 张华平，商建云.面向社会媒体的开放领域新词发现[J].中文信息学报，2017，31（3）：55?61.

[10] 叶雪梅，毛雪岷，夏锦春，等.文本分类TF?IDF算法的改进研究[J].计算机工程与应用，2019，55（2）：110?115.

[11] 孙净.基于Trie树的数学表达式运算结构检索[D].保定：河北大学，2015.

[12] 李清敏，张华平.面向话题的中文微博观点倾向性分析研究[J].科学技术与工程，2014，14（12）：227?231.

[13] 胡小荣，姚长青，高影繁.基于风险短语自动抽取的上市公司风险识别方法及可视化研究[J].情报学报，2017（7）：663?668.

[14] 龚双双，陈钰枫，徐金安，等.基于网络文本的汉语多词表达抽取方法[J].山东大学学报（理学版），2018（9）：40?48.