问题标签 [levenshtein-distance]

我目前正在编写的核心数据应用程序有一个小问题。我有两个不同的模型，上下文和永久存储。一个用于我的应用数据，另一个用于与我相关的网站。

大多数时候，我将我的应用程序中的一条记录与另一个来源的另一条记录完全匹配。然而，有时我不得不回退到模糊字符串匹配来链接两条记录。我正在尝试匹配歌曲标题。我的本地标题可能是（编造的）"The French Idealist is in your pensée"，而远程歌曲标题可能是"01 - 10 - French idealist in in you're pensee, The (dub remix, feat. DJ Objective-C)"

我搜索堆栈溢出、谷歌、可可文档，但在这些情况下我找不到任何关于如何进行模糊匹配的明确答案。我的字符串可以以任何开头，有一堆特殊字符，通常以随机或被忽略的字符结尾。

Regexp 不行，NSPredicates 也不行，Soundex 不能很好地处理外国名称，也许 Levenshtein 还不够（或者会吗？）。

我在一组大约十几个潜在的比赛中寻找一个标题，但我不得不做这个操作很多。100% 的准确率不是目标。

我正在考虑删除被忽略的单词，提取关键字（在本例中为“french, Idealist, pensée”），将它们连接起来，然后使用 Levenshtein 距离（歌曲标题中的单词应该按相同的顺序排列）。

在我的特殊情况下，它会起作用吗？关于这个问题的行业标准是什么（我不可能是世界上唯一一个想要匹配略有不同的歌曲名称的人）Core Data、Cocoa 或 Objective-C 可以帮助我吗？

非常感谢。

我对 Levenshtein 的距离很熟悉，所以我决定用它来解决UVA 的 Edit Steps Ladder 问题。

我的解决方案是：

使用此输入：

它为此示例产生正确的输出：

法官拒绝了我的回答。这是我第一次尝试解决在线法官的问题，我想我可能会在这里强制一个正确的答案：

因为 maxEdit 在简单地使用 Levenshtein 计算时的值为 4。这是怎么回事？

我的数据库中有一个字符串表。我选择其中一个，A。

如何搜索表的其余部分以找到与A最相似的字符串？

我目前正在使用similar_text将字符串与〜50,000 的列表进行比较，尽管由于比较的次数非常慢，但该列表有效。比较大约 500 个唯一字符串大约需要 11 分钟。

在运行它之前，我会检查数据库以查看它是否在过去被处理过，所以每次在初始运行之后它都接近即时。

我确信使用levenshtein会稍微快一些，并且手册中发布的 LevenshteinDistance 函数看起来很有趣。我是否遗漏了一些可以显着加快速度的东西？

我正在寻找这样一种算法，但它可以在单词之间而不是字母之间进行替换。有这样的算法吗？

我正在寻找 SQL Server 的实现，但算法的名称就足够了。

我想找到两个字符串之间的字符串相似性。此页面包含其中一些示例。Python 具有Levenshtein 算法的实现。在这些限制下，是否有更好的算法（希望是 python 库）。

1. 我想在字符串之间进行模糊匹配。例如matches('Hello, All you people', 'hello, all You people') 应该返回True
2. 假阴性是可以接受的，假阳性是可以接受的，除非在极少数情况下是不允许的。
3. 这是在非实时设置中完成的，因此速度不是（太多）问题。
4. [编辑] 我正在比较多字串。

除了 Levenshtein 距离（或 Levenshtein 比率）之外的其他东西会是我的情况更好的算法吗？

我将如何模拟 damerau leveshtein 距离算法以检测文档中的抄袭？谢谢！

我有一本包含“n”个单词的字典，并且有“m”个查询要响应。我想输出字典中编辑距离为 1 或 2 的单词数。鉴于 n 和 m 大约为 3000，我想优化结果集。

从下面的答案添加编辑：

我会尝试换一种说法。

最初有 'n' 个单词作为一组 Dictionary 单词给出。给出下一个“m”字，它们是查询词，对于每个查询词，我需要查找该词是否已存在于字典中（编辑距离“0”）或字典中位于编辑距离 1 或2 从字典单词。

我希望问题现在很清楚。

好吧，如果时间复杂度是 (m*n)n，它就会超时。DP 编辑距离算法的幼稚使用会超时。即使计算 2k+1 的对角元素也会超时，其中 k 是阈值，在上述情况下 k=3。

LD = Levenshtein 距离

只是在纸上做一些例子，这似乎有效，但有谁知道这是否总是正确的？

假设我有 3 个字符串

机器人

鲍勃

物料清单

LD(BOT,BOB) = 1

和

LD(BOB,BOM)=1

然后

LD(BOT,BOM)=max(LD(BOT,BOB) , LD(BOB,DOM))=1

或者

巴布

BBAB

BCCD

LD(BBAB,BAAB) = 1

和

LD(BBAB,BCCD)=3

然后

LD(BAAB,BCCD)=最大值(LD(BBAB,BAAB), LD(BBAB,BCCD))=3

我想知道这是否总是适用。

那是，

LD(B,C) = 最大值 (LD(A,C),LD(A,B))

编辑——添加于太平洋标准时间 2009 年 10 月 22 日晚上 7:08

我开始认为这适用于相同长度的单词，否则你仍然可以这样做，但你必须添加单词长度差异的绝对值。

本质上LD(B,C) = max(LD(A,C),LD(A,B)) + abs(length(B)-length(C))

Apaches Solr 搜索引擎是否提供近似字符串匹配，例如通过 Levenshtein 算法？

我正在寻找一种按姓氏查找客户的方法。但我不能保证名称的正确性。如何配置 Solr 以便即使我搜索“Levenstein”也能找到“Levenshtein”这个人？