PLANETCALC 在线计算器

登录
学习数学

莱文斯坦距离

这个在线计算器测量两个字符串之间的莱文斯坦距离。

这个页面的存在是由于以下各位的努力:

Timur

Timur

W

Wanghong

创建: 2021-12-04 02:21:54, 最后更新: 2021-12-06 15:12:07
Creative Commons Attribution/Share-Alike License 3.0 (Unported)

本内容采用知识共享署名/相同方式共享许可协议3.0（未移植）进行许可。这意味着你可以在相同的许可条件下自由地重新发布或修改本内容，并且必须在你的网站上放置一个超链接到本作品https://zh.planetcalc.com/1721/，以注明原作者。此外，请不要修改本内容中对原作的任何引用（如果有的话）。

两个字符串之间的莱文斯坦距离 (或者称 编辑距离) 是将源字符串转化为目标字符串所需的删除、插入或替换的数量。例如，如果源字符串是 "book"，目标字符串是 "back"，要将 "book "转化为 "back"，你需要将第一个 "o "改为 "a"，第二个 "o "改为 "c"，不需要额外的删除和插入。因此，"book "和 "back "之间的莱文斯坦距离将是2。

关于莱文斯坦距离算法及其应用的更多信息可以在计算器下面找到。

PLANETCALC, 莱文斯坦距离

莱文斯坦距离

莱文斯坦距离
 

莱文斯坦距离算法及其应用

两个字符串 a, b (长度分别为 |a| 和 |b|) 之间的莱文斯坦距离由 lev(a,b) 给出，其中
{\displaystyle \qquad \operatorname {lev} (a,b)={\begin{cases}|a|&{\text{if }}|b|=0,\\|b|&{\text{ if }}|a|=0,\\\operatorname {lev} (\operatorname {tail} (a),\operatorname {tail} (b))&{\text{ if}}a[0]=b[0]\\1+\min {\begin{cases}\operatorname {lev} (\operatorname {tail} (a),b)\\\operatorname {lev} (a,\operatorname {tail} (b))\\\operatorname {lev} (\operatorname {tail} (a),\operatorname {tail} (b))\\\end{cases}}&{\text{ otherwise }}\end{cases}}}.

莱文斯坦距离是以俄罗斯科学家弗拉基米尔莱文斯坦(Vladimir Levenshtein)的名字命名的，他在1965年设计了这种公制。计算莱文斯坦距离有几种算法:

  • 递归； 简单的算法，遵循定义
  • 全矩阵迭代； 上面计算器中使用的那个
  • 用两个矩阵行迭代

所有算法的更多细节和伪代码实现可以在百度百科的文章中找到莱文斯坦距离

已经证明1，莱文斯坦距离不能在强次二次时间内计算，这使得它用于比较长字符串不切实际，因为计算成本将与字符串长度的乘积成正比。但是，编辑距离可用于查找从字典中获取的，在长字符串中的短字符串的匹配。这对拼写检查器、光学字符识别的校正系统和类似产品很有用。

  1. Backurs, Arturs; Indyk, Piotr (2015). 编辑距离无法在强二次方时间内计算（除非SETH为假）。ACM第四十七届年度计算理论研讨会（STOC）。 ↩

URL 复制到剪贴板

类似计算器

 信息 度量 数学 算法 莱文斯坦 距离
PLANETCALC, 莱文斯坦距离
Timur2021-12-06 15:12:07

评论