一種改進的最大匹配分詞算法研究

摘 要:通過對最大匹配分詞算法做出改進，解決了最大匹配分詞算法所不能解決的一些問題，并得出較準確的粗分結果。

關鍵詞:MMSEG;最大匹配;分詞 

中圖分類號:TP

文獻標識碼:A

文章編號:1672-3198(2010)09-0297-02

1 引言

漢語的中文信息處理就是要用計算機對漢語的音，形，義進行處理。同時詞是最小的能夠獨立活動的有意義的語言成分。然而漢語是以字為基本的書寫單位，詞語之間沒有明顯的區分標記，因此，中文自動分詞是中文信息處理的基礎與關鍵。目前，中文自動分詞方法主要分為三類:第一類主要是基于字典，詞庫的字符串匹配方法，這類方法簡單實用，比較容易實現，然而精度不高;第二類主要是利用詞的頻度統計信息進行分詞的方法，這類方法能夠識別生詞，但對常用詞的識別精度不高;第三類主要是基于句法語法分析，并結合語義分析，根據上下文信息來分詞，這類方法原理比較復雜，難于實現。單靠某一類分詞方法很難實現滿意實用的分詞系統，而中文詞語分析一般都需要包括3個過程:預處理過程的詞語粗切分，切分排歧與未登錄詞識別和詞性標注。目前中文詞語分析采取的主要步驟是:先采取最大匹配，最短路徑，概率統計或全切分等方法，得到一個相對好的粗分結果，然后進行排歧，未登錄詞識別，最后標注詞性。在實際的系統中，這三個過程可能相互交叉，反復融合，也可能不存在明顯的先后次序。

衡量自動分詞系統的兩個主要指標是:切分精度和切分速度。對于處理海量數據的中文分詞系統來說，切分速度無疑是最重要的指標。因此，在處理海量數據的中文分詞系統中為了提高切分速度，通常使用基于基本分詞詞典(常用詞詞典)的串匹配分詞方法作為粗分手段，并在后續的處理過程中利用詞的頻度統計信息或漢語規則提高切分精度。預處理過程的粗分結果是后續過程的處理對象，因此在要求粗分效率的前提下必須盡量提高粗分結果的準確性，否則在后續過程中很難對錯誤的粗分結果進行補救，導致切分精度的下降。

本文提出一種旨在保證分詞效率的同時兼顧分詞準確率的詞語粗分模型，基于最大匹配分詞算法的中文詞語粗分模型。該模型使用切分速度快的最大匹配分詞算法對中文進行粗分，同時對最大匹配分詞算法進行改進以盡量提高粗分結果的準確性。

2 最大匹配中文分詞的基本概念

這種方法又叫做機械分詞方法，它是按照一定的策略將待分析的漢字串與一個“充分大的”機器詞典中的詞條進行配，若在詞典中找到某個字符串，則匹配成功(識別出一個詞)。按照掃描方向的不同，串匹配分詞方法可以分為正向匹配和逆向匹配;按照不同長度優先匹配的情況，可以分為最大(最長)匹配和最小(最短)匹配;按照是否與詞性標注過程相結合，又可以分為單純分詞方法和分詞與標注相結合的一體化方法。常用的幾種機械分詞方法如下:

(1)正向最大匹配法(由左到右的方向); 

(2)逆向最大匹配法(由右到左的方向); 

(3)最少切分(使每一句中切出的詞數最小)。

還可以將上述各種方法相互組合，例如，可以將正向最大匹配方法和逆向最大匹配方法結合起來構成雙向匹配法。由于漢語單字成詞的特點，正向最小匹配和逆向最小匹配一般很少使用。一般說來，逆向匹配的切分精度略高于正向匹配，遇到的歧義現象也較少。統計結果表明，單純使用正向最大匹配的錯誤率為1/169，單純使用逆向最大匹配的錯誤率為1/245.但這種精度還遠遠不能滿足實際的需要。實際使用的分詞系統，都是把機械分詞作為一種初分手段，還需通過利用各種其它的語言信息來進一步提高切分的準確率。

3 改進的最大匹配分詞算法(MMSEG)

首先來理解一下chunk，它是MMSeg分詞算法中一個關鍵的概念。Chunk中包含依據上下文分出的一組詞和相關的屬性，包括長度(Length)、平均長度(Average Length)、標準差的平方(Variance)和自由語素度(Degree Of Morphemic Freedom)。下面列出了這4個屬性: 

屬性含義

長度(Length)chuck中各個詞的長度之和

平均長度(Average Length)長度(Length)/詞數

標準差的平方(Variance)同數學中的定義

自由語素度(Degree Of Morphemic Freedom)各單字詞詞頻的對數之和

Chunk中的4個屬性只有在需要該屬性的值時才進行計算，而且只計算一次。

其次來理解一下規則(Rule)，它是MMSeg分詞算法中的又一個關鍵的概念。實際上我們可以將規則理解為一個過濾器(Filter)，過濾掉不符合要求的chunk。MMSeg分詞算法中涉及了4個規則:

規則1:取最大匹配的chunk (Rule 1: Maximum matching) 

規則2:取平均詞長最大的chunk (Rule 2: Largest average word length) 

規則3:取詞長標準差最小的chunk (Rule 3: Smallest variance of word lengths) 

規則4:取單字詞自由語素度之和最大的chunk (Rule 4: Largest sum of degree of morphemic freedom of one-character words) 

這4個規則符合漢語成詞的基本習慣。

再來理解一下匹配方式復雜最大匹配(Complex maximum matching):

復雜最大匹配先使用規則1來過濾chunks，如果過濾后的結果多于或等于2，則使用規則2繼續過濾，否則終止過濾過程。如果使用規則2得到的過濾結果多于或等于2，則使用規則3繼續過濾，否則終止過濾過程。如果使用規則3得到的過濾結果多于或等于2，則使用規則4繼續過濾，否則終止過濾過程。如果使用規則 4得到的過濾結果多于或等于2，則拋出一個表示歧義的異常，否則終止過濾過程。

4 MMSEG的分詞過程

我們以“研究生命起源“為例來簡述MMSEG算法的分詞過程。

使用規則1過濾后得到2個chunk，如下:

5 系統運行

本系統在winXP下，采用VC6.0編碼完成。在實際運行過程中，系統運行良好。對2500字的文章進行分詞用時1.7秒(其中包括讀取字典的時間)，實際分詞用時只有0.7秒左右。