最大匹配算法

最大匹配算法主要包括正向最大匹配算法、逆向最大匹配算法、雙向匹配算法等。 其主要原理都是切分出單字串，然後和詞庫進行比對，如果是一個詞就記錄下來， 否則通過增加或者減少一個單字，繼續比較，一直還剩下一個單字則終止，如果該單字串無法切分，則作為未登錄處理。

基本介紹

• 中文名：最大匹配算法
• 外文名：Maximum Matching
• 套用學科：數學，計算機，數據結構
• 適用領域範圍：分詞，語義理解
• 算法：MM，RMM，BMM
• 簡稱：RMM法

簡介

逆向最大匹配法通常簡稱為RMM法。RMM法的基本原理與MM法相同 ,不同的是分詞切分的方向與MM法相反，而且使用的分詞辭典也不同。逆向最大匹配法從被處理文檔的末端開始匹配掃描，每次取最末端的2i個字元（i字字串）作為匹配欄位，若匹配失敗，則去掉匹配欄位最前面的一個字，繼續匹配。相應地，它使用的分詞詞典是逆序詞典，其中的每個詞條都將按逆序方式存放。在實際處理時，先將文檔進行倒排處理，生成逆序文檔。然後，根據逆序詞典，對逆序文檔用正向最大匹配法處理即可。
例子：’我一個人吃飯’
反向最大匹配方式，最大長度為5

個人吃飯

人吃飯
吃飯 ====》得到一個詞– 吃飯
我一個人
一個人
個人 ====》得到一個詞– 個人
我一
一 ====》得到一個詞– 一
我 ====》得到一個詞– 我

最後反向最大匹配的結果是：

/我/一/個人/吃飯/

　

正向最大匹配算法思想

正向最大匹配算法：從左到右將待分詞文本中的幾個連續字元與詞表匹配，如果匹配上，則切分出一個詞。但這裡有一個問題：要做到最大匹配，並不是第一次匹配到就可以切分的 。我們來舉個例子：

待分詞文本： sentence[]={"計"，"算"，"語"，"言"，"學"，"課"，"程"，"有"，"意"，"思"}

詞表： dict[]={"計算", "計算語言學", "課程", "有", "意思"} （真實的詞表中會有成千上萬個已經平時我們使用的分好的詞語）

(1) 從sentence[1]開始，當掃描到sentence[2]的時候，發現"計算"已經在詞表dict[]中了。但還不能切分出來，因為我們不知道後面的詞語能不能組成更長的詞(最大匹配)。

(2) 繼續掃描content[3]，發現"計算語"並不是dict[]中的詞。但是我們還不能確定是否前面找到的"計算語"已經是最大的詞了。因為"計算語"是dict[2]的前綴。

(3) 掃描content[4]，發現"計算語言"並不是dict[]中的詞。但是是dict[2]的前綴。繼續掃描：

(3) 掃描content[5]，發現"計算語言學"是dict[]中的詞。繼續掃描下去：

(4) 當掃描content[6]的時候，發現"計算語言學課"並不是詞表中的詞，也不是詞的前綴。因此可以切分出前面最大的詞——"計算語言學"。

由此可見，最大匹配出的詞必須保證下一個掃描不是詞表中的詞或詞的前綴才可以結束。

逆向最大匹配算法思想

逆向匹配算法大致思路是從右往左開始切分。我們還是用上面的例子：

待分詞句子： sentence[]={"計算語言學課程有意思"}

詞表： dict[]={"計算", "計算語言學", "課程", "有", "意思"}

首先我們定義一個最大分割長度5，從右往左開始分割：

(1)首先取出來的候選詞W是 “課程有意思”。

(2) 查詞表，W不在詞表中，將W最左邊的第一個字去掉，得到W“程有意思”；

(3) 查詞表，W也不在詞表中，將W最左邊的第一個字去掉，得到W“有意思”；

(4) 查詞表，W也不在詞表中，將W最左邊的第一個字再去掉，得到W“意思”；

(5) 查詞表，W在詞表中，就將W從整個句子中拆分出來，此時原句子為“計算語言學課程有”

(6)根據分割長度5，截取句子內容，得到候選句W是“言學課程有”；

(7) 查詞表，W不在詞表中，將W最左邊的第一個字去掉，得到W“言學課程有”；

(8) 查詞表，W也不在詞表中，將W最左邊的第一個字去掉，得到W“學課程有”；

(9) 依次類推，直到W為“有”一個詞的時候，這時候將W從整個句子中拆分出來，此時句子為“計算語言學課程”

(10)根據分割長度5，截取句子內容，得到候選句W是“算語言學課程”；

(11)查詞表，W不在詞表中，將W最左邊的第一個字去掉，得到W“語言學課程”；

(12) 依次類推，直到W為“課程”的時候，這時候將W從整個句子中拆分出來，此時句子為“計算語言學”

(13)根據分割長度5，截取句子內容，得到候選句W是“計算語言學”；

(14) 查詞表，W在詞表，分割結束。