字符串之间的缩写相似度

Question

我的项目中有一个用例，我需要将key-string 与很多字符串进行相似性比较。如果这个值大于某个阈值，我认为这些字符串与我的“相似” key，并根据该列表，我进行一些进一步的计算/处理。

我一直在探索模糊匹配字符串相似性的东西，它使用edit distance基于“levenshtein、jaro 和 jaro-winkler”相似性的算法。

尽管它们工作得很好，但如果一个字符串是另一个字符串的“缩写”，我希望获得更高的相似度分数。有没有我可以使用的算法/实现。

笔记：

language: python3 
packages explored: fuzzywuzzy, jaro-winkler

例子：

using jaro_winkler similarity:

>>> jaro.jaro_winkler_metric("wtw", "willis tower watson")
0.7473684210526316
>>> jaro.jaro_winkler_metric("wtw", "willistowerwatson")
0.7529411764705883

using levenshtein similarity:

>>> fuzz.ratio("wtw", "willis tower watson")
27
>>> fuzz.ratio("wtw", "willistowerwatson")
30
>>> fuzz.partial_ratio("wtw", "willistowerwatson")
67
>>> fuzz.QRatio("wtw", "willistowerwatson")
30

在这种情况下，如果可能的话，我希望分数更高（>90%）。我也可以接受很少的误报，因为它们不会对我的进一步计算造成太多问题。但是，如果我们匹配 s1 和 s2，使得 s1 完全包含在 s2 中（反之亦然），那么它们的相似度得分应该会高得多。

编辑：我的用例的更多示例

对我来说，空格是多余的。这意味着，wtw被视为“willistowerwatson”和“willis tower watson”的缩写。

另外，stove是“STack OVERflow”或“STandardOVErview”的有效缩写

一种简单的算法是从较小字符串的第一个字符开始，看看它是否存在于较大字符串中。然后检查第二个字符，依此类推，直到条件满足第一个字符串完全包含在第二个字符串中。这对我来说是 100% 匹配。

诸如“willistowerwatson”之类的进一步示例wtwx可以给出例如 80% 的分数（这可以基于某些编辑距离逻辑）。即使我能找到一个提供True或False缩写相似性的包也会有所帮助。

Answer 1

您可以使用类似于序列比对的递归算法。只是不要对轮班给予惩罚（正如缩写中所期望的那样），但对第一个字符不匹配给予惩罚。

这个应该可以工作，例如：

def abbreviation(abr,word,penalty=1):
    if len(abr)==0:
        return 0
    elif len(word)==0:
        return penalty*len(abr)*-1
    elif abr[0] == word[0]:
        if len(abr)>1:
            return 1 + max(abbreviation(abr[1:],word[1:]),
                           abbreviation(abr[2:],word[1:])-penalty)
        else:
            return 1 + abbreviation(abr[1:],word[1:])
    else:
        return abbreviation(abr,word[1:])

def compute_match(abbr,word,penalty=1):
    score = abbreviation(abbr.lower(),
                         word.lower(),
                         penalty)
    if abbr[0].lower() != word[0].lower(): score-=penalty
    
    score = score/len(abbr)

    return score


print(compute_match("wtw", "willis tower watson"))
print(compute_match("wtwo", "willis tower watson"))
print(compute_match("stove", "Stackoverflow"))
print(compute_match("tov", "Stackoverflow"))
print(compute_match("wtwx", "willis tower watson"))

输出是：

1.0
1.0
1.0
0.6666666666666666
0.5

表明wtwandwtwo是 的完全有效缩写willistowerwatson，这是but notstove的有效缩写，它的第一个字符错误。And仅是部分有效的缩写，因为它以全名中未出现的字符结尾。Stackoverflowtovwtwxwillistowerwatson