标签: levenshtein-distance

我有一个给出'n'字样的字典,并且有'm'查询要回复.我想在字典中输出编辑距离为1或2的单词数.我想优化结果集,因为n和m大约是3000.

编辑从以下答案中添加:

我会尝试用不同的方式来表达它.

最初有'n'个单词作为一组字典单词给出.接下来给出的'm'单词是查询单词,对于每个查询单词,我需要查找单词是否已经存在于Dictionary(编辑距离'0')中,或者字典中单词的总计数是否在编辑距离1或者2来自字典的单词.

我希望问题现在是明确的.

好吧,如果时间复杂度为(m*n)n则超时.DP编辑距离算法的天真使用超时.甚至计算2k + 1次的对角元素,其中k是阈值,在这里k = 3.

请问Levenshtein距离的非英语语言字符串太算法的工作呢？

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

我想知道是否有一种有效的数据结构来执行“检索所有 levenshtein 距离小于 X 的字符串”。

我感兴趣的几件事：

• 算法说明。
• 现有数据库/编程语言中是否有现有实现？
• 我可以参考的论文/文章？

我想运行Levenshtein,但速度更快,因为它是我正在构建的实时应用程序.一旦距离大于10,它就可以终止.

我有一个包含以下各列的MySQL表：

City      Country  Continent
New York  States   Noth America
New York  Germany  Europe - considering there's one ;)
Paris     France   Europe

如果我想找到带有错字的“ New Yokr”，那么使用MySQL存储函数很容易：

$querylev = "select City, Country, Continent FROM table 
            WHERE LEVENSHTEIN(`City`,'New Yokr') < 3"

但是，如果有两个纽约城市，以全文搜索，则可以输入“ New York States”，您会得到想要的结果。

所以问题是，我可以搜索“ New Yokr Statse”并获得相同的结果吗？

是否有任何将levenshtein和全文本合并以形成一个完整解决方案的函数，还是应该在MySQL中创建一个将三列连接在一起的新列？

我知道还有其他解决方案，例如lucene或Sphinx（也有soundex，metaphone，但对此无效），但我认为对我来说可能很难实现。

在Ruby中,我有一个由大约一百万个字符串组成的数组dictionary_array.我有另一个由大约数千个字符串组成的数组arr.

对于每个元素arr,我想找到一个dictionary_array最接近的元素.

迭代每个元素arr,并且arr迭代每个元素dictionary_array以找到具有最小Levenshtein距离的元素是O(n ^ 2)并且对于我的目的而言太慢.

有没有更好的方法来解决这个问题？

我正在将校园内的建筑物名称与来自各种数据库的输入进行比较。人们输入这些名称，每个人都使用自己的缩写方案。我试图从用户输入到名称的规范形式中找到最佳匹配。

我已经实现了一个递归的 Levenshtein 距离方法，但是我正在尝试解决一些边缘情况。我的实现在 GitHub 上。

一些建筑物的名称是一个词，而另一些则是两个词。一个词上的一个词会产生相当准确的结果，但我需要记住两件事。

1. 缩写：假设输入是名称的缩写版本，有时我可以在输入和任意名称之间获得相同的 Levenshtein 距离，以及正确的名称。例如，如果我的输入是“ Ing”并且建筑物名称^1. are ["Boylan", "Ingersoll", "Whitman", "Whitehead", "Roosevelt", and "Library"]，我最终得到 6 的 LDBoylan和Ingersoll。想要的结果就在这里Ingersoll。

2. 多字字符串：第二个边缘情况是输入和/或输出是两个单词，用空格分隔。例如，New Ing是 的缩写New Ingersoll。在这种情况下，New Ingersoll 和 Boylan 的 Levenshtein 距离得分均为 6。如果我要拆分字符串，则完美New匹配New，然后我只需要参考我之前的边缘情况的解决方案。

处理这两种边缘情况的最佳方法是什么？

_{1. 对于好奇的人来说，这些是纽约市布鲁克林学院的建筑。}

我有以下任务.

给出的字符串列表如下:

        var strings = [
            'Steve jobs created the iPod when he was at Apple',
            'I really like the new Macbook by Apple',
            'Jony Ive was concerned being fired by Steve Jobs after his return to Apple',
            'The new Macbook has just one USB-C type connector',
            'I like bananas',
            'The brezels I can buy in my local store are much better than the ones in the supermarket',
            'the',
            'foo',
            'Steve'
        ];

我现在想要将每个字符串相互比较,并且对于每个比较,我想知道它们在0-1(或0%-100%)的范围内彼此之间的相似程度.

所以,我google了一下,发现了这个:Java中的相似性字符串比较

所以,我按照那里的指令,将方法移植similarity(String s1, String s2) …

根据维基百科,可以对Wagner-Fischer算法进行修改,该算法可以计算出两个单词的Levenshtein距离是否低于某个阈值,如果你想知道的话,这比原来的快得多.

"通过检查对角线而不是行,并通过使用延迟评估,我们可以在O(m(1 + d))时间内找到Levenshtein距离(其中d是Levenshtein距离),这比常规动态编程算法快得多如果距离很小."

这个解决方案如何运作？我真的很难看到它,因为感觉任何矩阵单元格的值都取决于上面的单元格的值,左边和左边的对角线,所以我不知道如何遍历矩阵仅使用斜条.

我一直在使用R中的"adist"函数,它计算两个字符串之间的Levenshtein距离.这是一个可重复的例子:

>a <- c("bonjour", "bonsoir", "good morning", "hello world")
>b <- c("maman", "bienjoue", "printemps")

>adist(a, b, counts = TRUE)

我得到的结果如下:

     [,1] [,2] [,3]
[1,]    7    3    8
[2,]    7    5    8
[3,]   10   11   12
[4,]   11   10   11

attr(,"counts")

, , ins

     [,1] [,2] [,3]
[1,]    0    1    2
[2,]    0    1    2
[3,]    0    0    1
[4,]    0    1    0

, , del

     [,1] [,2] [,3]
[1,]    2    0    0
[2,]    2    0    0
[3,]    7    4    4 …