中文分詞中基于詞典的正向最大匹配和逆向最大匹配
正向最大匹配和逆向最大匹配步驟類(lèi)似捎琐，只是方向不同，我以正向匹配為例，先用一句話去總結(jié)它：
在做整個(gè)正向成詞的過(guò)程中，我們做了兩個(gè)步驟飘弧，首先按照字典最大長(zhǎng)度進(jìn)行對(duì)原始文本進(jìn)行切分，然后逐漸去掉右邊一個(gè)單字砚著，去查看剩余文本在字典是否存在眯牧，依次迭代。
上面這句話只看不太好理解赖草，我來(lái)個(gè)簡(jiǎn)單的例子，如下：
我要被切分的句子是這樣的：”今天天氣真不錯(cuò)啊“
我的字典是這樣的：[今天,天天,天氣,真不錯(cuò),不錯(cuò),啊,哈哈哈哈哈]
對(duì)于字典這一塊剪个，最粗糙的就是存成列表秧骑，優(yōu)化一點(diǎn)可以存成字典樹(shù)，這里簡(jiǎn)化一點(diǎn)扣囊，我們存成列表乎折。
我字典的最大長(zhǎng)度是 “哈哈哈哈哈”，為5
所以我第一次正向匹配就是：
今天天氣真 # 取原始文本前五個(gè)單詞侵歇，查看是否存在于字典骂澄，否，刪除底部
今天天氣 # 查看是否存在于字典惕虑，否坟冲，刪除底部
今天天 # 查看是否存在于字典，否溃蔫，刪除底部
今天 #匹配到字典中的“今天”這個(gè)詞
第二次正向匹配是這樣的：
天氣真不錯(cuò)啊 # 因?yàn)椤苯裉臁耙呀?jīng)被匹配到了健提，所以我們不在考慮，取剩余文本的前五個(gè)單詞伟叛，查看是否存在于字典私痹，否，刪除底部
天氣真不錯(cuò) #查看是否存在于字典统刮，否紊遵，刪除底部
天氣真不 #查看是否存在于字典，否侥蒙，刪除底部
天氣真 #查看是否存在于字典暗膜，否，刪除底部
天氣 #匹配到字典中的“天氣“這個(gè)單詞
第三次正向匹配的過(guò)程：
真不錯(cuò)啊 # 剩余文本不夠5個(gè)辉哥，我們?nèi)⌒¤肷剑?個(gè)攒射，查看是否存在于字典，否恒水，刪除底部
真不錯(cuò) # 匹配到”真不錯(cuò)“ 這個(gè)單詞
第四次正向匹配的過(guò)程：
啊 # 字典中沒(méi)有與之相關(guān)的單詞会放，由于長(zhǎng)度已經(jīng)為1，直接單獨(dú)成詞就可以
在做整個(gè)正向成詞的過(guò)程中钉凌，我們做了兩個(gè)步驟咧最，首先按照字典最大長(zhǎng)度進(jìn)行對(duì)原始文本進(jìn)行切分（需要比對(duì)最大長(zhǎng)度和文本的長(zhǎng)度，如果文本長(zhǎng)度不夠的話御雕，就取文本長(zhǎng)度矢沿，總之取小。比如第三次正向匹配”真不錯(cuò)啊“這剩余的四個(gè)字就不夠5個(gè)）酸纲， 然后逐漸去掉右邊一個(gè)單字捣鲸，去查看剩余文本在字典是否存在，依次迭代闽坡。
其實(shí)逆向匹配是很類(lèi)似的過(guò)程栽惶，只不過(guò)方向變了，需要注意的是我們始終刪除的是底部單詞：
第一次逆向匹配：
氣真不錯(cuò)啊 # 查看是否存在于字典疾嗅，否外厂，刪除底部
真不錯(cuò)啊 # 查看是否存在于字典，否代承，刪除底部
不錯(cuò)啊 # 查看是否存在于字典汁蝶，否，刪除底部
錯(cuò)啊 # 查看是否存在于字典论悴，否掖棉，刪除底部
啊 # 字典中沒(méi)有與之相關(guān)的單詞，由于長(zhǎng)度已經(jīng)為1膀估，直接單獨(dú)成詞就可以
...... ...... ......
雙向最大匹配算法就是兩種方法都切一遍啊片，從中選擇一種比較好的，標(biāo)準(zhǔn)就是：大顆粒度詞越多越好玖像，非詞典詞和單字詞越少越好.
對(duì)于代碼的實(shí)現(xiàn)紫谷，我記得是好久之前從網(wǎng)上down下來(lái)的，具體來(lái)源忘了捐寥，不過(guò)都大同小異笤昨，自己寫(xiě)也沒(méi)啥問(wèn)題。
我在這里啰嗦的講一下大致思路握恳，如果您覺(jué)得比較簡(jiǎn)單瞒窒，或者只想看代碼，跳過(guò)就可以：
基本思路是這樣的乡洼，我有一個(gè)存儲(chǔ)我詞典的列表崇裁，以詞典中最大長(zhǎng)度為基線順序?qū)υ嘉谋具M(jìn)行切分匕坯，迭代查看當(dāng)前切分詞是否在詞典，在就算一個(gè)詞拔稳，不在的話葛峻，當(dāng)前詞長(zhǎng)度減一，就是往前縮小一個(gè)詞巴比，繼續(xù)進(jìn)行上述活動(dòng)术奖。直至長(zhǎng)度為1，是最后的一個(gè)迭代條件轻绞。
在寫(xiě)代碼的時(shí)候采记，我自己覺(jué)得從兩個(gè)方面來(lái)掌握，一個(gè)是從小方面政勃，怎么講唧龄，就是比如說(shuō)我的字典最大的長(zhǎng)度是5個(gè)單詞，我在5個(gè)單詞迭代的去找有沒(méi)有在字典的中的詞奸远，這是一個(gè)while循環(huán)选侨。
還有一個(gè)方面是大的方面，就是我現(xiàn)在5個(gè)單詞迭代完了然走，比如找到了一個(gè)長(zhǎng)度為2的在字典中的詞（需要注意的是如果沒(méi)有在字典中，那么長(zhǎng)度就是1的單字就可以加進(jìn)去了）戏挡，然后我要做的就是把這兩個(gè)單詞之后的字段作為輸入芍瑞，再重復(fù)上面這個(gè)過(guò)程，這個(gè)是大的方面褐墅，是另一個(gè)While循環(huán)
## 正向最大匹配算法
def cut_words(split_sentence,words_dic):
#統(tǒng)計(jì)詞典中最長(zhǎng)的詞
max_length = max(len(word) for word in words_dic)
sentence = split_sentence.strip() ## 簡(jiǎn)單清理一下
#統(tǒng)計(jì)序列長(zhǎng)度
words_length = len(sentence) ## 在第二個(gè)循環(huán)的時(shí)候拆檬，我需要不停的和字典最大長(zhǎng)度比較，取最小值作為基線
#存儲(chǔ)切分好的詞語(yǔ)
cut_word_list = []
while words_length > 0: ## 第二個(gè)循環(huán)妥凳，找到一個(gè)之后竟贯，循環(huán)的去找下一個(gè)符合要求的
max_cut_length = min(max_length, words_length)
subSentence = sentence[0 : max_cut_length]
while max_cut_length > 0: ## 第一個(gè)循環(huán)，迭代找到符號(hào)字典的
if subSentence in words_dic:
cut_word_list.append(subSentence)
break
elif max_cut_length == 1:
cut_word_list.append(subSentence)
break
else:
max_cut_length = max_cut_length -1
subSentence = subSentence[0:max_cut_length]
sentence = sentence[max_cut_length:]
words_length = words_length - max_cut_length
return cut_word_list
input_str="今天天氣真不錯(cuò)啊逝钥，適合出去旅游"
bmm_word_list = cut_words(input_str, words_dic)
print(bmm_word_list)
##逆向最大匹配
def cut_words(raw_sentence,words_dic):
#統(tǒng)計(jì)詞典中詞的最長(zhǎng)長(zhǎng)度
max_length = max(len(word) for word in words_dic)
sentence = raw_sentence.strip()
#統(tǒng)計(jì)序列長(zhǎng)度
words_length = len(sentence)
#存儲(chǔ)切分出來(lái)的詞語(yǔ)
cut_word_list = []
#判斷是否需要繼續(xù)切詞
while words_length > 0:
max_cut_length = min(max_length, words_length)
subSentence = sentence[-max_cut_length:]
while max_cut_length > 0:
if subSentence in words_dic:
cut_word_list.append(subSentence)
break
elif max_cut_length == 1:
cut_word_list.append(subSentence)
break
else:
max_cut_length = max_cut_length -1
subSentence = subSentence[-max_cut_length:]
sentence = sentence[0:-max_cut_length]
words_length = words_length -max_cut_length
cut_word_list.reverse()
return cut_word_list
