编辑距离 (Levenshtein 距离) 是将一个字符串转换为另一个字符串所需的最少字符插入、删除和替换操作次数。由俄罗斯数学家 Vladimir Levenshtein 于 1965 年提出。

例如"kitten"和"sitting"的编辑距离为 3 (k→s、e→i、在 n 后插入 g)。该指标广泛应用于拼写检查、模糊搜索和 DNA 序列比较。字符串算法书籍介绍了计算方法。

计算使用动态规划 (DP)，时间复杂度为 O(mn)，其中 m 和 n 是字符串长度。大规模数据集可能使用近似算法。

在字符计数中，编辑距离在字符级别量化两个文本的相似度，是衡量字符级差异的基本方法。自然语言处理基础书籍提供了更多背景知识。