问题标签 [levenshtein-distance]

我有一个大约 20,000 个电子邮件地址的列表，我知道其中一些是为了绕过“每封电子邮件 1 个”限制而进行的欺诈性尝试，例如 username1@gmail.com、username1a@gmail.com、username1b@gmail。 com 等。我想找到类似的电子邮件地址进行评估。目前，我正在使用 Levenshtein 算法来检查每封电子邮件与列表中的其他电子邮件，并报告编辑距离小于 2 的任何电子邮件。但是，这非常慢。有没有更有效的方法？

我现在使用的测试代码是：

编辑：我试图捕捉的一些东西看起来像：

01234567890@gmail.com
0123456789@gmail.com
012345678@gmail.com
01234567@gmail.com
0123456@gmail.com
012345@gmail.com
01234@gmail.com
0123@gmail.com
012@gmail.com

我在优化我正在做的这个 Levenshtein 距离计算时遇到了麻烦。我需要执行以下操作：

1. 获取源字符串的最小距离记录以及源字符串的修剪版本

2. 选择距离最短的记录
3. 如果最小距离相等（原始与修剪），则选择距离最小的修剪过的那个
4. 如果仍有多条记录属于上述两类，则选择频率最高的一条

这是我的工作版本：

我相信我需要在这里做的是......

1. 不要把结果变成临时表
2. 只从“MyTable”中选择 1 个
3. 在初始选择语句的选择中设置结果。（因为 select 会设置变量，你可以在一个 select 语句中设置多个变量）

我知道必须有一个很好的实现，但我无法弄清楚......这是我所得到的：

有任何想法吗？

<tl;dr>
在源代码版本控制 diff 补丁生成中，是否值得<optimizations>在我的 diff 的 Ruby 实现中使用本文最底部列出的优化（参见 参考资料）来制作 diff 补丁？
</tl;dr>

<introduction>
我正在编程我以前从未做过的事情，并且可能已经有工具可以做我正在编程的确切事情，但在这一点上，我有太多的乐趣在乎，所以我仍然会从头开始做，即使有一个工具可以做到这一点。

所以无论如何，我正在开发一个 Ruby on Rails 应用程序并且需要一个特定的功能。基本上，我希望我的表中的每个条目，例如一个视频游戏表，都有一个存储的文本块，代表该表条目的评论或类似的东西。但是，我希望任何注册用户都可以编辑此文本，并在版本控制系统中跟踪不同的提交。我能想到的最简单的解决方案就是实现一个解决方案，将文本主体和不同版本文本主体的差异补丁历史记录为 Ruby 中的对象，然后将其序列化，最好以人类可读的形式（所以我会最有可能为此使用 YAML）进行编辑，如果由于软件错误损坏或管理员在进行某些版本编辑时出错而需要进行编辑。

所以一开始我只是试着深入研究这个特性，发现生成差异补丁的问题比我认为要有效地完成要困难得多。所以我做了一些研究，并遇到了一些想法。有些我已经实现了，有些我还没有。然而，这几乎都是围绕最长公共子序列问题展开的，因为您已经知道您是否已经使用 diff 或类似 diff 的特征做了任何事情，并优化了解决它的函数。

目前我有它，所以它会从头到尾截断文本正文的比较版本，直到找到不匹配的行。然后它使用比较矩阵解决了这个问题，但是当它找到匹配行时，它不会像在我见过的大多数最长常见子序列算法的例子中那样增加存储在单元格中的值，而是在我有一条不匹配的行时增加，所以至于计算编辑距离而不是最长公共子序列。尽管据我所知，这两种方法本质上是同一枚硬币的两个面，因此任何一种都可以用来得出答案。然后，它通过比较矩阵回溯并记录何时有增量以及在哪个相邻单元格（西部、西北或北部）中确定该行的差异条目，并假设所有其他行保持不变。

通常我会把它留在那里，但由于这是进入 Rails 环境而不仅仅是一些独立的 Ruby 脚本，我开始担心需要至少进行足够的优化，所以如果垃圾邮件发送者以某种方式知道我是如何实现该版本的控制系统，并且知道我最坏的情况条目仍然无法击中服务器那么糟糕。通过互联网搜索和阅读研究论文和文章后，我遇到了一些看起来不错但似乎各有利弊的文章，我很难决定在这种情况下如何平衡利弊出去。那么这里列出的那些值得吗？我列出了它们已知的优缺点。
</introduction>

<optimizations>

1. 通过将未更改的行拆分，然后在每个部分的开头和末尾截断未更改的行的每个部分，将比较的序列切成多个子序列。然后求解每个子序列的编辑距离。

   • 优点：随着变化区域的增大，时间增加从二次增加变为更类似于线性增加。

   • 缺点：弄清楚在哪里分割似乎你必须解决编辑距离，但现在你不在乎它是如何改变的。如果这可以通过更接近于解决汉明距离的过程来解决，那会很好，但是单次插入就会把它扔掉。

