2019獨(dú)角獸企業(yè)重金招聘Python工程師標(biāo)準(zhǔn)>>>

本文分析：HanLP版本1.5.3中二元核心詞典的存儲(chǔ)與查找。當(dāng)詞典文件沒(méi)有被緩存時(shí)，會(huì)從文本文件CoreNatureDictionary.ngram.txt中解析出來(lái)存儲(chǔ)到TreeMap中，然后構(gòu)造start和pair數(shù)組，并基于這兩個(gè)數(shù)組實(shí)現(xiàn)詞共現(xiàn)頻率的二分查找。當(dāng)已經(jīng)有緩存bin文件時(shí)，那直接讀取構(gòu)建start和pair數(shù)組，速度超快。

源碼實(shí)現(xiàn)

二元核心詞典的加載

二元核心詞典在文件：CoreNatureDictionary.ngram.txt，約有46.3 MB。程序啟動(dòng)時(shí)先嘗試加載CoreNatureDictionary.ngram.txt.table.bin 緩存文件，大約22.9 MB。這個(gè)緩存文件是序列化保存起來(lái)的。

?ObjectInputStream in = new ObjectInputStream(IOUtil.newInputStream(path));

?start = (int[]) in.readObject();

?pair = (int[]) in.readObject();

當(dāng)緩存文件不存在時(shí)，拋出異常：警告: 嘗試載入緩存文件E:/idea/hanlp/HanLP/data/dictionary/CoreNatureDictionary.ngram.txt.table.bin發(fā)生異常[java.io.FileNotFoundException: 然后解析CoreNatureDictionary.ngram.txt

?

br = new BufferedReader(new InputStreamReader(IOUtil.newInputStream(path), "UTF-8"));

while ((line = br.readLine()) != null){

????String[] params = line.split("\\s");

????String[] twoWord = params[0].split("@", 2);

????...

}

然后，使用一個(gè)TreeMap<Integer, TreeMap<Integer, Integer>> map來(lái)保存解析的每一行二元核心詞典條目。

?

TreeMap<Integer, TreeMap<Integer, Integer>> map = new TreeMap<Integer, TreeMap<Integer, Integer>>();

?

int idA = CoreDictionary.trie.exactMatchSearch(a);//二元接續(xù)的 @ 前的內(nèi)容

int idB = CoreDictionary.trie.exactMatchSearch(b);//@ 后的內(nèi)容

?

TreeMap<Integer, Integer> biMap = map.get(idA);

if (biMap == null){

????biMap = new TreeMap<Integer, Integer>();

????map.put(idA, biMap);//

}

biMap.put(idB, freq);

比如二元接續(xù)：“一 一@中”，@ 前的內(nèi)容是：“一 一”，@后的內(nèi)容是 “中”。由于同一個(gè)前綴可以有多個(gè)后續(xù)，比如：

?

一一@中 1

一一@為 6

一一@交談 1

所有以 '一 一' 開(kāi)頭的 @ 后的后綴 以及對(duì)應(yīng)的頻率 都保存到 相應(yīng)的biMap中：biMap.put(idB, freq);。注意：biMap和map是不同的，map保存整個(gè)二元核心詞典，而biMap保存某個(gè)詞對(duì)應(yīng)的所有后綴(這個(gè)詞 @ 后的所有條目)

?

map中保存二元核心詞典示意圖如下：

二元核心詞典主要由CoreBiGramTableDictionary.java 實(shí)現(xiàn)。這個(gè)類中有兩個(gè)整型數(shù)組 支撐 二元核心詞典的快速二分查找。

?

????/**

?????* 描述了詞在pair中的范圍，具體說(shuō)來(lái)<br>

?????* 給定一個(gè)詞idA，從pair[start[idA]]開(kāi)始的start[idA + 1] - start[idA]描述了一些接續(xù)的頻次

?????*/

????static int start[];//支持快速地二分查找

????/**

?????* pair[偶數(shù)n]表示key，pair[n+1]表示frequency

?????*/

????static int pair[];

start 數(shù)組

首先初始化一個(gè)與一元核心詞典Trie樹(shù) size 一樣大小 的start 數(shù)組：

?

int maxWordId = CoreDictionary.trie.size();

...

start = new int[maxWordId + 1];

然后，遍歷一元核心詞典中的詞，尋找這些詞是 是否有二階共現(xiàn)（或者說(shuō)：這些詞是否存在 二元接續(xù)）

?

for (int i = 0; i < maxWordId; ++i){

????TreeMap<Integer, Integer> bMap = map.get(i);

????if (bMap != null){

????????for (Map.Entry<Integer, Integer> entry : bMap.entrySet()){

????????????//省略其他代碼

????????????++offset;//統(tǒng)計(jì)以 這個(gè)詞 為前綴的所有二階共現(xiàn)的個(gè)數(shù)

????????}

????}//end if

????start[i + 1] = offset;

}// end outer for loop

if (bMap != null)表示 第 i 個(gè)詞(i從下標(biāo)0開(kāi)始)在二元詞典中有二階共現(xiàn)，于是 統(tǒng)計(jì)以 這個(gè)詞 為前綴的所有二階共現(xiàn)的個(gè)數(shù)，將之保存到 start 數(shù)組中。下面來(lái)具體舉例，start數(shù)組中前37個(gè)詞的值如下：

其中start[32]=0，start[33]=0，相應(yīng)的 一元核心詞典中的詞為 （ ）。即，一個(gè)左括號(hào)、一個(gè)右括號(hào)。而這個(gè) 左括號(hào) 和 右括號(hào) 在二元核心詞典中是不存在詞共現(xiàn)的(接續(xù))。也就是說(shuō)在二元核心詞典中 沒(méi)有 （@xxx這樣的條目，也沒(méi)有 )@xxx 這個(gè)條目(xxx 表示任意以 ( 或者 ) 為前綴 的后綴接續(xù))。因此，這也是start[32] 和 start[33]=0 都等于0的原因。

