轉自：http://blog.csdn.net/pennyliang/archive/2010/07/07/5717498.aspx

中文分詞方法有很多，其中基于詞典的分詞方法有：

•     基于模式匹配的方法：（速度快）

                     正向最大匹配、逆向最大匹配法、雙向匹配法

      除了這些基本的方法，為了獲得最佳的效果，也可以引入動態規劃的方法獲得最優解。

     設句子P = W₀W₁W₂?W_n , 其中W_i (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)=2^n-1

    如果將詞頻看做是距離，則求解最佳切分方法等價于在2^n-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