本文摘要
· 理论来源：【统计自然语言处理】第七章 自动分词；【自然语言处理入门】第二章 词典分词；
· 代码目的：手写三种算法：正向最长匹配、逆向最长匹配、双向最长匹配，比较它们的单词切分效果与速度
· 电脑配置：联想拯救者Y7000，Intel(R) Core(TM) i5-8300H CPU @ 2.30GHz 2.30 GHz
作者：CSDN 征途黯然.
一、关于测试用的语料库
采用了2个预料库，一个是第二届国际分词的PKU测试集语料库（55303词），一个是网上随便找的（248303词）。它们的形式都如下：
中校 31 需要 353 圣彼得大 3 张德彝 2 周文德 2 ……
值得注意的是，语料库越大，代码搜索花费越大，会显著影响我们的算法速度测评环节。但是由于我们是比较三个算法的性能，不同系统配置、语料库不会影响三种算法的相对性能。
获取本数据集或者代码工程，可以关注公众号‘三黄工作室’回复‘中文分词’。
二、正向最长匹配算法
代码非常简单，见代码注释。
# 正向最长匹配 def forward_segment(text, dic): word_list = [] i = 0 while i < len(text): longest_word = text[i] # 当前扫描位置的单字 for j in range(i + 1, len(text) + 1): # 所有可能的结尾 word = text[i:j] # 从当前位置到结尾的连续字符串 if word in dic: # 是否在词典中 if len(word) > len(longest_word): # 且更长 longest_word = word # 则优先输出 word_list.append(longest_word) # 输出最长词 i += len(longest_word) # 正向扫描 return word_list
三、逆向最长匹配算法
代码非常简单，见代码注释。
# 逆向最长匹配 def backward_segment(text, dic): word_list = [] i = len(text) - 1 while i >= 0: longest_word = text[i] # 当前扫描位置的单字,作为词的终点 for j in range(0, i): # 所有可能的前缀 word = text[j:i + 1] # 从前缀到当前位置连续字符串 if word in dic: # 是否在词典中 if len(word) > len(longest_word): # 且更长 longest_word = word # 则优先输出 word_list.insert(0, longest_word) # 输出最长词 i -= len(longest_word) # 后向扫描 return word_list
四、双向最长匹配算法
代码非常简单，见代码注释。
# 双向最长匹配 def bidirectional_segment(text, dic): # 统计单字个数 def count_single_char(word_list): return sum(1 for word in word_list if len(word) == 1) f = forward_segment(text, dic) b = backward_segment(text, dic) if len(f) < len(b): # 词数更少优先级更高 return f elif len(f) > len(b): return b else: if count_single_char(f) < count_single_char(b): # 单字更少优先级更高 return f else: # 都相等时逆向匹配优先级更高 return b
五、切分效果测评
切分效果与所用的语料库大小有关，不具有使用价值。我们主要使用统计方法或者深度学习来进行分词。
# 加载数据集 def load_data(): dic = [] data = open("words.txt", "r", encoding="utf-8") for line in data: words = line.split(" ") dic.append(words[0]) return dic # 切分效果 sent = ["欢迎新老师生", "使用户满意"] for s in sent: print(forward_segment(s, load_data())) print(backward_segment(s, load_data())) print(bidirectional_segment(s, load_data()))
结果：
# 第一个语料库（55303）： ['欢迎', '新', '老师', '生'] # 前向 ['欢', '迎新', '老', '师生'] # 后向 ['欢', '迎新', '老', '师生'] # 双向 ['使用', '户', '满意'] # 前向 ['使', '用户', '满意'] # 后向 ['使', '用户', '满意'] # 双向 # 第二个语料库（248303）： ['欢迎', '新老', '师生'] # 前向 ['欢迎', '新老', '师生'] # 后向 ['欢迎', '新老', '师生'] # 双向 ['使用', '户', '满意'] # 前向 ['使', '用户', '满意'] # 后向 ['使', '用户', '满意'] # 双向
六、切分速度测评
测评代码，就是让算法切分一句话，重复循环切分多次：
# 速度测评 def evaluate_speed(segment, text, dic): start_time = time.time() for i in range(100): segment(text, dic) elapsed_time = time.time() - start_time print('%.8f 万字每秒' % (len(text) * 100 / 10000 / elapsed_time)) text = "想要了解更多北京相关的内容" dic = load_data() evaluate_speed(forward_segment, text, dic) evaluate_speed(backward_segment, text, dic) evaluate_speed(bidirectional_segment, text, dic)
结果：
# 第一个语料库（55303）： 0.03538441 万字每秒 # 前向 0.04058394 万字每秒 # 后向 0.01625951 万字每秒 # 双向 # 第二个语料库（248303）： 0.00714074 万字每秒 # 前向 0.00730858 万字每秒 # 后向 0.00372891 万字每秒 # 双向
七、结论
1、切分速度与电脑配置、语料库大小强相关；
2、后向匹配算法的速度略优于前向匹配算法；
3、双向匹配算法的性能是前向、后向的一半，因为它执行了一次前向+一次后向；
4、由于每次匹配都要去语料库判断是否含有字符串，吃了太多时间，我们要想办法通过一些数据结构的手段来解决这个问题，树就是一个好办法！
