基于最小費用最大流的中文分詞算法模型

馬凌霄

摘 要：中文自動分詞不僅是中文信息處理的基礎性工作而且對后續句法分析、語義分析等中文信息處理流程有著很大的影響。本文基于最小費用最大流，提出一個具有拓展性的中文分詞算法模型，實驗證明了本算法能夠準確地對輸入文字串進行切分。

關鍵詞：中文分詞 最小費用最大流 字符串匹配 中文信息處理

中圖分類號：TP319 文獻標識碼：A 文章編號：1672-3791（2014）09（b）-0219-01

隨著人工智能的快速發展，中文信息處理已經在搜索引擎、Web文本挖掘、自動文摘、文本校對等領域發揮越來越重要的作用。中文自動分詞不僅是中文信息處理的一項基礎性工作而且是嚴重制約中文信息處理發展的瓶頸之一。本文致力于中文自動分詞算法的研究，基于最小費用最大流的原理提出一個具有拓展性的中文分詞算法模型。

1 中文自動分詞算法簡述

中文分詞的基本方法是基于已有詞典庫或者規則庫，針對輸入文字的字符串做分詞、過濾處理，輸出最優切分的中文單詞[1]。

中文分詞算法主要分為以下四類[1-3]：

（1）基于字符串匹配的分詞方法：按照一定的字符串匹配策略，將輸入文字的字符串與詞典庫中的詞條進行匹配，若匹配成功，則進行切分。主要算法有：最大匹配法、逆向最大匹配法、最佳匹配法、逐詞遍歷法等。

（2）基于規則的分詞方法：將基于字符串匹配的分詞算法與分詞規則庫結合，采用不同的策略對輸入語句進行切分，切分一致的部分判定為切分正確，不一致的部分為歧義字段。

（3）基于統計的分詞方法：采用多種切分策略對輸入字符串進行切分，根據分詞詞典匹配出所有可能的切分情況并計算切分的概率，求出概率最大的切分策略作為切分結果。

（4）基于理解的分詞方法：在分詞的過程中，不僅進行字符串的切分，而且進行句法分析、語義分析，利用句法和語義信息處理切分歧義。目前此方法尚處于試驗階段。

本文提出的基于最小費用最大流的中文分詞算法模型即為基于字符串匹配的分詞方法，而且此分詞算法模型可以拓展為基于統計的分詞方法。

2 基于最小費用最大流的中文分詞算法模型

2.1 最小費用最大流

最小費用最大流問題的定義如下：設是一個有向圖，為起點（源點），為終點（匯點），其中每一條邊均有一個非負容量、一個費用和一個不大于容量的流量，問怎樣制定運輸方案使得從到的流量最大且總費用最小？

最小費用最大流問題的求解途徑有兩種[4]：（1）保持網絡中的可行流是最大流，逐步調整使得總費用逐步減小，最終得到最大流量的最小費用流；（2）保持網絡中的可行流是最小費用流，逐步調整使得流量逐步增大，最終得到最小費用的最大流。顯然第二種途徑與已知最大流問題的求解算法相近，并可以將問題轉化為一個求從點到點的最短路徑問題：不斷以費用為權值，使用最短路徑算法，尋找一條從點到點的最小費用增廣路，直至找不到從點到點的增廣路。

2.2 中文分詞算法模型

基于上述最小費用最大流模型，下面給出基于最小費用最大流的中文分詞算法模型。

（1）將輸入文字串進行全切分。

①刪去輸入文字串的空格、回車等非中文字符。

②將得到的字符串對切分大小從1到7進行反復切分，并在詞典庫中查找切分結果：找到，則在詞表增加一條記錄；沒找到，則忽略此次切分結果。

（2）基于全切分的結果建圖。

①遍歷全切分結果詞表：對詞表每一條記錄添加一個頂點。如果詞表兩個記錄，是相鄰的，則建立一條從到的有向邊，容量，費用，流量。

②將源點與字符串第一個詞對應的頂點建立一條從到的有向邊，容量，費用，流量。

③將字符串最后一個詞對應的頂點與匯點與建立一條從到的有向邊，容量，費用，流量。

（3）求解此最小費用最大流問題。

