标签: levenshtein-distance

我今天已经学习Levenshtein距离,并在它似乎是一个众所周知的瓦格纳 - 费舍尔的算法计算的一种奇怪的方式已经stummbled.请帮我找到错误的地方.

第一个字符串是Max.

第二是Annas.

转型矩阵如下:

算法报告Levenshtein距Max和Annas的距离为4.

所以这就是我理解它应该如何工作:(假设任何行动的成本是1)

Mvs A- >替换m为a(目前为止的1个动作)

Avs N- >替换a为n(目前为止的2个动作)

Xvs N- >替换x为n(目前为止的3个动作)

在此之后,我们只需要添加留下a和s的字母,这些字母从我们这里再采取2个动作,总计5个,而不是4个.

我看到它可能会沿着一条更简单的路径前进,但它是什么呢？请解释一下它的算法运算逻辑.

谢谢.

我一整天都在处理一个我似乎无法解决的问题。任务是证明编辑距离的递归实现具有时间复杂度 Ω(2 ^max(n,m) )，其中 n & m 是被测量单词的长度。

实现与这个小python示例相当

def lev(a, b):
    if("" == a):
       return len(b)   # returns if a is an empty string
    if("" == b):
        return len(a)   # returns if b is an empty string
    return min(lev(a[:-1], b[:-1])+(a[-1] != b[-1]), lev(a[:-1], b)+1, lev(a, b[:-1])+1)

来自：http : //www.clear.rice.edu/comp130/12spring/editdist/

我曾尝试为不同的短词绘制递归深度的树，但我找不到树深度和复杂性之间的联系。

来自我的计算的递归公式

m = length of word1
n = length of word2
T(m,n) = T(m-1,n-1) + 1 + T(m-1,n) + T(m,n-1)
With the base cases:
T(0,n) = n
T(m,0) …

我目前使用的方法get_close_matches从法difflib迭代通过15000个字符串列表以获得对大约15000串的另一个列表最接近的匹配：

a=['blah','pie','apple'...]
b=['jimbo','zomg','pie'...]

for value in a:
    difflib.get_close_matches(value,b,n=1,cutoff=.85)

每个值需要 0.58 秒，这意味着完成循环需要 8,714 秒或 145 分钟。是否有其他库/方法可能更快或提高此方法的速度？我已经尝试将两个数组转换为小写，但它只会导致速度略有增加。

我有postgreSQL 9.2

我的任务是在表格中找到相似的名字(受到一些levenshtain距离的限制).

例如,距离为3,表格包含数据:

|           name            |
|***************************|
|       Marcus Miller       |
|       Marcos Miller       |
|       Macus Miler         |
|       David Bowie         |
|       Dave Grohl          |
|       Dav Grol            |
|           ...             |

我想得到的结果是这样的:

|       Marcus Miller, Marcos Miller, Macus Miler       |
|       Dave Grohl, Dav Grol                            |
|           ...                                         |

要么

|       Marcus Miller, Marcos Miller                    | 
|       Marcus Miller, Macus Miler                      |
|       Dave Grohl, Dav Grol                            |
|           ...                                         |

我试过这个:

SELECT a.name, b.name
FROM …

我正在尝试比较两个数组之间的编辑距离。我尝试过使用 Text:Levenshtein。

#!/usr/bin/perl -w
use strict;
use Text::Levenshtein qw(distance);

my @words = qw(four foo bar);
my @list = qw(foo fear);
my @distances = distance(@list, @words);

print "@distances\n";
#results: 3 2 0 3

然而，我希望结果如下所示：

2 0 3
2 3 2

通过 @words 数组获取 @list 的第一个元素，并对 @list 的其余元素执行相同的操作。我计划将其升级为更大的阵列。

如果我有一些我不想超过的距离。示例 = 2. 我是否可以在知道最小允许距离的情况下在完全完成之前中断算法？

也许有类似的算法可以完成。

我有必要减少工作计划的时间。

我正在寻找 Python 中字符串相似度度量函数的有效实现（或提供 Python 绑定的库）。

我想比较平均大小为 10kb 的字符串，我不能采取任何捷径，例如逐行比较，我需要比较整个内容。我并不在乎将使用什么确切的度量标准，只要结果合理且计算速度快即可。这是我迄今为止尝试过的：

• difflib.SequenceMatcher来自标准库。ratio()给出了很好的结果，但对于 10kb 文本需要 >100 毫秒。quick_ratio()只需要一半的时间，但结果有时与真正的价值相差甚远。
• python-Levenshtein: levenshtein 对于我的用例来说是一个可以接受的指标，但Levenshtein.ratio('foo', 'bar')并不比SequenceMatcher.

在我开始对 pypi 上提供测量字符串相似度函数的每个库进行基准测试之前，也许您可​​以指出我正确的方向？如果可能的话，我很想将单次比较的时间减少到不到 10 毫秒（在商品硬件上）。

我想计算可以具有不同长度的时间序列数据段之间的相似性。在寻找相似性度量时，我想考虑长度和价值的差异。我认为 Levenshtein distance 对此会很好，只要它适用于一系列浮点数而不是字符串。

这个问题解释了当被替换的整数值的差异无关紧要时，如何将 Levenshtein distance 与整数列表一起使用。在这种情况下，值的差异很重要，较大的差异应该受到更多的惩罚（我正在使用浮点数）。

当然，我对完成类似事情的其他相似性指标持开放态度，我只是认为 Levenshtein 距离已经非常接近我想要的了。

例子：

1. (0.22, 0.8, 1.2, 3.89)
2. (0.2, 0.61, 9.2)

比较第一个元素的惩罚较小，下一个元素的惩罚稍大，然后第三个元素的惩罚较大，最后一个元素的删除惩罚。

假设我有一个数据帧df1:

Sr       A              B                            C
1      rains         It rain there.             It rains there
2      plane         This is a vertical planes  This is a vertical plane
3      tree          Plant a trees              Plant a tree

列C是我的预期输出.我需要比较B列的字符串中的每个单词和A中的单词,如果Levenshtein距离为1,则将其替换.

我的方法:

import jellyfish as jf
def word_replace(str1):
    comp = #don't know how to store value of column A in this variable.
    for word in str1.split():
        if jf.levenshtein_distance(word,comp) == 1:
           word = comp
        else:
            pass
    return str1

df1['C'] = df1['B'].apply(word_replace)

第二件事,如果列A …

我实施了一个levenshtein trie来找到与给定单词相似的单词.我的目标是快速进行拼写纠正.

但是我发现有更快的方法可以做到这一点:

Levenshtein Automata

我只是有一个问题...我不明白这里写的是什么 .有人可以用简单的词语向我解释levenshtein自动机的想法和基本功能吗？