Просмотрите список кортежей и найдите похожие значения в Python
У меня есть список кортежей, например, с хешем и путем к файлу. Я хотел бы найти все дубликаты, а также похожие предметы на основе расстояния Хэмминга. У меня есть функция для оценки дистанции, где я даю значения и получаю оценку.
Я решил перебрать список и найти подходящие элементы.
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': []}
Вторая пара ключ-значение dict {'/path/to/'file4.jpg': []} не обязательна, но полезна.
В настоящее время я дважды просматриваю список и сравниваю значения друг с другом. Но получаю двойные результаты.
Буду очень признателен за вашу помощь.
P.S. для расчета дистанции Хэмминга я использую:
def hamming_dist(h1, h2):
h1 = list(h1)
h2 = list(h2)
score = scipy.spatial.distance.hamming(h1, h2)
return score
привет, хватит, если он первый. Я только что вспомнил, что достаточно получить списки «похожих». Но только они не должны фигурировать в 2-х списках.
Ответы 2
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%, он создаст свой собственный путь / дерево / структуру результата.
Опять же, это всего лишь один пример того, как вы могли бы решить эту проблему. Есть много способов сделать это, но я предпочитаю Левенштейн, потому что с ним легко работать и он довольно точен.
Я оставил там немного отладочного кода, чтобы вы могли видеть образ мышления, какие значения куда передаются и т. д. Опять же, это все зависит от вашего набора правил для определения того, что соответствует, а что нет.
Да, и я также сохранил значения как подкаталоги. Это так, чтобы каждый потенциальный кандидат сохранил свой результат, полученный при проверке. Вы также можете сохранить их в виде списка. Но списки чрезвычайно медленны по сравнению со словарями как при повторении, так и при сравнении и хранении.
Второе "о" ... Этот код не тестировался на регрессию .. Здесь наверняка будут какие-то логические проблемы .. Особенно в расчете diff_percentage .. Я, неееет, имею в виду мастер математики. Но вы улавливаете мой тренд :)
Привет, я буду работать с вашим способом решения этой проблемы. Я просто хотел отметить, что сравниваю хеш-значения (созданные с помощью алгоритма dHash).
Чтобы записать, как я решил проблему, и помочь другим, вот мой код:
test = [('94ff39ad', '/path/to/file.jpg'), ('94ff39ad', '/path/to/file2.jpg'), ('94ff40ad', '/path/to/file3.jpg'), ('cab91acf', '/path/to/file4.jpg')]
seen = {}
new_seen = False
counter = 0
for x in test:
added = False
for k, v in seen.items():
if x[0] == k or hamming_dist(x[0], k) < .4:
v.append(x[1])
added = True
if not seen or not added:
seen[x[0]] = [x[1]]
print(seen)
>> {'/path/to/file.jpg': ['/path/to/file2.jpg', '/path/to/file3.jpg'], '/path/to/file4.jpg': []}
Как определить исходный ключ?
/path/to/file.jpgкаковы критерии того, что это первый ключ, а не/path/to/file2.jpg? Первое появление?