①在只允許通過容量-流量>0的邊的限制下，以費用為權值，使用SPFA算法[5]求從源點到匯點的一條最短路徑，即最小費用增廣路。

②對于（a）中求得的路徑，令路徑上的每一條邊的流量=容量。

③重復（a）（b）過程，直至無法找到從源點到匯點的最短路徑。

（4）從源點遍歷整個圖，對于任意一條有向邊，如果流量，輸出頂點和對應的中文單詞。即可得到中文分詞結果。

2.3 模型拓展

在上述分詞算法模型的基礎上，通過改變邊的費用權值，可以將算法拓展為基于統計的分詞方法。下面給出一種拓展方法[3]。

（1）設詞典包括個詞條，則為這個詞條建立的馬爾科夫一階轉移矩陣，其中

。

（2）建立從到的有向邊時，令費用。

這樣我們就得到一個基于統計方法的最小費用最大流中文分詞算法。

3 算法分析與實驗

3.1 算法的時間復雜度分析

設輸入字符串長度為，每次查詢詞典庫的時間復雜度為，則對字符串進行全切分的時間復雜度為；設有向圖的頂點個數為，邊的個數為，尋找最小費用增廣路的次數為，則每次求解從源點到匯點的最短路徑的時間復雜度為[5]，求解最小費用最大流問題的時間復雜度為。綜合上述兩個步驟的時間復雜度，中文分詞算法總時間復雜度為。

3.2 實驗

為了驗證本文提出的中文分詞算法的準確性，本文使用教育部語言文字應用研究所《現代漢語語料庫詞頻表》[6]作為詞典庫，對50篇新聞文章進行中文分詞，分詞正確率達到96.81%，說明了此分詞算法具有很高的準確性。

4 結語

本文提出的基于最小費用最大流的中文分詞算法模型不僅能準確地切分輸入字符串，而且可以通過改變費用權值拓展算法考慮的切分標準來提高切分準確度，具有很好的拓展性。

參考文獻

[1] 龍樹全，趙正文，唐華.中文分詞算法概述[J].電腦知識與技術，2009，5（10）： 2605-2607.

[2] 黃昌寧，趙海.中文分詞十年回顧[J].中文信息學報，2007，21（3）：8-19.

[3] 宋繼華，楊爾弘，王強軍.中文信息處理教程[M].北京：高等教育出版社，2011.

[4] Orlin，J.B.A faster strongly polynomial minimum cost flow algorithm [J].Operations research，1993：41（2），338-350.

[5] 段凡丁.關于最短路徑的SPFA快速算法[J].西南交通大學學報，1994，29（2）：207-212.

[6] 教育部語言文字應用研究所.現代漢語語料庫詞頻表[EB/OL].（2014-07-16） [2014-08-05].http：//www.cncorpus.org/resources.aspx.endprint

摘 要：中文自動分詞不僅是中文信息處理的基礎性工作而且對后續句法分析、語義分析等中文信息處理流程有著很大的影響。本文基于最小費用最大流，提出一個具有拓展性的中文分詞算法模型，實驗證明了本算法能夠準確地對輸入文字串進行切分。

關鍵詞：中文分詞 最小費用最大流 字符串匹配 中文信息處理

中圖分類號：TP319 文獻標識碼：A 文章編號：1672-3791（2014）09（b）-0219-01

隨著人工智能的快速發展，中文信息處理已經在搜索引擎、Web文本挖掘、自動文摘、文本校對等領域發揮越來越重要的作用。中文自動分詞不僅是中文信息處理的一項基礎性工作而且是嚴重制約中文信息處理發展的瓶頸之一。本文致力于中文自動分詞算法的研究，基于最小費用最大流的原理提出一個具有拓展性的中文分詞算法模型。

1 中文自動分詞算法簡述

中文分詞的基本方法是基于已有詞典庫或者規則庫，針對輸入文字的字符串做分詞、過濾處理，輸出最優切分的中文單詞[1]。

中文分詞算法主要分為以下四類[1-3]：

（1）基于字符串匹配的分詞方法：按照一定的字符串匹配策略，將輸入文字的字符串與詞典庫中的詞條進行匹配，若匹配成功，則進行切分。主要算法有：最大匹配法、逆向最大匹配法、最佳匹配法、逐詞遍歷法等。

