代码之家 › 专栏 › 技术社区 › vish4071

字符串之间的缩写相似性

jaro-winkler edit-distance similarity python

0

vish4071 · 技术社区 · 4 年前

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

我一直在探索模糊匹配字符串相似性的东西,它使用 edit distance 基于类似“levenstein,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”和“willistowerwatson”的缩写。

而且 stove 是“STack OVErflow”或“STandardOVErview”的有效缩写

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

其他示例如 wtwx “willistowerwatson”可以给出80%的分数(这可以基于一些编辑距离逻辑)。即使我能找到一个包裹 True 或 False 缩写的相似性也会有所帮助。

0 回复 | 直到 4 年前

1

2

Cardstdani 4 年前

要检测字符串中的缩写,您仍然可以使用 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)

2

0

Martin Wettstein 4 年前

您可以使用递归算法,类似于序列对齐。只是不要对移位进行惩罚(正如缩写中所期望的那样),而是对第一个字符不匹配进行惩罚。

例如,这个应该有效:

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 因为它以一个没有出现在全名中的字符结尾。