Levenshtein Distance

定义 Definition

Levenshtein distance（莱文斯坦距离）：衡量两个字符串之间差异的一种指标，表示把一个字符串变成另一个字符串所需的最少编辑次数。常见允许的编辑操作是：插入、删除、替换一个字符。（有些变体还允许“交换相邻字符”。）

发音 Pronunciation (IPA)

/ˈlɛvənʃtaɪn ˈdɪstəns/

例句 Examples

The Levenshtein distance between “cat” and “cut” is 1.
“cat”和“cut”的莱文斯坦距离是1。

In spell-checking, a lower Levenshtein distance often suggests a more likely correction, but context still matters.
在拼写检查中，较低的莱文斯坦距离通常意味着更可能的纠正结果，但语境仍然很重要。

词源 Etymology

该术语来自苏联/俄罗斯数学家与信息论学者 Vladimir I. Levenshtein（弗拉基米尔·莱文斯坦） 的姓氏。他在1965年的论文中系统提出并研究了这种用于度量字符串差异的“编辑距离”思想，因此后来以他的名字命名。

文学与著作 Literary Works

Vladimir I. Levenshtein, “Binary Codes Capable of Correcting Deletions, Insertions and Reversals”（1965）——提出并奠定该距离的经典论文
Dan Jurafsky & James H. Martin, Speech and Language Processing ——在自然语言处理中的拼写纠错、近似匹配等章节常出现
Christopher D. Manning, Prabhakar Raghavan & Hinrich Schütze, Introduction to Information Retrieval ——在信息检索的字符串相似度与纠错相关内容中常出现
Jon Bentley, Programming Pearls（部分版本/章节讨论“编辑距离”类问题，常与该概念并提）