标签: levenshtein-distance

给出2个字符串s和t.我需要找到s编辑距离(Levenshtein距离)中的每个子串t.实际上我需要知道每个i位置在s所有从位置开始的子串的最小编辑距离i.

例如:

t = "ab"    
s = "sdabcb"

我需要得到类似的东西:

{2,1,0,2,2}

说明:

1st position:
distance("ab", "sd") = 4 ( 2*subst )
distance("ab", "sda") = 3( 2*delete + insert )
distance("ab", "sdab") = 2 ( 2 * delete)
distance("ab", "sdabc") = 3 ( 3 * delete)
distance("ab", "sdabcb") = 4 ( 4 * delete)
So, minimum is 2

2nd position:
distance("ab", "da") = 2 (delete + insert)
distance("ab", …

我正在尝试使用Levenshtein距离算法在PHP中对齐字符串.问题是我的后台跟踪代码不适用于所有情况.例如,当第二个数组在开头插入行时.然后,后向跟踪将只到i = 0时.

如何正确实施Levenshtein距离的回溯？

Levenshtein距离,$ s和$ t是字符串数组(行)

function match_rows($s, $t)
{
$m = count($s);
$n = count($t);

for($i = 0; $i <= $m; $i++) $d[$i][0] = $i;
for($j = 0; $j <= $n; $j++) $d[0][$j] = $j;

for($i = 1; $i <= $m; $i++)
{
    for($j = 1; $j <= $n; $j++)
    {
        if($s[$i-1] == $t[$j-1])
        {
            $d[$i][$j] = $d[$i-1][$j-1];
        }
        else
        {
            $d[$i][$j] = min($d[$i-1][$j], $d[$i][$j-1], $d[$i-1][$j-1]) + 1;
        }
    }
}

// backtrace
$i = $m;
$j = …

我正在寻找用于PHP 的Damerau-Levenshtein算法的实现,但似乎我找不到任何与我的朋友谷歌的东西.到目前为止,我必须使用PHP实现的Levenshtein(没有Damerau转置,这是非常重要的),或者获得原始源代码(在C,C++,C#,Perl中)并将其编写(翻译)到PHP.

有没有人知道PHP的实现？

我正在使用soundex和双metaphone在我的公司内部网上使用"你是不是意思:"扩展,我想实现Damerau-Levenshtein算法来帮助我更好地对结果进行排序.类似于这个想法的东西:http://www.briandrought.com/blog/？p = 66,我的实现类似于前5个步骤.

我正在使用Daitch-Mokotoff soundexing和Damerau-Levenshtein来查明用户条目和应用程序中的值是否"相同".

Levenshtein距离应该被用作绝对值吗？如果我有一个20个字母的单词,那么4的距离就不那么糟了.如果这个单词有4个字母......

我现在正在做的是取距离/长度来获得更好地反映单词的百分比变化的距离.

这是一种有效/经证实的方法吗？还是愚蠢的？

我正在努力实现术语Web服务的模糊搜索,我正在寻找关于如何改进当前实现的建议.分享的代码太多了,但我认为解释可能足以提出深思熟虑的建议.我意识到这是很多东西,但我很感激任何帮助.

首先,术语基本上只是一些名称(或术语).对于每个单词,我们按空格将其拆分为标记,然后遍历每个字符以将其添加到trie.在终端节点上(例如当达到草莓中的字符y时),我们在列表中存储主术语列表的索引.因此,终端节点可以具有多个索引(因为草莓的终端节点将匹配'草莓'和'对草莓过敏').

对于实际搜索,搜索查询也按空间分解为标记.为每个令牌运行搜索算法.搜索令牌的第一个字符必须匹配(因此traw永远不会匹配草莓).之后,我们通过每个连续节点的子节点.如果有匹配的字符的子项,我们继续使用搜索令牌的下一个字符进行搜索.如果孩子与给定的角色不匹配,我们会使用搜索令牌的当前角色来查看孩子(因此不会推进它).这是模糊部分,因此'stwb'将匹配'草莓'.

当我们到达搜索令牌的末尾时,我们将搜索该节点处的其余trie结构以获得所有可能的匹配(因为到主术语列表的索引仅在终端节点上).我们称之为卷起.我们通过在BitSet上设置它们的值来存储索引.然后,我们简单地从每个搜索令牌的结果中得到BitSets.然后,我们从anded BitSet中获取前1000或5000个索引,并找到它们对应的实际项.我们使用Levenshtein对每个术语进行评分,然后按分数进行排序以获得最终结果.

这种方法效果很好而且非常快.树中有超过390k个节点,超过110万个实际术语名称.但是,现在存在问题.

例如,当我们不想要它时,搜索'car cat'将返回Catheterization(因为搜索查询是两个单词,结果应该至少为两个).这很容易检查,但它不会像导管过程那样处理,因为它是两个字.理想情况下,我们希望它与Cardiac Catheterization相匹配.

基于纠正这个问题的需要,我们想出了一些改变.首先,我们通过混合深度/广度搜索来检查trie.基本上,只要角色匹配,我们就会先进入深度.那些不匹配的子节点将添加到优先级队列中.优先级队列按编辑距离排序,可以在搜索特里时计算(因为如果有字符匹配,则距离保持不变,如果不匹配,则增加1).通过这样做,我们得到每个单词的编辑距离.我们不再使用BitSet了.相反,它是Terminfo对象的索引映射.此对象存储查询短语的索引以及术语短语和分数.因此,如果搜索是"汽车猫"并且匹配的术语是"导管过程" 术语短语索引将是1,查询短语索引也是如此.对于"心脏导管",术语短语索引将是1,2,查询短语索引也是如此.正如您所看到的,之后查看术语短语索引和查询短语索引的计数非常简单,如果它们不至少等于搜索词计数,则可以将它们丢弃.

之后,我们将单词的编辑距离相加,从与术语短语索引匹配的术语中删除单词,并计算剩余的字母以获得真正的编辑距离.例如,如果您将术语"过敏与草莓"匹配并且您的搜索查询为"稻草",您将从草莓中获得7分,那么您将使用术语短语索引从该术语中丢弃草莓,并且只计算"过敏"(减去空格)得分为16分.

这让我们得到了我们期望的准确结果.但是,它太慢了.在一个单词搜索之前我们可以获得25-40毫秒,现在它可能多达半秒.它主要来自实例化TermInfo对象,使用.add()操作,.put()操作以及我们必须返回大量匹配这一事实.我们可以将每次搜索限制为仅返回1000个匹配,但不能保证"car"的前1000个结果将匹配"cat"的前1000个匹配中的任何一个(记住,有超过1.1万个术语).

即使对于像cat一样的单个查询词,我们仍然需要大量的匹配.这是因为如果我们搜索'cat',搜索将匹配汽车并汇总其下方的所有终端节点(这将是很多).但是,如果我们限制结果的数量,则会过于强调以查询开头而不是编辑距离的单词.因此,像导尿管这样的词语比涂层更容易被包括在内.

那么,基本上,对于我们如何处理第二个实现修复的问题有什么想法,但没有引入的速度减慢那么多吗？我可以包含一些选定的代码,如果它可以使事情更清楚,但我不想发布一个巨大的代码墙.

首先,我想说我是python中的新手.我试图计算许多单词列表的Levenshtein距离.直到现在我成功编写了一对单词的代码,但是我在列表中遇到了一些问题.我只是有两个列表,其中一个在另一个之下,就像这样:carlos stiv peter

我想使用Levenshtein距离进行相似性处理.somebady可以告诉我如何加载列表然后使用函数计算距离？

我会感激的!

这是我的代码只有两个字符串:

#!/usr/bin/env python
# -*- coding=utf-8 -*-

def lev_dist(source, target):
    if source == target:
        return 0

#words = open(test_file.txt,'r').read().split();

    # Prepare matrix
    slen, tlen = len(source), len(target)
    dist = [[0 for i in range(tlen+1)] for x in range(slen+1)]
    for i in xrange(slen+1):
        dist[i][0] = i
    for j in xrange(tlen+1):
        dist[0][j] = j

    # Counting distance
    for i in xrange(slen):
        for j in xrange(tlen):
            cost = 0 if source[i] == target[j] else 1
            dist[i+1][j+1] = min( …

我被告知Levenshtein距离是对称的.当我使用google的diffMatchPatch工具来计算Levenshtein距离时,其结果并不意味着Levenshtein距离是对称的.即Levenshtein(x1,x2)不等于Levenshtein(x2,x1).Levenshtein是不对称的还是特定实现存在问题？谢谢.

例如,从一组英语单词开始,是否有一个结构/算法允许快速检索字符串,如"light"和"tight",使用"right"作为查询？即,我想检索与查询字符串的Levenshtein距离较小的字符串.

我有两个 DataFrame，每个 DataFrame 都有一个名字列。我想合并这些字符串上的列，但是是在编辑距离上，而不是在字符串相等的地方。

如果我可以在 SQL 中进行编辑距离，我基本上会尝试复制以下 SQL：

SELECT 
    *
FROM dataset_a a
    JOIN dataset_b b on Levenshtein(a.firstname,b.firstname) <= 3

是否可以基于这样的函数合并DataFrame？

使用函数stringdist，我可以计算字符串之间的Levenshtein距离：它计算将字符串转换为另一个字符串所需的删除，插入和替换的次数。例如，stringdist("abc abc","abcd abc") = 1因为在第二个字符串中插入了“ d”。

是否有可能知道为获取两个琴弦之间的Levenshtein距离而进行的操作？还是要知道两个字符串之间不同的字符（在此示例中，只有“ d”）？谢谢。

library(stringdist)
stringdist("abc abc","abcde acc") = 3

我想知道：

• 插入了“ d”

• 插入了“ e”

• “ b”被替换为“ c”

或更简单地说，我想要列表（“ d”，“ e”，“ c”）。