Understanding Edit Distance: A Python Guide

常见于自然语言处理（NLP）领域中对两个字符串相似程度的评估，在实际应用中十分常见。例如拼写错误纠正以及指代识别等任务都会遇到此类问题。通常用户在搜索时可能会输入误写字符，如将“微信”误输入为“为信”，但搜索引擎则会将其修正并返回正确的搜索结果（如图1-1所示）。此外还可以对比类似名称如“北京大学校长”与“北大校长”以及“北京故宫博物院”与“北京故宫”。

上述问题，可以利用两个词或短语的编辑距离大小来解决。

图1-1 搜索词“为信”的百度结果

编辑距离介绍

通过计算两个字符串之间的编辑距离……具体而言，则涉及三种基本操作：插入特定字符、删除多余字符以及将一个字符替换为另一个字符。其中最小的编辑距离则表示将一个字符串转换为另一个所需进行的最少操作数量。

在这里定义的单字符编辑操作有且仅有三种：

• 插入（Insertion）
• 删除（Deletion）
• 替换（Substitution）

如图2-1所示，在两个字符串之间建立了一个对比框架，在上层字符串INTENTION中通过一系列操作可转换为下层字符串EXECUTION。其中d表示删除字