詞是自然語言中能夠獨立運用的最小單位，是自然語言處理的基本單位。

自動分詞分析就是利用計算機對自然語言的形態(tài)進(jìn)行分析，判斷詞的結(jié)構(gòu)和類別等。

最大匹配法（Maximum Match Method）

• 正向最大匹配算法（Forward MM，FMM）
• 逆向最大匹配算法（Backward MM，BMM）
• 雙向最大匹配法（Bi-directional MM）

算法流程

前向最?匹配算法（FMM）：

（1）待切分的漢字串 s1 ，已切分的漢字串 s2（初始為空）；

（2）如果 s1 為空串，轉(zhuǎn)到（6）；

（3）從 s1 的左邊復(fù)制?個?串 w 作為候選詞， w 盡可能長，但不超過最?詞長；

（4）如果在詞表中能找到 w，或者 w 的長度為2（這個數(shù)值可以自己根據(jù)情況設(shè)定，通常為詞表內(nèi)最短的詞的長度），那么，將 w 和?個界詞標(biāo)記?起加到 s2?的右邊，并從 s1 的左邊去掉 w，轉(zhuǎn) 到（2）；

（5）去掉w的最后?個漢字，轉(zhuǎn)到（4）；

（6）結(jié)束。

實例

給定詞表：

['他', '是', '研究', '研究?', '?物', '物化', '化學(xué)', '?物化學(xué)', '的', '?位', '科學(xué)家', '學(xué)']

待劃分句?：

"他是研究?物化學(xué)的?位科學(xué)家"

最?詞長：

MaxWordLength = 8 (漢字)

劃分過程

FMM劃分過程：

1、考慮子串 "他是研究生物化學(xué)" ，判斷其不再給定詞表中，因此，刪除最后一個漢字，考慮子串 "他是研究生物化"，再次判斷其不再給定詞表中，因此，再次刪除最后一個漢字；重復(fù)這個過程，直到最后只剩一個漢字或考慮的子串在給定的詞表中，通過這一輪劃分，可以將 '他' 劃分出來。

2、將 '他' 從待劃分句子中排出，考慮子串 "是研究生物化學(xué)的"。重復(fù)（1）中的步驟，最終可以把 '是' 劃分出來。

3、重復(fù)上述的步驟，可以得到最終的劃分結(jié)果。

FMM劃分結(jié)果：他/是/研究?/物化/學(xué)/的/?/位/科學(xué)家

BMM的原理和FMM差不多，只不過BMM是從后往前劃分，如上述例子，BMM先考慮子串 "化學(xué)的一位科學(xué)家"，不再給定詞表中，BMM刪除的是子串的第一個漢字。

BMM劃分結(jié)果：他/是/研究/?物化學(xué)/的/?位/科學(xué)家

從劃分結(jié)果可以看出，FMM和BMM的劃分并不同，在這個例子中顯然BMM的劃分更好。

代碼實現(xiàn)

# -*- coding:utf-8 -*-def FMM(user_dict, sentence):""""前向最大匹配算法 FMM"""segment_words = [] # 用于保存已經(jīng)劃分好的詞max_len = max([len(item) for item in user_dict]) # 獲得給定的詞表中最長詞的長度start = 0 # 起始劃分位置，FMM從前往后劃分nums = 1 # 記錄劃分輪數(shù)print("FMM:")print("*****開始切分*****")while start != len(sentence):index = start + max_len # 每一輪劃分考慮 index-start=max_len 長度if index > len(sentence): # 如果當(dāng)前的 index 位置超過了句子長度，則讓其指向句子的最后index = len(sentence)for i in range(max_len):print(sentence[start:index])# 如果當(dāng)前考慮的詞在我們給定的詞表中或者詞的長度已經(jīng)等于1，就將其加入到劃分好的列表中if (sentence[start:index] in user_dict)\or (len(sentence[start:index]) == 1):segment_words.append(sentence[start:index])start = indexbreakindex -= 1print('當(dāng)前已切分：', segment_words)print("————第 %d 輪結(jié)束————" % nums)nums += 1return segment_wordsdef BMM(user_dict, sentence):""""逆向最大匹配算法 BMM"""# 大部分代碼同F(xiàn)MM一致，只需把start轉(zhuǎn)換為end即可segment_words = []max_len = max([len(item) for item in user_dict])end = len(sentence) # 起始劃分位置，BMM從后往前劃分nums = 1 # 記錄劃分輪數(shù)print("BMM:")print("*****開始切分*****")while end != 0:index = end - max_len # 每一輪劃分考慮 end-index=max_len 長度if index < 0:index = 0for i in range(max_len):print(sentence[index:end])if (sentence[index:end] in user_dict)\or (len(sentence[index:end]) == 1):segment_words.append(sentence[index:end])end = indexbreakindex += 1print('當(dāng)前已切分：', segment_words)print("————第 %d 輪結(jié)束————" % nums)nums += 1return segment_wordsif __name__ == '__main__':user_dict = ['時間', '就', '是', '生命'] # 給定詞表sentence = "時間就是生命" # 待劃分的例句# 使用FMM劃分segment_words = FMM(user_dict, sentence)print("最終結(jié)果：\n", segment_words)print()# 使用BMM劃分segment_words = BMM(user_dict, sentence)print("最終結(jié)果：\n", segment_words[::-1]) # 由于BMM是逆向劃分的，將其倒轉(zhuǎn)就與例句中詞的出現(xiàn)順序一致了