（2）基于規則的分詞方法：將基于字符串匹配的分詞算法與分詞規則庫結合，采用不同的策略對輸入語句進行切分，切分一致的部分判定為切分正確，不一致的部分為歧義字段。

（3）基于統計的分詞方法：采用多種切分策略對輸入字符串進行切分，根據分詞詞典匹配出所有可能的切分情況并計算切分的概率，求出概率最大的切分策略作為切分結果。

（4）基于理解的分詞方法：在分詞的過程中，不僅進行字符串的切分，而且進行句法分析、語義分析，利用句法和語義信息處理切分歧義。目前此方法尚處于試驗階段。

本文提出的基于最小費用最大流的中文分詞算法模型即為基于字符串匹配的分詞方法，而且此分詞算法模型可以拓展為基于統計的分詞方法。

2 基于最小費用最大流的中文分詞算法模型

2.1 最小費用最大流

最小費用最大流問題的定義如下：設是一個有向圖，為起點（源點），為終點（匯點），其中每一條邊均有一個非負容量、一個費用和一個不大于容量的流量，問怎樣制定運輸方案使得從到的流量最大且總費用最小？

最小費用最大流問題的求解途徑有兩種[4]：（1）保持網絡中的可行流是最大流，逐步調整使得總費用逐步減小，最終得到最大流量的最小費用流；（2）保持網絡中的可行流是最小費用流，逐步調整使得流量逐步增大，最終得到最小費用的最大流。顯然第二種途徑與已知最大流問題的求解算法相近，并可以將問題轉化為一個求從點到點的最短路徑問題：不斷以費用為權值，使用最短路徑算法，尋找一條從點到點的最小費用增廣路，直至找不到從點到點的增廣路。

2.2 中文分詞算法模型

基于上述最小費用最大流模型，下面給出基于最小費用最大流的中文分詞算法模型。

（1）將輸入文字串進行全切分。

①刪去輸入文字串的空格、回車等非中文字符。

②將得到的字符串對切分大小從1到7進行反復切分，并在詞典庫中查找切分結果：找到，則在詞表增加一條記錄；沒找到，則忽略此次切分結果。

（2）基于全切分的結果建圖。

①遍歷全切分結果詞表：對詞表每一條記錄添加一個頂點。如果詞表兩個記錄，是相鄰的，則建立一條從到的有向邊，容量，費用，流量。

②將源點與字符串第一個詞對應的頂點建立一條從到的有向邊，容量，費用，流量。

③將字符串最后一個詞對應的頂點與匯點與建立一條從到的有向邊，容量，費用，流量。

（3）求解此最小費用最大流問題。

①在只允許通過容量-流量>0的邊的限制下，以費用為權值，使用SPFA算法[5]求從源點到匯點的一條最短路徑，即最小費用增廣路。

②對于（a）中求得的路徑，令路徑上的每一條邊的流量=容量。

③重復（a）（b）過程，直至無法找到從源點到匯點的最短路徑。

（4）從源點遍歷整個圖，對于任意一條有向邊，如果流量，輸出頂點和對應的中文單詞。即可得到中文分詞結果。

2.3 模型拓展

在上述分詞算法模型的基礎上，通過改變邊的費用權值，可以將算法拓展為基于統計的分詞方法。下面給出一種拓展方法[3]。

（1）設詞典包括個詞條，則為這個詞條建立的馬爾科夫一階轉移矩陣，其中

。

（2）建立從到的有向邊時，令費用。

這樣我們就得到一個基于統計方法的最小費用最大流中文分詞算法。

3 算法分析與實驗

3.1 算法的時間復雜度分析

設輸入字符串長度為，每次查詢詞典庫的時間復雜度為，則對字符串進行全切分的時間復雜度為；設有向圖的頂點個數為，邊的個數為，尋找最小費用增廣路的次數為，則每次求解從源點到匯點的最短路徑的時間復雜度為[5]，求解最小費用最大流問題的時間復雜度為。綜合上述兩個步驟的時間復雜度，中文分詞算法總時間復雜度為。

