Хэширование для быстрого поиска одинаковых файлов

тигрово-древесный

А может что побыстрее есть? Данных много, скорость критична.

MD5 и не парь мозги.

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

сколько миллионов файлов и сколько терабайт они занимают?

Пользуй MD5 и не парься. Многие его используют именно для этих целей в продакшенах, да и быстрый он. То что доктор прописал, короче.

> сколько миллионов файлов и сколько терабайт они занимают?

До нескольких десятков тысяч zip-файлов, в каждом из которых несколько десятков (до сотни думаю) других файлов. Надо быстро найти одинаковые файлы (в основном, картинки jpeg, png), которых может быть до 20% по количеству и до 95% по занимаемой памяти). Надо быстро найти дубликаты и сделать новый zip, но уже без них.

Пока это писал, понял, что данные мне приходят из зипа, а значит уже посчитана CRC-32.

> Пользуй MD5 и не парься. Многие его используют именно для этих целей в продакшенах, да и быстрый он.

Это в каких продакшенах его используют для быстрого поиска дубликатов?

В энтерпрайзных, это очевидно.

что у тебя за тачка что md5 тормозит? :)

> Надо быстро найти дубликаты и сделать новый zip, но уже без них.

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

Если pitekantrop пользуется жабовской версией - я почти уверен, что тормозит жаба (или жабовское считывание файлов).

Я пользую md5 референс функцию от RSA на си бородатых годов (91го) и она летает. Боттлнек вовсе не на ней: там всего несколько сдвигов и работы с несколькими массивами в памяти. А зачитка стримов-файлов - она будет и для любого алгоритма.

Так что совет ТС: пользуйтесь md5, но используйте нормальные языки-технологии для задачи. Либо смиритесь (всё равно другие алгоритмы в вашем случае ничего не дадут)

Я использовал sha1sum:

#!/bin/sh
#	2 минуты 12.38 секунд  на 12'989 файлов общим размером 10'026'786'125 байт
#		(стало: 9'919'093'813 байт)
#	1 минута 13.00 секунд на 10'399 файлов общим размером 27'171'656'169 байт
#		(стало: 26'401'660'287 байт)
#	1 минута 17.82 секунд на 8'686 файлов общим размером 11'474'216'791 байт
#		(стало: 11'131'537'062 байт)
#	3 минуты 19.77 секунд на 16'257 файлов общим размером 70'697'892'519 байт
#		(стало: 69'132'667'051 байт)
#
FILELIST="filelist_4_mysql"
SQLFILE="tmp_4_mysql"
OUTP="double_files"

STEP_CNTR=0

function Step(){
	STEP_CNTR=$[$STEP_CNTR + 1 ]
	echo -e "\n\e[1;32m$STEP_CNTR\t\t$*...\e[0m"
}

alias mysql='mysql --default-character-set=koi8r --batch -s files_db'
rm -f $FILELIST $SQLFILE $OUTP

Step "Making list of files"
find  -type f -printf "%p\t%s\n" | iconv -f koi8-r -t utf8 > $FILELIST


Step "Finding files with same size"
cat > $SQLFILE << EOF
delete from files;
load data local infile "filelist_4_mysql" into table files(filename, filesize);
delete from files where filesize in (select filesize from (select filesize,count(*) c from files group by filesize having c = 1) T);
delete from files where filesize = 0;
select filesize from files group by filesize;
EOF

mysql < $SQLFILE > $OUTP

cat > $SQLFILE << EOF
delete from dups;
load data local infile "filelist_4_mysql" into table dups(filename, filemd5);
delete from dups where filemd5 in (select filemd5 from (select filemd5,count(*) c from dups group by filemd5 having c = 1) T);
select filename from dups group by filemd5;
EOF

Step "Finding duplicates"
while read SIZE
do
	rm -f $FILELIST
	echo "select filename from files where filesize = $SIZE ;" | mysql | while read FILE
	do
		MD=$(sha1sum -b "$FILE" | awk '{print $1}' 2>/dev/null);
		if [ "$MD" != "" ]; then
			echo -e "$FILE\t$MD" | iconv -f koi8-r -t utf8 >> $FILELIST 
		else
			echo -e "\e[1;31;40mCant read MD5 of $FILE\e[0m\nTrace:"
			echo "select filename from files where filesize = $SIZE;" | mysql
		fi
	done
	mysql < $SQLFILE | while read FILE
	do
		echo -e "\n\e[1;41;33m$FILE\e[36m has dublicates:\e[0m"
		echo "select filename from dups where filemd5 = (select filemd5 from dups where filename = \"$FILE\") AND filename != \"$FILE\";" | mysql  | while read D_FILE
		do
			echo -e "\e[1;32;40m$D_FILE\e[0m"
			[ "$1" = "-d" ] && rm -f "$D_FILE" && echo "deleted"
			[ "$1" = "-l" ] && ln -f "$FILE" "$D_FILE" && echo "linked"   #|| ln -fs "$FILE" "$D_FILE" || echo -e "\e[1;31;40merror linking $FILE to $D_FILE!!!\e[0m"
		done
	done
