Какой самый быстрый способ проверить, идентичны ли файлы?

Question

Если у вас есть 1 000 000 исходных файлов, вы подозреваете, что они все одинаковы, и вы хотите сравнить их, каков текущий ускоренный метод для сравнения этих файлов? Предположим, что это файлы Java, и платформа, на которой выполняется сравнение, не важна. cksum заставляет меня плакать. Когда я имею в виду идентичные, я имею в виду ВСЕ идентичные.

Обновление: Я знаю о создании контрольных сумм. Дифф смехотворен ... Я хочу скорость.

Обновление: Не зацикливайтесь на том факте, что они являются исходными файлами. Представьте, например, что вы взяли миллион прогонов программы с очень регулируемым выходом. Вы хотите доказать, что все 1 000 000 версий вывода одинаковы.

Обновление: читать количество блоков, а не байтов? Сразу выкинуть? Это быстрее, чем найти количество байтов?

Обновление: Отличается ли это ЛЮБЫМ от самого быстрого способа сравнения двух файлов?

Answer 1

Используйте концепцию Bloom Filter. Простое объяснение здесь: http://crzyjcky.com/2013/01/03/the-magical-bloom-filter/

Это дает вам постоянное время сравнения. Однако этот метод не может быть использован в одиночку. Apache Cassandra и HBase используют эту технику для внутреннего использования.

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

Answer 2

На мой взгляд, это операция файловой системы. Итак, сначала тщательно выбирайте свою файловую систему. Далее дедупликация. Тогда сравните иноды. Как:

% find / -inum "$(ls -di "./test.file" | grep -E '^[0-9]*')"
<list of identical files provided in a few seconds to a minute>

Answer 3

Я только что написал приложение на c #, которое делает что-то похожее на то, что вы хотите. Вот что делает мой код:

Считать все размеры каждого файла в список или массив.

Используйте цикл for, чтобы проверить, совпадает ли какой-либо из этих размеров. если они имеют одинаковый размер, сравните байт одного файла с байтом другого файла. Если два байта совпадают, переходите к следующему байту. Если разница найдена, верните, что файлы разные.

Если достигнут конец обоих файлов, а последние два байта совпадают, файлы должны быть идентичны.

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

Answer 4

Зачем изобретать велосипед? Как насчет стороннего приложения? Конечно, у него нет API, но я не думаю, что вы часто ставите себя в такую ​​ситуацию. Мне нравится это приложение doublekiller просто сделайте резервную копию, прежде чем начать. :) Это быстро и бесплатно!

Answer 5

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

Answer 6

MD5 хэш будет быстрее, чем сравнение, но медленнее, чем обычная проверка CRC. Вы должны выяснить, какую надежность вы хотите сравнивать.

Answer 7

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