问题标签 [levenshtein-distance]

我有带有 Postgres 后端的 Rails 应用程序。

我需要添加全文搜索，这将允许基于 Levenshtein 距离或其他类似指标的模糊搜索。添加词法分析器/词干分析器必须使用非英语单词的事实（可以在词法分析时关闭与语言相关的功能，以免与目标语言混淆，因为目标语言可能具有被英语引擎认为不相关的有意义的单词）。

我猜 Postgres 的 tsearch 在这里不适用，因为它没有模糊搜索——如果我错了，请纠正我。

后端和插件的可能组合是什么？它更喜欢对基础设施添加较少的解决方案（例如，如果 Postgres 可以有模糊 fts，为什么要使用外部 Lucene）；OTOH，所涉及的 Rails 插件的质量也很重要。

你会推荐什么？

更新：似乎我需要基于 n-gram 的指标而不是 Levenshtein。

我在一个数组中有 5000 个，有时甚至更多的街道地址字符串。我想将它们与 levenshtein 进行比较以找到相似的匹配项。如果不遍历所有 5000 并将它们与其他所有 4999 直接比较，我怎么能做到这一点？

编辑：如果有人有建议，我也对替代方法感兴趣。总体目标是根据用户提交的街道地址找到相似的条目（并消除重复项）。

我正在用 PHP 创建一个网络应用程序，人们可以在其中尝试翻译他们需要在学校学习的单词。

例如，有人需要将荷兰语单词“weer”翻译成英语中的“weather”，但不幸的是他输入了“whether”。因为他几乎打错了字，我想再试一次，.在他打错的地方加点“”：

或者，例如

或者：

但是，如果输入与所需的翻译相差太大，我不想得到像这样的输出........

我听说过 Levenshtein 距离，我认为我需要一种与该算法非常相似的算法，但我不知道如何将点放在正确的位置，而不是回显要完成多少操作。

那么，如何在某人犯错的地方返回拼写错误的单词呢？

在Levenshtein 距离算法中，这条线做了什么？：

尽管它获得了所有这些值中的最小值，但为什么将成本添加到末尾，为什么我们在每个数组索引器（前两个参数）的末尾都有 + 1？

我一直在尝试修改 Levenshtein Distance 函数，以便它可以找到两条线之间的距离，或 xy 坐标集（换句话说，线的相似或不同，而不是它们的几何距离）。我遇到了一些问题。我知道您如何使用上面的值来获得删除成本，而左边的值是为了获得加法，但是在替换过程中我试图使用欧几里得距离，它对我不起作用。

如果你能指出我做错了什么，那就太棒了。

这是javascript中的相关代码：

样本输出：

我想比较两个字符串并得到一些分数，它们看起来有多相似。例如“句子几乎相似”和“句子很相似”。

我不熟悉 Java 中的现有方法，但对于 PHP，我知道levenshtein 函数。

Java中有更好的方法吗？

我正在编写一个差异文本工具来比较两个相似的源代码文件。

周围有很多这样的“差异”工具，但我的应该会有所改进：

如果它发现一组行在两边不匹配（即在两个文件中），它不仅应突出显示这些行，还应突出这些行中的各个更改（我在这里称之为行间比较）。

我的一些可行的解决方案的一个例子：

替代文本 http://files.tempel.org/tmp/diff_example.png

它目前所做的是采用一组不匹配的行并再次通过差异算法运行它们的单个字符，从而产生粉红色突出显示。

但是，包含“原始 2”的第二组不匹配需要更多工作：这里，添加了前两行右侧（“添加的行 a/b”），而第三行是左侧的更改版本。我希望我的软件能够检测到可能的更改和可能的新行之间的差异。

在看这个简单的例子时，我可以很容易地检测到这种情况：

使用 Levenshtein 之类的算法，我可以发现在 3 到 5 组中的所有右行中，第 5 行与左行 3 匹配得最好，因此我可以推断出添加了右侧的第 3 行和第 4 行，并执行 inter - 左行 3 和右行 5 的行比较。

到目前为止，一切都很好。但是我仍然坚持如何将其变成为此目的的更通用的算法。

在更复杂的情况下，一组不同的线条可能会在两侧添加线条，中间有一些紧密匹配的线条。这变得相当复杂：

我不仅必须将左侧的第一行与右侧的最佳行匹配，反之亦然，以此类推。基本上，我必须将左边的每一行与右边的每一行相匹配。在最坏的情况下，这可能会产生甚至交叉，因此不再容易清楚哪些行是新插入的，哪些行是刚刚更改的（注意：我不想处理这样一个块中可能移动的行，除非这实际上会简化算法）。

当然，这永远不会是完美的，但我正在努力让它变得比现在更好。任何不太理论但相当实用的建议（我不太了解抽象算法）都会受到赞赏。

更新

我必须承认我什至不明白 LCS 算法是如何工作的。我只是简单地给它输入两个字符串数组，然后输出一个不匹配的序列列表。我基本上使用这里的代码：http: //www.incava.org/projects/java/java-diff

查看代码，我发现一个函数 equal() 负责告诉算法两行是否匹配。根据 Pavel 的建议，我想知道这是否是我进行更改的地方。但是怎么做？这个函数只返回一个布尔值——而不是一个可以识别匹配质量的相对值。而且我不能简单地使用一个固定的 Levenshtein 配给来决定一条类似的线是否仍然被认为是相等的——我需要一些能够自我采用的东西来适应整个有问题的线。

所以，我基本上要说的是，我仍然不明白我将在哪里应用与不（完全）匹配的线条的相对相似性相关的模糊值。

Levenshtein距离算法也适用于非英语语言字符串吗？

更新：在比较亚洲字符时，这会在 Java 等语言中自动工作吗？

在实现带有单词建议的拼写检查器时通常使用什么算法？

起初，我认为检查输入的每个新单词（如果在字典中找不到）与字典中每个其他单词的Levenshtein 距离并返回最佳结果可能是有意义的。但是，这似乎效率很低，必须反复评估整个字典。

这通常是如何完成的？

我有两个字幕文件。我需要一个函数来判断它们是代表相同的文本还是相似的文本

有时仅在一个文件中会出现诸如“风在吹……音乐正在播放”之类的评论。但是 80% 的内容将是相同的。该函数必须返回 TRUE（文件代表相同的文本）。有时会出现像 1 这样的拼写错误，而不是 l (one - L)，如下所示： She 1eft the bag。当然，这意味着函数必须返回 TRUE。

我的评论：
该函数应该返回文本相似度的百分比 - 同意

“所有人都很开心”和“所有人都不开心”——在这里这会被认为是拼写错误，所以会被认为是相同的文本。确切地说，函数返回的百分比会更低，但足以说明短语相似

请考虑是否要将 Levenshtein 应用于整个文件或只是一个搜索字符串 - 不确定 Levenshtein，但该算法必须应用于整个文件。不过，这将是一个很长的字符串。