基于最大匹配算法的句子分词
目标
我们的最终目标是实现把一个句子分解成若干个合理的单词
- “我们今天一起去吃麦当劳吧” => [“我们”,“今天”,“一起”,“去”,“吃”,“麦当劳”,“吧”]
算法介绍
进行本次使用的分词方法是非常好理解的正向最大匹配算法
已知条件
- 在分词前首先得有一个字典来存储已知的单词
[一起,今天,吃饭,我们,我,肯德基 ]
- 从这个词典我们知道,单词的最大长度为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
-
参数计算