中文分词算法--最大匹配算法

在 Fri 25 March 2016 发布于 自然语言处理 分类

中文分词算法分两大方向:一是机械分词算法, 一是基于统计的分词算法。本篇文章主要介绍机械分词算法中最基础的算法: 最大匹配算法(Maximum Matching, 一下简称MM算法)。 MM算法有三种: 正向最大匹配算法, 逆向最大匹配算法。双向最大匹配算法是取前面两种分词算法切分出来词, 然后根据一定的策略筛出切分效果最好的最为最终的切分结果。下面一一介绍这三种分词方法。

正向最大匹配算法和逆向最大匹配算法

最大匹配算法以字典为例子, 在目标串中取出长度为最大词长(按需任意配置)的连续词在字典中进行扫描匹配。其流程图如下:

forward_max_match_algorithm

依据此逻辑, 给出简单的python实现。对于逆向最大匹配算法, 其和正向最大匹配算法的原理一样, 只是从后向前切词。 这里的字典使用的是搜狗提供的字典, 点击下载

#!/usr/bin/env python
# encoding: utf-8
# -*- coding: UTF-8 -*-

import os
import sys 

def get_trie(filepath):
    trie = {}
    reader = open(filepath, 'r')
    for line in reader:
        try:
            p = trie
            encodeLine = line.decode('GBK')
            sentence = encodeLine.split('\t')[0].strip()
            for word in sentence:
                if word not in p:
                    p[word] = {}
                p = p[word]
            p[None] = {}
        except Exception, err:
            print line, err 
            continue
    reader.close()
    return trie

def inTrie(trie, sentence):
    p = trie
    for word in sentence:
        if word not in p:
            return False
        p = p[word]
    if not p or None in p:
        return True
    return False

#正向最大匹配算法
def ForwardMMSeg(sentence, trie, maxLen = 0): 
    pdb.set_trace()
    if not isinstance(sentence, unicode):
        print "input must be unicode"
    if maxLen == 1:
        return [word for word in sentence]
    result = []
    while len(sentence) != 0:
        if len(sentence) == 1:
            result.append(sentence)
            break
        if maxLen == 0:
            preWord = sentence
        else:
            preWord = sentence[:maxLen]
        while preWord:
            if len(preWord) == 1:
                result.append(preWord)
                break
            if inTrie(trie, preWord):
                result.append(preWord)
                break
            else:
                preWord = preWord[:-1]
        sentence = sentence.replace(preWord, u'', 1)
    return result


#逆向最大匹配算法
def ReverseMMSeg(sentence, trie, maxLen = 0): 
    if not isinstance(sentence, unicode):
        print "input must be unicode"
    if maxLen == 1:
        return [word for word in sentence]
    result = []
    while len(sentence) != 0:
        if len(sentence) == 1:
            result.append(sentence)
            break
        if maxLen == 0:
            preWord = sentence
        else:
            preWord = sentence[-maxLen:]
        while preWord:
            if len(preWord) == 1:
                result.append(preWord)
                break
            if inTrie(trie, preWord):
                result.append(preWord)
                break
            else:
                preWord = preWord[1:]
        sentence = sentence[::-1].replace(preWord[::-1], u'', 1)[::-1]
    return result[::-1]



if __name__ == '__main__':
    pdb.set_trace()
    trie = get_trie(sys.argv[1])
    pdb.set_trace()
    print(ForwardMMSeg(u'单机游戏,中文输入法, 水灵儿她出污泥而不染', trie, maxLen = 10)) # ['单机游戏', '中文输入法', '水灵儿', '她', '出污泥而不染']
    print(ForwardMMSeg(u'天降大任于斯人也必先苦其心志劳其筋骨饿其体肤空乏其身行指乱其所为所以动心忍性曾益其所不能', trie, maxLen = 5)) #['天降大任','于', '斯人也', '必先', '苦', '其心', '志', '劳', '其', '筋骨', '饿', '其', '体', '肤', '空乏', '其身','行', '指', '乱', '其所', '为', '所以', '动心忍性', '曾益', '其所', '不能']
    print(ForwardMMSeg(u'结婚的和尚未结婚的', trie, maxLen = 5)) #['结婚', '的', '和尚', '未', '结婚', 的']
    print(ReverseMMSeg(u'结婚的和尚未结婚的', trie, maxLen = 5)) #['结婚', '的', '和', '尚未', '结婚', '的']
双向最大匹配算法

参考文献:

[1]中文分词入门之最大匹配法