28

我正在尝试使用 Levenshtein 距离算法将单个搜索词与可能匹配的字典进行匹配。该算法返回一个距离，表示为将搜索字符串转换为匹配字符串所需的操作数。我想在排名前“N”（比如 10 个）匹配的百分比列表中显示结果。

由于搜索字符串可以比单个字典字符串更长或更短，将距离表示为百分比的适当逻辑是什么，这将定性地反映每个结果与查询字符串的“百分比”有多接近，100 % 表示完全匹配。

我考虑了以下选项：

Q = query string
M = matched string
PM = Percentage Match
Option 1. PMi = (1 - Lev_distance(Q, Mi)/Strlen(Q)) * 100
Option 2. PMi = (1 - Lev_distance(Q, Mi)/max(Strlen(Q), strlen(Mi))) * 100

如果距离大于搜索字符串长度（匹配字符串很长），选项 1 可能会出现负百分比。例如查询“ABC”与“ABC Corp.”匹配。将导致负匹配百分比。

选项 2 似乎没有在一组 Mi 中给出一致的百分比，因为每次计算可能会使用不同的分母，因此得到的百分比值不会被标准化。

我能想到的唯一其他方法是放弃 lev_distance 与任一字符串长度的比较，而是将前“N”个匹配的比较距离呈现为反向百分位数排名（100-percentile-rank）。

有什么想法吗？有更好的方法吗？我一定遗漏了一些东西，因为 Levenshtein 距离可能是最常见的模糊匹配算法，这一定是一个非常常见的问题。

4

8 回答 8

36

我有一个类似的问题，这个线程帮助我找到了解决方案。希望它也可以帮助其他人。

int levDis = Lev_distance(Q, Mi)
int bigger = max(strlen(Q), strlen(Mi))
double pct = (bigger - levDis) / bigger

如果两个字符串完全相同，它应该返回 100%，如果它们完全不同，它应该返回 0%。

（对不起，如果我的英语不是那么好）

于 2014-02-11T14:49:52.013 回答
5

我解决这个问题的方法是计算最大允许操作，这就是 Levenshtein 距离。我使用的公式是： 

percent = 0.75; // at least 75% of string must match
maxOperationsFirst = s1.length() - s1.length() * percent;
maxOperationsSecond = s2.length() - s2.length() * percent;
maxOperations = round(min(maxOperationsFirst, maxOperationsSecond));

它计算每个字符串的最大操作数，相信计算容易理解。我使用两个结果的最小值并将其四舍五入到最接近的整数。您可以跳过这部分并仅使用任一字符串的最大操作值，这实际上取决于您的数据。

获得最大操作数后，您可以将其与 levenshtein 结果进行比较，并确定该字符串是否可以接受。这样，您可以使用任何扩展的 levenshtein 方法，例如Damerau–Levenshtein distance，它计算拼写错误，例如 test -> tset，仅作为 1 次操作，这在检查这些拼写错误经常发生的用户输入时非常有用。

我希望这可以帮助您了解如何解决此问题。

于 2013-08-14T23:11:45.060 回答
2 
Max = Lev_distance(Q,''); //max operations to transform query string to empty string
PM = (Max - Lev_distance(Q, Mi)) / Max * 100%;

我认为这足以满足您的需求。它对于极值是正确的（完全满足相同和完全不同的字符串）并且是合理的

于 2021-05-29T21:09:42.287 回答
1

这本质上是我的问题中提到的选项 2。但是，让我演示一下这种方法的一个问题。

Q = "ABC Corp" (len = 8)
M1 = "ABC"
M2 = "ABC Corporati"
M3 = "ABC Corp"

我选择了 M1 和 M2，使它们的 Lev 距离相同（每个 5）。使用选项 2，匹配百分比将是

M1 = (1 - 5/8)*100  = 37.5%
M2 = (1 - 5/13)*100 = 61.5%
M3 = 100%

正如您所看到的，如果我按此顺序显示比赛，M1 和 M2 之间的排名差异很大，即使它们具有完全相同的 lev 距离。你看到问题了吗？

于 2013-01-11T01:01:45.557 回答
0 
(1 - (levNum / Math.max(s.length,t.length) ) ) *100

应该是正确的

于 2013-01-09T14:51:50.137 回答
0

我认为更简单的方法可能是：

from nltk import edit_distance

str1 = 'abc'
str2 = 'abd'
edit_dist  = edit_distance(str1,str2)
len_total = len(str1)+len(str2)
pct_edit_dist = ((len_total-edit_dist)/len_total)*100
print(pct_edit_dist)

pct_edit_dist 为 100 表示完全匹配，0 表示不匹配。

于 2021-06-26T20:14:02.663 回答
0

这个如何：

100 - ( ((2*Lev_distance(Q, Mi)) / (Q.length + Mi.length)) * 100 )

(Q, M1)它给出了相同的距离(Q,M2)

于 2016-05-08T09:06:52.137 回答
0

levenshtein 距离的最大数量是[l1, l2].max。我认为这是真的。但我们不应该除此之外。

gem install levenshtein diff-lcs

Diff::LCS.lcs "abc", "qwer"
=> []
Levenshtein.distance("abc", "qwer").to_f / [3, 4].max
=> 1.0

Diff::LCS.lcs "abc", "cdef"
=> ["c"]
Levenshtein.distance("abc", "cdef").to_f / [3, 4].max
=> 1.0

Diff::LCS.lcs "1234", "34567890"
=> ["3", "4"]
Levenshtein.distance("1234", "34567890").to_f / [4, 8].max
=> 1.0

Levenshtein 看起来不像是比较字符串的可靠方法percents。我不想将相似的字符串视为100% 不同。

我可以建议只分析每个序列和 LCS 之间的差异。

def get_similarity(sequence_1, sequence_2)
  lcs_length = Diff::LCS::Internals.lcs(sequence_1, sequence_2).compact.length
  lcs_length.to_f * 2 / (sequence_1.length + sequence_2.length)
end
于 2018-06-20T20:08:57.710 回答