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


目标

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

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

算法介绍

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

已知条件

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

匹配流程

  1. 从当前位置开始,向右截取单词可能的最大长度,组成当前词
    • 例如一开始,当前位置就是0,单词最大可能的长度为3
    • 也就是截取了从0开始长度为3的字符串,我们今
  2. 和字典中的词逐一进行匹配
    • 在字典[一起,今天,吃饭,我们,我,肯德基 ],去寻找是否有我们今
  3. 如果匹配成功,则进行下一次匹配 ,下次匹配从当前这个词后面开始
  4. 如果匹配不成功,就缩短长度,重新截取,直到能匹配成功或单词长度为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

    • 可以看到第一行直接给了单词个数和单词的最大长度
    image-20201020230647761
  • 句子文件corpus.sentence.txt

    image-20201020230735172
  • 标准答案文件corpus.answer.txt

    image-20201020231434417

程序组成

  • 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

    image-20201021144224528
  • 参数计算

    image-20201021145508485