Изпечатай

[tarator]

gateway,

Големината на "съобщението" няма никакво значение. Помисли! Иначе подобни системи се използват от много хора и никой досега не се е оплакал от колизии. Аз например вкъщи използвам подобна система, съдържаща около 20 милиона хеша (200GB данни на по 8КБ блокове), засега нямам колизии. Ако имаш 1 ексабайт данни (10^18) и правиш SHA1 хеш на блокове по 8К, вероятността два блока да имат един и същ хеш е 10^-20. Ако такава вероятност те притеснява, използвай друга хеш функция '>

luda_glawa,

А за колко време се download-ва 4.5GB файл? :Р

[gat3way]

В този случай големината на съобщението ти не се ли води 8кб?

[lastcyrol]

А дали не може да се напише един скрипт, викан периодично, който да проверява дали в резултата от

Примерен код

ls -lR

няма два еднакви(или относително еднакви, зависи какви критерии определят дубликациите) реда?

[romeo_ninov]

Цитат (gat3way @ Март 07 2007,20:17)

Прекрасно, опресних си знанията за hash алгоритмите. SHA1 генерира 180-битов хеш. MD5 генерира 128-битов, в този ред на мисли, при SHA1 вероятността от колизии наистина е по-малка. Интересен е въпросът, какво се влага в понятието "колизия", защото има огромно значение големината на съобщението, от което се вади хеша. Ако става въпрос за пароли дето са рядко над 16 символа, въпросът с колизиите сигурно е важен, а вероятността за наличието на такива е...много малка. Ако става въпрос за 700-мегабайтови файлове обаче нещата стоят малко по-различно. Съвсем се абстрахирам от хеш-алгоритмите, защото при това положение те нямат толкова значение. Представи си че имаш 700 милиона позиции да наредиш както си искаш 256 стойности, това ти е множеството възможни 700-мегабайтови файлове. Съответно множеството възможни изходни MD5 хешове представлява броят възможности да наредиш на 16 позиции 256 различни стойности. Чисто теоретично, възможните колизии при това положение са 700.000.000 / 16. Не са малко все пак, как мислите? При това положение SHA1 би променило нещата с порядък 180/128 пъти по-малко възможни колизии. Надали има особена разлика '>

Малка поправка - SHA-1 е 160 бита, а не 180 и теоретическата вероятност за колизия е 2**80 т.е. 10**24

[tarator]

gateway,

Големината на съобщенията няма _нищо_ общо с вероятността от колизия.

[gat3way]

Добре де, нека няма, признавам се за победен '>

Вземаме случаят с MD5.

Сметките обаче пак не излизат правилни, 2^64 е вероятността за колизия на хешовете при две произволни съобщения. В случая обаче не смятаме директно възможността при два файла да се получат еднакви хешове, а възможността това да се случи по принцип с която и да е двойка файлове.

Една предварителна сметка: 2^64 е приблизително равно на 2*10^19.

Значи ако например има 10000 файла, то има C= 10000! / 2*(10000-2)! = (10000*9999)/2 = 5000*9999 - приблизително 50 милиона комбинации от два файла от тези 10000, върху които да смятаме възможността за колизия. Следователно, общата вероятност да се случи колизия на хешовете измежду някоя двойка файлове от тази файлова система става приблизително:

5*10^7 / 10^19 = 5 / 10^12 = 1/2*10^11

или едно на 200.000.000.000, уаааа, наистина е много малко вероятно да стане, не съм го очаквал.

Ще сметна само какво ще стане със 100.000 файла, просто за справка:

C=100000!/2!*(100000-2)! = 100000*99999/2=50000*99999
= 4.999.950.000 = (appr.) 5.000.000.000= 5*10^9

P(колизия)=5*10^9/10^19=5/10^10=1/2^9 = 1 на 2.000.000.000.

Съответно при един милиона файла, вероятноста става едно на (хм) 20 милиона.

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

[tarator]

Сметките ти са грешни. Ако имаме 10000 файла, значи имаме 10000 хеш стойности. Ако предположим, че вероятността за получаване на всяка възможна хеш стойност за еднаква (2^-128, прибл. 10^-28), тогава вероятността хеш стойностите на два файла да са еднакви е 10^-24.

Комбинаториката в случая не ти дава нищо повече. Припомни си теория на вероятностите. '>

[gat3way]

Цитат

Сметките ти са грешни. Ако имаме 10000 файла, значи имаме 10000 хеш стойности. Ако предположим, че вероятността за получаване на всяка възможна хеш стойност за еднаква (2^-128, прибл. 10^-28), тогава вероятността хеш стойностите на два файла да са еднакви е 10^-24

Мне '> Това, което получаваш е вероятността един определен от тези файлове да съвпадне с някой от останалите 10000. Нека опростим примера и не са 10 хиляди, ами само 3 файла - ф1,ф2,ф3. По твоят начин ще получиш вероятността хеша на ф1 да съвпадне с ф2 или ф3. Но не включваш и вероятността ф2 да съвпадне с ф3.

Алтернативно с 4 файла, смяташ вероятността ф1 да съвпадне с ф2/ф3/ф4. Но не смяташ вероятността ф2 да съвпадне с ф3/ф4 или ф3 да съвпадне с ф4.

Формулата за броят комбинации е n!/k!(n-k)! - n ти е броят на елементите в множеството, k ти е броят на елементите в една комбинация - в случаят 2.

Търсим точно комбинациите, защото при тях не се взема  редът на елементите, т.е случаите (a1,a2) и (a2,a1) са еквивалентни и не влизат 2 пъти.

