Список всех дубликатов файлов в файловой системе, заданных корневым каталогом.

Question

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

Answer 1

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

Я бы порекомендовал 3-шаговый алгоритм:

1. сканирование каталогов и запишите дорожкам & размеры файлов
2. Хэш только те файлы, которые имеют тот же размер, как и другие файлы, только если существует более двух файлов с одинаковым размером: если файл имеет тот же размер, что и только один файл, вам не нужно хеширование, просто сравните их содержимое один-к-одному (экономит время хэширования, вы не будете необходимо значение хеша после этого)
3. Даже если хэш-код тот же, вам все равно придется сравнивать файлы байтов за байт, потому что ha sh может быть идентичным для разных файлов (хотя это очень маловероятно, если размер файла тот же, и это ваша файловая система).

Вы также можете обойтись без хэширования, открыв все файлы в одно и то же время, если это возможно, и сравните содержимое. Это позволит сохранить многократное чтение в больших файлах. Существует много настроек, которые вы можете реализовать, чтобы сэкономить время в зависимости от типа ваших данных (например: если 2 сжатых/tar-файла имеют одинаковый размер> x Ggigabytes size (и одно и то же имя), не читайте содержимое , учитывая ваш процесс, файлы, скорее всего, будут дублировать)

Таким образом, вы избегаете хэширования файлов, размер которых уникален в системе. Экономит много времени.

Примечание: здесь я не учитываю имена, потому что, по-моему, имена могут быть разными.

EDIT: Я сделал несколько исследований (слишком поздно) и выяснил, что fdupes, кажется, делает точно, что если вы используете Un * X-подобные системы:

https://linux.die.net/man/1/fdupes

видел в что вопрос: List duplicate files in a directory in Unix