分詞技術在搜索引擎，信息提取，機器翻譯等領域的重要地位與應用就不敖述了。步入正題：）
<!--[if !supportLists]-->壹、 <!--[endif]-->項目概述
本切分系統的統計語料是用我們學校自己開放的那部分，大家可以在 這裏 下載，中文字符約184萬，當然這都是已切分好了的，可以用此建立壹個比較小的語料庫。本系統我主要分下面四個步驟完成：
<!--[if !supportLists]-->1、 <!--[endif]-->語料預處理
<!--[if !supportLists]-->2、 <!--[endif]-->建立 2-gram（統計二元模型）
<!--[if !supportLists]-->3、 <!--[endif]-->實現全切分
<!--[if !supportLists]-->4、 <!--[endif]-->評估測試
下面我分別對這四個方面壹壹道來。
<!--[if !supportLists]-->1、 <!--[endif]-->語料預處理
下載的已切分的語料都是形如“19980131-04-012-001/m 現實/n 的/u 頓悟/vn 卻/d 被/p 描/v 出/v 形/Ng 來/v 。/w ” ，有的前面還保留了日期編號，因為這些切分語料的來源是人民日報。預處理主要是按標點符號分句，句子簡單定義為（ 。？！ ： ；）這五種標點符號結尾的詞串，句子首尾分別添加<BOS>和<EOS>這兩個表示句子開始和結束的標記，這在2-gram建模時要用的，後面會提到。處理過程中，忽略詞類信息和前面的日期信息，因為我這個切分系統不考慮詞類標註。如前面這句預處理後應該為下面形式 “<BOS>現實 的 頓悟 卻 被 描 出 形 來 。<EOS>” ，當然切分詞之間妳可以用妳想用的符號標記，而不必是空格。因為考慮到所有的英文字符和數字的ASCII，我用了下面方法實現之：
out ; //輸出流
in; //輸入流
StringBuffer s1 = new StringBuffer(); //緩沖
char a = in.read();
while (a != -1) //判斷是否已到流的終點
{
if ((a == '。' || a == '？' || a == '！' || a == '：' || a == '；' )) //壹句結束
{
String s2 = new String(s1);
out.write("<BOS>"); //在句子前加 <BOS>
out.write(s2);
out.write("<EOS>"); //在句子末尾加 <EOS>
out.write('/n'); //換行
s1 = new StringBuffer();
}
else if ( a == '/')
s1 = s1.append((char)32); //分詞位置空格
else if (a > 256 )
s1 = s1.append((char)a);
a = in.read();
}
out.close();
in.close();
<!--[if !supportLists]-->2、 <!--[endif]-->建立 2-gram模型（統計二元模型）
在這裏首先簡單介紹壹下n-gram模型和2-gram模型。
根據語言樣本估計出的概率分布P就稱為語言L的語言模型。對給定的句子s = w1w2…wn，（數字，n,i都為下標，wi為句子s的壹個詞）。由鏈式規則（Chain rule），P(s) = p(w1)p(w2|w1)p(w3|w1w2)……p(wn|w1w2w3…w(n-1)) , 對p(wi|w1w2…w(i-1))而言，(w1w2…w(i-1))即為wi的歷史。考慮前面n-1個詞構成歷史的模型即為n-gram模型。 n越大，提供的語境信息也越多，但代價就越大，且需訓練語料多；n較小時，提供的信息比較少，但計算代價小，且無需太多訓練語料。
令c(w1,…，wi)表示詞串w1,w2…wi在訓練語料中出現的次數，則由最大似然估計， P(wn|w1,…,w(n-1)) = c(w1,…，wn) / c(w1,…，w(n-1)). 同理，則2-gram為 P(wn|w(n-1)) = c(w(n-1),wn) / c(w(n-1)).
若想了解更多相關知識，大家找相關資料看看，隨便把大學時的那本概率與統計課本拿出來翻翻，數學真是壹個好東東：）
回歸項目：） 訓練語料壹***有5萬多個不同的詞。建立2-gram統計模型時不斷要把每個詞在訓練語料中出現頻率統計出來，還要把每個詞及其後面的那個詞組成的2-gram在訓練語料中出現頻率統計出來。因為在切分時會頻繁的在建立的2-gram模型中查找相關的數據，所有，存儲這個2-gram模型數據的數據結構壹定要能提供高效的查找。故選擇hash表，它能提供常數時間的查找。Java類庫裏提供了HashMap類，基於數據兩還不是非常大，故可直接拿來用。在存儲時，每壹個key值對應壹個在訓練語料中出現過的詞語，而每壹個key值對應的value值又是壹個HashMap。暫且稱為子hashmap.這個結構有點類似文件結構裏的二級索引。 其相關代碼如下：
怎麽在預處理文件裏把詞分別讀出來就不羅嗦了，方法：每讀入壹行，按空格分成String數組，用個正則表達式匹配下即能得到。
//此方法傳入的兩個詞組成壹個2-gram，prewd為前壹個詞,currwd為緊隨其後的詞
public static void add(String prewd , String currwd){
String key = prewd;
String curr = currwd;
boolean bb = HMap.containsKey(key); //Hmap是壹個已存在的HashMap，用來存儲2-gram統計模型。在這裏判斷 preword 是否在 主map 中
if (bb == false) { //若 主map 中無，則添加
HashMap hm = new HashMap(); //首先，新構造壹個 子MAP
hm.put(key , new Integer(1)); //存儲 主KEY 的頻率 hm.put(curr , new Integer(1)); //存儲 主KEY 後面緊接著的那個詞頻率
HMap.put(key,hm); //將 主KEY 和對應的 子MAP 放入 主MAP 中
}
else //若 主map 中含有該詞
{
HashMap temp = (HashMap)HMap.get(key); //返回 主KEY 所對應的 子MAP ，進行值的修改
int count = ((Integer)temp.get(key)).intValue() + 1; //在 子map 中將 主key 次數加 1
temp.put(key , new Integer(count));
if (temp.containsKey(curr)) //判斷 子map 中是否含有該詞
{
int value = ((Integer)temp.get(curr)).intValue() + 1; temp.put(curr , new Integer(value));
}
else
temp.put(curr, new Integer(1)); //若無，則將其存入子map
HMap.put(key , temp); //子map 修改完畢 ，將其重新放入 主map
}
}
}
因為語言中的大部分詞屬於低頻詞，所以稀疏問題肯定存在。而MLE（最大似然估計）給在訓練語料中沒有出現的2-gram的賦給0概率。所以還得對2-gram模型進行數據平滑，以期得到更好的參數。目前平滑技術比較多，如Add-one,Add-delta,Witten-Bell，held-out留存平滑等。本系統主要采用了Add-delta和held-out兩中平滑方式，下面就Add-delta平滑技術為例，對2-gram進行平滑。對2-gram模型，其平滑公式為：
P(wn|w(n-1)) = [c(w(n-1),wn) + delta ] / ( N + delta * V) ,這裏去delta為0.5
其中，N：訓練語料中所有的2-gram的數量
V：所有的可能的不同的2-gram的數量
平滑思路 ：1.產生主hashmap的叠代器iterator，依次讀key;
2.對每壹個key，又讀出其value，即壹個子hashmap;
3.然後根據平滑公式對子map裏的值進行計算修改
算法框架：
Iterator it = 主hashmap.keySet().iterator();
While(it.hasNext())
{
主key = it.next();
子hashmap = (HashMap)主hashmap.get(主key);
Iterator itr = 子hashmap.keySet().iterator();
While(itr.hasNext())
{
根據平滑公式依次計算修改
}
}
註意問題：1.因為計算得出的概率值壹般都比較小，為了防止出現下溢，可對其取對數，再取反。
2.每壹個主key所對應的所有沒有出現過的，即頻率為零的2-gram，統壹用壹個鍵值對存儲在相應的子hashmap裏即可。
完畢，對象序列化。使用該系統時，lazy load將其載入內存，然後可讓其壹直存活在內存，這會大大加快速度。
到此，2-gram模型建立完畢。
<!--[if !supportLists]--> 3、 <!--[endif]-->全切分實現
切詞壹般有最大匹配法（MM、RMM），基於規則的方法，基於統計的方法。關於前兩者就不羅嗦了。所謂全切分就是要根據字典得到所以可能的切分形式。歧義識別的方法主要有：基於規則的方法和基於統計的方法。這裏當然是采用基於2-gram統計模型的方法了：）為了避免切分後再進行歧義分析的時間浪費。並且這裏采用邊切分邊評價的方法，即在切分進行的同時進行評價的方法。
對壹個句子進行全切分的結果，即所以可能的組合，可以形成壹棵解空間樹
於是，可用回溯法搜索最優解
若將所有的全切分組合先搜索出來，然後再根據2-gram選擇最佳，顯然會很浪費時間，因為過程中可能存在很多的重復搜索,而回溯搜索的時間復雜度為指數時間
所以，在搜索過程中要結合 剪枝，避免無效搜索，可很大提高效率
采用樹的深度優先法則。可找到最優解
具體算法如下：
Stack.push(BOS) //樹節點
while stack不為空
x=stack.pop()
pos：=x．Pos， w = x.w oldvalue：= x.value preword：=x.preword
if m>O then //m為首詞串的個數
forj：=1 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+FWj，posl，newsate)>maxValue(pos1)
stack.push(x)
endif
endfor
endif
endwhile
end．
在算法實現過程中需要考慮壹些諸如樹節點保存，首詞串處理等問題。
4.評估測試
環境：windows XP2, AMD Athlon 1800+, Memory 768m，JDK1.5
Delta平滑：隨著delta的取值變小，準確率上升，0.5，0.01，0.0001
召回率： 0.9756 0.9826 0.9928
準確率： 0.9638 0.9710 0.9883
留存平滑
召回率： 0.9946
準確率： 0.9902
壹般情況下，留存平滑應該還是比delta平滑更好
所有建模過程及平滑過程在1分鐘內都可完成。
切分時間與效率：
<!--[if !supportLists]-->n <!--[endif]-->測試語料，17455字符， （中文17287），平均句長 41個字，時間 ：340ms, 平均切分速度：5.1 萬/S
<!--[if !supportLists]-->n <!--[endif]-->20.5萬測試語料（取自笑傲江湖）， 預處理後 17.46萬 ，時間 110 MS,句子文本行數目 24945，平均句長 7 ， 切分時間 1300MS ， 平均13.46 萬 / 秒
<!--[if !supportLists]-->n <!--[endif]-->20.5萬測試語料（取自笑傲江湖），不預處理，平均句長 239 ，切分時間40S， 平均 5000字/秒
回溯算法是時間開銷為O(N!),所以在切分過程中句子長度直接決定了切分的速度,因為句子越長詞越多
經過預處理，句子短，平均句長 7, 回溯短，故速度要快很多。
到此，該系統基本完成，告壹段落。感覺寫的挺亂的呵呵
現在在做另壹個作業，做個簡單搜索引擎，準備把這個東東結合在搜索引擎裏面，實現切分功能：）