改进的Levenshtein算法

Question

我最近在我们的搜索引擎数据库中实现了levenshtein算法，但我们遇到了一个问题。

根据基本的水平

Levenshtein('123456'，'12x456')与Levenshtein('123456'，'12345x')值相同

通常这是可以的，但对于我的特定问题，这是不正确的。当有人使用我们的网站时，这是不正确的。电子元器件制造商经常制造类似的产品，只是最后一个字母有所不同。如果第一个字母不同，它通常是一个完全不同的类别。因此，我需要一个算法，它认为单词开头附近的匹配比后面的匹配更有价值，或者换句话说，在单词开头附近发生的不匹配应该比后面的匹配应用更大的惩罚。

如果谁有任何想法，请让我知道。

Answer 1

我们遇到了类似的问题，并使用了Brew edit distance method

我们使用的是Perl，所以我们使用Text::Brew库。我的同事做了一个关于使用few different algorithms的很好的演示，包括Brew。

Answer 2

查看在生物信息学中广泛使用的Smith-Waterman算法。它可以执行查询的本地对齐，但这将比Levenshtein慢。

Answer 3

使用Jaro-Winkler Distance...这正是你所要求的。