了解初学者的Levenshtein距离方程

最近,我遇到了一种情况,在这种情况下,我为所构建的命令行应用程序需要模糊字符串匹配功能。 在使用Ruby谷歌搜索了一种方法之后,我发现了一个Stack Overflow帖子,告诉我安装一个名为levenshtein-ffi的红宝石,然后继续前进。 但是,我的好奇心得到了我的最大帮助,我走上了一个网上兔子洞,试图了解幕后真正发生的事情。 最终,我登陆了Levenshtein距离Wikipedia页面,在其中看到了以下内容:

我对矩阵的经验很少,并且从未学习过线性代数,因此一开始,我很困惑。 最终,我最终对所发生的事情有了一个基本的了解,下面将尝试解释。 该说明适用于初学者-任何对上述方程式感到困惑或从未修过更高层次的数学课程的人。 警告 :如果您不属于上述阵营,则可能会发现下面的说明不必要地乏味。

介绍

Levenshtein距离是一个数字,告诉您两个字符串的不同程度。 数字越高,两个字符串的差异就越大。

例如,“小猫”和“坐着”之间的Levenshtein距离为3,因为至少需要进行3次编辑才能将其中一个更改为另一个。

  1. k itten→sten(将“ s”替换为“ k”)
  2. sitt e n→sitt i n(用“ i”代替“ e”)
  3. 坐姿→坐姿g (末尾插入“ g”)。

“编辑”是通过插入字符,删除字符或替换字符来定义的。

功能

如果您最近没有看过函数,请快速复习……首先要了解的是,函数是一组指令,这些指令采用给定的输入,遵循一组指令并产生输出。 您可能在中学数学课程中看到了许多基本功能。

分段函数

分段函数是更复杂的函数。 在分段函数中,有多组指令。 您可以根据特定条件选择一组而不是另一组。 考虑下面的示例:

在上面的示例中,我们根据输入内容使用了不同的指令集。 分段函数用大括号{符号表示。

考虑到这一点,Levenshtein距离方程应该更具可读性。

a,b,i和j代表什么?

a =字符串#1

b =字符串#2

i =字符串#1的终端字符位置

j =字符串#2的终端字符位置。

位置为1索引。 考虑下面的示例,我们将字符串“ cat”与字符串“ cap”进行比较:

条件(aᵢ≠bⱼ)

aᵢ表示位置i处的字符串a的字符

bⱼ表示位置j处的字符串b的字符

我们要检查它们是否相等,因为如果它们相等,则不需要编辑,因此我们不应该加1。相反,如果它们不相等,则要对1进行必要的编辑。

使用矩阵求解

可以使用矩阵计算字符串A和B的Levenshtein距离。 它通过以下方式初始化:

从这里开始,我们的目标是从左上角开始填充整个矩阵。 然后,右下角将产生Levenshtein距离。

让我们按照分段函数填写矩阵。

现在,我们可以对矩阵中的所有点使用相同的分段函数来填充矩阵的其余部分。

再举一个例子:

如果此时您对方程感到满意,请尝试填写矩阵的其余部分。 结果如下:

由于右下角是3,所以我们知道“小猫”和“坐着”的Levenshtein距离是3。这是我们期望的,因为我们已经知道Levenshtein距离是3(如引言中所述)。 这也反映在Levenshtein距离Wikipedia页面上显示的矩阵中。

结论

希望上面的内容现在对您来说不再那么吓人了。 更好的是,希望您理解它的含义!

现在您已在一定程度上了解了幕后的情况,那么当您下载levenshtein-ffi之类的gem并运行Levenshtein.distance(“ kitten”,“ sitting”)之类的方法并获得时,您可以真正体会到发生的一切。返回值为3。所有艰苦的工作都已被抽象化,以便您可以简单地用数字表示两个字符串的不同程度。 我们都应该感谢弗拉基米尔·莱文斯泰因(Vladimir Levenshtein)于1965年提出了他的算法。该算法已有50多年没有得到改进,这是有充分理由的。 根据麻省理工学院的说法,就效率而言,Levenshtein的算法很可能是我们获得的最好的算法。

二手/引用作品

Levenshtein算法
Levenshtein距离是用于测量两个序列之间差异的字符串量度。 非正式地,Levenshtein… www.cuelogic.com Levenshtein距离–维基百科
在信息论,语言学和计算机科学中,Levenshtein距离是衡量……的线性度量 。en.wikipedia.org 易于理解的动态编程编辑距离
重要信息:该博客已移至jlordiales.me。 这里的内容可能已过时。 要在新的… jlordiales.wordpress.com 上看到这篇文章