字符串的编辑距离是我们都知道的，事实上，编辑距离的计算，本质上是对列表元素的操作，那么，自然也可以是token列表。本文的想法正是基于此。
字符串的编辑距离
在文章动态规划法算法之编辑距离中，笔者详细介绍了字符串的编辑距离定义及使用动态规划法（Dynamic
Programming, DP）来解决。
我们再来看看字符串的编辑距离的定义。什么是两个字符串的编辑距离（edit
distance）？给定字符串s1和s2，以及在s1上的如下操作：
插入（Insert）一个字符移除（Remove）一个字符替换（Replace）一个字符
试问最小需要多少次这样的操作才能使得s1转换为s2？
在leetcode网站中，这是题目中的第72题，难度为hard。
笔者当时使用动态规划算法，代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| def string_edit_distance(s1, s2):
n = len(s1)
m = len(s2)
if n * m == 0:
return n + m
D = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n + 1):
D[i][0] = i
for j in range(m + 1):
D[0][j] = j
for i in range(1, n + 1):
for j in range(1, m + 1):
left = D[i - 1][j] + 1
down = D[i][j - 1] + 1
left_down = D[i - 1][j - 1]
if s1[i - 1] != s2[j - 1]:
left_down += 1
D[i][j] = min(left, down, left_down)
return D[n][m]
|
该算法是字符串编辑距离的常规优化算法。
基于token的编辑距离
不难发现，上述的字符串编辑距离的算法，可以扩展至一切列表元素的编辑距离。在这里，我们选择token列表。
我们使用tiktoken将字符串转化为token列表。
基于token的编辑距离代码如下：
1
2
3
4
5
6
7
8
9
10
| import tiktoken
def token_edit_distance(s1, s2):
enc = tiktoken.get_encoding("cl100k_base")
token_list1 = enc.encode(s1)
token_list2 = enc.encode(s2)
print(token_list1)
print(token_list2)
return string_edit_distance(token_list1, token_list2)
|
我们选取两个例子进行测试：
1
2
3
4
5
6
7
8
9
10
11
12
| if __name__ == '__main__':
text1 = "tiktoken is good"
text2 = "tiktoken is great"
print(string_edit_distance(text1, text2))
print(token_edit_distance(text1, text2))
text1 = "iPhone手机很棒！"
text2 = "华为手机很棒！"
print(string_edit_distance(text1, text2))
print(token_edit_distance(text1, text2))
|
输出结果如下：
1
2
3
4
5
6
7
8
| 4
[83, 1609, 5963, 374, 1695]
[83, 1609, 5963, 374, 2294]
1
6
[45840, 59505, 17599, 230, 77062, 240, 6447]
[86461, 18184, 59505, 17599, 230, 77062, 240, 6447]
2
|
总结
本文的想法较为简单，是将字符串的编辑距离推广至token列表的编辑距离，可以作为一种衡量字符串相似度的指标。
其它想法如下：
- 不仅字符串，token可以作为字符串相似度的衡量标准，在文本纠错中，拼音也可作为标准
- edit distance本质上是两个列表的编辑距离
- 利用预训练模型进行文本纠错，实质上是对token进行纠错
- 在中英文混合场景也许有用
推荐阅读
欢迎关注我的公众号NLP奇幻之旅，原创技术文章第一时间推送。
欢迎关注我的公众号“自然语言处理奇幻之旅”，笔者正在努力构建自己的技术社区。