[gat3way]

Но пък всъщност може двамата да имаме предвид две различни неща. Аз имам предвид възможността да има колизия на хешове между кои и да са два файла в някаква файлова система. Ти вероятно имаш предвид вероятността за всеки нов качен файл да се случи колизия. В този случай и двамата сме прави '>

[tarator]

Мисля, че си позабравил теория на вероятностите. Припомни си я и ще разбереш защо няма нужда от сметки с комбинации.

[gat3way]

Това не е аргумент. Замисли се малко:

Задачата не е каква е вероятността от 10 хиляди тегления да извадиш червена топка, при положение че в кутията червените топки са 1 на 2^x. Задачата е каква е вероятността ако изтеглиш 10.000 топки, да изтеглиш 2 с един и същ цвят. При положение че в кутията имаш неограничен брой топки от 2^64 различни разцветки. Как според теб се решава задачата?

Апропо, нека променим леко задачата и искаме да намерим вероятността да имаме не 2, а 3 файла с еднаква MD5 стойност. Това по какъв начин ще промени твоята сметка?

[neter]

Много се отклонихте от темата ве, хора. Това, което е най-удобно за използване в случая е fdupes. Използва MD5 за сравнение на файловете. Т.е., ако файловете се казват по един и същи начин, това не е достатъчен аргумент да ги счете за еднакви, но ако съдържанието им е едно и също, дори и файловете да се казват по различен начин, ще ги счете за еднакви. Според мен това е добър инструмент за премахване на повтарящи се файлове. Използвам го от време на време и досега не съм имал колизии. Тъй като досега го използвах ръчно, време е да напиша някакъв скрипт за автоматизиране на процеса. Тъкмо ще помогна и на човека. Ако някой иска, нека и той се пробва, та да си помогнем взаимно в написването на добър скрипт за целта. Сигурен съм, че ще е полезен на много хора.

[tarator]

gateway,

Днес нещо не мога да смятам, но мисля, че и двамата грешим. Ще помисля по въпроса утре '>

[neter]

Ето това, което сътворих. Приемам предложения за подобряване.

Примерен код

#!/bin/sh # Pyt do osnovnata papka, v koqto 6te se tyrsqt ednakvi failove # Skriptyt tyrsi i v podpapkite failove=/pyt/do/papkata # Pyt do faila, v koito 6te se izpisvat syvpadeniqta syvpadeniq=/pyt/do/faila/fail ### Ne e nujno redaktirane na komandite po-dolu ### osnova=`echo $failove | cut -d/ -f2` /usr/bin/fdupes -q -f -r $failove > $syvpadeniq cat $syvpadeniq | grep / | sed 's/ /\\ /' | sed 's/\/'$osnova'/rm \/'$osnova'/' > $syvpadeniq chmod +x $syvpadeniq $syvpadeniq chmod -x $syvpadeniq

За използването на скрипта, предварително трябва да се създаде един празен неизпълним файл някъде. В него ще се впишат всички съвпадения, като в списъка няма да влиза по едно съвпадение от всяка група съвпадения. Това невписано съвпадение ще е файла, който няма да се премахва. Скриптът трябва да се сложи в един изпълним файл и да се сложи в crontab-а да се изпълнява в определени моменти. Трябва да се има предвид, че процеса е натоварващ. Изпробвах скрипта на машина със Celeron 2,7MHz, 1GB RAM, ATA HD с 16MB cache за търсене на съвпадения в папка с 40 386 файла (какви ли не файлове от текстови бележки до филми; оказа се, че няма съвпадения) и процеса отне 20 минути. Като цяло, бих препоръчал скрипта да се изпълнява в интервал минимум 2 часа при такава бройка и вид на файловете (препоръчително - 12 часа). Това, което се опитвам да изчистя като недостатък в скрипта, е контрол на автоматичния избор на файла, който няма да се премахне. В момента скрипта си избира един от файловете по логика, която все още не мога да хвана, но в симулациите, в които го пробвах, винаги избираше един и същи файл от групата със съвпадения.

edit: Всъщност не е задължително файла, в който ще се записват съвпаденията, да се създава предварително. Ако файлът го няма, скриптът ще си го създаде, според зададената стойност на променливата $syvpadeniq.

[lastcyrol]

Хрумна ми още по-интересна идея, за съжаление, не мога да предложа реализацията и. Идеята е следната:
През определено време се стартира Програмката;
Програмката изпълнява

Примерен код

ls -laR /home/

и пъха някъде изхода. После търси редове със еднакви файлови имена. При съвпадение, проверява размера и при съвпадение проверява md5 или sha1 сумите им и чак тогава при равенство трие по-новия. Иначе нищо.
Така ми се струва, че ще става по-бързо, отколкото ако се смята сумата на всеки файл и ще може да се изпълнява по честичко. Освен това не ми изглежда точно добра идея да се пренебрегва разликата на файловото име при съвпадение на md5 сумата. Колкото и малка да е вероятността от колизия, все пак е по-голяма от нула. Никой не може да гарантира, че колизия няма да настъпи на втората проверка(да речем. Не съм достатъчно запознат, да го твърдя съвсем убедително, но знам, че ако гръм удря човек веднъж на 100 години, това не означава, че през следващите 99 години няма да се случи.).
Принципно бих написал Програмата на Java, понеже не съм запознат достатъчно от близо със bash-а, но принципно нямам време в момента. Иначе май със bash(или некоя друга люспа) ще стане най-бръзо(с по-малко писане).