3.2 實驗

為了驗證本文提出的中文分詞算法的準確性，本文使用教育部語言文字應用研究所《現代漢語語料庫詞頻表》[6]作為詞典庫，對50篇新聞文章進行中文分詞，分詞正確率達到96.81%，說明了此分詞算法具有很高的準確性。

4 結語

本文提出的基于最小費用最大流的中文分詞算法模型不僅能準確地切分輸入字符串，而且可以通過改變費用權值拓展算法考慮的切分標準來提高切分準確度，具有很好的拓展性。

參考文獻

[1] 龍樹全，趙正文，唐華.中文分詞算法概述[J].電腦知識與技術，2009，5（10）： 2605-2607.

[2] 黃昌寧，趙海.中文分詞十年回顧[J].中文信息學報，2007，21（3）：8-19.

[3] 宋繼華，楊爾弘，王強軍.中文信息處理教程[M].北京：高等教育出版社，2011.

[4] Orlin，J.B.A faster strongly polynomial minimum cost flow algorithm [J].Operations research，1993：41（2），338-350.

[5] 段凡丁.關于最短路徑的SPFA快速算法[J].西南交通大學學報，1994，29（2）：207-212.

[6] 教育部語言文字應用研究所.現代漢語語料庫詞頻表[EB/OL].（2014-07-16） [2014-08-05].http：//www.cncorpus.org/resources.aspx.endprint

摘 要：中文自動分詞不僅是中文信息處理的基礎性工作而且對后續句法分析、語義分析等中文信息處理流程有著很大的影響。本文基于最小費用最大流，提出一個具有拓展性的中文分詞算法模型，實驗證明了本算法能夠準確地對輸入文字串進行切分。

關鍵詞：中文分詞 最小費用最大流 字符串匹配 中文信息處理

中圖分類號：TP319 文獻標識碼：A 文章編號：1672-3791（2014）09（b）-0219-01

隨著人工智能的快速發展，中文信息處理已經在搜索引擎、Web文本挖掘、自動文摘、文本校對等領域發揮越來越重要的作用。中文自動分詞不僅是中文信息處理的一項基礎性工作而且是嚴重制約中文信息處理發展的瓶頸之一。本文致力于中文自動分詞算法的研究，基于最小費用最大流的原理提出一個具有拓展性的中文分詞算法模型。

1 中文自動分詞算法簡述

中文分詞的基本方法是基于已有詞典庫或者規則庫，針對輸入文字的字符串做分詞、過濾處理，輸出最優切分的中文單詞[1]。

中文分詞算法主要分為以下四類[1-3]：

（1）基于字符串匹配的分詞方法：按照一定的字符串匹配策略，將輸入文字的字符串與詞典庫中的詞條進行匹配，若匹配成功，則進行切分。主要算法有：最大匹配法、逆向最大匹配法、最佳匹配法、逐詞遍歷法等。

（2）基于規則的分詞方法：將基于字符串匹配的分詞算法與分詞規則庫結合，采用不同的策略對輸入語句進行切分，切分一致的部分判定為切分正確，不一致的部分為歧義字段。

（3）基于統計的分詞方法：采用多種切分策略對輸入字符串進行切分，根據分詞詞典匹配出所有可能的切分情況并計算切分的概率，求出概率最大的切分策略作為切分結果。

（4）基于理解的分詞方法：在分詞的過程中，不僅進行字符串的切分，而且進行句法分析、語義分析，利用句法和語義信息處理切分歧義。目前此方法尚處于試驗階段。

本文提出的基于最小費用最大流的中文分詞算法模型即為基于字符串匹配的分詞方法，而且此分詞算法模型可以拓展為基于統計的分詞方法。

2 基于最小費用最大流的中文分詞算法模型

2.1 最小費用最大流

最小費用最大流問題的定義如下：設是一個有向圖，為起點（源點），為終點（匯點），其中每一條邊均有一個非負容量、一個費用和一個不大于容量的流量，問怎樣制定運輸方案使得從到的流量最大且總費用最小？

