Levenshtein

释义 Definition

Levenshtein（通常指 Levenshtein distance，莱文斯坦距离/编辑距离）：衡量两个字符串相似度的一种指标，表示把一个字符串变成另一个字符串所需的最少单字符编辑次数（常见操作：插入、删除、替换）。在拼写纠错、模糊搜索、DNA 序列比对等场景中很常用。（也可指姓氏“Levenshtein”。）

例句 Examples

The spell checker uses Levenshtein distance to suggest corrections.
拼写检查器使用莱文斯坦距离来给出纠正建议。

By minimizing the Levenshtein distance between user queries and product titles, the search engine improves recall without sacrificing too much precision.
通过最小化用户查询与商品标题之间的莱文斯坦距离，搜索引擎在不过度牺牲准确率的前提下提升了召回率。

发音 Pronunciation (IPA)

/ˈlɛvənʃtaɪn/
/ˈliːvənʃtaɪn/

词源 Etymology

该词来自俄裔数学家/信息论学者 Vladimir I. Levenshtein（弗拉基米尔·莱文斯坦）的姓氏。后来以他的名字命名了“Levenshtein distance”，用来描述字符串之间的编辑差异。

相关词 Related Words

• Algorithm
• Edit
• Distance
• String
• Similarity
• Hamming
• Damerau
• Jaccard

文学与作品 Literary Works

• Vladimir I. Levenshtein, Binary Codes Capable of Correcting Deletions, Insertions, and Reversals（经典论文，提出相关思想）
• Dan Gusfield, Algorithms on Strings, Trees, and Sequences（字符串算法领域常引用编辑距离/Levenshtein 距离）
• Christopher D. Manning, Prabhakar Raghavan, Hinrich Schütze, Introduction to Information Retrieval（信息检索教材中常讨论编辑距离及其应用）