C#. Какой алгоритм контрольной суммы выбрать?

Question

[Limbend]

Задача: сравнить два файла, и определить, что они копии друг друга.

Тип файлов - неограничен. (большинство- файлы проектов в различных ide, документы и т.п. Количество файлов - неограничен. (тестируется на 10 000шт.)

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

P. S. Опробовал CRC32 и MD5. MD оказался примерно в 2 раза быстрее, но думаю у меня была не лучшая реализация CRC32...

Answer 1

[GavriKos]

MD5 и CRC32 не обеспечивает отсутствие коллизий, поэтому использовать только контрольные суммы некорректно. Как минимум сравнивайте еще и размер, причем сначала его.

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

Comments

[Limbend]

А что делать с разными файлами и одним размером? Или в обязательно проводить расчет хеша?

[GavriKos]

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

[Limbend]

GavriKos: хм... Спасибо, пойду писать

Answer 2

[d-stream]

Собственно напрашивается таблица в виде
"полное имя файла"
"CRC"
"MD5"

и если задача не запрещает sql - то файлы-клоны отлично будут найдены как

select * from table where MD5 in (
            select MD5 from table group by MD5 having count(*)>1
)
order by MD5

MD5 можно заменить на CRC32 или даже скомбинировать их как MD5+CRC32 - вероятность одновременной коллизии и в CRC32 и MD5 получится как произведение вероятностей коллизии для каждого из алгоритмов - этого скорее всего хватит для военно-космической приемки -)

Comments

[Limbend]

Видимо из-за плохой постоновки вопроса, не удалось донести, что находить все хеши придется много раз и создание зарание бд не является применимы решением. (как минимум я так вижу)

Основная задача синхронизировать файлы в 2 папках указаных пользователем, причем полное удаление второй и копирование первой не самый "вкусный" вариант.

[d-stream]

Termir988: сдается мне что подсчет хэшей каждый раз - задчать соизмеримая с копированием файлов

так что в том или ином виде но бд потребуется

иначе "в лоб" посчитать хэши придется (N-1)! раз то бишь для 10 файлов - это придется сделать 362880 раз

оптимизация сравнения по размеру конечно существенно поможет, но если даже десяток файлов по 20мб совпадут по размеру - полчим что-то около 362880*20мб=7Тб чтения - сколько времени будут читаться 7Tb?

Кстати хорошее место для хранения хэшей - ADS: https://support.microsoft.com/en-us/help/105763/ho...

[Limbend]

d-stream: а от куда число 362880?

[d-stream]

Termir988: https://ru.wikipedia.org/wiki/%D0%A4%D0%B0%D0%BA%D...

[Limbend]

d-stream: что факториал? Я так и не понял почему считать хеш придется 362880 раз... Даже если файлов будет 10000 (как в моем примере) то ко всем ним и придется посчитать и записать хеши в ОЗУ, на кой считать их каждый раз. Другое дело, что даже подсчет всех 10000 хешей - не очень быстро проходит.

[d-stream]

Termir988: если их не хранить, как говорилось, то подразумевается подсчет на лету то бишь сколько сравнений - столько и расчетов

и что делать если количество файлов не ограничено, а вот размер озу - ограничен? -)

[Limbend]

d-stream: в нашем мире все ограничено, и файлы и ОЗУ. Упирание в предел - это уже другая проблема.

[d-stream]

Termir988: да, поэтому более-менее нащупанный путь - это так или иначе хранить инфу например рядом с файлами, но какими путями к этому прийти - отдельный вопрос -))

Answer 3

[AxisPod]

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

Comments

[Limbend]

Получение хеша быстрее чем чтение файла?

[AxisPod]

Termir988: Хэши можно посчитать один раз и затем среди них искать дубликаты. А уж для дубликатов по хэшам сравнить по содержимому.

[Limbend]

AxisPod: в данной ситуации хранить хеши можно только до конца алгоритма. В следующий раз предполагается, что файлы изменятся.