最小費用最大流問題的求解途徑有兩種[4]：（1）保持網絡中的可行流是最大流，逐步調整使得總費用逐步減小，最終得到最大流量的最小費用流；（2）保持網絡中的可行流是最小費用流，逐步調整使得流量逐步增大，最終得到最小費用的最大流。顯然第二種途徑與已知最大流問題的求解算法相近，并可以將問題轉化為一個求從點到點的最短路徑問題：不斷以費用為權值，使用最短路徑算法，尋找一條從點到點的最小費用增廣路，直至找不到從點到點的增廣路。

2.2 中文分詞算法模型

基于上述最小費用最大流模型，下面給出基于最小費用最大流的中文分詞算法模型。

（1）將輸入文字串進行全切分。

①刪去輸入文字串的空格、回車等非中文字符。

②將得到的字符串對切分大小從1到7進行反復切分，并在詞典庫中查找切分結果：找到，則在詞表增加一條記錄；沒找到，則忽略此次切分結果。

（2）基于全切分的結果建圖。

①遍歷全切分結果詞表：對詞表每一條記錄添加一個頂點。如果詞表兩個記錄，是相鄰的，則建立一條從到的有向邊，容量，費用，流量。

②將源點與字符串第一個詞對應的頂點建立一條從到的有向邊，容量，費用，流量。

③將字符串最后一個詞對應的頂點與匯點與建立一條從到的有向邊，容量，費用，流量。

（3）求解此最小費用最大流問題。

①在只允許通過容量-流量>0的邊的限制下，以費用為權值，使用SPFA算法[5]求從源點到匯點的一條最短路徑，即最小費用增廣路。

②對于（a）中求得的路徑，令路徑上的每一條邊的流量=容量。

③重復（a）（b）過程，直至無法找到從源點到匯點的最短路徑。

（4）從源點遍歷整個圖，對于任意一條有向邊，如果流量，輸出頂點和對應的中文單詞。即可得到中文分詞結果。

2.3 模型拓展

在上述分詞算法模型的基礎上，通過改變邊的費用權值，可以將算法拓展為基于統計的分詞方法。下面給出一種拓展方法[3]。

（1）設詞典包括個詞條，則為這個詞條建立的馬爾科夫一階轉移矩陣，其中

。

（2）建立從到的有向邊時，令費用。

這樣我們就得到一個基于統計方法的最小費用最大流中文分詞算法。

3 算法分析與實驗

3.1 算法的時間復雜度分析

設輸入字符串長度為，每次查詢詞典庫的時間復雜度為，則對字符串進行全切分的時間復雜度為；設有向圖的頂點個數為，邊的個數為，尋找最小費用增廣路的次數為，則每次求解從源點到匯點的最短路徑的時間復雜度為[5]，求解最小費用最大流問題的時間復雜度為。綜合上述兩個步驟的時間復雜度，中文分詞算法總時間復雜度為。

3.2 實驗

為了驗證本文提出的中文分詞算法的準確性，本文使用教育部語言文字應用研究所《現代漢語語料庫詞頻表》[6]作為詞典庫，對50篇新聞文章進行中文分詞，分詞正確率達到96.81%，說明了此分詞算法具有很高的準確性。

4 結語

本文提出的基于最小費用最大流的中文分詞算法模型不僅能準確地切分輸入字符串，而且可以通過改變費用權值拓展算法考慮的切分標準來提高切分準確度，具有很好的拓展性。

參考文獻

[1] 龍樹全，趙正文，唐華.中文分詞算法概述[J].電腦知識與技術，2009，5（10）： 2605-2607.

[2] 黃昌寧，趙海.中文分詞十年回顧[J].中文信息學報，2007，21（3）：8-19.

[3] 宋繼華，楊爾弘，王強軍.中文信息處理教程[M].北京：高等教育出版社，2011.

[4] Orlin，J.B.A faster strongly polynomial minimum cost flow algorithm [J].Operations research，1993：41（2），338-350.

[5] 段凡丁.關于最短路徑的SPFA快速算法[J].西南交通大學學報，1994，29（2）：207-212.

[6] 教育部語言文字應用研究所.現代漢語語料庫詞頻表[EB/OL].（2014-07-16） [2014-08-05].http：//www.cncorpus.org/resources.aspx.endprint