2. 使用加密哈希函数将所有序列元素转换为整数并确保唯一性。然后解决比较哈希整数而不是序列元素本身的编辑距离。

   • 优点：比较两个整数的操作比比较两个字符串的操作要快，因此每次比较后都会获得轻微的性能提升，总体上可以很多。

   • 缺点：使用加密哈希函数需要时间来转换所有序列元素，并且最终可能会花费更多时间来进行从整数比较中获得的转换。您可以对字符串使用内置的哈希函数，但这不能保证唯一性。

3. 使用惰性求值只计算比较矩阵最中心的三个对角线，然后只根据需要计算额外的对角线。然后也使用这种方法可能消除一些比较的需要，以比较所有三个相邻的单元格，如此处所述。

   • 优点：可以转动一个总是花费 O(n * m) 时间的算法，并使其只有最坏的情况是那个时间，最好的情况实际上是线性的，而平均情况介于两者之间。

   • 缺点：这是一种我只见过用函数式编程语言实现的算法，我很难理解如何根据上面链接的站点上的描述将其转换为 Ruby。

4. 制作一个 C 模块并在 C 的本机级别完成艰苦的工作，然后为它制作一个 Ruby 包装器，以便 Ruby 可以对其进行所有需要的调用。

   • Pro：我不得不想象评估这样的事情可能会快很多。

   • 缺点：我不知道 Rails 如何处理带有 C 扩展的 ruby​​ 代码的应用程序，这会损害应用程序的可移植性。

5. 这是解决编辑距离后的优化，但想法是存储额外的组合差异与每个版本产生的差异，以制作一个增量树数据结构，其中最近制作的差异作为树的根节点，因此得到到任何版本都需要 O(log n) 而不是 O(n) 的最坏情况时间。

   • 优点：会更快地回到旧版本。

   • 缺点：这意味着每次新的提交，delta-tree 都会获得一个新的根节点，这将花费时间来重新组织 delta-tree 以执行比返回一个版本更频繁的操作，更不用说不太可能是旧版本。

</optimizations>

那么这些东西值得努力吗？

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?

我正在尝试编写一个自由文本搜索算法来查找墙上的特定帖子（类似于 Facebook 使用的墙）。假设用户能够在搜索字段中写一些单词并在包含这些单词的帖子上获得点击；最佳匹配在顶部，然后根据匹配分数以降序排列其他帖子。

我使用编辑距离 (Levenshtein) "e(x, y) = e" 来计算每个帖子与查询词 "x" 和帖子词 "y" 相比的分数： score(x, y ) = 2^(2 - e)(1 - min(e, |x|) / |x|)，其中“|x|” 是查询词中的字母数。

帖子中的每个单词都会影响该特定帖子的总分。当帖子大小大致相同时，这种方法似乎效果很好，但有时某些大型帖子仅靠其中包含很多单词而在实践中与查询无关时设法获得分数。

我是在以错误的方式处理这个问题，还是有一些方法可以使我没有想到的分数正常化？

我有一个用户上传文章的数据库。我想制作一种算法，让我的网络应用程序根据用户阅读的内容建议类似的文本。

我看到了一些例子，比如Levenshtein distance。但是这些算法测量的是字符串的距离，而不是整篇文章的距离。有没有办法从文本中提取最重要的关键字？当然，我理解“最重要”是一个模棱两可的术语。

其他网站如何管理这个？

多谢

我正在寻找 PHP 的Damerau–Levenshtein算法的实现，但我的朋友 google 似乎找不到任何东西。到目前为止，我必须使用 PHP 实现的 Levenshtein（没有 Damerau 转置，这非常重要），或者获取原始源代码（C、C++、C#、Perl）并将其写入（翻译）为 PHP。

有人对 PHP 实现有任何了解吗？

我在公司内部网上使用 soundex 和双变音作为“你的意思是：”扩展，我想实现 Damerau-Levenshtein 算法来帮助我更好地对结果进行排序。类似于这个想法的东西：http ://www.briandrought.com/blog/?p=66 ，我的实现类似于前 5 个步骤。

是否有包含以 C 或 Fortran 代码实现的 Levenshtein 距离计数功能的包？我有很多字符串要比较，并且stringMatchfromMiscPsycho太慢了。

我刚刚实现了一个最佳匹配文件搜索算法来查找与字典中的字符串最接近的匹配。在分析我的代码后，我发现绝大多数时间都花在了计算查询与可能结果之间的距离上。我目前正在实现使用二维数组计算 Levenshtein 距离的算法，这使得实现成为 O(n^2) 操作。我希望有人可以提出一种更快的方法来做同样的事情。

这是我的实现：

我最近发布了一个关于优化算法以计算 Levenshtein 距离的问题，这些回复将我带到了关于Levenshtein 距离的 Wikipedia 文章。

文章提到，如果在最大距离上存在一个界限k，则可能的结果可以来自给定查询，那么运行时间可以从O(mn)减少到O(kn)，m和n是字符串。我查看了算法，但我无法真正弄清楚如何实现它。我希望在这里得到一些线索。

优化是“可能的改进”下的#4。

让我感到困惑的部分是说我们只需要计算以主对角线为中心的宽度为2k+1的对角线条纹（主对角线定义为坐标 (i,i)）。

如果有人可以提供一些帮助/见解，我将非常感激。如果需要，我可以在这里发布书中算法的完整描述作为答案。