问题标签 [levenshtein-distance]

不同的软件项目有不同的编码约定；即使在同一个项目中，也可能使用不同的语言并且会有不同的约定。使用源代码中的标识符标记搜索文档（出现在源文件之外）有什么好处？

例如，如果源具有self._def_passwd或this.defPasswd，则文档树上的查询应努力匹配默认密码。

到目前为止，我一直在尝试按 Levenshtein 距离进行排序，这对于较小的编辑距离非常有效，但是当我增加阈值时会出现太多误报，这对文档中的空白是有问题的。

其中第一个值是 Levenshtein 距离，第二个值是距离除以匹配单词的长度。我想

1. 研究 Jaccard，Tanimoto 算法
2. 智能/建议有点代码
3. 在某处，有一些关于生物家伙用于匹配序列的算法的帖子
4. 根据http://en.wikipedia.org/wiki/Naming_convention_%28programming%29提出正则表达式链式规则

最后一个实际上是最后一个选项。您认为哪些其他算法可以为这类东西提供更好的结果？

我正在研究 C++ 中的拼写检查器，但我被困在实现的某个步骤。

假设我们有一个包含正确拼写单词的文本文件和一个我们想要检查拼写错误的输入字符串。如果该字符串是拼写错误的单词，我可以通过检查文本文件中的所有单词并选择与它不同且字母最少的单词来轻松找到其正确形式。对于这种类型的输入，我实现了一个计算 2 个字符串之间的 Levenshtein 编辑距离的函数。到目前为止，一切都很好。

现在，困难的部分：如果输入的字符串是拼写错误的单词的组合怎么办？例如，“iloevcokies”。考虑到“i”、“love”和“cookies”是可以在文本文件中找到的词，我如何使用已经实现的 Levenshtein 函数来确定文件中哪些词适合更正？另外，我如何在正确的位置插入空白？

欢迎任何想法:)

我遇到了这种编辑距离问题的变体：

找到从一个词到另一个词的最短路径，例如storm->power，使用isValidWord()函数验证每个中间词。没有其他对单词字典的访问权限，因此无法构建图形。

我试图弄清楚这一点，但它本身似乎不是与距离相关的问题。也许使用简单的递归？但是，你怎么知道你正朝着正确的方向前进呢？

其他人觉得这很有趣吗？期待一些帮助，谢谢！

假设我想为Levensthein 距离（编辑距离）实现通常的动态规划算法。很容易想出递归：

这受到指数运行时间的影响，因此有必要记住该函数。我想通过使用 Data.Memocombinators 来做到这一点，并且我尝试了几种方法。这是我目前的尝试：

然而，记忆化似乎没有任何效果，尽管我希望任何记忆化都能显着改善运行时间，因为它至少是多项式的。我的实施有什么问题？如何在尽可能多地保留编辑距离的高级定义的同时获得良好的运行时间？

我已经阅读了有关计算两个不同单词之间距离的 Levenshtein distance 。

我有一个源字符串，我必须将它与所有 10,000 个目标词匹配。应该返回最接近的单词。

问题是我已经给出了 10,000 个目标词的列表，输入的源词也很庞大......那么在这里应用什么最短和有效的算法。每个组合（蛮力逻辑）的每个 n 的 Levenshtein 距离计算将非常耗时。

任何提示或想法都是最受欢迎的。

首先我想说我是python的新手。我试图计算许多单词列表的 Levenshtein 距离。到目前为止，我成功地为一对单词编写了代码，但我在为列表编写代码时遇到了一些问题。我只是有两个列表，其中一个在另一个下面，如下所示：carlos stiv peter

我想将 Levenshtein 距离用于相似性方法。有人能告诉我如何加载列表然后使用函数计算距离吗？

我会很感激的！

这是我的两个字符串的代码：

我想找出两个字符串之间的差异。例如，如果

然后我应该能够得到名称 - 年龄和 ABC - xyz 的差异。

我想我可以使用 Levenshtein 距离，但无法弄清楚。任何帮助是极大的赞赏。

我用 C++ 编写了 Levenshtein 算法

如果我输入：
字符串 s：民主党
字符串 t：共和党

我得到了填充矩阵 D 并且可以在 D[10][8] = 8 中读取操作数（Levenshtein 距离）
超出填充矩阵我想构造最佳解决方案。必须如何看待这个解决方案？我没有主意。
请只写给我这个例子的外观。

我需要一种将多个字符串与测试字符串进行比较并返回与其非常相似的字符串的方法：

（如果我这样做正确）与“TEST STRING”最接近的字符串应该是“CHOICE C”。最简单的方法是什么？

我计划将其实现为多种语言，包括 VB.net、Lua 和 JavaScript。此时，伪代码是可以接受的。如果您可以提供特定语言的示例，我们也很感激！

我已经在模型中编写了这些函数（我正在使用 CodeIgniter）。

此功能在控制器中

$allingrd是一组成分名称。我$closeword在 javascript 中显示警报消息。如果我给$lev=levenshtein($ingrdname,$allingrd[0])它完美的工作；但是，它不在循环中工作。关于为什么的任何想法？提前致谢。