目錄

一，正向最大匹配算法（FMM）

?二，反向最大匹配算法（RMM)

---

一，正向最大匹配算法（FMM）

????????正向最大匹配分詞（Forward maximum matching segmentation）通常簡稱為FＭＭ法。其基本思想為：假定分詞詞典中的最長詞有i個漢字字符，則用被處理文檔的當前字串中的前i個字作為匹配字段，查找字典。若字典中存在這樣的一個字詞，則匹配成功，匹配字段被作為一個詞切分出來。如果詞典中找不到這樣的一個字詞，則匹配失敗，將匹配字段中的最后一個字去掉，對剩下的字串重新進行匹配處理。如此進行下去，直到匹配成功，即切分出一個詞或剩余字串的長度為零為止。這樣就完成了一輪匹配，然后取下一個i字字串進行匹配處理，直到文檔被掃描完為止。

例子:

設變量dt為字典，s為待切字符串，result為被切后的詞

令dt = ['abc', 'bcd'] ,s = ['abcd'],則?result = ['abc', 'd']

原理：字典中最大字符長度為‘abc’和‘bcd’，正向選取‘abc’，則拿‘abc’去匹配，s中匹配到‘abc’后切出，之后字典中最長的是‘d’，匹配到s的‘d’后切出，得到切片后的result?= ['abc', 'd']

代碼實現：?

def FMM(dt, s):  # 正向最大匹配算法result = []   max_len = max([len(i) for i in dt])    # 選取字典里長度最大的字符串start = 0while start != len(s):    # 判斷列表不為空，建立循環                index = start + max_len    # 從0開始正向索引最大長度的字符串if index > len(s):         # 判斷是否溢出列表index = len(s)for _ in range(max_len):    t = s[start:index]       # t是切片if t in dt or len(t) == 1:result.append(t)start = indexbreakindex -= 1 # 為了保證算法能夠掃描到所有字符return result

?二，反向最大匹配算法（RMM)

????????逆向最大匹配算法（Reserve?maximum matching segmentation）的基本原理與正向最大匹配法相同，不同的是分詞切分的方向與FMM法相反。逆向最大匹配法從被處理文檔的末端開始匹配掃描，每次取最末端的i個字符（為詞典中最長詞數）作為匹配字段，若匹配失敗，則去掉匹配字段最前面的一個字，繼續匹配。相應地，它使用的分詞詞典是逆序詞典，其中的每個詞條都將按逆序方式存放。在實際處理時，先將文檔進行倒排處理，生成逆序文檔。然后，根據逆序詞典，對逆序文檔用正向最大匹配法處理即可。

例子：

設變量dt為字典，s為待切字符串，result為被切后的詞

令dt = ['abc', 'bcd'] ,s = ['abcd'],則?result = ['a', 'bcd']

原理：字典中最大長度為'abc'，‘bcd’，反向選取‘bcd’，則拿‘bcd’去匹配，s中匹配到‘bcd’后切出，之后字典中最長的是‘a’，匹配到s的‘a’后切出，得到切片后的result?= ['a', 'bcd']

代碼實現：

def RMM(dt, s): # 反向最大匹配算法result = []max_len = max([len(i) for i in dt]) # 選取字典里長度最大的字符串start = len(s)while start != 0:    #判斷列表不為空，建立循環index = start - max_len    # 從列表最后開始索引最大長度的字符串if index < 0:        # 判斷是否溢出列表index = 0for _ in range(max_len):t = s[index:start]    # t是切片if t in dt or len(t) == 1:result.insert(0, t)    # 在最前面插入start = indexbreakindex += 1return result

三，雙向匹配算法（BM）

????????雙向最大匹配算法的原理就是將正向最大匹配算法和逆向最大匹配算法進行比較，從而選擇正確的分詞方式。

????????比較原則/步驟：

????????1.比較兩種匹配算法的結果

????????2.如果分詞數量結果不同：選擇數量較少的那個

????????3.如果分詞數量結果相同

? ????????????????1.分詞結果相同，返回任意一個

? ????????????????2.分詞結果不同，返回單字數較少的一個

? ????????????????3.若單字數也相同，任意返回一個

例子:

設變量dt為字典，s為待切字符串，result_1為被正向切后的詞，result_2為被反向切后的詞

令dt = ['abc', 'deab'] ,s = ['abcdeabc'],則?result_1?= ["abc", "deab", "c"]，result_2=["c", "deab"]

原理：字典中最大長度為'deab'，則拿‘deab’去匹配，s中匹配到‘deab’后切出，之后字典中最長的是‘abc’，匹配到s的‘abc’后切出，得到切片后的result_1?= ["abc", "deab", "c"]，同理result_2=["c", "deab"]，其中正向的切詞有三個，逆向有兩個，數量不相等選擇分詞數量 少的，則輸出逆向切詞result_2=["c", "deab"]

def BM(dt, s): # 雙向最大切詞r1 = FMM(dt, s)r2 = RMM(dt, s)if len(r1) == len(r2):if r1 == r2:return r1else:r1_cnt = len([i for i in r1 if len(i)==1])r2_cnt = len([i for i in r2 if len(i)==1])return r1 if r1_cnt < r2_cnt else r2else:return r1 if len(r1) < len(r2) else r2