Oct 20, 2020

基于最大匹配算法的句子分词

目标

我们的最终目标是实现把一个句子分解成若干个合理的单词

“我们今天一起去吃麦当劳吧” => [“我们”，“今天”，“一起”，“去”，“吃”，“麦当劳”，“吧”]

算法介绍

进行本次使用的分词方法是非常好理解的正向最大匹配算法

已知条件

在分词前首先得有一个字典来存储已知的单词
- [一起，今天，吃饭，我们，我，肯德基 ]
- 从这个词典我们知道，单词的最大长度为3
需要进行分词的句子
- 我们今天一起吃麦当劳吧

匹配流程

从当前位置开始，向右截取单词可能的最大长度，组成当前词
- 例如一开始，当前位置就是0，单词最大可能的长度为3
- 也就是截取了从0开始长度为3的字符串，我们今
和字典中的词逐一进行匹配
- 在字典[一起，今天，吃饭，我们，我，肯德基 ]，去寻找是否有我们今
如果匹配成功，则进行下一次匹配，下次匹配从当前这个词后面开始
如果匹配不成功，就缩短长度，重新截取，直到能匹配成功或单词长度为1
- 我们今，匹配失败，所以就令当前的长度减一
- 现在是截取的字符串是我们，匹配成功
- 匹配成功后就从今天一开始继续尝试

分词结果

通过上面的匹配流程可以很容易看出来最终结果：

[我们，今天，一起，吃，麦，当，劳，吧]

由于“麦当劳”不存在我们的词典中，所以最后分词结果中，它只能以单个字存在

课程实验

任务

使用最大匹配算法、词典文件（corpus.dict.txt），对语料（corpus.sentence.txt）进行分词
将分词的结果输出到文件corpus.out.txt中；
对比corpus.answer.txt和corpus.out.txt，给出算法的P/R/F指标

输出

一个corpus.out.txt文件（格式参照corpus.answer.txt）
P/R/F指标(格式类似于：Precision = 36 / 100 = 36.00%

文件格式

词典文件corpus.dict.txt
- 可以看到第一行直接给了单词个数和单词的最大长度
句子文件corpus.sentence.txt
标准答案文件corpus.answer.txt

程序组成

wordsegment.py
- 使用最大匹配算法进行句子分词，并将结果输出到corpus.out.txt文件中
cal_prf.py
- 给出算法的P/R/F指标（在命令行输出）

程序编写

`wordsegment.py`

首先初始化词典

def get_dict():
    # 读取词典文件
    print("开始初始化词典...")
    with open('corpus.dict.txt', 'r', encoding='utf-8', ) as f:
        try:
            words_all = f.readlines()
        finally:
            f.close()
    # 读取第一行信息，包括词数和单词最大长度
    dic = []
    rows, max_length = words_all[0].split()
    rows, max_length = int(rows), int(max_length)
    for i in range(1, rows):
        dic.append(words_all[i].rstrip('\n'))
    print("初始化词典完成，单词个数%d，最大单词长度%d" % (rows, max_length))
    return dic, max_length

然后初始化所有句子

def get_sentences():
    print("开始读取句子文件...")
    with open('corpus.sentence.txt', 'r', encoding='utf-8', ) as f:
        try:
            data = f.readlines()
        finally:
            f.close()
    for i in range(len(data)):
        data[i] = data[i].rstrip('\n')
    print("句子文件读取完毕")
    return data

使用最大向前法进行分词

def output_corpus(dic, max_length, data):
    print("利用向前最大匹配法进行分词...")
    f = open("corpus.out.txt", "w", encoding="utf-8")
    for line in data:
        while len(line) > 0:
            max_len = min(len(line), max_length)
            try_word = line[0:max_len]
            while try_word not in dic:
                if len(try_word) == 1:
                    break
                try_word = try_word[0:(len(try_word) - 1)]
            f.write(try_word + " ")
            line = line[len(try_word):]
        f.write("\n")
    f.close()
    print("分词完毕")
    return

main函数

def main():
    # 读取匹配单词所需字典和单词的最大长度
    words_dic, max_word_len = get_dict()
    # 读取所有句子
    sentences = get_sentences()
    # 分词
    output_corpus(words_dic, max_word_len, sentences)

`cal_prf.py`

读取分词结果

def get_out():
    print("读取分词结果文件...")
    with open('corpus.out.txt', 'r', encoding='utf-8', ) as f:
        try:
            out = f.readlines()
        finally:
            f.close()
    return out

读取分词的标准答案

def get_answer():
    print("读取分词标准答案文件...")
    with open('corpus.answer.txt', 'r', encoding='utf-8', ) as f:
        try:
            answer = f.readlines()
        finally:
            f.close()
    return answer

计算并输出PRF三个参数

def cal_prf():
    out = get_out()
    answer = get_answer()
    right_cnt = 0  # 正确识别的个体总数
    rec_cnt = 0  # 识别出的个体总数
    ans_cnt = 0  # 测试集中存在的个体总数
    for i in range(len(out)):
        rec_line = out[i].split()
        ans_line = answer[i].split()
        rec_cnt += len(rec_line)
        ans_cnt += len(ans_line)
        for word in rec_line:
            if word in ans_line:
                right_cnt += 1
    precision = right_cnt/rec_cnt
    recall = right_cnt/ans_cnt
    f1 = precision*recall*2/(precision+recall)
    print("Precision = %d/%d = %.3f" %(right_cnt, rec_cnt, precision))
    print("Recall = %d/%d = %.3f" %(right_cnt, ans_cnt, recall))
    print("F1 = %.3f*%.3f*2/(%.3f+%.3f) = %.3f" %(precision, recall, precision, recall, f1))

运行结果

分词结果文件corpus_out.txt
参数计算