python - 遍历元组列表并在 python 中查找相似值

Question

我有一个元组列表，例如哈希值和文件路径。我想根据汉明距离找到所有重复项以及类似项。我有一个用于汉明距离分数的函数，我可以在其中给出值并获得分数。

我坚持循环遍历列表并找到匹配项的问题。

list = [('94ff39ad', '/path/to/file.jpg'), ('94ff39ad', '/path/to/file2.jpg'), ('94ff40ad', '/path/to/file3.jpg'), ('cab91acf', '/path/to/file4.jpg')]
score = haming_score(h1, h2)
# score_for_similar > 0.4

我需要一个字典，其中原始(路径)作为键，并以可能的相似或重复项的列表作为值。

喜欢:

result = {'/path/to/file.jpg': ['/path/to/file2.jpg', '/path/to/file3.jpg'], '/path/to/file4.jpg': []}

第二个字典键值对 {'/path/to/'file4.jpg': []} 不是必需的，但有帮助。

目前，我在列表中循环两次并相互比较值。但我得到了双重结果。

我将非常感谢您的帮助。

附注计算我使用的汉明距离分数:

def hamming_dist(h1, h2):
    h1 = list(h1)
    h2 = list(h2)
    score = scipy.spatial.distance.hamming(h1, h2)
    return score

Answer 1

import Levenshtein as leven

# This is your list
xlist = [('94ff39ad', '/path/to/file.jpg'), ('512asasd', '/somepath/to/file.jpg'), ('94ff39ad', '/path/to/file2.jpg'), ('94ff40ad', '/path/to/file3.jpg'), ('cab91acf', '/path/to/file4.jpg')]

# Here's what you'll base the difference upon:
simalarity_threshhold = 80 # 80%
results = {}

for item in xlist:
    path = item[1]
    print('Examining path:', path)

    max_similarity = None
    similarity_key = None
    for key in results:
        diff = leven.distance(path, key)
        diff_percentage = 100 / max(len(path), len(key)) * (min(len(path), len(key)-diff))

        print('    {} vs {} = {}%'.format(path, key, int(diff_percentage)))
        if diff_percentage > simalarity_threshhold:
            if not max_similarity or diff_percentage > max_similarity:
                max_similarity = diff_percentage
                similarity_key = key

    if not max_similarity:
        results[path] = {}
    else:
        results[similarity_key][path] = max_similarity

print(results)

如果两条路径的相似度超过彼此距离值的 80%，它们将被配对为潜在匹配项。如果另一个路径更相似，它将被添加到其中。

如果路径相似度低于 80%，它将创建自己的结果路径/树/结构。

同样，这只是解决问题的一个示例。
有many ways to do it ，但我更喜欢 Levenshtein因为它易于使用并且非常准确。

我在那里留下了一些调试代码，以便您可以看到思维方式、在何处传递什么值等等，这完全取决于您的规则集来确定什么是匹配的，什么是不匹配的。

哦，我还将这些值存储为子字典。这样每个潜在的候选人都可以保留其在检查时得到的分数。您也可以将它们保存为列表。但与字典相比，列表在迭代、比较和存储方面都非常慢。

第二个“哦”..这段代码没有经过回归测试..这里肯定存在一些逻辑问题..特别是在diff_percentage计算中..我的意思是数学向导。但你明白我的意思了:)