标签: levenshtein-distance

如果是这样,请解释如何.

Re:什么是距离 - "两个字符串之间的距离定义为将一个字符串转换为另一个字符串所需的最小编辑数."

例如,xyz到XYZ将进行3次编辑,因此字符串xYZ更接近XYZ和xyz.

如果模式是[0-9] {3}或例如123,那么a23将比ab3更接近模式.

如何找到正则表达式与非匹配字符串之间的最短距离？

以上是Damerau-Levenshtein距离算法.

我在C++中编写了Levenshtein算法

如果我输入:
string s:democrat
string t:republican

我得到矩阵D填充,并且可以在D [10] [8] = 8中读取操作数(Levenshtein距离).
在填充矩阵之外,我想构建最优解.怎么看这个解决方案？我没有主意.
请只写我如何看这个例子.

这是计算Levenshtein距离的一般算法的教科书示例(我从Magnus Hetland的网站中提取):

def levenshtein(a,b):
    "Calculates the Levenshtein distance between a and b."
    n, m = len(a), len(b)
    if n > m:
        # Make sure n <= m, to use O(min(n,m)) space
        a,b = b,a
        n,m = m,n

    current = range(n+1)
    for i in range(1,m+1):
        previous, current = current, [i]+[0]*n
        for j in range(1,n+1):
            add, delete = previous[j]+1, current[j-1]+1
            change = previous[j-1]
            if a[j-1] != b[i-1]:
                change = change + 1
            current[j] = min(add, delete, change)

    return current[n]

然而,我想知道是否有更高效(可能更优雅)的纯Python实现使用difflib的SequenceManager.在玩完之后,这就是我想出的: …

我正在尝试实施“您的意思是？” 某种搜索功能。

我正在尝试使用使用ruby编写的levenshtein函数进行查询。我想知道如何在sqlite3查询中使用此功能。我在想可能是这样的：

@results = the_db.where('levenshtein(name, ?) <= 3', searchphrase)

但是我不确定如何使它工作。有人可以帮我吗？

有没有人知道Objective-c的模糊搜索匹配的快速实现？(levenshtein距离算法).

我发现了这个:https://github.com/thetron/StringScore/blob/master/NSString%2BScore.m - 但不幸的是它很慢.我需要将它与大约200个字符串进行比较,并且它是连续的 - 每次键入新键击.

有任何想法吗？

我正在写一个Python聊天机器人.无论技术是什么(Levenshtein,LCS,正则表达式等),我想要一个像My name is [ A ].智能足够的模式来匹配字符串,如:

My name is Tslmy.              #Distance should = 0, and groupdict()['a'] outputs "Tslmy"
My name is Tesla Tahomana.     #Distance should = 0(!), and groupdict()['a'] outputs "Tesla Tahomana"
my  naem ist tslmy .           #With a little typo, the distance = 5, and groupdict()['a'] outputs "tslmy "

请允许我用来groupdict()['a']指代[ A ](实际上(?P<identifier>match))抓住的东西.

• 换句话说,我正在寻找一个带有省略/跳过/空白/忽略的"Levenshtein",并挑选出已被跳过的内容.
• 换句话说,我正在寻找一个模糊(也就是近似)正则表达式,它可以对模式不那么严格,仍然提供良好的旧groupdict(),以及"模糊"值(或"编辑距离",需要确定"与字符串"稍后"匹配的最佳模式.
  这是首选解决方案,因为groupdict()如果管理良好,它提供"足够" .
  然而,TRE库和REGEX库被发现是最接近的解决方案,似乎没有提供"模糊"值.如果这可以解决,那就更好了!

那可能吗？感谢您的关注.

更新:

我决定最终使用强大的正则表达式模块,但仍然无法获得"模糊值".

由于 …

对于客户端搜索工具,我需要找到一个单词的Levenshtein距离以及数百万个其他单词.用户应该能够将大约二十个单词的短文与一本书进行比较.用户可以通过查找书中文本的最具特征的单词的位置来做到这一点."寻找位置"并不意味着寻找完全匹配,但几乎与levenshtein匹配.我从已经可用的实现开始,但我需要更快的速度.我最终得到了这个:

var rowA = new Uint16Array(1e6);
var rowB = new Uint16Array(1e6);
function levenshtein(s1, s2) {
    var s1_len = s1.length, s2_len = s2.length, i1, i2 = 0, a, b, c, c2, i = 0;
    if (s1_len === 0)
        return s2_len;
    if (s2_len === 0)
        return s1_len;
    while (i < s1_len)
        rowA[i] = ++i;
    while (i2 < s2_len) {
        c2 = s2[i2];
        a = i2;
        ++i2;
        b = i2;
        for (i1 = 0; i1 < s1_len; ++i1) {
            c = a + …

我有一个大城市数据库,它是从许多不同来源编译而来的.我正试图找到一种方法,可以根据城市名称轻松发现重复项.天真的答案是使用levenshtein距离.然而,城市的问题在于它们通常具有前缀和后缀,这些前缀和后缀对于它们所在的国家而言是共同的.

例如:

Boulleville对阵Boscherville

这些几乎肯定是不同的城市.然而,因为它们都以"ville"结尾(并且都以"Bo"开头),所以它们具有相当小的Levenstein距离.

*我正在寻找一种字符串距离算法,该算法考虑到字符的位置,通过将单词中间的字母加权高于单词末尾的字母来最小化前缀和后缀的影响.*

我本可以自己写一些东西,但我觉得很难相信没有人发表过合适的算法.

我在 SO/elsewhere 上看到了一堆类似的问题，但没有一个答案能完全满足我的需求，所以我不认为这是一个重复的问题。

此外，我完全知道如何自己实现这一点，但我试图不必重新发明轮子。

有谁知道任何 python 包可以执行 levenshtein/其他编辑距离比较 2 个单词列表（我找到了一些），但也允许指定你自己的插入、删除、替换和换位成本？

基本上，我希望计算的距离是句子中单词的编辑次数，而不是句子不同的字符数。

我正在尝试使用 python2 的 C api 替换实际用 C 编写的自定义 python 扩展模块。我可以用纯 python 或 cython 重写，但我宁愿简单地向项目添加一个依赖项。唯一的问题是这段代码允许你为各种选项指定你自己的成本，到目前为止我还没有找到一个允许这样做的包。

假设我有 2 个非常相似的字符串。我想找到在 Levenshtein 距离方面接近 s1 和 s2 的其他字符串。

import Levenshtein
s1 = 'aaabbbccc'
s2 = 'abacbbbccde'
dist = Levenshtein.distance(s1, s2)
print(dist)
mid_str = get_avg_string(s1, s2)

什么可以有效实现功能：

def get_avg_string(s1, s2):
    return ''

我需要这个变量：

sum_lev = Levenshtein.distance(s1, mid_str) + Levenshtein.distance(s2, mid_str)
diff_lev = abs(Levenshtein.distance(s1, mid_str) - Levenshtein.distance(s2, mid_str)

最小（我认为sum_lev将等于dist和diff_lev <= 1）。