目标

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

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

算法介绍

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

已知条件

  • 在分词前首先得有一个字典来存储已知的单词
    • [一起，今天，吃饭，我们，我，肯德基 ]
    • 从这个词典我们知道，单词的最大长度为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

  • 首先初始化词典

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    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

  • 然后初始化所有句子

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    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

  • 使用最大向前法进行分词

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    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函数

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

cal_prf.py

  • 读取分词结果

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

  • 读取分词的标准答案

    1
    2
    3
    4
    5
    6
    7
    8
    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三个参数

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    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