标签: levenshtein-distance

我正在尝试提出最快的搜索建议方法.起初我认为Levenstein UDF函数结合mysql表可以完成这项工作.但是使用levenshtein,mysql必须遍历表中的每一行(大量的单词),这会使查询真的变慢.

现在我最近安装并开始使用Sphinx(http://sphinxsearch.com/)进行全文搜索,主要是因为它的性能和与SphinxSE的紧密mysql集成.

所以我问自己是否可以使用sphinx以某种方式实现"你的意思"算法来提升性能,我想我发现了一个简单的算法.基本上我采取我想要纠正的所有关键字,在每个字母之间放一个空格,然后将它放在sphinx索引中.如果单词是'keyword',它就变成'keywor d'.现在,当用户输入一个单词时,我将其拆分为字母,并在sphinx索引中搜索与所提供的任何字母匹配的记录(我只需要一个).最好的部分是狮身人面像非常适合计算匹配行的相关性(权重),因此最佳匹配总是具有最大权重(我认为).它还会考虑单词(我的情况下的字母)位置,因此最佳匹配将按此顺序排列.

通过sphinx查询,我在关键字列表中得到了最相似的单词.然后我使用扩展的Levenshtain距离检查它,它考虑了重新排列的字母http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance.如果字符串距离小于2(和!= 0),则建议单词.否则不建议任何事情.

我的想法有问题吗？我没想到的东西？任何预期的sphinx查询故障,以及与sphinx相关性计算的怪癖都没有给出最佳匹配？如果我在某处误会,请纠正我.

我试图用一点插件来实现levenshtein算法.我想优先考虑具有连续匹配字母的值.我已经尝试使用下面的代码实现我自己的形式:

function levenshtein_rating($string1, $string2) {
    $GLOBALS['lvn_memo'] = array();
    return lev($string1, 0, strlen($string1), $string2, 0, strlen($string2));
}

function lev($s1, $s1x, $s1l, $s2, $s2x, $s2l, $cons = 0) {
    $key = $s1x . "," . $s1l . "," . $s2x . "," . $s2l;
    if (isset($GLOBALS['lvn_memo'][$key])) return $GLOBALS['lvn_memo'][$key];

    if ($s1l == 0) return $s2l;
    if ($s2l == 0) return $s1l;

    $cost = 0;
    if ($s1[$s1x] != $s2[$s2x]) $cost = 1;
    else $cons -= 0.1;

    $dist = min(
                (lev($s1, $s1x + …

我有两个文本文件,我想比较.我做的是:

1. 我把它们分成了句子.
2. 我测量了一个文件中每个句子与第二个文件中每个句子之间的levenshtein距离.

我想计算这两个文本文件之间的平均相似度,但是我无法提供任何有意义的值 - 显然算术平均值(所有距离之和[标准化]除以比较次数)是一个坏主意.

如何解释这样的结果？

编辑:距离值已标准化.

我正在研究php的levenshtein函数,即使在提交的搜索词中存在拼写错误,也可以在小型redis实例中创建搜索以获得匹配.虽然大部分内容都是自我解释,但我很难弄清楚如何最好地使用这三个不同的cost参数.

int levenshtein ( string $str1 , string $str2 , int $cost_ins , int $cost_rep , int $cost_del )

文档中有一个简短的解释

第二个变体将采用三个附加参数来定义插入,替换和删除操作的成本.这比变体1更通用和自适应,但效率不高.

但这并不能解决我的理解.有人可以解释我如何使用成本参数来改善结果/性能吗？

我正在尝试基于自定义距离函数为字​​符串创建距离矩阵(用于聚类).我在6000字的列表上运行代码,并且自上次90分钟后它仍在运行.我有8 GB RAM和Intel-i5,所以问题只在于代码.这是我的代码:

library(stringdist)
#Calculate distance between two monograms/bigrams
stringdist2 <- function(word1, word2)
{
    #for bigrams - phrases with two words
    if (grepl(" ",word1)==TRUE) {
        #"Hello World" and "World Hello" are not so different for me
        d=min(stringdist(word1, word2),
        stringdist(word1, gsub(word2, 
                          pattern = "(.*) (.*)", 
                          repl="\\2,\\1")))
    }
    #for monograms(words)
    else{
        #add penalty of 5 points if first character is not same
        #brave and crave are more different than brave and bravery
        d=ifelse(substr(word1,1,1)==substr(word2,1,1),
                            stringdist(word1,word2),
                            stringdist(word1,word2)+5)
    }   
    d
}
#create distance matrix
stringdistmat2 …

我正在计算包​​含最多6个值的序列之间的Levenshtein距离。这些值的顺序不应影响距离。

如何将其实现为迭代或递归算法？

例：

# Currently 
>>> LDistance('dog', 'god')
2

# Sorted
>>> LDistance('dgo', 'dgo')
0

# Proposed
>>> newLDistance('dog', 'god')
0

'dog'和'god'具有完全相同的字母，在手之前对字符串进行排序将返回所需的结果。但是，这并非始终有效：

# Currently 
>>> LDistance('doge', 'gold')
3

# Sorted
>>> LDistance('dego', 'dglo')
2

# Proposed
>>> newLDistance('doge', 'gold')
1

“ doge”和“ gold”具有3/4个匹配字母，因此应返回距离1。这是我当前的递归代码：

def mLD(s, t):
    memo = {}
    def ld(s, t):
        if not s: return len(t)
        if not t: return len(s)
        if s[0] == t[0]: return ld(s[1:], t[1:])
        if (s, t) not in memo:
            l1 = ld(s, t[1:]) …

我正在为电视节目和其他媒体(游戏,电影等)编写刮刀,并不是所有来源的格式都与某个节目相同.例如,一个源可能表示带有破折号的字幕,其他分号.我目前正在使用Levenshtein距离将刮下的数据与从电视节目文件名中提取的数据进行比较,但我想知道该算法是否是针对短句长度而设计的.有没有更适合这种需求的算法？

如果两个字符串之间的Levenshtein距离，s并且t由下式给出L(s,t)，

以下两种不同的规范化方案对结果启发式的影响有何不同？

1. L(s,t) / [length(s) + length(t)]

2. L(s,t) / max[length(s), length(t)]

3. (L(s,t)*2) / [length(s) + length(t)]

我注意到Levenshtein距离Wikipedia页面建议使用规范化方法2，但没有提及方法1。这两种方法是否同样有效？只是想知道是否有数学上的理由来使用一种方法。

另外，方法1和方法3有什么区别？

用下面的例子：

s = "Hi, my name is"

t = "Hello, my name is"

L(s,t) = 4

length(s) = 14 （包括空格）

length(t) = 17 （包括空格）

给出以上三种归一化算法的Levenshtein距离为：

1. 4 /（14 + 17）= 0.129

2. 4 /（17）= 0.235

3. （4 * 2）/（14 + 17）= 0.258

我正在尝试编写一个函数来检测用户输入特定短语/句子/单词/单词的准确程度.我的目标是构建一个应用程序来训练用户对某些短语的打字准确性.

我最初的直觉是使用基本的levenshtein距离算法(主要是因为这是我认识的唯一算法).

但经过一番研究后,我发现Jaro-Winkler是一个稍微有趣的算法,因为它考虑了换位.

我甚至找到了一个链接,讨论了这些算法之间的差异:

Jaro-Winkler与Levenshtein距离的区别？

阅读完所有这些内容后,除了各自的维基百科帖子外,对于哪种算法最符合我的目标,我仍然有点无能为力.

我有几组数据。第一个（A）是具有复杂名称的设备列表。第二个是更广泛的设备类别（B）的列表-我必须将第一个列表归类为使用字符串比较。我知道这并不完美。

对于列表A中的每个实体-我想为列表B中的每个实体建立levenshtein距离。列表B中得分最高的记录将是我将其分配给该数据点的组。

我在python中非常生锈-并且正在使用FuzzyWuzzy来获取两个字符串值之间的距离。但是-我不太清楚如何遍历每个列表以生成所需的内容。

我想我只是为每个数据集创建一个列表，并为每个数据集编写一个非常基本的循环-但是就像我说的那样，我有点生疏，没有运气。

任何帮助将不胜感激！如果还有其他软件包可以使我做到这一点（而不是Fuzzy）-我很乐意提出建议。