分詞技術在搜索引擎、信息抽取、機器翻譯等領域的重要地位和應用就不多說了。言歸正傳:)
& lt！-【如果！支持列表]-& gt；愛達荷（Idaho的縮寫）
這個切分系統的統計語料庫就是我們學校開放的部分。妳可以在這裏下載。漢字約為1.84萬。當然，這已經被分割了，所以妳可以用它來建立壹個相對較小的語料庫。該系統主要由以下四個步驟完成:
& lt！-【如果！支持列表]-& gt；1 、& lt！-[endif]-& gt；語料庫預處理
& lt！-【如果！支持列表]-& gt；2 、& lt！-[endif]-& gt；建立二元模型(統計二元模型)
& lt！-【如果！支持列表]-& gt；3 、& lt！-[endif]-& gt；實現完全細分
& lt！-【如果！支持列表]-& gt；4 、& lt！-[endif]-& gt；評價試驗
下面我就這四個方面逐壹來說。
& lt！-【如果！支持列表]-& gt；1 、& lt！-[endif]-& gt；語料庫預處理
下載的分段語料庫都是“19980131-04-012-001/mReality/n/u Epiphany/VN Que/d Bei/p Description/v Chu/v shape/Ng Lai/”/w”，其中有壹部分前面是日期數字，因為這些分段語料庫的來源是人民日報。預處理主要是根據標點符號劃分句子，句子簡單定義為(。？！: ;)對於這五個標點符號末尾的單詞串，添加
出；//輸出流
在；//輸入流
string buffer s 1 = new string buffer()；//緩沖區
char a = in . read()；
而(a！= -1) //判斷是否到達流的末尾。
{
if ((a == ' .|| a == '？'|| a == '！'| | a = = ':' | | a = = '；'))//句子結束
{
字符串s2 =新字符串(s 1)；
out . write(" & lt；BOS >；");//添加
out . write(S2)；
out . write(" & lt；EOS >；);//添加
out . write('/n ')；//換行
s 1 = new string buffer()；
}
else if ( a == '/')
s 1 = s 1 . append((char)32)；//分詞位置空間
else if(a & gt；256 )
s 1 = s 1 . append((char)a)；
a = in . read()；
}
out . close()；
in . close()；
& lt！-【如果！支持列表]-& gt；2 、& lt！-[endif]-& gt；建立二元模型(統計二元模型)
這裏首先簡單介紹壹下n元模型和2元模型。
從語言樣本估計的概率分布p稱為語言l的語言模型，對於給定的句子s = w1w2…wn，(數字，n，I都是下標，wi是句子s的壹個詞)。根據鏈式法則，p(s)= p(w 1)p(w2 | w 1)p(w3 | w 1 w2)...p (wn | w1w2w3...w(n-65438n-gram模型是考慮前n-1個單詞的歷史的模型。N越大，提供的上下文信息越多，但是成本越大，需要的訓練語料也越多。當n較小時，提供的信息較少，但計算成本較小，訓練語料不多。
設c(w1，…，wi)表示單詞串w1，w2…wi在訓練語料中出現的次數，則用最大似然估計，p (wn | w1，…，w(n-1)) = c (w65438則2-gram為p(wn | w(n-1))= c(w(n-1)，wn)/c(n
想了解更多，請找相關資料，拿出大學時的概率統計教材。數學真的是個好東西:)
回歸項目:)訓練語料庫1 * * *有5萬多個不同的詞。在建立2-gram統計模型時，需要不斷統計每個詞在訓練語料中出現的頻率，還要統計每個詞組成的2-gram及其後面的詞在訓練語料中出現的頻率。因為在分割期間將在所建立的2-gram模型中頻繁地搜索相關數據，所以用於存儲該2-gram模型數據的數據結構必須能夠提供高效的搜索。所以選擇哈希表，可以提供常量時間搜索。Java類庫中提供了HashMap類，基於數據不是很大，可以直接使用。存儲時，每個鍵值對應壹個在訓練語料庫中出現過的詞，每個鍵值對應的value值就是壹個HashMap。暫且稱之為子hashmap吧。這種結構有點類似於文件結構中的二級索引。相關代碼如下:
如何把預處理文件中的單詞單獨讀出來並不繁瑣。方法:讀取每壹行，用空格分割成字符串數組，匹配壹個正則表達式得到。
//此方法傳入的兩個單詞組成壹個2-gram，prewd為前壹個單詞，currwd為後壹個單詞。
public static void add(String prewd，String currwd){
String key = prewd
String curr = currwd
boolean bb = hmap . contains key(key)；//Hmap是現有的HashMap，用於存儲2-gram統計模型。這裏判斷preword是否在主圖中。
If (bb == false) {//如果不在主圖中，則添加。
HashMap hm = new HashMap()；//首先，構造壹個新的子地圖。
hm.put(key，新整數(1))；//存儲主鍵的頻率hm.put(curr，new Integer(1))；//存儲緊接在主關鍵字之後的單詞的頻率。
HMap.put(key，hm)；//將主鍵和對應的子映射放到主映射中。
}
Else //如果該單詞包含在主地圖中，
{
HashMap temp =(HashMap)hmap . get(key)；//返回主鍵對應的子映射來修改值。
int count =((Integer)temp . get(key))。int value()+1；//子映射中的主鍵數加1。
temp.put(key，new Integer(count))；
If (temp.containsKey(curr)) //確定子映射是否包含單詞。
{
int value =((Integer)temp . get(curr))。int value()+1；temp.put(curr，新整數(值))；
}
其他
temp.put(curr，新整數(1))；//如果沒有，則存儲在子映射中。
HMap.put(key，temp)；//修改完子地圖後，放回主地圖。
}
}
}
因為語言中的詞大多屬於低頻詞，所以壹定存在稀疏性的問題。然而，MLE(最大似然估計)給沒有出現在訓練語料庫中的2-gram 0概率。因此，為了得到更好的參數，有必要對2-gram模型的數據進行平滑處理。目前有許多平滑技術，如加壹、加增量、威滕-貝爾、保持平滑等。該系統主要采用兩種平滑方法:增量平滑法和保持平滑法。讓我們以Add-delta平滑技術為例來平滑2-gram。對於2克模型，平滑公式為:
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的叠代器，依次讀取key
2.對於每個鍵，再次讀取其值，即壹個子hashmap
3.然後根據平滑公式計算並修改submap中的值。
算法框架:
叠代器it = primary hashmap.keySet()。叠代器()；
While(it.hasNext())
{
primary key = it . next()；
子HashMap =(HashMap)primary HashMap . get(primary key)；
iterator itr = child hashmap . keyset()。叠代器()；
While(itr.hasNext())
{
根據平滑公式，依次計算修改量。
}
}
關註:1。因為計算出來的概率值壹般都比較小，為了防止下溢，可以先取對數再取逆。
2.每個主密鑰對應的所有不存在的2-gram，即出現頻率為零的2-gram，都可以用壹個鍵-值對統壹存儲在對應的子hashmap中。
完成，對象序列化。在使用這個系統的時候，lazy load把它加載到內存中，然後它就可以壹直住在內存中，這樣會大大加快速度。
至此，2-gram模型已經建立。
& lt！-【如果！支持列表]-& gt；3 、& lt！-[endif]-& gt；完全分段實現
分詞壹般有最大匹配法(MM，RMM)，基於規則的方法，統計的方法。前兩個我就不贅述了。所謂全切分，就是根據詞典得到所有可能的切分形式。歧義識別的方法主要包括基於規則的方法和統計的方法。當然這裏采用的是基於2-gram統計模型的方法:)為了避免切分後歧義分析的時間浪費。而這裏我們用的是邊分段邊評價的方法，也就是邊分段邊評價的方法。
對壹個句子進行全切分的結果，即所有可能的組合，可以形成壹棵解空間樹。
因此，可以用回溯法搜索最優解。
如果先把所有的全切分組合都搜索出來，然後按照2-gram選取最好的，顯然會浪費時間，因為過程中可能會有很多次重復搜索，回溯搜索的時間復雜度是指數級的時間。
所以在搜索過程中要結合剪枝，避免無效搜索，這樣可以大大提高效率。
采用樹的深度優先規則。可以找到最優解
具體算法如下:
Stack.push(BOS) //樹節點
而堆棧不為空。
x=stack.pop()
位置:=x .位置，w = x.w舊值:= x .值前字:= x .前字
如果m & gto那麽//m是前綴字符串的個數。
forj:=1到m do
FWj是fwc的第j個元素l。
如果length(w+FWj) =length(c)和最大概率則輸出w+FWjl並設置最新句子的最大概率值。
其他
posl:= pos+長度(FWj)l
if probability(w+FWj，posl，newsate)>最大值(pos1)
stack.push(x)
endif
結束
endif
結束時間
結束。
算法實現中需要考慮壹些問題，如樹節點保存、前綴字符串處理等。
評估測試
環境:windows xp2，amd速龍1800+，內存768m，JDK1.5。
Delta平滑:Delta的值越小，精度越高，0.5，0.01，0.0005438+0。
召回率:0.9756 0.9826 0.9928
精確度:0.9638 0.9710 0.9883
保持平滑
召回率:0.9946
精確度:0.9902
壹般而言，保留平滑仍應優於增量平滑。
所有建模和平滑過程可以在1分鐘內完成。
分段時間和效率:
& lt！-【如果！支持列表]-& gt；n & lt！-[endif]-& gt；測試語料庫，17455字，(中文17287)，平均句子長度41字，時間340ms，平均切分速度5.10000/s。
& lt！-【如果！支持列表]-& gt；n & lt！-[endif]-& gt；20.5萬測試語料(來自笑傲江湖)，預處理後，174600，時間110 ms，句子行數24945，平均句子長度7，切分時間134600 ms，平均134600/s
& lt！-【如果！支持列表]-& gt；n & lt！-[endif]-& gt；205000個測試語料(來自笑傲江湖)，無預處理，平均句長239，切分時間40S，平均每秒5000字。
回溯算法是時間開銷為O(N！)，所以句子的長度直接決定了分詞的速度，因為句子越長，單詞就越多。
預處理後句子短，平均句子長度7，回溯短，所以速度快很多。
至此，系統基本完成，告壹段落。感覺寫的挺亂的，呵呵
現在在做另壹個功課，做壹個簡單的搜索引擎，我準備把這個東西和搜索引擎結合起來，實現分詞功能:)