标签: levenshtein-distance

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

TEST STRING: THE BROWN FOX JUMPED OVER THE RED COW

CHOICE A   : THE RED COW JUMPED OVER THE GREEN CHICKEN
CHOICE B   : THE RED COW JUMPED OVER THE RED COW
CHOICE C   : THE RED FOX JUMPED OVER THE BROWN COW

(如果我这样做的话)最接近"TEST STRING"的字符串应该是"CHOICE C".最简单的方法是什么？

我计划将其实现为多种语言,包括VB.net,Lua和JavaScript.此时,伪代码是可以接受的.如果您可以提供特定语言的示例,这也是值得赞赏的!

我想做模糊字符串比较,但与使用哪个库混淆.

选项1:

import Levenshtein
Levenshtein.ratio('hello world', 'hello')

Result: 0.625

选项2:

import difflib
difflib.SequenceMatcher(None, 'hello world', 'hello').ratio()

Result: 0.625

在这个例子中,两者给出了相同的答案.但我更喜欢使用__CODE__.专家的任何建议.谢谢.

__CODE__

我正在进行临床信息规范化(拼写检查),其中我检查每个给定的单词对900,000字的医学词典.我更关注时间复杂度/性能.

在这种情况下,你认为两者都表现相似吗？

在实现伴随单词建议的拼写检查器时,通常使用什么算法？

起初我认为检查每个键入的新单词(如果没有在字典中找到)与字典中的每个其他单词的Levenshtein距离并返回最高结果可能是有意义的.然而,这似乎非常低效,不得不反复评估整个字典.

这通常是怎么做的？

我对计算Levenshtein距离的T-SQL算法感兴趣.

我有一个用例,我需要对来自多个文件的数百万条记录进行模糊匹配.我确定了两种算法:Jaro-Winkler和Levenshtein编辑距离.

当我开始探索两者时,我无法理解两者之间的确切差异.似乎Levenshtein给出了两个字符串之间的编辑数量,而Jaro-Winkler给出了0.0到1.0之间的匹配分数.我不明白算法.由于我需要使用任何一种算法,我需要知道算法性能的确切差异.

我需要计算2个字符串之间的相似度.那究竟是什么意思呢？让我用一个例子来解释一下:

• 真实的一句话: hospital
• 误区: haspita

现在我的目标是确定修改错误单词以获得真实单词所需的字符数.在这个例子中,我需要修改2个字母.那么百分比是多少？我总是把真正的词长度.因此它变为2/8 = 25%所以这两个给定的字符串DSM是75%.

如何以性能为关键考虑因素来实现这一目标？

我有excel表格的数据,我想得到Levenshtein他们之间的距离.我已经尝试导出为文本,从脚本(php)读入,运行Levenshtein(计算Levenshtein距离),再次将其保存为excel.

但我正在寻找一种以编程方式计算VBA中的Levenshtein距离的方法.我该怎么做呢？

对于我正在研究的问题,找到两个序列之间的距离来确定它们的相似性,序列顺序非常重要.但是,我所拥有的序列长度并不完全相同,所以我用空点填充任何不足的字符串,使得两个序列的长度相同,以满足汉明距离要求.我这样做是否有任何重大问题,因为我所关心的只是换位次数(不是像Levenshtein那样的插入或删除)？

我发现汉明距离比Levenshtein快得多,作为长度较长的序列的距离度量.何时应该使用Levenshtein距离(或Levenshtein距离的导数)而不是更便宜的汉明距离？汉明距离可以被认为是两个序列之间可能的Levenshtein距离的上限,因此如果我将两个序列进行比较以获得有序偏差的相似性度量而不是绝对最小的移动数量以匹配序列,则没有明显的我之所以选择Levenshtein而不是Hamming作为指标,是吗？

所以我有一个随机的javascript数组...

[@ larry,@ nicholas,@ notch]等

它们都以@符号开头.我想用Levenshtein距离对它们进行排序,以便列表顶部的那些最接近搜索项.目前,我有一些使用jQuery的javascript,.grep()使用javascript .match()方法围绕按键输入的搜索词:

(自首次发布以来编辑的代码)

limitArr = $.grep(imTheCallback, function(n){
    return n.match(searchy.toLowerCase())
});
modArr = limitArr.sort(levenshtein(searchy.toLowerCase(), 50))
if (modArr[0].substr(0, 1) == '@') {
    if (atRes.childred('div').length < 6) {
        modArr.forEach(function(i){
            atRes.append('<div class="oneResult">' + i + '</div>');
        });
    }
} else if (modArr[0].substr(0, 1) == '#') {
    if (tagRes.children('div').length < 6) {
        modArr.forEach(function(i){
            tagRes.append('<div class="oneResult">' + i + '</div>');
        });
    }
}

$('.oneResult:first-child').addClass('active');

$('.oneResult').click(function(){
    window.location.href = 'http://hashtag.ly/' + $(this).html();
});

它还有一些if语句,用于检测数组是否包含主题标签(#)或提及(@).忽略这一点.这imTheCallback是名称数组,无论是主题标签还是提及,然后modArr是排序的数组.然后.atResults, …

我想创建一个模糊搜索算法.然而,经过数小时的研究,我真的很挣扎.

我想创建一个算法,在学校名称列表上执行模糊搜索.

这是我到目前为止所看到的:

我的大部分研究都指向Google和Stackoverflow上的" 字符串指标 ",例如:

• Levenshtein距离
• Damerau-Levenshtein距离
• Needleman-Wunsch算法

然而,这仅仅给出了两个字符串相似的分数.我可以想到将其实现为搜索算法的唯一方法是执行线性搜索并对每个字符串执行字符串度量算法,并返回分数高于某个阈值的字符串.(原来我把我的琴弦存放在一棵树上,但这显然不会帮助我!)

虽然这对于小型列表来说并不是一个坏主意,但对于名为100,000个名称的列表来说,这将是一个问题,并且用户执行了许多查询.

我看到的另一种算法是拼写检查方法,您只需搜索所有可能的拼写错误.然而,这也是非常低效的,因为对于长度为7的单词而言需要超过75,000个单词并且错误计数仅为2.

我需要的？

有人可以建议我一个很好的高效模糊搜索算法.有:

• 算法的名称
• 它是如何工作的或它是如何工作的链接
• Pro和cons以及何时最佳使用(可选)

我知道所有算法都有其优点和缺点,没有最好的算法.