NLP学习（四）规则分词-正向、逆向和双向最大匹配算法的中文分词-python3实现

规则分词

规则分词是一种机械分词方法，主要通过维护词典，在切分语句时将语句的每个字符串和词表中的词逐一匹配找到则切分，找不到则不切分。
具体包括正向最大匹配法、逆向最大匹配法和双向最大匹配法

正向最大匹配

算法描述

①从左向右取待切分汉语句的m 个字符作为匹配字段， m 为机器词典中最长词条的
字符数。
②查找机器词典并进行匹配。
若匹配成功， 则将这个匹配字段作为一个词切分出来。
若匹配不成功，则将这个匹配宇段的最后一个字去掉，剩下的字符串作为新的匹配字段， 进行再次匹配。
③重复以上过程，直到切分出所有词为止。

# 正向最大匹配
class MM(object):
    def __init__(self, dic_path):
        self.dictionary = set()
        self.maximum = 0
        with open(dic_path, 'r', encoding='utf8') as f:
            for line in f:
                line = line.strip()
                if not line:
                    continue
                self.dictionary.add(line)
                if len(line) > self.maximum:
                    self.maximum = len(line)

    def cut(self, text):
        result = []
        size = self.maximum
        text_len = len(text)
        while text_len > 0:
            word = text[0:size]
            while word not in self.dictionary:
                if len(word) == 1:
                  break
                word = word[0:len(word) - 1]
            result.append(word)
            text = text[len(word):]
            text_len = len(text)
        return result

if __name__ == '__main__':
    text = "南京市长江大桥"
    tokenizer = MM('dic.utf8')
    print(tokenizer.cut(text))

逆向最大匹配

算法描述

①从被处理文挡的末端开始匹配扫描
②每次取最末端i个字符（ i 为词典中最长词数）作为匹配字段
若匹配失败，则去掉匹配字段最前面的一个字，继续匹配。
若匹配成功则保存字段，它使用的分词词典是逆序词典， 其中的每个词条都将按逆序方式存放。
③在实际处理时，可以先将文档进行倒排处理成逆序文档。然后根据逆序词典，对逆序文档用正向最大匹配法处理即可。

由于汉语中偏正结构较多，若从后向前匹配，可以适当提高精确度。所以，逆向最大匹配法比正向最大匹配法的误差要小。
统计结果表明，单纯使用正向最大匹配的错误率为1/169 ，单纯使用逆向最大匹配的错误率为1/245

# 逆向最大匹配
class IMM(object):
    def __init__(self, dic_path):
        self.dictionary = set()
        self.maximum = 0
        with open(dic_path, 'r', encoding='utf8') as f:
            for line in f:
                line = line.strip()
                if not line:
                    continue
                self.dictionary.add(line)
                if len(line) > self.maximum:
                    self.maximum = len(line)

    def cut(self, text):
        result = []
        index = len(text)
        while index > 0:
            word = None
            for size in range(self.maximum, 0, -1):
                if index - size < 0:
                    continue
                piece = text[(index - size):index]
                if piece in self.dictionary:
                    word = piece
                    result.append(word)
                    index -= size
                    break
            if word is None:
                index -= 1
        return result[::-1]

if __name__ == '__main__':
    text = "南京市长江大桥"
    tokenizer = IMM('dic.utf8')
    print(tokenizer.cut(text))

双向最大匹配

算法描述

将正向最大匹配法得到的分词结果和逆向最大匹配法得到的结果进行比较
按照最大匹配原则，选取词数切分最少的作为结果。

双向匹配法被广泛应用

据SunM.S. 和Bejamin K.T. ( 1995 ）的研究表明，中文中90.0% 左右的句子，正向最大匹配法和逆向最大匹配法完全重合且正确，只有大概9.0% 的句子两种切分方法得到的结果不一样，但其中必有一个是正确的（歧义检测成功），只有不到1.0%的句子，使用正向最大匹配法和逆向最大匹配法的切分虽重合却是错的，或者正向最大匹配法和逆向最大匹配法切分不同但两个都不对（歧义检测失败） 。

# 正向最大匹配
class MM(object):
    def __init__(self, dic_path):
        self.dictionary = set()
        self.maximum = 0
        with open(dic_path, 'r', encoding='utf8') as f:
            for line in f:
                line = line.strip()
                if not line:
                    continue
                self.dictionary.add(line)
                if len(line) > self.maximum:
                    self.maximum = len(line)

    def cut(self, text):
        result = []
        size = self.maximum
        text_len = len(text)
        while text_len > 0:
            word = text[0:size]
            while word not in self.dictionary:
                if len(word) == 1:
                  break
                word = word[0:len(word) - 1]
            result.append(word)
            text = text[len(word):]
            text_len = len(text)
        return result
        
# 逆向最大匹配
class IMM(object):
    def __init__(self, dic_path):
        self.dictionary = set()
        self.maximum = 0
        with open(dic_path, 'r', encoding='utf8') as f:
            for line in f:
                line = line.strip()
                if not line:
                    continue
                self.dictionary.add(line)
                if len(line) > self.maximum:
                    self.maximum = len(line)

    def cut(self, text):
        result = []
        index = len(text)
        while index > 0:
            word = None
            for size in range(self.maximum, 0, -1):
                if index - size < 0:
                    continue
                piece = text[(index - size):index]
                if piece in self.dictionary:
                    word = piece
                    result.append(word)
                    index -= size
                    break
            if word is None:
                index -= 1
        return result[::-1]

def doubleMax(text, path):
    left = MM(path)
    right = IMM(path)

    leftMatch = left.cut(text)
    rightMatch = right.cut(text)

    # 返回分词数较少者
    if (len(leftMatch) != len(rightMatch)):
        if (len(leftMatch) < len(rightMatch)):
            return leftMatch
        else:
            return rightMatch
    else:  # 若分词数量相同，进一步判断
        leftsingle = 0
        rightsingle = 0
        isEqual = True  # 用以标志结果是否相同
        for i in range(len(leftMatch)):
            if (leftMatch[i] != rightMatch[i]):
                isEqual = False
            # 统计单字数
            if (len(leftMatch[i]) == 1):
                leftsingle += 1
            if (len(rightMatch[i]) == 1):
                rightsingle += 1
        if (isEqual):
            return leftMatch
        if (leftsingle < rightsingle):
            return leftMatch
        else:
            return rightMatch

if __name__ == '__main__':
    text = "南京市长江大桥"
    print(doubleMax(text,'dic.utf8'))

注：dic.utf8文件是自定义的词典文件
这个词典包括一下词汇：
南京市
南京市长
长江大桥
人名解放军
大桥