Porównywanie plików binarnych, jak to robić skutecznie

Dla specjalistów Programowanie
#1

Mam ok. 20 mln. plików (ok. 5 TB) binarnych różnej wielkości od 1 Kb do 100 Mb, jednak w 97% są to pliki których wielkość mieści się pomiędzy 1Kb a 10 MB. Co miesiąc przybywa kolejnych 2 mln. plików. Szukam pomysłu w jaki sposób je porównywać do siebie ażeby mieć prawie 100% pewność, że są identyczne i tylko wówczas je usuwać. Można oczywiście zastosować mechanizm by porównywać bajt do bajta, ale jednak nieco szybsze jest liczenie sum kontrolnych. Pytanie jakich sum kontrolnych użyć, czy powinno być to MD5 lub innych? Przy 20 mln. plików trzeba porównać każdy z każdym co daje nam 400 000 000 000 000 operacji porównań.

Gdybym chciał użyć programu EasyDuplicate, który i tak jest jednym z szybszych to porównanie tej kolekcji zajęłoby ok. 14 dni ciągłej pracy komputera.

Jaki algorytm proponujecie, w jakiej kolejności, jaką metodologię i co warto rozważyć aby przyspieszyć pracę?

Pzd.

Staszek

#2

Raczej nie ma w tym wielkiej filozofii. Najpierw skanujesz wszystkie katalogi i dla każdego znalezionego pliku zapamiętujesz wielkość, co do bajta, oraz jakiś kawałek niewielki kawałek z końca* pliku, policz sobie na ile wystarczy pamięci przy takiej ilości plików. Potem sortujesz to wszystko po rozmiarze i pliki z identycznym rozmiarem sprawdzasz każdy z każdym, po tym pobranym kawałku. Jeśli końcówka się zgadza sprawdzasz całe pliki. Nie ma mowy o liczeniu żadnych sum kontrolnych, bo to wymaga odczytania całego pliku, a to właśnie operacje dyskowe są wąskim gardłem.

*początki plików mogą być identyczne dla np. plików graficznych.

#3

Przecież żeby policzyć sumę kontrolną musisz odczytać wszystkie bajty z pliku. A żeby porównać dwa pliki nie musisz tego robić.

Nie.

Przecież jeśli pliki mają różne rozmiary, to siłą rzeczy nie mogą być identyczne. Przypadków, w których dwa pliki mają dokładnie ten sam rozmiar jest w zasadzie niewiele. Myślę, że takie sprawdzenie pozwoli odrzucić zdecydowaną większość kombinacji.

A następnie nie ma innego wyjścia niż sprawdzać plik bajt po bajcie, jeśli w którymś miejscu się nie zgodzą, to już wiadomo, że to nie jest ten sam plik. Jedynie pliki identyczne zostaną przeczytane w całości.

Pisząc sprawdzać bajt po bajcie mam oczywiście na myśli operację w pamięci programu. Nie wolno odczytywać plików z dysku po bajcie, bo jest to bardzo niewydajne, trzeba wczytać np. 1MB, sprawdzić go, jeśli wszystko się zgadza, to odczytać następny.

BTW - http://www.skcleaner.somekind.pl - to jest program mojego autorstwa, który to właśnie robi i jest raczej szybki.

#4

No tak, po co porównywać pliki, które są różnych rozmiarów. Zbiorów plików powtarzających się będzie zdecydowanie mniej (choć też nie mało). Ilość operacji porównywania zmniejszy się w zdecydowany sposób.

Sprawdzę dziś Twój skaner do porównywania plików, a raczej porównam go do tego czego teraz używam i napiszę jak sobie poradził na dużych zbirach.

– Dodane 19.09.2010 (N) 0:02 –

do Somekind…

Zainstalowałem Twój skcleaner i pochwała za to, że nie marnuje zasobów przy skanowaniu, nie wyświetla zbędnych bajerów itp., oczywiście niektórym może to przeszkadzać, bo powiedzą że nie widać co się dzieje (jednak jest pasek działania i widać że nie wisi), oczywiście jakby chociaż pasek % wykonania był widoczny, możnaby oszacować gdzie jesteśmy i czas. Ale mniejsza o szczegóły.

Powiedz jaki algorytm został użyty? Czy tak jak Pisałeś bajt po bajcie?

Testowałem go na 95 589 plikach umieszczonych w 2 351 folderach i porównał mi pliki (nie wiem ile znalazł, bo nie podaje tej wartości na końcu - a wartoby było) w 21 minut i 40 sekund. Znany i uznawany za najwydajniejszy program Easy Duplicate Finder zrobił to w 24 minuty i 7 sekund.

Wszystko wyglądałoby pięknie, gdyby nie fakt, że Twój soft znalazł 21 duplikaty, a EDF 73. Sprawdziłem to zatem jeszcze dwoma innymi wolniejszymi programami i zawsze wynik liczby duplikatów był 73. Nadmienię iż nie był to dysk systemowy, tylko katalog na innym dysku, bez ukrytych plików i folderów.

Co może być powodem takiej różnicy w Twoim sofcie? Zapewne gdzieś jest błąd i czegoś nie porównuje. Jakbyś chciał znać więcej szczegółów to pytaj.

Jednak brawo za szybkość, jeżeli jeszcze nie będzie popełniał błędów przy zachowaniu czasu to…

Daj znać.