?

部分詞的一元核心詞典如下：

?

再來(lái)看 start[34]=22，start[35]=23。在一元核心詞典中，第34個(gè)詞是"一 一"，而在二元核心詞典中 '一 一'的詞共現(xiàn)共有22個(gè)，如下：

?

?

在一元核心詞典中，第35個(gè)詞是 "一 一列舉"，如上圖所示，"一 一列舉" 在二元核心中只有一個(gè)詞共現(xiàn)：“一 一列舉@芒果臺(tái)”。因此，start[35]=22+1=23。從這里也可以看出：

給定一個(gè)詞idA，從pair[start[idA]]開(kāi)始的start[idA + 1] - start[idA]描述了一些接續(xù)的頻次

比如，idA=35，對(duì)應(yīng)詞“一 一列舉”，它的接續(xù)頻次為1，即：23-22=1

這樣做的好處是什么呢？自問(wèn)自答一下：^~^，就是大大減少了二分查找的范圍。

pair 數(shù)組

pair數(shù)組的長(zhǎng)度是二元核心詞典行數(shù)的兩倍

?

int total = 0;

while ((line = br.readLine()) != null){

????//省略其他代碼

????total += 2;

}

pair數(shù)組 偶數(shù) 下標(biāo) 存儲(chǔ) 保存的是 一元核心詞典中的詞 的下標(biāo)，而對(duì)應(yīng)的偶數(shù)加1 處的下標(biāo) 存儲(chǔ) 這個(gè)詞的共現(xiàn)頻率。即： pair[偶數(shù)n]表示key，pair[n+1]表示frequency

?

????????????pair = new int[total]; ?// total是接續(xù)的個(gè)數(shù)*2

?

????????????for (int i = 0; i < maxWordId; ++i)

????????????{

????????????????TreeMap<Integer, Integer> bMap = map.get(i);//i==0?

????????????????if (bMap != null)//某個(gè)詞在一元核心詞典中, 但是并沒(méi)有出現(xiàn)在二元核心詞典中(這個(gè)詞沒(méi)有二元核心詞共現(xiàn))

????????????????{

????????????????????for (Map.Entry<Integer, Integer> entry : bMap.entrySet())

????????????????????{

????????????????????????int index = offset << 1;

????????????????????????pair[index] = entry.getKey();//詞 在一元核心詞典中的id

????????????????????????pair[index + 1] = entry.getValue();//頻率

????????????????????}

????????????????}

????????????}

舉例來(lái)說(shuō)：對(duì)于 '一 一@中'，pair數(shù)組是如何保存這對(duì)詞的詞共現(xiàn)頻率的呢？

'一 一'在 map 中第0號(hào)位置處，它是一元核心詞典中的第34個(gè)詞。?共有22個(gè)共現(xiàn)詞。如下：

其中，第一個(gè)共現(xiàn)詞是 '一 一 @中'，就是'一 一'與 '中' 共同出現(xiàn)，出現(xiàn)的頻率為1。而 ''中'' 在一元核心詞典中的 4124行，如下圖所示：

?

因此，'一 一@中'的pair數(shù)組存儲(chǔ)如下：

?

0=4123 （‘中’在一元核心詞典中的位置（從下標(biāo)0開(kāi)始計(jì)算））

?

1=1 （'一 一@中'的詞共現(xiàn)頻率）

?

2=5106 （'為' 在一元核心詞典中的位置） 【為 p 65723】

?

3=6 ('一 一@為'的詞共現(xiàn)頻率)

?

