时间戳

首页 > 解决方案 > 如何从不同长度的字符串python列表中找到字符串的最接近匹配？

python - 如何从不同长度的字符串python列表中找到字符串的最接近匹配？

问题描述

考虑：

string = 'pizza'
matchings = ['pizzas', 'potato chips', 'cheesy lime', 'pretzels', 'pork']

我正在尝试找到一种在列表中找到最佳匹配的好方法。我正在计算：

matchings_indices = {matching:sum([s == m for s,sdx in enumerate(string)\
                                 for m, mdx in enumerate(matching) if sdx<=mdx])/len(string) 
                     for matching in matchings}
matchings_indices

结果是：

{'pizzas': 1.0,
 'potato chips': 0.6,
 'cheesy lime': 0.2,
 'pretzels': 0.6,
 'pork': 0.4}

简单但足够好！我可以取出最大值，这将是匹配项（我只需要一个匹配值，为清楚起见计算分数）。但是当列表中出现非常相似的字符串时，它真的很困难：

string = 'pizza'
matchings = ['pizzas', 'pizza fries', 'cheesy lime', 'pizzo', 'pizza']

现在我的输出变为：

{'pizzas': 1.0,
 'pizza fries': 1.0,
 'cheesy lime': 0.2,
 'pizzo': 1.0,
 'pizza': 1.0}

当然这里的比萨饼应该有最大的索引。我也尝试对它们进行排序，例如：

matchings_indices = {matching:sum([s == m for s,sdx in enumerate(sorted(string))\
                                 for moose in matching.split() 
                                 for m, mdx in enumerate(sorted(moose)) if sdx==mdx])/len(string) 
                     for matching in matchings}

但在那种情况下，这是第一种情况的输出：（对于非常不同的字符串仍然足够好）

{'pizzas': 0.8,
 'potato chips': 0.0,
 'cheesy lime': 0.0,
 'pretzels': 0.0,
 'pork': 0.2}

这里是第二个：

{'pizzas': 0.8,
 'pizza fries': 1.0,
 'cheesy lime': 0.2,
 'pizzo': 0.6,
 'pizza': 1.0}

哪个更好但仍然如此。pizzas是一个更好的匹配pizza fries，应该得到更高的分数。

因此，任何改善情况的帮助都会很棒！

标签： pythonstring

解决方案

你可以看看使用编辑距离/编辑距离。从维基百科页面：

Levenshtein 距离是用于测量两个序列之间差异的字符串度量。非正式地，两个单词之间的 Levenshtein 距离是将一个单词更改为另一个单词所需的单字符编辑（插入、删除或替换）的最小数量。

我找到了计算距离的这个答案，然后你可以从 1 中减去这个距离，使你的最高分最好：

# from https://stackoverflow.com/a/32558749/6386471
def levenshteinDistance(s1, s2):
    if len(s1) > len(s2):
        s1, s2 = s2, s1

    distances = range(len(s1) + 1)
    for i2, c2 in enumerate(s2):
        distances_ = [i2+1]
        for i1, c1 in enumerate(s1):
            if c1 == c2:
                distances_.append(distances[i1])
            else:
                distances_.append(1 + min((distances[i1], distances[i1 + 1], distances_[-1])))
        distances = distances_
    return distances[-1]

string = 'pizza'
matchings = ['pizzas', 'pizza fries', 'cheesy lime', 'pizzo', 'pizza']

scores = {}

for m in matchings:
    scores[m] = 1 - levenshteinDistance(string,m)

scores

>>> {'pizzas': 0, 'pizza fries': -5, 'cheesy lime': -10, 'pizzo': 0, 'pizza': 1}

import operator
max(scores.items(), key=operator.itemgetter(1))[0]

>>> 'pizza'

推荐阅读