前幾天讀到google研究員吳軍的數學之美系列篇頗有感觸而恰好自己前段時間做了個基於統計語言模型的中文切分系統的課程項目於是乎帖出來與大家共同學習
分詞技術在搜索引擎信息提取機器翻譯等領域的重要地位與應用就不敖述了步入正題）
一 項目概述
本切分系統的統計語料是用我們學校自己開放的那部分大家可以在 這裡 下載中文字符約萬當然這都是已切分好了的可以用此建立一個比較小的語料庫本系統我主要分下面四個步驟完成
語料預處理
建立 gram（統計二元模型）
實現全切分
評估測試
下面我分別對這四個方面一一道來
語料預處理
下載的已切分的語料都是形如/m 現實/n 的/u 頓悟/vn 卻/d 被/p 描/v 出/v 形/Ng 來/v /w 有的前面還保留了日期編號因為這些切分語料的來源是人民日報預處理主要是按標點符號分句句子簡單定義為（ ？！ ）這五種標點符號結尾的詞串句子首尾分別添加<BOS>和<EOS>這兩個表示句子開始和結束的標記這在gram建模時要用的後面會提到處理過程中忽略詞類信息和前面的日期信息因為我這個切分系統不考慮詞類標注如前面這句預處理後應該為下面形式 <BOS>現實 的 頓悟 卻 被 描 出 形 來 <EOS> 當然切分詞之間你可以用你想用的符號標記而不必是空格因為考慮到所有的英文字符和數字的ASCII我用了下面方法實現之
out ; //輸出流
in; //輸入流
StringBuffer s = new StringBuffer(); //緩沖
char a = inread();
while (a != ) //判斷是否已到流的終點
{
if ((a == || a == ？ || a == ！ || a == || a == )) //一句結束
{
String s = new String(s);
outwrite(<BOS>); //在句子前加 <BOS>
outwrite(s);
outwrite(<EOS>); //在句子末尾加 <EOS>
outwrite(/n); //換行
s = new StringBuffer();
}
else if ( a == /)
s = sappend((char)); //分詞位置空格
else if (a > )
s = sappend((char)a);
a = inread();
}
outclose();
inclose();
建立 gram模型（統計二元模型）
在這裡首先簡單介紹一下ngram模型和gram模型
根據語言樣本估計出的概率分布P就稱為語言L的語言模型對給定的句子s = ww…wn（數字ni都為下標wi為句子s的一個詞）由鏈式規則（Chain rule）P(s) = p(w)p(w|w)p(w|ww)……p(wn|www…w(n)) 對p(wi|ww…w(i))而言(ww…w(i))即為wi的歷史考慮前面n個詞構成歷史的模型即為ngram模型 n越大提供的語境信息也越多但代價就越大且需訓練語料多n較小時提供的信息比較少但計算代價小且無需太多訓練語料
令c(w…wi)表示詞串ww…wi在訓練語料中出現的次數則由最大似然估計 P(wn|w…w(n)) = c(w…wn) / c(w…w(n)) 同理則gram為 P(wn|w(n)) = c(w(n)wn) / c(w(n))
若想了解更多相關知識大家找相關資料看看隨便把大學時的那本概率與統計課本拿出來翻翻數學真是一個好東東）
回歸項目） 訓練語料一共有萬多個不同的詞建立gram統計模型時不斷要把每個詞在訓練語料中出現頻率統計出來還要把每個詞及其後面的那個詞組成的gram在訓練語料中出現頻率統計出來因為在切分時會頻繁的在建立的gram模型中查找相關的數據所有存儲這個gram模型數據的數據結構一定要能提供高效的查找故選擇hash表它能提供常數時間的查找Java類庫裡提供了HashMap類基於數據兩還不是非常大故可直接拿來用在存儲時每一個key值對應一個在訓練語料中出現過的詞語而每一個key值對應的value值又是一個HashMap暫且稱為子hashmap這個結構有點類似文件結構裡的二級索引 其相關代碼如下
怎麼在預處理文件裡把詞分別讀出來就不羅嗦了方法每讀入一行按空格分成String數組用個正則表達式匹配下即能得到
//此方法傳入的兩個詞組成一個gramprewd為前一個詞currwd為緊隨其後的詞
public static void add(String prewd String currwd){
String key = prewd;
String curr = currwd;
boolean bb = ntainsKey(key);
//Hmap是一個已存在的HashMap用來存儲gram統計模型在這裡判斷 preword 是否在 主map 中
if (bb == false) { //若 主map 中無則添加
HashMap hm = new HashMap(); //首先新構造一個 子MAP
hmput(key new Integer()); //存儲 主KEY 的頻率
hmput(curr new Integer()); //存儲 主KEY 後面緊接著的那個詞頻率
HMapput(keyhm); //將 主KEY 和對應的 子MAP 放入 主MAP 中
}
else //若 主map 中含有該詞
{
HashMap temp = (HashMap)HMapget(key); //返回 主KEY 所對應的 子MAP 進行值的修改
int count = ((Integer)tempget(key))intValue() + ; //在 子map 中將 主key 次數加
tempput(key new Integer(count));
if (ntainsKey(curr)) //判斷 子map 中是否含有該詞
{
int value = ((Integer)tempget(curr))intValue() + ;
tempput(curr new Integer(value));
}
else
tempput(curr new Integer()); //若無則將其存入子map
HMapput(key temp); //子map 修改完畢 將其重新放入 主map
}
}
}
因為語言中的大部分詞屬於低頻詞所以稀疏問題肯定存在而MLE（最大似然估計）給在訓練語料中沒有出現的gram的賦給概率所以還得對gram模型進行數據平滑以期得到更好的參數目前平滑技術比較多如AddoneAdddeltaWittenBellheldout留存平滑等本系統主要采用了Adddelta和heldout兩中平滑方式下面就Adddelta平滑技術為例對gram進行平滑對gram模型其平滑公式為
P(wn|w(n)) = [c(w(n)wn) + delta ] / ( N + delta * V)
這裡去delta為
其中N訓練語料中所有的gram的數量
V所有的可能的不同的gram的數量
平滑思路 產生主hashmap的迭代器iterator依次讀key;
對每一個key又讀出其value即一個子hashmap;
然後根據平滑公式對子map裡的值進行計算修改
算法框架
Iterator it = 主hashmapkeySet(erator();
While(ithasNext())
{
主key = itnext();
子hashmap = (HashMap)主hashmapget(主key);
Iterator itr = 子hashmapkeySet(erator();
While(itrhasNext())
{
根據平滑公式依次計算修改
}
}
注意問題因為計算得出的概率值一般都比較小為了防止出現下溢可對其取對數再取反
每一個主key所對應的所有沒有出現過的即頻率為零的gram統一用一個鍵值對存儲在相應的子hashmap裡即可
完畢對象序列化使用該系統時lazy load將其載入內存然後可讓其一直存活在內存這會大大加快速度
到此gram模型建立完畢
全切分實現
切詞一般有最大匹配法（MMRMM）基於規則的方法基於統計的方法關於前兩者就不羅嗦了所謂全切分就是要根據字典得到所以可能的切分形式歧義識別的方法主要有基於規則的方法和基於統計的方法這裡當然是采用基於gram統計模型的方法了）為了避免切分後再進行歧義分析的時間浪費並且這裡采用邊切分邊評價的方法即在切分進行的同時進行評價的方法
對一個句子進行全切分的結果即所以可能的組合可以形成一棵解空間樹
於是可用回溯法搜索最優解
若將所有的全切分組合先搜索出來然後再根據gram選擇最佳顯然會很浪費時間因為過程中可能存在很多的重復搜索而回溯搜索的時間復雜度為指數時間
所以在搜索過程中要結合 剪枝避免無效搜索可很大提高效率
采用樹的深度優先法則可找到最優解
具體算法如下
Stackpush(BOS) //樹節點
while stack不為空
x=stackpop()
pos=x．Pos w = xw oldvalue= xvalue preword=xpreword
if m>O then //m為首詞串的個數
forj= to m do
FWj為fwc的第j個元素l
if length(w+FWj) =length(c)且概率最大 then output w+FWjl且設置最新的句子最大概率值
else
posl=pos+length(FWj)l
if probability(w+FWjposlnewsate)>maxValue(pos)
stackpush(x)
endif
endfor
endif
endwhile
end．
在算法實現過程中需要考慮一些諸如樹節點保存
首詞串處理等問題
評估測試
環境windows XP AMD Athlon + Memory mJDK
Delta平滑隨著delta的取值變小准確率上升
召回率
准確率
留存平滑
召回率
准確率
一般情況下
留存平滑應該還是比delta平滑更好
所有建模過程及平滑過程在分鐘內都可完成
切分時間與效率
n 測試語料字符 （中文）平均句長 個字時間 ms 平均切分速度 萬/S
n 萬測試語料（取自笑傲江湖） 預處理後 萬 時間 MS句子文本行數目 平均句長 切分時間 MS 平均 萬 / 秒
n 萬測試語料（取自笑傲江湖）不預處理平均句長 切分時間S 平均 字/秒
回溯算法是時間開銷為O(N!)所以在切分過程中句子長度直接決定了切分的速度因為句子越長詞越多
經過預處理句子短平均句長 回溯短故速度要快很多
到此該系統基本完成告一段落感覺寫的挺亂的呵呵
現在在做另一個作業做個簡單搜索引擎准備把這個東東結合在搜索引擎裡面實現切分功能
From:http://tw.wingwit.com/Article/program/Java/hx/201311/25784.html
