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

郭理 張恒旭 王嘉岐 秦懷斌

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

關(guān)鍵詞： 新詞發(fā)現(xiàn)算法; 左右熵; 互信息; Trie樹(shù); 算法設(shè)計(jì); 對(duì)比驗(yàn)證

中圖分類號(hào)： TN911?34; TP391.1? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼： A? ? ? ? ? ? ? ? ? ? ?文章編號(hào)： 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? 引? 言

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

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

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

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

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

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

1? 左右信息熵和互信息

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

1.1? 左右信息熵

熵是一種表示信息量的指標(biāo)，熵越高就意味著信息含量越大，不確定性越高，越難以預(yù)測(cè)。左右信息熵是通過(guò)計(jì)算一個(gè)字符片段左邊和右邊的信息熵，通過(guò)信息熵的值來(lái)反映了一個(gè)詞是否有豐富的左右搭配，如果達(dá)到一定閾值則可認(rèn)為兩個(gè)片段可以成為一個(gè)新詞。以下給出計(jì)算信息熵的公式：

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

信息熵是用來(lái)衡量一個(gè)詞的隨機(jī)性的標(biāo)準(zhǔn)。[Pxi]在新詞挖掘時(shí)就是一個(gè)詞出現(xiàn)的概率，用信息熵來(lái)衡量一個(gè)文本片段的左鄰字集合和右鄰字集合的隨機(jī)性。

1.2? 互信息

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

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

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

2.1? 算法設(shè)計(jì)

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

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

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

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

2.2? Trie樹(shù)

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

2.3? 算法流程

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

2.4? 算法過(guò)程

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

輸入：語(yǔ)料文件位置dataPath

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

1.orginText= new String（Files.readAllBytes（Paths.get（dataPath）））;? ? ? ? ? ? ? //讀入數(shù)據(jù)流文本并轉(zhuǎn)化為字符流文本

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

//去除所有非中文字符

3.stopword = readFile（"stopword.dict"）;? ? ? ? ? //讀取停用詞

4.for （eachStopword ：stopword） {

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

3.3? 與其他分詞器效果對(duì)比實(shí)驗(yàn)

實(shí)驗(yàn)使用SIGHAN Backoff2（2005）中微軟亞洲研究院提供的 MSR 公開(kāi)中文簡(jiǎn)體數(shù)據(jù)集，采用普遍使用的召回率（R） 、正確率（P）和F值來(lái)評(píng)價(jià)分詞效果，定義如下：

[R=CNN×100%]

[P=CNM×100%]

[F=2PRP+R×100%]

式中： CN表示算法正確識(shí)別出的詞數(shù);N表示實(shí)際的詞數(shù);M表示分詞器分出的詞數(shù)。

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

表1? 分詞效果對(duì)比表? ? ? ? ? ? ? ?%

[分詞器 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)功能，可以從語(yǔ)料中識(shí)別出詞典中沒(méi)有的新詞并加入到詞典中，從而不斷更新詞典，因此加入新詞發(fā)現(xiàn)后的LTP分詞器的分詞效果要優(yōu)于SnowNLP分詞器和Jieba分詞器的分詞效果。

4? 結(jié)? 語(yǔ)

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

參考文獻(xiàn)

[1] 萬(wàn)琪，于中華，陳黎，等.利用新詞探測(cè)提高中文微博的情感表達(dá)抽取[J].中國(guó)科學(xué)技術(shù)大學(xué)學(xué)報(bào)，2017（1）：66?72.

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

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

[4] 成于思，施云濤.面向?qū)I(yè)領(lǐng)域的中文分詞方法[J].計(jì)算機(jī)工程與應(yīng)用，2018，54（17）：35?39.

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

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

[7] 歐陽(yáng)柳波，周偉光.基于位置標(biāo)簽與詞性結(jié)合的組合詞抽取方法[J].計(jì)算機(jī)應(yīng)用研究，2016，33（4）：1062?1065.

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

[9] 張華平，商建云.面向社會(huì)媒體的開(kāi)放領(lǐng)域新詞發(fā)現(xiàn)[J].中文信息學(xué)報(bào)，2017，31（3）：55?61.

[10] 葉雪梅，毛雪岷，夏錦春，等.文本分類TF?IDF算法的改進(jìn)研究[J].計(jì)算機(jī)工程與應(yīng)用，2019，55（2）：110?115.

[11] 孫凈.基于Trie樹(shù)的數(shù)學(xué)表達(dá)式運(yùn)算結(jié)構(gòu)檢索[D].保定：河北大學(xué)，2015.

[12] 李清敏，張華平.面向話題的中文微博觀點(diǎn)傾向性分析研究[J].科學(xué)技術(shù)與工程，2014，14（12）：227?231.

[13] 胡小榮，姚長(zhǎng)青，高影繁.基于風(fēng)險(xiǎn)短語(yǔ)自動(dòng)抽取的上市公司風(fēng)險(xiǎn)識(shí)別方法及可視化研究[J].情報(bào)學(xué)報(bào)，2017（7）：663?668.

[14] 龔雙雙，陳鈺楓，徐金安，等.基于網(wǎng)絡(luò)文本的漢語(yǔ)多詞表達(dá)抽取方法[J].山東大學(xué)學(xué)報(bào)（理學(xué)版），2018（9）：40?48.