正、反向分词算法

Table of Contents

1 反向最大匹配分词

假设要分割句子S:

我在别人那里听说你是黑客

分割出的结果应该是:

我/在/别人/那里/听说/你/是/黑客

首先反向取出最多N个字,这里N=5,所以第一次取出“说你是黑客” 然后再将这句话逐步带入词典查询,如果没找到,就去掉最后个字。整个过程中会产生两个结果:

结果1:

找到这个词了,那么这句话的字符串变成这个词余下的字符串;

结果2:

没有找到,但必须将最后一个字作为一个单独的词分割出来(往往是“的”、“是”之类的字)

这句话的分割过程如下:

1.1 第一轮

1 说你是黑客-> 没有找到 2 你是黑客-> 没有找到 3 是黑客-> 没有找到 4 黑客-> 找到

1.2 第二轮

S=里听说你是

1 里听说你是-> 没有找到 2 说你是-> 没有找到 3 你是-> 没有找到 4 是 -> 遇到剩下一个字,所以单独成为一个词

1.3 第三轮

S=那里听说你

1 那里听说你-> 没有找到 2 里听说你-> 没有找到 3 听说你-> 没有找到 4 说你-> 没有找到 4 你 -> 遇到剩下一个字,所以单独成为一个词

1.4 第四轮

S=人那里听说

1 人那里听说-> 没有找到 2 那里听说-> 没有找到 3 里听说-> 没有找到 4 听说-> 找到,进入第五轮

1.5 第五轮

S=在别人那里

1 在别人那里-> 没有找到 2 别人那里-> 没有找到 3 人那里-> 没有找到 4 那里-> 找到,进入第六轮

1.6 第六轮

S=我在别人

1 我在别人-> 没有找到 2 在别人-> 没有找到 3 别人-> 找到,进入第七轮

1.7 第七轮

S=我在

1 我在-> 没有找到 2 在 -> 只剩下一个字,所以单独作为一个词

1.8 第八轮

S=我

1 我-> 仅剩一个字,结束分词

1.9 实现代码

# create date: 2013-06-23
# last update: 2013-06-23

word_dict = list()


def load_dict():
    """
    将词典加载到内存中
    """
    # 需要自己去找一份字典文件,命名为words.dic
    with open('words.dic', 'r') as f:
        for line in f:
            line = line.strip()
            line = line.decode('utf-8')
            word_dict.append(line)


def split_words(words):
    max_len = 5            # 每次取max_len个字
    split_result = list()    # 分词结果

    while words:
        # 先取max_len个字出来分词
        text = words[0 - max_len:]
        # 标志位,如果为True表示找到词了
        is_find = False

        # 开始尝试分词
        while not is_find:
            if text in word_dict:
                is_find = True
                split_result.insert(0, text)
                # 后移
                words = words[:0-len(text)]
                # 如果只剩下一个字了,它单独成为一个词
                # 比如“我的是他的”这句话里就没有一组词,所以要将它们分割成一个个字
                # 这里参考函数注释中的“结果1”
            elif len(text) == 1:
                is_find = True
                split_result.insert(0, text)
                words = words[:-1]
                # 如果没有找到,就去掉第一位
            else:
                text = text[1:]

    return split_result


if __name__ == '__main__':
    load_dict()
    print('/'.join(split_word(u'我在别人那里听说你是黑客')))

2 正向最大匹配分词

假设要分割句子S:

我在别人那里听说你是黑客

分割出的结果应该是:

我/在/别人/那里/听说/你/是/黑客

首先取出最多N个字,这里N=5,所以第一次取出“我在别人那” 然后再将这句话逐步带入词典查询,如果没找到,就去掉最后个字。整个过程中会产生两个结果:

结果1:找到这个词了,那么这句话的字符串变成这个词余下的字符串; 结果2:没有找到,但必须将最后一个字作为一个单独的词分割出来(往往是“的”、“是”之类的字)

这句话的分割过程如下:

2.1 第一轮

1 我在别人那 => 没有找到 2 我在别人 => 没有找到 3 我在别 => 没有找到 4 我在 => 没有找到 5 我 => 只剩下一个字,这个字必须作为一个单独的词

2.2 第二轮

在第一轮中,“我”作为单独一个词后,下一步就不需要查找这个词了,这时再取5个字(接着上次没有找到的地方开始取):

S=在别人那里

1 在别人那里 => 没有找到 2 在别人那 => 没有找到 3 在别人 => 没有找到 4 在别 => 没有找到 5 在 => 又遇到剩下一个字,所以单独出现

2.3 第三轮

S=别人那里听

1 别人那里听 => 没有找到 2 别人那里 => 没有找到 3 别人那 => 没有找到 4 别人 => 找到,进入第四轮

2.4 第四轮

S=那里听说你

1 那里听说你 => 没有找到 2 那里听说 => 没有找到 3 那里听 => 没有找到 4 那里 => 找到,进入第五轮

2.5 第五轮

S=听说你是黑

1 听说你是黑 => 没有找到 2 听说你是 => 没有找到 3 听说你 => 没有找到 4 听说 => 找到,进入第六轮

2.6 第六轮

S=你是黑客

1 你是黑客 => 没有找到 2 你是黑 => 没有找到 3 你是 => 没有找到 4 你 => 只剩下一个字,所以单独作为一个词

2.7 第七轮

S=是黑客

1 是黑客 => 没有找到 2 是黑 => 没有找到 3 是 => 只剩下一个字,所以单独作为一个词

2.8 第八轮

S=黑客

1 黑客 => 找到,结束分词

2.9 实现代码

只用简单修改上面的splitwords函数

def split_word(words):
    max_len = 5            # 每次取max_len个字
    split_result = list()    # 分词结果

    while(words):
        # 先取max_len个字出来分词
        text = words[0: max_len]
        # 标志位,如果为True表示找到词了
        is_find = False

        # 开始尝试分词
        while not is_find:
            if text in word_dict:
                is_find = True
                split_result.append(text)
                # 后移
                words = words[len(text):]
                # 如果只剩下一个字了,它单独成为一个词
                # 比如“我的是他的”这句话里就没有一组词,所以要将它们分割成一个个字
                # 这里参考函数注释中的“结果1”
            elif len(text) == 1:
                is_find = True
                split_result.append(text)
                words = words[1:]
                # 如果没有找到,就去掉最后一位
            else:
                text = text[:len(text)-1]

    return split_result