问题标签 [levenshtein-distance]

我们最近在工作中遇到了一个有趣的问题，我们在数据库中发现了重复的用户提交数据。我们意识到，大多数数据之间的 Levenshtein 距离仅仅是两个字符串之间的差异。这表明，如果我们只是将一个字符串中的字符添加到另一个字符串中，那么我们最终会得到相同的字符串，并且对于大多数事情来说，这似乎是我们解释重复项的最佳方式。

我们还想考虑错别字。所以我们开始考虑人们平均多久在网上每个单词打错字，并尝试在这个距离内使用这些数据。我们找不到任何这样的统计数据。

在为数据匹配创建这种阈值时，有什么方法可以解决拼写错误？

让我知道我是否可以澄清！

可能重复：
如何纠正此 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强制转换，但添加一些代码来检查溢出和在猖獗差异的情况下早期堕胎。

是否有用于在图中搜索结构的 levenshtein 距离的概括？

我有一个带有顶部菜单树的在线 Web 应用程序，用于打开不同的小部件来执行不同的任务。随着应用程序变得越来越强大，该树变得越来越大并且难以导航。我已经实现了一个搜索功能，用户可以只输入菜单名称或其中的一部分，我使用正则表达式在菜单树中查找与用户类型匹配的所有项目。我的正则表达式允许部分单词和交换单词，并且还将搜索限制在每个单词的开头。它不允许的一件事是拼写错误的单词。我知道要允许拼写错误的单词，最好不要使用正则表达式，而是使用字符串距离方法，但我仍然希望允许部分单词和交换单词。这可能吗？

例如，现在，如果菜单项是“Finance Rate Maintenance”，则以下任何一项都将与该菜单项匹配：“finance”、“finance ra”、“rate finance”等。“inance rate”不会匹配，因为“inance”没有出现在该菜单项的任何单词的开头。我想要“fnane rate”和“rate maintenance”之类的搜索，它们的拼写略有错误以匹配。

我带着另一个冗长的问题回来了。在尝试了许多基于 Python 的 Damerau-Levenshtein 编辑距离实现后，我终于找到了下面列出的editdistance_reference(). 它似乎提供了正确的结果，并且似乎有一个有效的实施。

所以我开始着手将代码转换为 Cython。在我的测试数据中，参考方法能够提供 11,000 次比较的结果（对于 12 个字母长的词对），而 Cythonized 方法每秒进行超过 200,000 次比较。可悲的是，结果不正确：当您查看thisrow 我打印出来进行调试的变量时，无论我向其输入什么数据，我的版本都充满了变量，而参考输出显示了另一张图片。例如，测试'helo'产生'world' 以下输出（ED标记我的函数，EDR是正确工作的参考）：

来自editdistance()：

来自editdistance_reference()：

我一定很愚蠢，因为错误可能是那些非常明显的事情之一。但我似乎找不到它。

还有第二个问题：三个数组、、 和malloc的 i 空间，然后它们以循环方式交换。当我尝试等等时，我得到一条 glibc 抱怨的行。我用谷歌搜索过；会不会是指针交换业务让 glibc 有点头晕，从而无法正确释放内存？twoagooneagothisrowfree( twoago )double free or corruption

下面我首先列出setup.py进行编译所需的内容（/path/to/python3.1 ./setup.py build_ext --inplace），然后是适当的编辑距离代码，因此有兴趣的人会发现它更容易复制。

还有一件事：这是用 Python3.1 运行的；一件有趣的事情是，在*.pyx文件内部我们确实有裸 unicode 字符串，但print它仍然是一个语句，而不是一个函数。

是的，我知道这里有很多代码要粘贴，但问题是，当你把它剪得太多时，代码根本无法运行。我相信除了editdistance()正常工作之外的所有方法，但请随时指出您发现的任何问题。

setup.py：

cython_dameraulevenshtein.pyx（一直滚动到最后，看看有趣的东西）：

编辑我还将此文本发布到pastebin和 Cython 列表。

昨天我有一个问题，人们建议我使用Levenshtein方法。它是一个缓慢的查询吗？也许我可以用别的东西？

我有一长串单词，我将它们放入一个非常简单的 SOLR / Lucene 数据库中。我的目标是从单项查询列表中找到“相似”单词，其中“相似性”具体理解为 (damerau) levensthein 编辑距离。我了解 SOLR 为拼写建议提供了这样的距离。

在我的 SOLRschema.xml中，我配置了一个字段类型string：

我用来定义一个字段

我想搜索这个字段并根据他们的编辑距离返回结果。但是，当我webspace~0.1对 SOLR 运行带有调试和解释的查询时，报告显示在计算分数时需要考虑很多因素，例如：

显然，对于我的应用，词频、idfs 等是没有意义的，因为每个文档只包含一个词。我尝试使用拼写建议组件，但没有设法让它返回实际的相似度分数。

任何人都可以提供提示如何配置 SOLR 以执行 levensthein / jaro-winkler / n-gram 搜索并返回分数并且不做额外的东西，比如,tf等等？在某处是否有 SOLR 的基本配置示例？我发现选项的数量确实令人生畏。idfboost

我正在玩在 Haskell 中计算Levenshtein 距离，并且对以下性能问题感到有点沮丧。如果您为 Haskell 实现最“正常”的方式，如下所示（dist），一切正常：

但是，如果你稍微弯曲你的大脑并将其实现为 dist'，它的执行速度会快得多（大约 10 倍）。

我已经尝试seq了第一个版本中的所有常用技巧，但似乎没有什么可以加快速度。这对我来说有点不满意，因为我希望第一个版本更快，因为它不需要评估整个矩阵，只需要评估它需要的部分。

有谁知道是否有可能让这两个实现类似地执行，或者我只是在后者中获得尾递归优化的好处，因此如果我想要性能，就需要忍受它的不可读性？

谢谢，猎户座

我有以下实现，但我想添加一个阈值，所以如果结果要大于它，就停止计算并返回。

我该怎么做呢？

编辑：这是我当前的代码，threshold尚未使用......目标是使用它

我正在研究模糊搜索实现，作为实现的一部分，我们正在使用 Apache 的 StringUtils.getLevenshteinDistance。目前，我们正在为我们的模糊搜索设定一个特定的最大平均响应时间。经过各种增强和一些分析后，花费最多时间的地方是计算 Levenshtein 距离。搜索三个字母或更多字母的字符串大约占总时间的 80-90%。

现在，我知道这里可以做的事情有一些限制，但我已经阅读了以前的 SO 问题和 LD 的 Wikipedia 链接，如果有人愿意将阈值限制在设定的最大距离，这可能有助于遏制花在算法上的时间，但我不确定如何准确地做到这一点。

如果我们只对小于阈值 k 的距离感兴趣，那么在矩阵中计算宽度为 2k+1 的对角条纹就足够了。这样，算法可以在 O(kl) 时间内运行，其中 l 是最短字符串的长度。 [3]

下面您将看到来自 StringUtils 的原始 LH 代码。之后是我的修改。我试图基本上计算从 i,j 对角线到设定长度的距离（因此，在我的示例中，在 i,j 对角线的上方和下方有两条对角线）。但是，这不可能是正确的，因为我已经这样做了。例如，在最高的对角线上，它总是会选择正上方的单元格值，这将是 0。如果有人能告诉我如何按照我所描述的那样使它起作用，或者关于如何使它如此的一些一般性建议， 这将不胜感激。

我的修改（仅限于 for 循环）：