标签: levenshtein-distance

我希望能够按照以下方式搜索一个表格,因为它可以获得1个方差范围内的所有内容.

数据:

O'Brien
Smithe
Dolan
Smuth
Wong
Smoth
Gunther
Smiht

我已经研究过使用Levenshtein距离有没有人知道如何实现它？

我想找到两个字符串之间的字符串相似性.此页面包含其中一些示例.Python有Levenshtein算法的实现.在这些约束下,是否有更好的算法(并且希望是python库).

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

除了Levenshtein距离(或Levenshtein比率)以外的其他东西对我的情况更好吗？

我一直在寻找一种先进的levenshtein距离算法,到目前为止我发现的最好的是O(n*m),其中n和m是两个弦的长度.算法处于这种规模的原因是因为空间而不是时间,创建了两个字符串的矩阵,例如:

是否有一个公开的levenshtein算法,它比O(n*m)更好？我并不反对看高级计算机科学论文和研究,但却找不到任何东西.我找到了一家名为Exorbyte的公司,该公司据称已经建立了超级先进且超快的Levenshtein算法,但当然这是商业秘密.我正在构建一个iPhone应用程序,我想使用Levenshtein距离计算.有一个Objective-c实现可用,但由于iPod和iPhone上的内存有限,我想找到一个更好的算法,如果可能的话.

我想使用字符串相似性函数来查找我的数据库中的损坏数据.

我遇到了其中几个:

• 哈罗,
• 哈罗,温克勒,
• 莱文斯坦,
• 欧几里德和
• Q-克,

我想知道它们之间的区别以及它们最适合的情况？

我想比较两个字符串并获得一些评分看起来有多相似.例如"句子几乎相似"和"句子相似".

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

Java中有更好的方法吗？

更新3

完成.下面是最终通过我所有测试的代码.再次,这是模仿Murilo Vasconcelo的Steve Hanov算法的修改版本.感谢所有帮助!

/**
 * Computes the minimum Levenshtein Distance between the given word (represented as an array of Characters) and the
 * words stored in theTrie. This algorithm is modeled after Steve Hanov's blog article "Fast and Easy Levenshtein
 * distance using a Trie" and Murilo Vasconcelo's revised version in C++.
 * 
 * http://stevehanov.ca/blog/index.php?id=114
 * http://murilo.wordpress.com/2011/02/01/fast-and-easy-levenshtein-distance-using-a-trie-in-c/
 * 
 * @param ArrayList<Character> word - the characters of an input word as an array representation
 * @return int - the minimum …

分析显示这是我写的一个小字游戏的代码中最慢的部分:

def distance(word1, word2):
    difference = 0
    for i in range(len(word1)):
        if word1[i] != word2[i]:
            difference += 1
    return difference

def getchildren(word, wordlist):
    return [ w for w in wordlist if distance(word, w) == 1 ]

笔记:

• distance()被调用超过500万次,其中大部分是来自getchildren,它应该让wordlist中的所有单词与word1个字母完全不同.
• wordlist被预先过滤为只有包含相同数量字母的单词,word所以它保证word1并word2具有相同数量的字符.
• 我是Python的新手(3天前开始学习它)所以对命名约定或其他风格的东西的评论也很受欢迎.
• 对于wordlist,使用"2 + 2lemma.txt"文件获取12dict单词列表

结果:

谢谢大家,通过不同建议的组合,我现在运行程序的速度提高了两倍(除了我自己在询问之前做的优化之外,所以从初始实现开始,速度提高了4倍)

我测试了2组输入,我称之为A和B.

优化1:迭代word1,2 ...的索引

for i in range(len(word1)):
        if word1[i] != word2[i]:
            difference += 1
    return difference

使用迭代迭代字母对zip(word1, word2)

for x,y in zip …

我使用PHP levenshtein函数比较字符串有一些成功.

但是,对于包含已交换位置的子串的两个字符串,算法会将这些字符串计为全新的子字符串.

例如:

levenshtein("The quick brown fox", "brown quick The fox"); // 10 differences

被视为没有共同点:

levenshtein("The quick brown fox", "The quiet swine flu"); // 9 differences

我更喜欢一种算法,它看到前两个更相似.

我怎么能想出一个比较函数,它可以识别将位置切换为与编辑不同的子串？

我想到的一种可能的方法是在比较之前将字符串中的所有单词按字母顺序排列.这使得单词的原始顺序完全脱离了比较.然而,这样做的一个缺点是,只更改一个单词的第一个字母可能会造成比单个字母更改所造成的更大的中断.

我想要实现的是比较两个关于自由文本字符串的人的事实,并决定这些事实表明相同事实的可能性.事实可能是有人上学的学校,例如雇主或出版商的名字.两个记录可能有相同的学校拼写不同,单词的顺序不同,额外的单词等,所以如果我们要好好猜测他们指的是同一所学校,那么匹配必须有些模糊.到目前为止,它在拼写错误方面表现得非常好(我使用的是一种类似于metaphone的phoenetic算法),但是如果你改变学校中常见的单词顺序则非常糟糕:"xxx college"vs "xxx学院".

这是一个难题......

我有两个相同50000+电子产品的数据库,我想将一个数据库中的产品与另一个数据库中的产品相匹配.但是,产品名称并不总是相同的.我已经尝试使用Levenshtein距离来测量弦的相似性但是这没有用.例如,

-LG 42CS560 42-Inch 1080p 60Hz LCD HDTV
-LG 42 Inch 1080p LCD HDTV

这些项目是相同的,但他们的产品名称变化很大.

另一方面...

-LG 42 Inch 1080p LCD HDTV
-LG 50 Inch 1080p LCD HDTV

这些是具有非常相似产品名称的不同产品.

我该如何解决这个问题？

我有一组(2k - 4k)的小字符串(3-6个字符),我想将它们聚类.由于我使用字符串,以前的答案关于如何进行聚类(尤其是字符串聚类)？,告诉我,Levenshtein距离很适合用作弦乐的距离函数.此外,由于我事先并不知道群集的数量,因此分层聚类是要走的路而不是k-means.

虽然我以抽象的形式得到问题,但我不知道实际做什么的简单方法.例如,MATLAB或R是使用自定义函数(Levenshtein距离)实际实现层次聚类的更好选择.对于这两种软件,人们可以很容易地找到Levenshtein距离实现.聚类部分似乎更难.例如,MATLAB中的聚类文本计算所有字符串的距离数组,但我无法理解如何使用距离数组来实际获得聚类.你能不能向大家们展示如何在MATLAB或R中使用自定义函数实现层次聚类的方法？