轉自：http://blog.csdn.net/pennyliang/archive/2010/07/07/5717498.aspx
中文分詞方法有很多，其中基于詞典的分詞方法有：
正向最大匹配、逆向最大匹配法、雙向匹配法
最少分詞法
基于統計的分詞方法有：
- 統計語言模型分詞（2-gram，3-gram）
- 串頻統計的漢語自動分詞
除了這些基本的方法，為了獲得最佳的效果，也可以引入動態規劃的方法獲得最優解。
設句子P = W0W1W2?Wn , 其中Wi (0≤i≤n) 為句子P中的第i 個漢字。Si(0≤i≤n+1)為句子的第i個間隙（切分位置）
那么一個句子P理論上有多少種分詞法呢？
分詞分法總數的通項：F（n）表示一個有n個單詞的句子包含的全部不同的分詞方法。
F(n)=1+ F(n-1)+F(n-2)+F(n-3)+F(n-4)+..F(1)
F(1)=1
F(2)=2
F(3)=4
F(4)=8
…
F(n)=2F(n-1)
則F(n)=2n-1
如果將詞頻看做是距離，則求解最佳切分方法等價于在2n-1的解空間中尋找1種最佳的切分方法使得路徑最短。為此我們舉個例子：
早起先刷牙
圖中紅圈為切分點，切分點之間的連線表示確定的一種分詞
圖中給出了三種分法，分別是[早][起][先][刷][牙]、[早起][先][刷牙]和[早][起先][刷牙]
假定我們有這樣一個字頻和詞頻表，分別如下
早 400
早起 100
起 500
起先 150
先 500
刷 300
刷牙 100
牙 500
則以上三種切分法的代價分別為
[早][起][先][刷][牙]：400+500+500+300+500 = 2200
[早起][先][刷牙]：100+500+100 = 700
[早][起先][刷牙]：400+150+100 =750 （此處應為650）
因此選用第2種切分法。
動態規劃的偽代碼大致為：
Segment(S,low,high,cost,last)
{
Mincost = MAX;
If(high-low<=1)
{
mincost = Costof(cost，L(low,high-low)); //其中L(start,length)的含義表示從start開始從P中取length長度的文本，Costof為該段文本的字頻，或者詞頻，如果不存在則為無窮大；如果cost數組中已經計算過，則不重復計算，直接取值返回。
cost[low][high] = mincost;
Return mincost；
}
for（i = low+1 to high ）
{
a = Segment(S,low,i,cost,last);//為了簡單這里做了精簡，事實上如果a返回的是無窮大，則后面不用繼續計算，直接跳出，因為這種情況下無論如何也不可能是最優解，可以直接剪枝。
b = Segment(S,i,high,cost,last);
if(a+b<Mincost)
{
Mincost = a + b;
Cost[low][high]=Mincost;
Last[low][high] = i;//Last記錄最佳切分點
}
}
ExtractSegmentPos(Last,low,high);//該函數是將切分點一一展開。
}
ExtractSegmentPos(Last,low,high)
{
SegPos=MAX;
if(high-low>1)
{
If(Last[low][high]>0)
{
SegPos = Last[low][high]；
output(SegPos);
}
else
{
return;
}
}
ExtractSegmentPos(Last,low, SegPos);
ExtractSegmentPos(Last, SegPos,high);
}
參考文獻
[1] 孫 曉, 黃德根 基于動態規劃的最小代價路徑漢語自動分詞 [J]小型微型計算機系統 第27 卷第3 期 2006 年3 月
其他推薦閱讀
http://www.leadbbs.com/MINI/default.asp?230-2682632-0-0-0-0-0-a-.htm
posted on 2010-07-30 09:06
胡滿超 閱讀(779)
評論(0) 編輯 收藏 引用