PLANETCALC 在线计算器

登录
学习数学

莱文斯坦距离

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

两个字符串之间的莱文斯坦距离 (或者称 编辑距离) 是将源字符串转化为目标字符串所需的删除、插入或替换的数量。例如，如果源字符串是 "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

评论