我试图使用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百分位等级).
有什么想法吗？有更好的方法吗？我必须遗漏一些东西,因为Levenshtein距离可能是最常见的模糊匹配算法,这一定是一个非常常见的问题.