改进的Levenshtein算法

Question

改进的Levenshtein算法

9

我最近将Levenshtein算法引入了我们的搜索引擎数据库，但是我们遇到了一个问题。

根据基本的Levenshtein规则：

Levenshtein('123456', '12x456')与Levenshtein('123456', '12345x')的值相同。

通常情况下这没问题，但对于我的特定问题来说是不正确的。当有人使用我们的网站时，这是错误的。电子元器件制造商经常只在最后一个字母上有所不同地生产类似的产品。如果第一个字母不同，通常就属于完全不同的类别。因此，我需要一种算法，将单词开头附近的匹配项视为比后面的更有价值，换句话说，发生在开头附近的不匹配应该有较大的惩罚。

如果有任何想法，请告诉我。

- Mike D

你尝试过什么来改进算法？ - alf

1

我尝试根据字母在序列中的位置（前面的权重更高）为不匹配添加权重，但结果不理想。我正在寻找更精确的方法。 - Mike D

3个回答

2

使用Jaro-Winkler距离，这正是你所需要的。

- Will Castillo

1

我们曾经遇到过类似的问题，使用了Brew编辑距离算法。

当时我们在Perl中使用了Text::Brew库。我的同事做了一份关于使用几种不同算法（包括Brew）的精美演示。

- Rob Di Marco

这看起来很有前途，因为它考虑了不同的权重来处理不同的不匹配，使得插入操作比删除或替换操作更便宜，但是如何将其应用于考虑单词顺序的重要性呢？我的例子是这样的。有一个零件号1-480424-0。如果我搜索1-480424-0，则结果1-480424-8应该比1-430424-0更高。 - Mike D

一个关键点是，您可以获得将第一个字符串转换为第二个所需的编辑描述。例如，在我们的世界中（匹配事物的名称），字符串的开头更重要，因此我们主要使用brew来访问路径，然后基于该路径进行排序，将字符串开头的事物排名高于末尾。关键是我们得到了路径，而不仅仅是编辑距离数字。 - Rob Di Marco

我明白了，那很有道理。好的，我会看看如何利用这些信息。谢谢你的帮助 :) - Mike D

所以我想出了自己的解决方案，似乎效果不错。在普通的Levenshtein中，当不匹配时应用1的成本。我所做的是将成本改为1-Min(i,j)/(2*MAX(m,n))，其中i和j是我们正在查看的当前值，m和n是两个单词的长度。您也可以使用Max(i,j)，因为它会产生类似的结果。 - Mike D

“Brew编辑距离方法”不过是众所周知的Wagner-Fischer算法。Chris Brew并非该算法的原始作者，他不希望自己的名字与其不当地联系在一起。该算法显然已经被多次独立地发现和重新发现：https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm#History。 - Robert Jacobson

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Pierre · Accepted Answer

请参考广泛应用于生物信息学的Smith-Waterman算法。它可以对您的查询进行局部比对，但速度比Levenshtein慢。