编辑距离 (Levenshtein 距离) 是一个表示将一个字符串转换为另一个字符串所需的字符插入、删除、替换的最少操作次数的指标。1965 年由前苏联的数学家 Vladimir Levenshtein 定义。作为定量衡量两个字符串"有多相似"的手法，它在信息科学的广泛领域中得到活用。

作为具体例子，"kitten"和"sitting"的编辑距离是 3。把 k 替换为 s、把 e 替换为 i、在末尾插入 g，用这 3 次操作即可完成转换。距离为 0 表示两个字符串完全一致，距离越大则表示字符串之间的差异越大。

计算使用动态规划 (DP)。设两个字符串的长度为 m 和 n，则构建一个 (m+1) x (n+1) 的矩阵，在各个单元格中依次记录子字符串之间的最小编辑距离。时间复杂度为 O(mn)，空间复杂度也是 O(mn)，但通过只保留前一行的优化，可以把空间复杂度削减到 O(min(m,n))。时间一侧的情形则不同：在只能做字符比较的计算模型中已经给出了 Ω(mn) 的下界，此外在以强指数时间假设为前提时，已知无法在准二次时间 (O(n^2-ε)) 内计算。也就是说，"去寻找更快的算法"这个方向上无法抱有期待，因此在处理长字符串或大量候选时，惯例做法是不去加快计算本身，而是切换为事先缩小需要比较的组合这样的设计。

编辑距离的代表性应用例是拼写检查器。当用户输入的单词在词典中不存在时，计算它与词典内单词的编辑距离，把距离小的单词作为修正候选提示出来。在模糊检索 (fuzzy matching) 中同样如此，不要求完全一致而是返回一定编辑距离以内的结果，从而实现能应对打字错误的检索。

实现时最先要决定的，是把多大的距离视为"相似"这一阈值。距离不会低于两者字符数之差的绝对值，因此长度差超过阈值的候选，可以在计算距离之前就筛除掉。这作为前段的缩小手段，成本最低而效果最好。阈值本身宜结合词的长度来决定才安全。在 3 个字母的英文单词中，仅仅允许距离 1，对于"cat"来说"cut""cap""car"就会全部以相同的距离 1 并列，连意思不同的词也会进入候选。反过来，也存在像"サーバ"和"サーバー"、"リポジトリ"和"レポジトリ"这样希望以距离 1 捞取的不同写法。短的词收紧到 1，长的字符串则不用绝对值而用比率 (距离 ÷ 较长一侧的字符数) 来判定，最终的排列顺序不只由距离决定，而是连候选词的出现频率也一并加以权重。按这样的组合方式搭建，就能抑制错误的修正候选。

在生物信息学领域，DNA 和蛋白质的序列比较中使用了编辑距离的变种。由于在生物学的序列比较中插入、删除、替换的代价并不均等，因此发展出了可为每种操作设置不同权重的加权编辑距离，以及引入了空位罚分的 Needleman-Wunsch 算法等。

作为类似的指标，还有汉明距离 (等长字符串之间不同位置的数量)、Damerau-Levenshtein 距离 (把相邻字符的转置也当作 1 次操作) 和 Jaro-Winkler 距离 (重视开头部分的一致) 等。其差别用具体例子看会更容易理解："form"和"from"只是相邻的 2 个字母互换位置的打字错误，但在编辑距离中会被当作 2 次替换、数为距离 2。若用 Damerau-Levenshtein 距离，则是 1 次转置、距离为 1。是想捞取键盘输入的敲错，还是想衡量拼写的接近程度，会改变该使用哪一种。

从字符计数的观点看，编辑距离是以字符为单位定量化两段文本相似度的基本手法。它在文本的差异检测、版本管理、抄袭检测、机器翻译的质量评估 (TER: Translation Edit Rate) 等一切需要比较字符串的场合中得到活用。在大规模数据集中计算成本会成为课题，因此也开发出了使用 BK 树和字典树的高效近似检索手法。

实现中容易被漏看的，是把"1 个字符"按哪种单位来数。JavaScript 的字符串以 UTF-16 的码元附加下标，因此若用 str.length 和 str[i] 朴素地遍历矩阵，用代理对表示的表情符号 1 个字的增减就会被数为距离 2。实际比较"猫🙂"和"猫"，按码元是 2，先用 [...str] 转成码位的数组再比较则是 1。有无规范化的影响也同样大。用 U+30AC 表示的"ガ"，与在 U+30AB (カ) 后接 U+3099 (组合用的浊点) 所表示的、看起来相同的字符串，直接比较会得出距离 2，但把两者都对齐到 NFC 之后再比较则是 0。若想以人所感到的"只差 1 个字符"的单位得出距离，那么把规范化形式对齐、并把分割单位定为码位 (若想把表情符号当作 1 个字处理则定为书写素簇)，这一步之前都属于实现的范围。