NLP之逆向最大匹配算法（BMM）

算法概述

BMM是一个基于词典的分词算法，与之相似的还有正向最大匹配算法(FMM)和双向匹配算法(BM)。
算法的大致过程为：
1、输入最大词长maxWordLength，字典wordDict，待分句子。
2、从待分句子的末尾开始向前截取长度为maxWordLength的子句，进行分词。
3、对一个子句的分词过程为，首先判断子句是否在字典中，若在，则保存这个子句，并从原句中删除这个子句，转到2。
若不在，则判断子句长度是否为1，若为1，则将单字保存，从原句中删除单字，转到2。若不为1，则将子句中最右边的一个字删除，形成新的子句，转到3。

代码实现

"""逆向最大匹配算法"""
def BMM(wordDict, maxWordLength, sentence):
    """
        @:param:
        wordDict:分词字典
        maxWordLength:最大词长
        sentence:待分句子,不要有标点符号
        @:return:
        result:分词结果，是句子分词的逆序
    """
    result = []
    while len(sentence) != 0:
        #最大词长大于待分句子时，重置最大词长
        if len(sentence) < maxWordLength:
            maxWordLength = len(sentence)
        #待分子句
        segWord = sentence[len(sentence)-maxWordLength:len(sentence)]
        while not(segWord in wordDict):
            #while 循环结束有两种情况，1是segWord存在于字典中，
            #2是，segWord为单字。
            #防止初始segWord长度为1，出错
            if len(segWord) > 1:
                segWord = segWord[1:]
            else:
                #result.append(segWord)
                #sentence = sentence[:len(sentence)-1]
                break

        #第二个循环结束，则将分词结果保存到result
        #并从原句中删除已分词
        result.append(segWord)
        sentence = sentence[:len(sentence)-len(segWord)]
    return result
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

运行结果

def main():
    maxWordLength, sougoDict = readDict("sougoDict.txt")

    sentence1 = "今天天气怎么样"
    result1 = BMM(sougoDict, maxWordLength, sentence1)
    printResult(result1)

    sentence2 = "最高买价和最低买价分别是多少"
    result2 = BMM(sougoDict, maxWordLength, sentence2)
    printResult(result2)

    sentence3 = "乱七八糟的字绗舆硎闿庹"
    result3 = BMM(sougoDict, maxWordLength, sentence3)
    printResult(result3)
1
2
3
4
5
6
7
8
9
10
11
12
13
14

运行结果

说明
这个代码只是一个基础版本，没有经过完整测试，仅供参考，如有什么问题，还望多多指教。

分词词典
分词词典是从参考文章《千万级巨型汉语词库分享》中截取出的一小部分，共有30万常用词，需说明的是字典不是最新的。
下载链接

参考文章
中文分词入门之最大匹配法
千万级巨型汉语词库分享