我正在尝试使用 Levenshtein 距离算法将单个搜索词与可能匹配的字典进行匹配。该算法返回一个距离，表示为将搜索字符串转换为匹配字符串所需的操作数。 我想以前“N”(例如 10)场比赛的排名百分比列表的形式显示结果。
由于搜索字符串可能比各个字典字符串更长或更短，因此将距离表示为百分比的适当逻辑是什么，这将定性地反射(reflect)每个结果“以百分比”与查询字符串的接近程度，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)。
有什么想法吗？有更好的方法吗？我一定错过了一些东西，因为编辑距离可能是模糊匹配最常见的算法，这一定是一个非常常见的问题。
最佳答案
我遇到了类似的问题，这个帖子帮助我找到了解决方案。希望它也能帮助其他人。
int levDis = Lev_distance(Q, Mi)
int bigger = max(strlen(Q), strlen(Mi))
double pct = (bigger - levDis) / bigger
如果两个字符串完全相同，则应返回 100%；如果完全不同，则应返回 0%。
(抱歉，如果我的英语不太好)
关于distance - 使用 Levenshtein 距离匹配的匹配百分比排名，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10405440/