郭理 張恒旭 王嘉岐 秦懷斌

摘? 要： 由于大量新詞的出現(xiàn)，使得中文文本分析產生了較大的困難，因此新詞發(fā)現(xiàn)成為目前中文自然語言處理中的熱點和難點問題。為此，文中提出了一種基于Trie樹的詞語左右熵和互信息新詞發(fā)現(xiàn)算法。先根據成詞規(guī)則，篩選掉文本中的停用詞和非中文字符，將每個字與其右鄰的字組成二元組;然后利用左右信息熵和互信息進行成詞概率的計算，根據計算到的成詞概率和詞頻篩選出新詞;并且設計了三個實驗，驗證了算法的有效性和可行性。實驗結果表明，該新詞發(fā)現(xiàn)算法成詞準確率較高，比其他新詞發(fā)現(xiàn)算法時間效率有較大的提高，對于中文分詞結果的優(yōu)化起到重要的作用。

關鍵詞： 新詞發(fā)現(xiàn)算法; 左右熵; 互信息; 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? 引? 言

漢語言歷史悠久，文化源遠流長，很多地方有不同的方言，有著不同的書寫習慣，這些方言大多不被包含在已有的詞庫中;另外，隨著互聯(lián)網的發(fā)展，產生了不同于傳統(tǒng)語言的網絡語言，其中包含著大量不存在于詞庫中的詞，但是這些詞卻廣泛存在于互聯(lián)網中，并且常常是熱門話題的關鍵詞。由于中文無法像西方語言那樣使用詞與詞間的分隔符進行分詞，因此在面向中文的自然語言處理中，如何對中文文本進行分詞處理就成為了一個難點。一個比較簡單直接的解決方案是建立一個詞庫來進行中文詞匯的分詞處理。

一般來說，新詞是指隨時代發(fā)展新出現(xiàn)或舊詞新用的詞[1?2]，由于大量新詞的出現(xiàn)，導致了中文文本分詞精度低下，對中文文本分析造成了較大的困難。既有研究結果顯示，60%的分詞錯誤都由新詞導致[2]，因此如何有效地識別新詞并將其添加到已有詞庫中就成為當前中文自然語言處理中的熱點和難點問題之一。

近幾年研究者提出的新詞發(fā)現(xiàn)研究方法大致可分為以下兩類：

1） 基于成詞規(guī)則的新詞發(fā)現(xiàn)方法。通過構詞的原理、詞性和語義構建數學模型，從而對文本中的新詞進行挖掘[3?4]。這種方法具有準確率高、針對性強的特點，但是后期對于成詞規(guī)則的維護非常困難，并且只適用于針對的領域，通用性不強。

2） 基于統(tǒng)計學的新詞發(fā)現(xiàn)算法。通過使用統(tǒng)計模型來對文本中的各種語料信息發(fā)現(xiàn)新詞[2，5]。這種方法具有靈活性高、普適性強的特點，但需要對模型進行大量訓練，準確率較低。

目前，多數研究者多采用兩者相結合的方法進行新詞發(fā)現(xiàn)研究[6?10]：夭榮朋等利用N元遞增算法提取新詞的候選項[6];歐陽柳波等利用相鄰度和反規(guī)則進行新詞發(fā)現(xiàn)研究[7];王馨等利用改進的關聯(lián)規(guī)則算法和互信息得到新詞[8];張華平等建造最大熵模型和二元語法分詞模型[9];葉雪梅等驗證了TF?IDF特征權重算法能有效提高新詞發(fā)現(xiàn)分類器性能[10]。

1? 左右信息熵和互信息