由此可知，對(duì)于二元核心詞典共現(xiàn)詞而言，共同前綴的后續(xù)詞 在 pair數(shù)組中是順序存儲(chǔ)的，比如說(shuō)：前綴'一 一'的所有后綴：中、為、交談……按順序依次在 pair 數(shù)組中存儲(chǔ)。而這也是能夠?qū)?pair 數(shù)組進(jìn)行二分查找的基礎(chǔ)。

?

一 一@中 1

一 一@為 6

一 一@交談 1

一 一@介紹 1

一 一@作 1

一 一@分析

?

.......//省略其他

?

二分查找

現(xiàn)在來(lái)看看 二分查找是干什么用的？為什么減少了二分查找的范圍。為了獲取某 兩個(gè)詞（idA 和 idB） 的詞共現(xiàn)頻率，需要進(jìn)行二分查找：

?

public static int getBiFrequency(int idA, int idB){

????//省略其他代碼

????int index = binarySearch(pair, start[idA], start[idA + 1] - start[idA], idB);

????return pair[index + 1];

}

根據(jù)前面介紹，start[idA + 1] - start[idA]就是以 idA 為前綴的 所有詞的 詞共現(xiàn)頻率。比如，以 '一 一' 為前綴的詞一共有22個(gè)，假設(shè)我要查找 '一 一@向' 的詞共現(xiàn)頻率是多少？在核心二元詞典文件CoreNatureDictionary.ngram.txt中，我們知道 '一 一@向' 的詞共現(xiàn)頻率為2，但是：如何用程序快速地實(shí)現(xiàn)查找呢？

?

二元核心詞典的總個(gè)數(shù)還是很多的，比如在HanLP1.5.3大約有290萬(wàn)個(gè)二元核心詞條，如果每查詢一次 idA@idB 的詞共現(xiàn)頻率就要從290萬(wàn)個(gè)詞條里面查詢，顯然效率很低。若先定位出 所有以 idA 為前綴的共現(xiàn)詞：idA@xx1，idA@xx2，idA@xx3……，然后再?gòu)膹倪@些 以idA為前綴的共現(xiàn)詞中進(jìn)行二分查找，來(lái)查找 idA@idB，這樣查找的效率就快了許多。

?

而start 數(shù)組保存了一元詞典中每個(gè)詞 在二元詞典中的詞共現(xiàn)情況： start[idA] 代表 idA在 pair 數(shù)組中共現(xiàn)詞的起始位置，而start[idA + 1] - start[idA]代表 以idA 為前綴的共現(xiàn)詞一共有多少個(gè)，這樣二分查找的范圍就只在 start[idA] 和 start[idA] + (start[idA + 1] - start[idA]) - 1之間了。

?

????private static int binarySearch(int[] a, int fromIndex, int length, int key)

????{

????????int low = fromIndex;

????????int high = fromIndex + length - 1;

????????//省略其他代碼

說(shuō)到這里，再多說(shuō)一點(diǎn)：二元核心詞典的二分查找 是為了獲取 idA@idB 的詞共現(xiàn)頻率，而這個(gè)詞共現(xiàn)頻率的用處之一就是最短路徑分詞算法(維特比分詞)，用來(lái)計(jì)算最短路徑的權(quán)重。關(guān)于最短路徑分詞，可參考這篇解析：

?

//只列出關(guān)鍵代碼

List<Vertex> vertexList = viterbi(wordNetAll);//求解詞網(wǎng)的最短路徑

to.updateFrom(node);//更新權(quán)重

double weight = from.weight + MathTools.calculateWeight(from, this);//計(jì)算兩個(gè)頂點(diǎn)(idA->idB)的權(quán)重

int nTwoWordsFreq = CoreBiGramTableDictionary.getBiFrequency(from.wordID, to.wordID);//查核心二元詞典

int index = binarySearch(pair, start[idA], start[idA + 1] - start[idA], idB);//二分查找 idA@idB共現(xiàn)頻率

總結(jié)

有時(shí)候由于特定項(xiàng)目需要，需要修改核心詞典。比如添加一個(gè)新的二元詞共現(xiàn)詞條 到 二元核心詞典中去，這時(shí)就需要注意：添加的新詞條需要存在于一元核心詞典中，否則添加無(wú)效。另外，添加到CoreNatureDictionary.ngram.txt里面的二元共現(xiàn)詞的位置不太重要，因?yàn)橄嗤那熬Y 共現(xiàn)詞 都會(huì)保存到 同一個(gè)TreeMap中，但是最好也是連續(xù)放在一起，這樣二元核心詞典就不會(huì)太混亂。

?

文章來(lái)源 hapjin的博客

轉(zhuǎn)載于:https://my.oschina.net/u/3793864/blog/2966681

總結(jié)

以上是生活随笔為你收集整理的HanLP二元核心词典详细解析的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。