done < $OUTP

Step "Deleting trash"
echo "delete from files; delete from dups;" | mysql
rm -f $FILELIST $SQLFILE $OUTP

sha1 будет медленнее md5 по-любому. Хоть на 30% но медленнее.

fdups использует md5 (ещё не известно какую реализацию - быструю ли). И создают в скрипте кучу пайпов.

Может ТСу свой скрипт написать и свою прогу скомпилировать - вот тогда бы летало.

Я не использую md5 из-за большей вероятности коллизий, сам сначала в тестовом варианте прогнал с md5 - выявил как минимум одну коллизию (два файла одинакового размера, но с разным содержанием, имели одинаковые md5). Конечно, вероятность невысока, но все-таки, ИМХО, пусть в ущерб скорости, но надежность будет повыше. Тем более - посмотрите на результаты теста в шапке скрипта, работает он достаточно быстро.

> Если сделать надо всего один раз, быть может стоит сначала факторизовать набор файлов по длине?

Естественно файлы разной длины сравнивать не имеет смысла. Я об этом написал в стартовом посте.

Используя n-битный хеш, ты за один проход разобьёшь свою кучу файлов на 2^n групп. Если файлов будет на порядки больше этого количества (никогда не видел таких помоек!), то сравнение файлов в группах будет неоптимальным и надо выбрать хеш подлиннее. CRC-32 хватит. Низкая криптостойкость хеша грозит тем, что злой пользователь сможет задосить твою программу, подсунув тебе кучу файлов с одинаковыми хешами, так что программа будет сравнивать их долго. Но всегда можно подсунуть просто кучу одинаковых файлов :)

Я бы сделал так. Заводим словарик (размер -> файл). Перебираем файлы, занося их в словарик. При возникновении коллизии заменяем файл на словарик (хеш -> файлы). В конце все коллизии по хешам, если такие всё же случатся, разрешаем честным сравнением. В частных случаях можно ещё поотимизировать.

> Если pitekantrop пользуется жабовской версией - я почти уверен, что тормозит жаба (или жабовское считывание файлов).

У меня ещё ничего не тормозит. :) Я эту байду завтра написать собрался. И таки да, на жабе.

В таких задачах чаще всего тормозит не жаба, а алгоритм.

Что есть на свете MD5, SHA и TTH, я знаю. Но в них заложена криптостойкость, т.е. защита от злонамеренных коллизий, которая мне в данном случае не нужна. А значит можно использовать более быстрые алгоритмы. Вот я и решил узнать у ЛОРа про достижения прогрессивного человечества в этой области, кроме CRC и Adler-32.

Пишите, а потом выложите тестик (по аналогии с моим) - сравним производительность :)

>Данных много, скорость критична.

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

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

man hardlink

>Вообще-то, если файлов несколько десятков тысяч, размеры будут часто совпадать...

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

Тоже так думал.

На самом деле есть распространённые длины файлов, например 100МБ предлагаемые RAR-ом при разбивке архива на тома часто встречаются на файлообменниках.

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

> Сравнивай размеры.

Ну это первым делом. :)

И в тех _немногих_ случаях, когда размеры совпадут

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

сравнивай хоть хэши, хоть побайтово

Побайтово очень не хочется, т.к. одинаковых файлов могут быть тысячи. Но, как я уже писал, читаю я их из зипа, а значит мне на халяву достаётся уже посчитанный CRC-32.

Интересно, какова вероятность встретить 2 разных jpeg или png одинакового размера и с одинаковым CRC-32? Но можно для очистки совести сравнить побайтово, скажем, первый килобайт.

> Интересно, какова вероятность встретить 2 разных jpeg или png одинакового размера и с одинаковым CRC-32?

Для идеальной хэш-функции c n-битным результатом эта вероятность, я так понимаю, 1 / 2 ^ n. Т.е. для идеального сферической 32-битной хэш-функции в вакууме это будет 2.33e-10, т.е. практически никогда для моего случая.

> в тестовом варианте прогнал с md5 - выявил как минимум одну коллизию (два файла одинакового размера, но с разным содержанием, имели одинаковые md5)

O_o Просто невероятно! файлы в студию!

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

А может для каждого файла хранить два (три, четыре,...) хэша, полученных путем применения относительно дешевых хэш-функций?

Обновил скриптик. Теперь не надо специально создавать базу данных. Скрипт самодостаточен.

