поиск предметов для дублирования
У меня есть пул данных (X1..ИксN), для которого я хочу найти группы равных значений. Сравнение очень дорогое, и я не могу хранить все данные в памяти.
Результат, который мне нужен, например:
Икс1 равно X3 и Х6
Икс2 уникален
Икс4 равно X5
(Порядок строк или порядок внутри строки не имеет значения).
Как я могу реализовать это с помощью парных сравнений?
Вот что у меня так далеко:
Сравнить все пары (Xя, ИксК) с я < к, а также использовать транзитивность: если я уже нашел X1== X3 и Х1== X6, Мне не нужно сравнивать X3 и Х6.
поэтому я мог бы использовать следующую структуру данных:
map: index --> group
multimap: group --> indices
где группа назначена произвольно (например, «номер строки» в выходных данных).
Для пары (Xя, ИксК) с я < к:
-
если и i, и k уже имеют назначенную группу, пропустите
-
если они сравниваются равными:
- если у меня уже есть назначенная группа, поместите k в эту группу
- в противном случае создайте новую группу для i и вставьте в нее k
-
если они не равны:
- если мне еще не назначена группа, назначьте новую группу для меня
- то же самое для к
Тот должен работать, если я осторожен с порядком предметов, но мне интересно, если это лучший / наименее удивительный способ решить эту проблему, так как эта проблема кажется несколько распространенной.
Предыстория / Дополнительная информация: целью является дедупликация хранения предметов. У них уже есть хэш, в случае коллизии мы хотим гарантировать полное сравнение. Размер рассматриваемых данных имеет очень резкое распределение длинных хвостов.
Итеративный алгоритм (найти любые два дубликата, поделиться ими, повторять до тех пор, пока не останется никаких дубликатов) может быть проще, но нам нужна немодифицирующая диагностика.
Основой кода является C ++, что-то, что работает с контейнерами или алгоритмами STL / boost, было бы неплохо.
[редактировать] Относительно хеш-функции: Для целей этого вопроса, пожалуйста, предположите, что слабая хеш-функция не может быть заменена.
Это требуется для однократной дедупликации существующих данных и должно иметь дело с коллизиями хешей. Первоначальный выбор был «быстрый хеш, и сравните при столкновении», выбранный хеш получился немного слабым, но его изменение нарушило бы обратную совместимость. Даже тогда я лучше сплю с простым утверждением: В случае столкновения вы не получите неверные данные. вместо того, чтобы вести блог о волчьи атаки.
Решение
Вот еще одна, может быть, более простая структура данных для использования транзитивности. Сделайте очередь сравнений, которые вам нужно сделать. Например, в случае 4 пунктов это будет [(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)] , Также есть массив для сравнений, которые вы уже сделали. Перед каждым сравнением проверяйте, было ли это сравнение выполнено ранее, и каждый раз, когда вы находите совпадение, проходите очередь и заменяйте индекс соответствующего элемента его более низким индексом эквивалента.
Например, предположим, что мы pop (1,2), сравнить, они не равны, нажмите (1,2) в массив already_visited и продолжай. Затем нажмите pop (1,3) и найдите, что они равны. На этом этапе пройдите очередь и замените все 3 на 1. Очередь будет [(1,4), (2,1), (2,4), (1,4)] и так далее. Когда мы достигаем (2,1), оно уже посещено, поэтому мы пропускаем его, и то же самое с (1,4).
Но я согласен с предыдущими ответами. Поскольку сравнение требует значительных вычислительных ресурсов, вы, вероятно, захотите сначала вычислить быструю, надежную хеш-таблицу и только затем применять этот метод к коллизиям.
Другие решения
Итак … у вас уже есть хэш? Как насчет этого:
- сортировать и группировать по хешу
- распечатать все группы размером 1 как уникальные
- сравнить столкновения
Совет для сравнения коллизий: почему бы просто не перефразировать их с другим алгоритмом? Промыть, повторить.
(Я предполагаю, что вы храните файлы / blob / images здесь и у вас есть их хеши, и что вы можете перетаскивать хэши в память, а также, что они похожи на sha1 / md5 и т. Д., Поэтому коллизии очень маловероятны)
(также я предполагаю, что два разных алгоритма хеширования не будут конфликтовать на разных данных, но это, вероятно, безопасно предположить …)
Сделайте хэш каждого элемента. Составьте список pair<hash,item_index>, Вы можете найти группы, отсортировав этот список по хешу или поместив его в std::multimap,
Когда вы выводите список групп, вам нужно сравнивать элементы для коллизий хешей.
Таким образом, для каждого элемента вы будете делать один расчет хеша и примерно одно сравнение. И сортировка хэш-списка.
Я согласен с идеей использовать вторую (надеюсь, улучшенную) хеш-функцию, чтобы вы могли разрешать некоторые коллизии со слабым хешем без необходимости выполнять дорогостоящие попарные сравнения. Поскольку вы говорите, что у вас есть проблемы с ограничением памяти, мы надеемся, что вы можете разместить всю хеш-таблицу (с дополнительными ключами) в памяти, где для каждой записи в таблице вы храните список индексов записей для записей на диске, которые соответствуют этому ключу пара. Тогда возникает вопрос: можно ли для каждой пары ключей загрузить все записи в память, в которой есть эта пара ключей? Если так, то вы можете просто перебирать пары ключей; для каждой пары ключей освободите все записи в памяти для предыдущей пары ключей и загрузите записи в памяти для текущей пары ключей, а затем выполните сравнения среди этих записей, как вы уже обрисовали. Если у вас есть пара ключей, в которую вы не можете поместить все записи в память, вам придется загружать частичные подмножества, но вы определенно должны иметь возможность хранить в памяти все группы (с уникальным представителем записи для каждой группы). вы нашли для пары ключей, так как количество уникальных записей будет небольшим, если у вас есть хороший вторичный хеш.