问题标签 [edit-distance]

我本着回答您自己的问题的精神发布此消息。

我的问题是：如何在 Delphi 中实现 Levenshtein 算法来计算两个字符串之间的编辑距离，如此处所述？

只是关于性能的说明：这东西非常快。在我的台式机（2.33 Ghz 双核、2GB 内存、WinXP）上，我可以在不到一秒的时间内运行 100K 字符串数组。

这是一个让 CS 家伙用理论大放异彩的练习。

想象一下，您有 2 个带有元素的容器。文件夹、URL、文件、字符串，真的没关系。

什么是计算添加和删除的算法？

注意：如果有很多方法可以解决这个问题，请每个答案发布一个，以便分析和投票。

编辑：所有答案都用 4 个容器解决了这个问题。是否可以只使用最初的 2？

我对 T-SQL 计算 Levenshtein 距离的算法感兴趣。

我在使用 PHP levenshtein函数比较字符串方面取得了一些成功。

但是，对于包含交换位置的子字符串的两个字符串，算法将它们计为全新的子字符串。

例如：

被视为具有以下共同点：

我更喜欢一种算法，它看到前两个更相似。

我怎么能想出一个比较函数来识别已经切换位置的子字符串与编辑不同？

我想到的一种可能的方法是在比较之前将字符串中的所有单词按字母顺序排列。这将单词的原始顺序完全排除在比较之外。然而，这样做的一个缺点是，仅更改单词的第一个字母会造成比更改单个字母更大的干扰。

我想要实现的是比较关于人的两个作为自由文本字符串的事实，并确定这些事实表明相同事实的可能性有多大。事实可能是某人就读的学校，例如他们的雇主或出版商的名称。两个记录可能有相同的学校拼写不同，单词的顺序不同，多余的单词等，所以如果我们要很好地猜测它们指的是同一所学校，匹配必须有点模糊。到目前为止，它在拼写错误方面效果很好（我使用的是类似于变音位的语音算法），但如果你切换学校中常见的单词顺序，效果就很差：“xxx 学院”vs “xxx学院”。

我将“块转置”放在引号中，因为我不知道技术术语是否或应该是什么。只知道该过程是否有技术术语将非常有帮助。

关于编辑距离的Wikipedia 文章为这个概念提供了一些很好的背景。

通过考虑“块转置”，我的意思是

应该匹配

比匹配更接近

即距离计算应该检测文本的子串何时在文本中简单地移动。常见的 Levenshtein 距离公式并非如此。

字符串最多只有几百个字符——它们是作者姓名或作者姓名列表，可以采用多种格式。我不做 DNA 测序（尽管我怀疑做过的人会对这个主题有所了解）。

对于数据结构项目，我必须找到两个单词（如"cat"和"dog"）之间的最短路径，一次只更改一个字母。我们得到了一个拼字游戏单词列表，用于寻找我们的路径。例如：

我已经使用广度优先搜索解决了这个问题，但正在寻找更好的东西（我用特里树表示字典）。

请给我一些想法，以获得更有效的方法（在速度和内存方面）。一些荒谬和/或具有挑战性的东西是首选。

我问了我的一个朋友（他是一名大三学生），他说这个问题没有有效的解决方案。他说我会在学习算法课程时了解原因。对此有何评论？

我们必须逐字逐句。我们不能去cat -> dat -> dag -> dog。我们还必须打印出遍历。

假设您有一个包含 10,000 个电子邮件地址的列表，并且您想查找此列表中一些最接近的“邻居”是什么 - 定义为与您列表中的其他电子邮件地址可疑地接近的电子邮件地址。

我知道如何计算两个字符串之间的Levenshtein 距离（感谢这个问题），这将为我提供将一个字符串转换为另一个字符串需要多少操作的分数。

假设我将“可疑地靠近另一个电子邮件地址”定义为 Levenshtein 分数小于 N 的两个字符串。

除了将每个可能的字符串与列表中的每个其他可能的字符串进行比较之外，是否有更有效的方法来查找分数低于此阈值的字符串对？换句话说，这种类型的问题能比 解决得更快O(n^2)吗？

Levenshtein 对这个问题的算法选择是否糟糕？

是否可以通过检测一个物体的base64编码的变化来检测物体的变化程度。

假设我向多个用户发送了一个文档附件，每个用户都对其进行了更改并通过电子邮件发送给我，我是否可以使用原始 base64 和收到的 base64 之间的字符串距离来检测哪个版本的更改最多。这会是一个有效的指标吗？

如果没有，是否有任何其他指标来量化增量？

I have a stored procedure that uses Levenshtein distance to determine the result closest to what the user typed. The only thing really affecting the speed is the function that calculates the Levenshtein distance for all the records before selecting the record with the lowest distance (I've verified this by putting a 0 in place of the call to the Levenshtein function). The table has 1.5 million records, so even the slightest adjustment may shave off a few seconds. Right now the entire thing runs over 10 minutes. Here's the method I'm using:

Where should I go from here?

可能重复：
如何纠正此 Damerau-Levenshtein 实现中的错误？

我有以下Cython代码（改编自bpbio项目）进行Damerau-Levenenshtein 编辑距离计算：

该代码运行良好且快速（在我的 PC 上每秒进行 300,000...400,000 次比较）。

挑战在于使此代码也可以与 unicode 字符串一起使用。我正在运行 Python 3.1 并从数据库中检索文本，然后将其与查询文本匹配。

将这些字符串编码为bytes在将它们传递给 Cython 函数进行比较之前不是一个好主意，因为性能会受到很大影响（经过测试），并且对于包含 7 位 US ASCII 以外的字符的任何文本，结果可能是错误的。

（非常简洁的）Cython 手册确实提到了 unicode 字符串，但对手头的问题几乎没有帮助。

正如我所看到的，一个unicode字符串可以被认为是一个整数数组，每个代表一个单独的代码点，上面的代码基本上char已经在s数组上运行，所以我的猜测是我应该（1）扩展它处理 C 整数数组；(2)添加将python unicode字符串转换为C数组的代码；(3)利润！

（ 注意： 这种方法有两个潜在问题：一个是处理 unicode 代理字符，但我想我知道如何处理这些。另一个问题是 unicode 代码点并没有真正将 1:1 映射到“字符”的概念'。我很清楚这一点，但我认为它超出了这个问题的范围。请假设一个 unicode 代码点是一个比较单位。）

所以我正在征求建议如何

• 编写一个快速的 Cython 函数，该函数接受 python unicode 字符串并返回 Cythonunsigned int的 C 数组（4 个字节）；

• 修改显示的代码以处理这些数组并进行正确的内存分配/释放（这对我来说很陌生）。

编辑：John Machin指出奇怪的类型转换char *m1等可能是为了速度和/或内存优化；这些变量仍被视为数字数组。我意识到代码没有做任何事情来防止可能的长字符串溢出；当一个数组元素超过 127 或 255（取决于所使用的 C 编译器）时，可能会出现错误结果。来自生物信息学项目的代码有点令人惊讶。

也就是说，我只对少于一百个字符的大致相同字符串的精确结果感兴趣。出于我的目的，低于 60% 相同性的结果可以安全地报告为“完全不同”（通过返回较长文本的长度），所以我想最好保留char *m1强制转换，但添加一些代码来检查溢出和在猖獗差异的情况下早期堕胎。