轉(zhuǎn)自：http://blog.csdn.net/pennyliang/archive/2010/07/07/5717498.aspx

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

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

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

      除了這些基本的方法，為了獲得最佳的效果，也可以引入動(dòng)態(tài)規(guī)劃的方法獲得最優(yōu)解。

     設(shè)句子P = W₀W₁W₂?W_n , 其中W_i (0≤i≤n) 為句子P中的第i 個(gè)漢字。Si(0≤i≤n+1)為句子的第i個(gè)間隙（切分位置）

     那么一個(gè)句子P理論上有多少種分詞法呢？

     分詞分法總數(shù)的通項(xiàng)：F（n）表示一個(gè)有n個(gè)單詞的句子包含的全部不同的分詞方法。

     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

    如果將詞頻看做是距離，則求解最佳切分方法等價(jià)于在2^n-1的解空間中尋找1種最佳的切分方法使得路徑最短。為此我們舉個(gè)例子：

    早起先刷牙

 

    

 

圖中紅圈為切分點(diǎn)，切分點(diǎn)之間的連線(xiàn)表示確定的一種分詞

圖中給出了三種分法，分別是[早][起][先][刷][牙]、[早起][先][刷牙]和[早][起先][刷牙]

假定我們有這樣一個(gè)字頻和詞頻表，分別如下

 

早              400

早起            100

起              500

起先            150

先              500

刷              300

刷牙            100

牙              500

則以上三種切分法的代價(jià)分別為

[早][起][先][刷][牙]：400+500+500+300+500 = 2200

[早起][先][刷牙]：100+500+100 = 700

[早][起先][刷牙]：400+150+100 =750 （此處應(yīng)為650）

因此選用第2種切分法。

動(dòng)態(tài)規(guī)劃的偽代碼大致為：

Segment(S,low,high,cost,last)

{

        Mincost = MAX;

        If(high-low<=1)

        {

        mincost = Costof(cost，L(low,high-low)); //其中L(start,length)的含義表示從start開(kāi)始從P中取length長(zhǎng)度的文本，Costof為該段文本的字頻，或者詞頻，如果不存在則為無(wú)窮大；如果cost數(shù)組中已經(jīng)計(jì)算過(guò)，則不重復(fù)計(jì)算，直接取值返回。

        cost[low][high] = mincost;

        Return mincost；

       }

        for（i = low+1 to high ）

       {

           a = Segment(S,low,i,cost,last);//為了簡(jiǎn)單這里做了精簡(jiǎn)，事實(shí)上如果a返回的是無(wú)窮大，則后面不用繼續(xù)計(jì)算，直接跳出，因?yàn)檫@種情況下無(wú)論如何也不可能是最優(yōu)解，可以直接剪枝。

           b = Segment(S,i,high,cost,last);

           if(a+b<Mincost)

           {

               Mincost = a + b;

               Cost[low][high]=Mincost;

               Last[low][high] = i;//Last記錄最佳切分點(diǎn)

           }

        }

        ExtractSegmentPos(Last,low,high);//該函數(shù)是將切分點(diǎn)一一展開(kāi)。

}

 

 

 

 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);

}

參考文獻(xiàn)

[1] 孫　曉, 黃德根  基于動(dòng)態(tài)規(guī)劃的最小代價(jià)路徑漢語(yǔ)自動(dòng)分詞   [J]小型微型計(jì)算機(jī)系統(tǒng) 　第27 卷第3 期 2006 年3 月

其他推薦閱讀

http://www.leadbbs.com/MINI/default.asp?230-2682632-0-0-0-0-0-a-.htm