@pcdesign

Как рассчитать «похожесть» двух словарей?

Вот, например, два словаря:
Апельсин 1
Яблоко 2
Банан 3


Апельсин 2
Яблоко 2
Инжир 1


На сколько одна накладная "похожа" на другую и получить коэффициент похожести?
Я понимаю, что скорее всего надо это решать с помощью https://ru.wikipedia.org/wiki/Коэффициент_Жаккара
На сколько долгий будет расчет просто с бумажкой и ручкой без компа?
  • Вопрос задан
  • 192 просмотра
Решения вопроса 1
@o5a
Если значения ключей не важны для сравнения, то достаточно использовать keys()
d1 = {'Апельсин': 1,
'Яблоко': 2,
'Банан': 3
}

d2 = {'Апельсин': 2,
'Яблоко': 2,
'Инжир': 1
}

print(d1.keys())
# общие ключи
print(d1.keys()&d2.keys())

Судя по ссылке, этого достаточно для расчета Вашего коэффициента.
Ответ написан
Пригласить эксперта
Ответы на вопрос 2
@isol
Посмотрите на Bloom Filter. Возможно пригодится. Если построить bloom filter для каждого множества, то можно сравнивать насколько похожи фильтры.
Ответ написан
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, гуглер, экс-олимпиадник.
Если отсутствие слова в словаре равносильно слову с весом в 0, то можно считать какую-угодно меру от векторов чисел. Хоть корень из суммы квадратов разностей по каждому слову.

В вашем примере это будет (1-2)^2+(2-2)^2+(3-0)^2+(1-0)^2 = 11.
Чем меньше это число, тем похожее словари. Можно ее еще как-то нормировать, поделив на, допустим количество уникальных ключей в обоих словарях. Или на количество всевозможных слов.

Если ваш язык/структура позволяет пройтись по словарю в лексикографическом порядке, то можно подсчитать такую меру за линейное время выполняя что-то вроде слияния сортированных списков. Изначально 2 указателя на минимальные элементы (по словарю) в каждом словаре. Если два элемента с одинаковым ключем, то считайте разность двух весов и двигайте оба указателья. Иначе считайте разность веса с минимальным ключем и 0 и двигайте только этот указатель. Случай, когда один из словарей уже пуст совпадает со вторым случаем.

В питоне позволяет обходить ключи по порядку OrderedDict.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы