Определение того, является ли файл дубликатом

Question

Есть ли надежный способ определить, являются ли два файла одинаковыми? Например, два файла одинакового размера и типа могут быть одинаковыми или не одинаковыми (да, я знаю, что это не совсем слово). Я предполагаю, что сравнение одной или двух контрольных сумм файлов поможет, но мне интересно:

1. Насколько надежны контрольные суммы при определении, являются ли два файлы разные; каковы шансы двух разных файлов с одинаковой контрольной суммой?
2. Повысилась бы надежность применение дополнительной контрольной суммы сравнения?
3. Какой алгоритм (ы) контрольной суммы будет самый эффективный и / или надежный?

Любые идеи, предложения или мысли приветствуются!

P.S. Код для этого пишется на Java, работающем в системе nix, но общий ввод или независимый от платформы ввод наиболее полезен.

Answer 1

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

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

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

Ваш третий вопрос уже решен ответом leonbloy; MD5 и SHA-1 являются общими.

Answer 2

1) Very reliable
2) Not theoretically
3) SHA-1

Answer 3

Любая контрольная сумма даст вам ложное срабатывание для очень небольшого числа случаев. Если вы можете жить с этим, хорошо. Если нет, то способ сделать это - сначала выполнить сравнение контрольной суммы, а если контрольные суммы равны, то побайтный тест. Побайтовое тестирование будет проводиться очень редко, поэтому усредненная стоимость за множество сравнений будет очень мала. ОДНАКО это не тот случай, когда большинство ваших сравнений должны возвращать «true».

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

Answer 4

Любой стандартный алгоритм контрольной суммы, такой как MD5, даст вам надежный тест для большинства реальных сценариев. Если вам нужно еще больше надежности, иди SHA. http://en.wikipedia.org/wiki/Cryptographic_hash_function#Cryptographic_hash_algorithms