最大比對算法

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

中文名

最大比對算法

外文名

Maximum Matching

應用學科

數學，計算機，資料結構

适用領域範圍

分詞，語義了解

算    法

MM，RMM，BMM

簡    稱

RMM法

目錄

1. 1 ​​簡介​​
2. 2 ​​正向最大比對算法思想​​
3. 3 ​​逆向最大比對算法思想​​

簡介

編輯

逆向最大比對法通常簡稱為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]的時候，發現"計算語言學課"并不是詞表中的詞，也不是詞的字首。是以可以切分出前面最大的詞——"​​計算語言學​​"。

由此可見，最大比對出的詞必須保證下一個掃描不是詞表中的詞或詞的字首才可以結束 [1]  。

逆向最大比對算法思想

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

待分詞句子： 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在詞表，分割結束 [2]  。