字符串的缩写相似度

Question

字符串的缩写相似度

pythonsimilarityedit-distancejaro-winkler

7

在我的项目中，我有一个使用场景，需要将一个key字符串与许多字符串进行相似性比较。如果这个值大于某个阈值，我认为这些字符串与我的key相似，并且基于这个列表，我进行进一步的计算/处理。

我一直在探索模糊匹配字符串相似性的东西，这些东西使用基于编辑距离的算法，例如“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%的匹配。

其他如wtwx到"willistowerwatson"的示例可能给出80%的得分（这可以基于某些编辑距离逻辑）。即使我能找到一个可以为缩写相似性提供True或False的软件包也会很有帮助。

- vish4071

请查看以下在StackOverflow上的答案：https://dev59.com/unbZa4cB1Zd3GeqPMPoY - Pythonista

2个回答

0

你可以使用递归算法，类似于序列对齐。只是不要因为移位而给予惩罚（因为缩写中预期会出现移位），但是对于第一个字符不匹配则给予惩罚。

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

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

表明wtw和wtwo是willistowerwatson的完全有效缩写，stove是Stackoverflow的有效缩写，但tov不是，因为它的第一个字符错误。而wtwx只是willistowerwatson的部分有效缩写，因为它以在完整名称中不存在的字符结尾。

- Martin Wettstein

嗨@Martin，这是一个很棒的答案。由于今天是最后一天，我将授予此赏金。这可能会在行为上解决我的用例，我只需要检查它在我拥有的大型数据集中的性能即可。然而，至于输出分数，这可能正是我想要的。谢谢 :) - vish4071

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Cardstdani · Accepted Answer

要检测字符串中的缩写，您可以仍然使用fuzzywuzzy模块的process()函数：

from fuzzywuzzy import fuzz, process

s1 = ["willis tower watson", "stack overflow", "willistowerwatson", "international business machines"]
s2 = ['wtw', "so", "wtw", "ibz"]

queries = [''.join([i[0] for i in j.split()]) for j in s1]

for query, company in zip(queries, s1):
    print(company, '-', process.extractOne(query, s2, scorer=fuzz.partial_token_sort_ratio))

输出：

willis tower watson - ('wtw', 100)
stack overflow - ('so', 100)
willistowerwatson - ('wtw', 100)
international business machines - ('ibz', 67)