#!/bin/sh
FILELIST="/tmp/filelist_4_mysql"
SQLFILE="/tmp/tmp_4_mysql"
OUTP="/tmp/double_files"
DB="/tmp/filelistdb"

STEP_CNTR=0

function SQL(){
	echo -e $* | sqlite3 $DB
}

function SQLF(){
	sqlite3 $DB < $SQLFILE
}


function Step(){
	STEP_CNTR=$[$STEP_CNTR + 1 ]
	echo -e "\n\e[1;32m$STEP_CNTR\t\t$*...\e[0m"
}

rm -f $FILELIST $SQLFILE $OUTP $DB

Step "Init database"
SQL "create table files(filename string, filesize integer); create table dups(filename string, filemd5 long);"

Step "Making list of files"
find  -type f -printf "%p\t%s\n" > $FILELIST

Step "Finding files with same size"
cat > $SQLFILE << EOF
delete from files;
.mode tabs
.import /tmp/filelist_4_mysql files
delete from files where filesize in (select filesize from (select filesize,count(*) c from files group by filesize having c = 1) T);
delete from files where filesize = 0;
select filesize from files group by filesize;
EOF

SQLF > $OUTP

cat > $SQLFILE << EOF
delete from dups;
.mode tabs
.import /tmp/filelist_4_mysql dups
delete from dups where filemd5 in (select filemd5 from (select filemd5,count(*) c from dups group by filemd5 having c = 1) T);
select filename from dups group by filemd5;
EOF

Step "Finding duplicates"
while read SIZE
do
	rm -f $FILELIST
	SQL "select filename from files where filesize = $SIZE ;" | while read FILE
	do
		MD=$(sha1sum -b "$FILE" | awk '{print $1}' 2>/dev/null);
		if [ "$MD" != "" ]; then
			echo -e "$FILE\t$MD" >> $FILELIST
		else
			echo -e "\e[1;31;40mCant read MD5 of $FILE\e[0m\nTrace:"
			SQL "select filename from files where filesize = $SIZE;" 
		fi
	done
	SQLF | while read FILE
	do
		echo -e "\n\e[1;41;33m$FILE\e[36m has dublicates:\e[0m"
		SQL "select filename from dups where filemd5 = (select filemd5 from dups where filename = \"$FILE\") AND filename != \"$FILE\";"  | while read D_FILE
		do
			echo -e "\e[1;32;40m$D_FILE\e[0m"
			[ "$1" = "-d" ] && rm -f "$D_FILE" && echo "deleted"
			[ "$1" = "-l" ] && ln -f "$FILE" "$D_FILE" && echo "linked"   #|| ln -fs "$FILE" "$D_FILE" || echo -e "\e[1;31;40merror linking $FILE to $D_FILE!!!\e[0m"
		done
	done
done < $OUTP

Step "Deleting trash"
rm -f $FILELIST $SQLFILE $OUTP $DB

По моим наблюдениям быстрее упрёшься в диск, нежели в md5. Можно md4, но вряд ли будет ощутимый профит.

> Вопрос: какой алгоритм хэширования лучше всего подходит для данной задачи? Насколько велика вероятность коллизий при этом? (Побайтовое контрольное сравнение делать не хочется.)
Одному мне кажется что побайтное сравнение будет быстрей?

>Одному мне кажется что побайтное сравнение будет быстрей?

Если сравнивать два файла то да, если много то нет.

> А может что побыстрее есть? Данных много, скорость критична.

Суммируй байты. На совпадающих считай CRC32.

А не лучше ли выбрать самую-самую быструю хэш-функцию, а в случае совпадения применить ещё одну — надёжную?

Точно. Не учел.

встечный вопрос, интереса ради: чем fdupe не устроил?

>А не лучше ли выбрать самую-самую быструю хэш-функцию, а в случае совпадения применить ещё одну — надёжную?

О!

> Суммируй байты. На совпадающих считай CRC32.

2 прохода? Нах-нах.

И, как я уже писал, я файлы достаю из зипа, так что CRC32 уже посчитана.

Сделал так: сравниваю длину и CRC32. Если совпадает, то считаю, что файлы одинаковы. Всё.

> А не лучше ли выбрать самую-самую быструю хэш-функцию, а в случае совпадения применить ещё одну — надёжную?

Нет, 2 раза перечитывать файл совершенно не лучше.

У самопального скрипта легко настроить вывод, да и поведение. А для настройки fdupes надо в его исходниках ковыряться...

> встечный вопрос, интереса ради: чем fdupe не устроил?

Тем, что у меня серверная кросплатформенная Java-библиотека. Поэтому, зависимости от перлов мне не нужны.

Меня интересовал исключительно оптимальный алгоритм хэширования.