上述代碼考慮的實例：

詞表：['時間', '就', '是', '生命']

例句："時間就是生命"

劃分結(jié)果：

FMM: *****開始切分***** 時間 當(dāng)前已切分： ['時間'] ————第 1 輪結(jié)束———— 就是 就 當(dāng)前已切分： ['時間', '就'] ————第 2 輪結(jié)束———— 是生 是 當(dāng)前已切分： ['時間', '就', '是'] ————第 3 輪結(jié)束———— 生命 當(dāng)前已切分： ['時間', '就', '是', '生命'] ————第 4 輪結(jié)束———— 最終結(jié)果：['時間', '就', '是', '生命']BMM: *****開始切分***** 生命 當(dāng)前已切分： ['生命'] ————第 1 輪結(jié)束———— 就是 是 當(dāng)前已切分： ['生命', '是'] ————第 2 輪結(jié)束———— 間就 就 當(dāng)前已切分： ['生命', '是', '就'] ————第 3 輪結(jié)束———— 時間 當(dāng)前已切分： ['生命', '是', '就', '時間'] ————第 4 輪結(jié)束———— 最終結(jié)果：['時間', '就', '是', '生命']進(jìn)程已結(jié)束，退出代碼為 0

從這個例子可以看出，FMM和BMM的劃分結(jié)果相同，我們現(xiàn)在將代碼的詞表和例句改為上述的例子：

詞表：['他', '是', '研究', '研究?', '?物', '物化', '化學(xué)', '?物化學(xué)', '的', '?位', '科學(xué)家', '學(xué)']

例句："他是研究?物化學(xué)的?位科學(xué)家"

劃分結(jié)果：

FMM: *****開始切分***** 他是研究 他是研 他是 他 當(dāng)前已切分： ['他'] ————第 1 輪結(jié)束———— 是研究? 是研究 是研 是 當(dāng)前已切分： ['他', '是'] ————第 2 輪結(jié)束———— 研究?物 研究? 當(dāng)前已切分： ['他', '是', '研究?'] ————第 3 輪結(jié)束———— 物化學(xué)的 物化學(xué) 物化 當(dāng)前已切分： ['他', '是', '研究?', '物化'] ————第 4 輪結(jié)束———— 學(xué)的?位 學(xué)的? 學(xué)的 學(xué) 當(dāng)前已切分： ['他', '是', '研究?', '物化', '學(xué)'] ————第 5 輪結(jié)束———— 的?位科 的?位 的? 的 當(dāng)前已切分： ['他', '是', '研究?', '物化', '學(xué)', '的'] ————第 6 輪結(jié)束———— ?位科學(xué) ?位科 ?位 當(dāng)前已切分： ['他', '是', '研究?', '物化', '學(xué)', '的', '?位'] ————第 7 輪結(jié)束———— 科學(xué)家 當(dāng)前已切分： ['他', '是', '研究?', '物化', '學(xué)', '的', '?位', '科學(xué)家'] ————第 8 輪結(jié)束———— 最終結(jié)果：['他', '是', '研究?', '物化', '學(xué)', '的', '?位', '科學(xué)家']BMM: *****開始切分***** 位科學(xué)家 科學(xué)家 當(dāng)前已切分： ['科學(xué)家'] ————第 1 輪結(jié)束———— 學(xué)的?位 的?位 ?位 當(dāng)前已切分： ['科學(xué)家', '?位'] ————第 2 輪結(jié)束———— 物化學(xué)的 化學(xué)的 學(xué)的 的 當(dāng)前已切分： ['科學(xué)家', '?位', '的'] ————第 3 輪結(jié)束———— ?物化學(xué) 當(dāng)前已切分： ['科學(xué)家', '?位', '的', '?物化學(xué)'] ————第 4 輪結(jié)束———— 他是研究 是研究 研究 當(dāng)前已切分： ['科學(xué)家', '?位', '的', '?物化學(xué)', '研究'] ————第 5 輪結(jié)束———— 他是 是 當(dāng)前已切分： ['科學(xué)家', '?位', '的', '?物化學(xué)', '研究', '是'] ————第 6 輪結(jié)束———— 他 當(dāng)前已切分： ['科學(xué)家', '?位', '的', '?物化學(xué)', '研究', '是', '他'] ————第 7 輪結(jié)束———— 最終結(jié)果：['他', '是', '研究', '?物化學(xué)', '的', '?位', '科學(xué)家']進(jìn)程已結(jié)束，退出代碼為 0

FMM的劃分結(jié)果：

['他', '是', '研究?', '物化', '學(xué)', '的', '?位', '科學(xué)家']

BMM的劃分結(jié)果：

['他', '是', '研究', '?物化學(xué)', '的', '?位', '科學(xué)家']

可以看出兩者的劃分結(jié)果并不相同。

總結(jié)

以上是生活随笔為你收集整理的用python实现FMM和BMM的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。