алгоритм поиска дубликатов

Question

Существуют ли какие-либо известные алгоритмы для эффективного поиска дубликатов?

Например, предположим, если у меня есть тысячи фотографий и фотографии названы с уникальными именами.Могут быть шансы, что дубликаты могут существовать в разных подпапках.Является ли использование std :: map или любых других хэш-карт хорошей идеей?

Answer 1

Если вы имеете дело с файлами, одна из идей - сначала проверить длину файла, а затем сгенерировать хеш только для файлов одинакового размера.

Тогда просто сравните хэши файла. Если они одинаковые, у вас есть дубликат файла.

Между безопасностью и точностью существует компромисс: может быть, кто знает, может иметь разные файлы с одинаковым хешем. Таким образом, вы можете улучшить свое решение: сгенерируйте простой и быстрый хеш для поиска ошибок. Когда они разные, у вас разные файлы. Когда они равны, сгенерируйте второй хэш. Если второй хеш отличается, у вас просто был ложный положительный результат. Если они снова равны, возможно, у вас есть настоящий дубликат.

Другими словами:

generate file sizes
for each file, verify if there's some with the same size.
if you have any, then generate a fast hash for them.
compare the hashes.
If different, ignore.
If equal: generate a second hash.
Compare.
If different, ignore.
If equal, you have two identical files.

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

Answer 2

Может быть, вы хотите хешировать каждый объект и хранить хеши в какой-то таблице?Чтобы проверить наличие дубликатов, вы просто просматриваете таблицу.

Структура данных Mystery ???

Что касается "известного алгоритма" для выполнения этой задачивзгляните на MD5 .