在本文提出的新詞發(fā)現(xiàn)算法中，如果需要發(fā)現(xiàn)一段文本語料中的新詞。首先使用該新詞發(fā)現(xiàn)算法對文本進行中文新詞發(fā)現(xiàn)，再將得到的詞與詞庫進行匹配，將現(xiàn)有詞庫沒有的詞加入到詞庫中。這些后來加入到詞庫中的詞即為算法發(fā)現(xiàn)的新詞，通過將新詞不斷加入到詞庫，新詞發(fā)現(xiàn)數量逐漸減少，這有利于減小后續(xù)的計算負擔。要使用基于零詞庫的新詞發(fā)現(xiàn)算法，在中文分詞過程中，明確成詞標準非常關鍵。本文提出的新詞發(fā)現(xiàn)算法中的左右信息熵和互信息就是用來衡量一個字符片段是否能夠稱之為詞的標準。

1.1? 左右信息熵

熵是一種表示信息量的指標，熵越高就意味著信息含量越大，不確定性越高，越難以預測。左右信息熵是通過計算一個字符片段左邊和右邊的信息熵，通過信息熵的值來反映了一個詞是否有豐富的左右搭配，如果達到一定閾值則可認為兩個片段可以成為一個新詞。以下給出計算信息熵的公式：

假設發(fā)生一件事情的概率有[Pxi]，它們發(fā)生的次數[i]分別為1，2，3。則該事件在平均情況下的信息熵為：

信息熵是用來衡量一個詞的隨機性的標準。[Pxi]在新詞挖掘時就是一個詞出現(xiàn)的概率，用信息熵來衡量一個文本片段的左鄰字集合和右鄰字集合的隨機性。

1.2? 互信息

在信息論相關領域中，互信息（Mutual Information）是指兩個事件集合之間的相關性，是一種有用的信息度量，應用于文本處理中，詞的互信息指兩個詞的相關程度。在傳統(tǒng)的文本中，互信息可以用以下公式來計算：

式中：[ptk，ci]是字符[tk]與字符[ci]組合起來的字符[tkci]在文本中出現(xiàn)的概率;[ptk]是字符[tk]在文本中出現(xiàn)的概率;[pci]是字符[ci]在文本中出現(xiàn)的概率。

2? 基于Trie樹的詞語左右熵和互信息新詞發(fā)現(xiàn)算法

2.1? 算法設計

本文在研究文本數據的新詞發(fā)現(xiàn)過程中，發(fā)現(xiàn)原有的基于詞語左右熵和互信息的新詞發(fā)現(xiàn)算法不太理想，算法在新詞發(fā)現(xiàn)過程中存在錯分、誤分等現(xiàn)象，且由于在文本數據中存在著大量重復的前綴，這導致使用哈希樹結構的新詞發(fā)現(xiàn)算法的時間復雜度非常高。為解決以上兩個問題，本文對基于詞語左右熵和互信息的新詞發(fā)現(xiàn)算法進行了以下改進：

1） 在讀入文本數據之后，對文本中的停用詞加入規(guī)則，進行了相關清理，減少了停用詞對新詞發(fā)現(xiàn)結果造成的影響，使分詞結果有了較大的提升。

2） 使用Trie樹[11]代替哈希樹使算法的時間復雜度從[On2]優(yōu)化到[Onlog n]。

3） 在新詞發(fā)現(xiàn)的最后加入基于詞頻的成詞篩選，通過設置詞頻的閾值，篩選掉數據集中出現(xiàn)較少的詞，使分詞結果有了進一步的提升。

2.2? Trie樹

Trie樹[11]用于存儲鍵值對，存儲的鍵值對中鍵值類型往往是字符串。與二叉搜索樹的區(qū)別是鍵值的存儲位置不同，Trie樹中的鍵值不直接存儲在節(jié)點中，而是根據樹中節(jié)點的位置決定。一個節(jié)點的所有后代都具有一樣的前綴，即與該節(jié)點對應的字符串，且根節(jié)點往往存儲空字符串，因此Trie樹也稱為前綴樹或字典樹。 通常，并非所有節(jié)點都具有對應的值，只有葉節(jié)點和一些內部節(jié)點對應的鍵值具有相關值。Trie樹的具體結構如圖1所示。

2.3? 算法流程

