问题标签 [levenshtein-distance]

我怎样才能将所有这些移到一个查询中？不想查询所有术语并在 PHP 中进行过滤。

Here is the problem states to convert a string into a palindrome with minimum number of operations. I know it is similar to the Levenshtein distance but I can't solve it yet

For example, for input mohammadsajjadhossain, the output is 8.

给定两个长度相等的字符串，Levenshtein 距离允许找到在给定第一个字符串的情况下获得第二个字符串所需的最小转换次数。但是，我想找到一种方法来调整多对字符串的算法，因为它们都是以相同的方式生成的。

我有一大堆查询并使用 levenshtein 来计算拼写错误，现在 levenshtein 导致 mysql 占用全部 cpu 时间。我的查询是 UNION 语句中的全文搜索 + levenshtein。sql1 是我当前的查询，sql2 只是全文搜索，速度快且不使用太多 cpu 时间，最后一个将达到峰值！

你们中的任何人都有其他方法来获取拼写错误吗？请不要回答规范化数据，我已经想到了，但不适用于我的数据，因为我无法预先进行匹配/计算并创建一个带有索引的单独表。

更新 3

完毕。下面是最终通过了我所有测试的代码。同样，这是模仿穆里洛·瓦斯康塞洛对史蒂夫·汉诺夫算法的修改版本。感谢所有帮助！

更新 2

最后，我设法使它适用于我的大多数测试用例。我的实现实际上是从Murilo 的 C++ 版本的Steve Hanov's algorithm的直接翻译。那么我应该如何重构这个算法和/或进行优化呢？下面是代码...

感谢所有为这个问题做出贡献的人。我试图让 Levenshtein Automata 工作，但我无法实现。

因此，我正在寻找有关上述代码的重构和/或优化建议。如果有任何混淆，请告诉我。与往常一样，我可以根据需要提供其余的源代码。

更新 1

所以我实现了一个简单的 Trie 数据结构，并且我一直在尝试按照 Steve Hanov 的 python 教程来计算 Levenshtein 距离。实际上，我对计算给定单词和 Trie 中的单词之间的最小Levenshtein 距离感兴趣，因此我一直在关注Murilo Vasconcelos 的 Steve Hanov 算法版本。它工作得不是很好，但这是我的 Trie 课程：

...和 ​​TrieNode 类：

现在，我尝试按照Murilo Vasconcelos的方式实现搜索，但是有些东西出了问题，我需要一些帮助来调试它。请就如何重构提出建议和/或指出错误在哪里。我想重构的第一件事是“minCost”全局变量，但这是最小的事情。无论如何，这是代码......

我为缺乏评论表示歉意。那么我做错了什么？

初始帖子

我一直在阅读一篇文章Fast and Easy Levenshtein distance using a Trie，希望找到一种有效的方法来计算两个字符串之间的Levenshtein 距离。我的主要目标是，给定大量单词，能够找到输入单词和这组单词之间的最小 Levenshtein 距离。

在我的简单实现中，我为每个输入词计算输入词和词集之间的 Levenshtein 距离，并返回最小值。它有效，但效率不高......

我一直在寻找 Java 中 Trie 的实现，并且遇到了两个看似不错的资源：

• Koders.com 版本
• code.google.com 版本 （编辑：这似乎已移至github.com/rkapsi）

但是，对于我正在尝试做的事情，这些实现似乎太复杂了。当我一直在阅读它们以了解它们如何工作以及 Trie 数据结构通常如何工作时，我只会变得更加困惑。

那么如何在 Java 中实现一个简单的 Trie 数据结构呢？我的直觉告诉我，每个 TrieNode 都应该存储它所代表的字符串以及对字母表字母的引用，不一定是所有字母。我的直觉正确吗？

一旦实现，下一个任务就是计算 Levenshtein 距离。我通读了上面文章中的 Python 代码示例，但我不会说 Python，一旦我点击递归搜索，我的 Java 实现就会耗尽堆内存。那么如何使用 Trie 数据结构计算 Levenshtein 距离？我有一个简单的实现，仿照这个源代码，但它不使用 Trie ......它效率低下。

除了您的评论和建议之外，看到一些代码真的很高兴。毕竟，这对我来说是一个学习过程……我从未实施过 Trie……所以我可以从这次经历中学到很多东西。

谢谢。

ps 如果需要，我可以提供任何源代码。另外，我已经按照Nick Johnson 的博客中的建议通读并尝试使用 BK-Tree ，但它的效率不如我想象的那么高……或者我的实现可能是错误的。

地狱，

PHP 有很多字符串函数，如 levenshtein、similar_text 和 soundex，可以比较字符串的相似性。 http://www.php.net/manual/en/function.levenshtein.php

哪个最适合准确性和性能？

您能解释一下为什么在确定 levenshtein 百分比时我需要同时使用输入字符串和匹配字符串吗？

我正在尝试以最快的方式提出搜索建议。起初我认为 Levenstein UDF 函数与 mysql 表相结合就可以完成这项工作。但是使用 levenshtein，mysql 将不得不检查表中的每一行（大量的单词），这会使查询变得非常慢。

现在我最近安装并开始使用 Sphinx ( http://sphinxsearch.com/ ) 进行全文搜索，主要是因为它的性能和 mysql 与 SphinxSE 的紧密集成。

所以我问自己是否可以使用 sphinx 实现“你的意思是”算法以某种方式提高性能，我想我找到了一个简单的算法。基本上我把所有我想更正的关键字，在每个字母之间放一个空格，然后把它放在狮身人面像索引中。如果这个词是'keyword'，它就变成'keyword d'。现在，当用户输入一个单词时，我将其拆分为字母并在 sphinx 索引中搜索与提供的任何字母匹配的记录（我只需要一个）。最好的部分是 sphinx 在计算匹配行的相关性（权重）方面非常好，所以最好的匹配总是有最大的权重（我认为）。它还考虑了单词（在我的情况下为字母）位置，因此最佳匹配将按该顺序排列。

通过 sphinx 查询，我在关键字列表中得到了最相似的词。然后我使用扩展的 Levenshtain 距离用 php 检查它，该距离占重新排列的字母https://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance。如果字符串距离小于 2（并且 != 0），则建议该词。否则不要提出任何建议。

我的想法有问题吗？有什么我没想到的？sphinx 查询的任何预期故障，以及不会给出最佳匹配的 sphinx 相关性计算的怪癖？如果我在某个地方弄错了，请纠正我。

给定字符串 A，BI 需要计算 B 成为 A 的插入、删除和替换的次数。什么是一个好的算法呢？

我正在构建一个 Android 应用程序，它接受一个字符串输入并使用 Google API 返回一个排序的书籍列表。

我正在寻找一种方法来比较用户输入的开放式字符串与列表中的第一项，以查看他们输入的内容是否“可能”是一本书。我有大量关于这本书、书名、作者、描述等的信息，所以我可以搜索任何部分。

一个例子是：

解决此问题的最佳方法是什么？我已经查看了 levenshtein 距离，但认为它不适用于这种开放式输入，n-gram 似乎是一个很好的方法，或者模糊匹配。

还有其他想法吗？