标签: levenshtein-distance

有人能解释一下Python中fuzzywuzzy库的这个函数是如何工作的吗？我知道编辑距离是如何工作的，但我不明白比率是如何计算的。

b = fuzz.token_sort_ratio('controlled', 'comparative')

结果是38

我有一个包含成对名称的数据集，它看起来像这样：

ID; name1; name2
1; Mike Miller; Mike Miler
2; John Doe; Pete McGillen
3; Sara Johnson; Edita Johnson
4; John Lemond-Lee Peter; John LL. Peter
5; Marta Sunz; Martha Sund
6; John Peter; Johanna Petera
7; Joanna Nemzik; Joanna Niemczik

我有一些案例，已贴上标签。所以我手动检查它们并确定它们是否重复。这些情况下的手动判断将是：

1: Is a duplicate
2: Is not a duplicate
3: Is not a duplicate
4: Is a duplicate
5: Is not a duplicate
6: Is not a duplicate
7: Is a duplicate

（第七个案例是一个具体案例，因为这里语音也参与了游戏。但这不是主要问题，我可以忽略语音。）

第一种方法是计算每对的编辑距离并将其标记为重复项，其中编辑距离例如小于或等于 2。这将导致以下输出：

1: Levenshtein distance: …

我们最近遇到了一个有趣的问题,我们在数据库中发现了重复的用户提交数据.我们意识到大部分数据之间的Levenshtein距离只是所讨论的2个字符串之间的差异.这表明如果我们只是将一个字符串中的字符添加到另一个字符串中,那么我们最终会得到相同的字符串,对于大多数情况来说,这似乎是我们考虑重复项目的最佳方式.

我们也想说明错别字.因此,我们开始平均考虑人们在每个单词上在线制作拼写错误的频率,并尝试在此距离内使用这些数据.我们找不到任何这样的统计数据.

在为数据匹配创建这种阈值时,有没有办法解决拼写错误？

如果我能澄清,请告诉我!

晚安,

我一直在使用模糊字符串匹配已经有一段时间了,并且使用带有一些指针的C,我可以写一个非常快的(根据我的需要)实现两个字符串之间的Levenshtein距离.我试图使用不安全的代码和fixed关键字将代码移植到C#,但性能却慢了.所以我选择构建一个C++ DLL并使用[DllImport]来自C#,自动编组每个字符串.问题是,在分析之后,这仍然是我的程序中最耗时的部分,占用程序总运行时间的50-57%.由于我认为我需要做一些繁重的工作,包含大量来自300万个数据库记录的文本字段的子字符串,我认为Levenshtein距离所采用的时间几乎是不可接受的.那就是,我想知道您是否对下面的代码有任何建议,包括算法或编程相关,或者您是否知道有任何更好的算法来计算这个距离？

#define Inicio1  (*(BufferVar))
#define Inicio2  (*(BufferVar+1))
#define Fim1  (*(BufferVar+2))
#define Fim2  (*(BufferVar+3))
#define IndLinha (*(BufferVar+4))
#define IndCol  (*(BufferVar+5))
#define CompLinha (*(BufferVar+6))
#define TamTmp  (*(BufferVar+7))

int __DistanciaEdicao (char * Termo1, char * Termo2, int TamTermo1, int TamTermo2, int * BufferTab, int * BufferVar)
{
 *(BufferVar) = *(BufferVar + 1) = 0;
    *(BufferVar + 2) = TamTermo1 - 1;
    *(BufferVar + 3) = TamTermo2 - 1;

 while ((Inicio1 <= *(BufferVar + 2)) && (Inicio2 <= …

我正在使用Jena来查询存储在本体中的数据.一些对象由字符串标识,但有时完全相同的字符串不可用,因为我正在处理扫描的文档,因此可能存在OCR错误.因此,我想找到最相似的字符串.有没有办法将SPARQL用于此目的？我可以以某种方式计算SPARQL中的levenshtein距离吗？

如果这是不可能的,我仍然可以计算java中的levenshtein距离.但是,有效的算法仍然需要使用SPARQL过滤掉不相关的字符串.

对于Levenshtein算法,我发现了Delphi的这个实现.

我需要一个版本,一旦达到最大距离就停止,并返回到目前为止找到的距离.

我的第一个想法是在每次迭代后检查当前结果:

for i := 1 to n do
    for j := 1 to m do
    begin
      d[i, j] := Min(Min(d[i-1, j]+1, d[i,j-1]+1), d[i-1,j-1]+Integer(s[i] <> t[j]));

      // check   
      Result := d[n, m];
      if Result > max then
      begin
        Exit;
      end; 

    end;

我一直在看这个简单的Levenshtein编辑距离的 python实现.

def lev(a, b):
    """Recursively calculate the Levenshtein edit distance between two strings, a and b.
    Returns the edit distance.
    """
    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/

我知道它具有指数复杂性,但我将如何从头开始计算这种复杂性？

我一直在互联网上搜索,但没有找到任何解释,只有它是指数的声明.

谢谢.

我正在寻找一种快速算法来确定给定2D阵列的特定最小属性 - 没有共同行或列的最小值之和.我敢肯定这必须有一个名字,但我不知道它叫什么.

我有一个字符串匹配系统,它将在空格上分割输入字符串并将其与搜索值的语料库(也在空格中分割)进行比较,并返回每个字符串中的标记之间的距离矩阵,我想减少通过采用不重复使用任何输入/输出令牌组合的最小距离组合,可以达到单个聚合距离.

例子:

{ 1, 2 }   => 5 (either 1+4, or 3+2)
{ 3, 4 }

{ 0, 2 }   => 6 (because 2+4 < 0+8)
{ 4, 8 } 

{ 1, 0, 0 }
{ 0, 1, 0 } => 0
{ 0, 0, 1 }

{ 2, 3, 4 }
{ 3, 2, 4 } => 6 (2+2+2)
{ 4, 3, 2 } 

我一直使用的天真算法看起来像这样(C#):

public static int Minimux(this int[,] array) {
  var xUsed = new …

所以我试图设计一个Levenshtein算法的旋转,在那里我跟踪我在字符串中做了什么转换(插入a或替换为b).

例:

基本上,我说计算"bbd"和"bcd"的编辑距离

编辑距离为1,转换为"c的替代b"

问题: 我如何处理这个问题,因为我看到的实现并不关心自己知道什么样的操作,而只是总成本？

Levenshtein距离是用于测量两个序列之间差异的字符串度量.Wagner-Fischer算法是一种动态编程算法,用于计算两个字符串之间的编辑距离.

两者都使用矩阵,我没有看到差异？这种差异是回溯还是由于一个是"文学"而另一个是编程这一事实没有进一步的区别？

另外,我只是写一篇论文,我不知道如何划分它 - 我是否应首先首先解释Levenshtein距离,然后再解释Wagner-Fisher算法或两者兼而有之？我在这里有点困惑.