【自然语言处理】正向、逆向、双向最长匹配算法的 切分效果与速度测评_自然语言处理速度测评代码

本文摘要 · 理论来源：【统计自然语言处理】第七章 自动分词；【自然语言处理入门】第二章 词典分词；
· 代码目的：手写三种算法：正向最长匹配、逆向最长匹配、双向最长匹配，比较它们的单词切分效果与速度
· 电脑配置：联想拯救者Y7000，Intel(R) Core(TM) i5-8300H CPU @ 2.30GHz 2.30 GHz
作者：CSDN 征途黯然.

一、关于测试用的语料库

  采用了2个预料库，一个是第二届国际分词的PKU测试集语料库（55303词），一个是网上随便找的（248303词）。它们的形式都如下：

中校 31
需要 353
圣彼得大 3
张德彝 2
周文德 2
……
1
2
3
4
5
6

  值得注意的是，语料库越大，代码搜索花费越大，会显著影响我们的算法速度测评环节。但是由于我们是比较三个算法的性能，不同系统配置、语料库不会影响三种算法的相对性能。

  获取本数据集或者代码工程，可以关注公众号‘三黄工作室’回复‘中文分词’。

二、正向最长匹配算法

  代码非常简单，见代码注释。

# 正向最长匹配
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14

三、逆向最长匹配算法

  代码非常简单，见代码注释。

# 逆向最长匹配
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14

四、双向最长匹配算法

  代码非常简单，见代码注释。

# 双向最长匹配
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

五、切分效果测评

  切分效果与所用的语料库大小有关，不具有使用价值。我们主要使用统计方法或者深度学习来进行分词。

# 加载数据集
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()))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

  结果：

# 第一个语料库（55303）：
['欢迎', '新', '老师', '生'] # 前向
['欢', '迎新', '老', '师生'] # 后向
['欢', '迎新', '老', '师生'] # 双向
['使用', '户', '满意'] # 前向
['使', '用户', '满意'] # 后向
['使', '用户', '满意'] # 双向
# 第二个语料库（248303）：
['欢迎', '新老', '师生'] # 前向
['欢迎', '新老', '师生'] # 后向
['欢迎', '新老', '师生'] # 双向
['使用', '户', '满意'] # 前向
['使', '用户', '满意'] # 后向
['使', '用户', '满意'] # 双向
1
2
3
4
5
6
7
8
9
10
11
12
13
14

六、切分速度测评

  测评代码，就是让算法切分一句话，重复循环切分多次：

# 速度测评
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)
1
2
3
4
5
6
7
8
9
10
11
12
13

  结果：

# 第一个语料库（55303）：
0.03538441 万字每秒 # 前向
0.04058394 万字每秒 # 后向
0.01625951 万字每秒 # 双向
# 第二个语料库（248303）：
0.00714074 万字每秒 # 前向
0.00730858 万字每秒 # 后向
0.00372891 万字每秒 # 双向
1
2
3
4
5
6
7
8

七、结论

  1、切分速度与电脑配置、语料库大小强相关；
  2、后向匹配算法的速度略优于前向匹配算法；
  3、双向匹配算法的性能是前向、后向的一半，因为它执行了一次前向+一次后向；
  4、由于每次匹配都要去语料库判断是否含有字符串，吃了太多时间，我们要想办法通过一些数据结构的手段来解决这个问题，树就是一个好办法！

获取本项目的源代码

如果需要本组件的源代码，请扫描关注我的公众号，回复“中文分词”即可。