由于對文本數據的新詞發(fā)現(xiàn)是針對中文進行的新詞發(fā)現(xiàn)，所以要先對文本數據進行預處理，去除文本中的所有非中文符號和常用停用詞，將每個字與其右鄰的字組成二元組。建立Trie樹，利用左右信息熵和互信息進行成詞概率的計算，根據計算到的成詞概率和詞頻篩選出新詞。算法流程如圖2所示。

2.4? 算法過程

1） 數據預處理。讀入數據流文本，將數據流文本轉化為字符流文本，轉化結束后，根據成詞規(guī)則過濾掉字符流文本中所有非中文字符和停用詞。文本數據預處理算法如下：

輸入：語料文件位置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表示分詞器分出的詞數。

實驗分別以加入本文的新詞發(fā)現(xiàn)算法后的LTP分詞器、市場上常用的Jieba中文分詞器和SnowNLP中文分詞器對語料進行分詞，得到的實驗結果如表1所示。

表1? 分詞效果對比表? ? ? ? ? ? ? ?%

[分詞器 R P F 加入新詞發(fā)現(xiàn)后的LTP分詞器 91.771 89.746 90.747 SnowNLP分詞器 84.851 80.272 82.498 Jieba分詞器 80.599 80.809 80.704 ]

由表1可以看出，由于本文所使用的LTP分詞器加入了新詞發(fā)現(xiàn)功能，可以從語料中識別出詞典中沒有的新詞并加入到詞典中，從而不斷更新詞典，因此加入新詞發(fā)現(xiàn)后的LTP分詞器的分詞效果要優(yōu)于SnowNLP分詞器和Jieba分詞器的分詞效果。

4? 結? 語

本文對中文文本語料新詞發(fā)現(xiàn)方法進行了研究，提出了一種基于Trie樹的詞語左右熵和互信息新詞發(fā)現(xiàn)算法。該算法先根據成詞規(guī)則，篩選掉文本中的停用詞和非中文字符，將每個字與其右鄰的字組成二元組，通過建立Trie樹索引來提升新詞發(fā)現(xiàn)的效率，然后利用左右信息熵和互信息進行成詞概率的計算，根據計算到的成詞概率和詞頻篩選出新詞。最后設計了三個實驗，取得了理想的結果，實驗結果表明基于Trie樹的詞語左右熵和互信息新詞發(fā)現(xiàn)算法成詞準確率比較高，在時間復雜度上對比其他新詞發(fā)現(xiàn)算法有較大的降低，算法對詞典要求降低，可以較好地在文本中發(fā)掘新詞，并且表明新詞發(fā)現(xiàn)對于中文分詞結果的優(yōu)化能起到非常重要的作用。

參考文獻

[1] 萬琪，于中華，陳黎，等.利用新詞探測提高中文微博的情感表達抽取[J].中國科學技術大學學報，2017（1）：66?72.

[2] 李文坤，張仰森，陳若愚.基于詞內部結合度和邊界自由度的新詞發(fā)現(xiàn)[J].計算機應用研究，2015，32（8）：2302?2304.

[3] 唐亮，席耀一，趙曉峰，等.基于特征相似度的跨語言事件映射[J].計算機應用，2016，36（2）：247?250.

[4] 成于思，施云濤.面向專業(yè)領域的中文分詞方法[J].計算機工程與應用，2018，54（17）：35?39.

[5] 雷一鳴，劉勇，霍華.面向網絡語言基于微博語料的新詞發(fā)現(xiàn)方法[J].計算機工程與設計，2017（3）：789?794.

[6] 夭榮朋，許國艷，宋健.基于改進互信息和鄰接熵的微博新詞發(fā)現(xiàn)方法[J].計算機應用，2016，36（10）：2772?2776.

[7] 歐陽柳波，周偉光.基于位置標簽與詞性結合的組合詞抽取方法[J].計算機應用研究，2016，33（4）：1062?1065.

[8] 王馨，王煜，王亮.基于新詞發(fā)現(xiàn)的網絡新聞熱點排名[J].圖書情報工作，2015（6）：68?74.

[9] 張華平，商建云.面向社會媒體的開放領域新詞發(fā)現(xiàn)[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.