Niedawno dowiedziałem się o programie o nazwie Total Commander. Jest to zamiennik Eksploratora Windows i ma własne rzeczy do kopiowania plików. Aby sprawdzić, czy pliki są identyczne, zamiast obliczać CRC, dosłownie sprawdza każdy bajt, jeden po drugim, zarówno na oryginale, jak i na kopii.
Moje pytanie brzmi: czy to konieczne? Czy CRC lub jakakolwiek inna technika może się nie udać? Czy jako programista powinieneś wdrożyć ten doskonały, ale powolny system, czy może jest on zbyt ekstremalny?
difference
file-handling
Koen027
źródło
źródło
sha1sumty, nie musisz się o to martwić, chyba że ktoś celowo i kosztownie konstruuje pliki, których sumy zderzają się. Nie mam na to źródła, ale słyszałem (w kontekście git), że prawdopodobieństwo, że dwa różne pliki mają tę samą sumę sumaryczną, jest mniej więcej takie samo, jak prawdopodobieństwo, że każdy członek zespołu programistów zostanie zjedzony przez wilki Tego samego dnia. W całkowicie niepowiązanych zdarzeniach.Odpowiedzi:
Obliczanie CRC (lub, lepiej, sum sha1) w obu plikach i tak wymaga odczytu każdego bajtu. Jeśli porównasz bajt po bajcie, możesz wyjść, gdy tylko zobaczysz niedopasowanie - i nie musisz się martwić o dwa różne pliki, które mają taką samą sumę kontrolną (choć jest to mało prawdopodobne w przypadku sha1sum) . Jeśli więc przeprowadzasz porównanie lokalnie, porównanie bajt po bajcie będzie co najmniej tak szybkie jak porównanie sumy kontrolnej (chyba że i tak już obliczyłeś sumy kontrolne).
Z drugiej strony porównania sum kontrolnych są przydatne podczas porównywania plików, które nie znajdują się na tym samym komputerze; sumy kontrolne można obliczać lokalnie i nie trzeba przesyłać całej zawartości przez sieć.
Możliwe są również podejścia hybrydowe. Na przykład możesz obliczyć i porównać sumy kontrolne dla dwóch plików po jednym kawałku, co pozwoli uniknąć odczytu całych plików ( jeśli się różnią), a jednocześnie pozwoli uniknąć przesyłania całego pliku przez sieć. Protokołem rsync robi coś takiego.
Zauważ, że użycie prostego CRC daje uczciwą szansę na kolizję, jak wspomniał Dave Rager w swojej odpowiedzi. Użyj przynajmniej sha1sum lub nawet czegoś nowszego. (Nie próbuj wynaleźć własnego algorytmu haszującego; ludzie, którzy opracowali sha1sum, wiedzą o tym dużo więcej niż każdy z nas.)
Jeśli chodzi o prawdopodobieństwo kolizji, jeśli używasz porządnego skrótu, takiego jak sha1sum, prawie nie musisz się tym martwić, chyba że ktoś celowo i kosztownie konstruuje pliki, których zderzają się sha1sum (generowanie takich kolizji nie było wykonalne, kiedy pierwszy raz to napisałem , ale poczyniono postępy ). Cytując „Pro Git” Scotta Chakona , sekcja 6.1 :
Streszczenie :
Porównanie bajtów po bajcie jest dobre dla porównań lokalnych. sha1sum jest dobry do zdalnego porównywania i nie ma znaczącej szansy na fałszywe alarmy.
źródło
Oto inny sposób, aby o tym pomyśleć.
Jeśli nie ma możliwości, że dwa różne pliki mają ten sam CRC, to przez rozszerzenie oznacza, że każdy plik może być reprezentowany przez unikalny CRC. Jeśli CRC byłby mniejszy niż oryginalny plik, reprezentowałby on formę bezstratnej kompresji. Jeśli nie, równie dobrze byłoby porównać oryginalne pliki, ponieważ porównywałbyś tę samą liczbę bajtów.
Teoretycznie możesz użyć bezstratnej kompresji obu stron porównania, aby zmniejszyć liczbę bajtów potrzebnych w porównaniu, ale jest to głupota, ponieważ marnowałbyś więcej cykli i musiałeś czytać każdy bajt obu plików, aby wykonać kompresję . Oznacza to, że aby zakodować każdy bajt (i jego kolejność) w bezstratnym schemacie kompresji, musisz najpierw go odczytać i podłączyć do algorytmu, prawda? Koniec gry.
Oto analogia:
jeśli chciałbyś szybko ustalić, czy dwa drukowane dokumenty były identyczne bez porównywania liter po literze, możesz porównać liczbę liter w każdym wierszu dokumentów. Jeśli liczone są wszystkie pasujące, szanse znacznie się poprawiają, że dokumenty są identyczne, jednak nikt nie argumentowałby, że można być pewnym, że każda litera była taka sama, stosując takie podejście.
źródło
Jedynym doskonałym sposobem sprawdzenia identycznych plików jest bajt do porównania bajtów. Innym sposobem na uczciwe zbliżenie jest obliczenie skrótu, takiego jak MD5, dla plików i ich porównanie. Możliwe, że doszło do kolizji skrótu, ale mało prawdopodobne.
Wyobrażam sobie, że bajt dla porównania bajtów byłby szybszy niż obliczanie skrótu dla obu plików w czasie, gdy robisz porównanie. Jeśli jednak aplikacja wstępnie obliczy skrót i zapisze metadane dotyczące plików, porównanie skrótów będzie znacznie szybsze.
CRC prawdopodobnie nie jest właściwą drogą, ponieważ jest to po prostu mechanizm wykrywania błędów, a nie skrót. (lub słaby skrót z dużą ilością możliwych kolizji)
źródło
Aby być w 100% pewnym, że dwa pliki są identyczne, naprawdę trzeba sprawdzić bajty.
Dlaczego? Hash kolizje, dlatego! W zależności od algorytmu używanego do mieszania, kolizja może być mniej lub bardziej prawdopodobna, ale jest jednak możliwa. Wykonując następujące kroki:
Daje ci bardzo wysoką gwarancję pewności, że oba pliki są takie same, jednak istnieje bardzo (bardzo) niewielka szansa, że masz kolizję. Wybór tego, jak daleko chcesz posunąć się w porównaniu, będzie podyktowany sytuacją.
źródło
Jak powiedzieli inni, szybsze jest porównanie bajtów po bajcie, jeśli dwa pliki są w tym samym systemie. Jeśli próbujesz porównać kilka plików, dojdziesz do punktu, w którym haszowanie jest lepszą odpowiedzią, jeśli pliki są w spinningowym magazynie.
Hashowanie naprawdę świeci, gdy nie masz wszystkich dostępnych danych. Na przykład pliki znajdują się na różnych komputerach. Pozwala także zapisać wyniki obliczeń i odwołać się do nich później. (Czy ten raport jest taki sam jak stary? Kiedy tworzysz raport, zachowujesz jego skrót. Kiedy robisz następny, możesz po prostu porównać skróty. Nie tylko nie musisz czytać starego w sobie muszę nawet mieć dostępną jego kopię.)
źródło
Myślę, że powinieneś użyć dostarczonego narzędzia porównywania plików z systemem operacyjnym lub narzędzia porównywania plików (patrz: narzędzia porównywania plików wiki ) do porównywania zawartości PO sprawdzeniu właściwości pliku opisanych przez @Glenn Nelson.
Nie sądzę, że CRC jest w 100% dokładny i myślę, że jego dokładność maleje wraz z długością pliku. Nie sugeruję też, aby pisać od zera, ponieważ może to wymagać wielu testów.
źródło
Czy trzeba czytać każdy bajt, aby sprawdzić, czy skopiowany plik jest identyczny z oryginałem? TAK, aby być w 100% pewnym
Czy trzeba czytać każdy bajt, aby sprawdzić, czy skopiowany plik NIE jest identyczny z oryginałem? NIE
Dlatego, aby szybko ustalić brak identyczności, najpierw sprawdź metadane, takie jak rozmiar pliku i jakakolwiek suma kontrolna / CRC lub MIME, które system / system plików / sklep może już utrzymywać . Ponieważ są one wstępnie obliczane przez ten system, nie płacisz tego kosztu w momencie porównania.
Jeśli ten test się powiedzie, nadal musisz porównywać każdy bajt osobno, jeśli chcesz być w 100% pewien, ALE UWAGA, że w nowoczesnych procesorach potokowych i przy użyciu wielu wątków i być może wielu procesorów / procesorów porównywanie dużych plików jest NAPRAWDĘ szybkie i wydajny, ponieważ proces jest wysoce równoległy. O wiele szybsze niż JAKIEKOLWIEK obliczenia matematyczne obejmujące każdy bajt (chociaż niektóre algorytmy są również możliwe do zrównoleglenia, ale być może nie tak łatwo lub tak dobrze). Dzieje się tak, ponieważ procesory przetwarzane potokowo mogą wykonywać operacje porównywania bloków pamięci w mikrokodzie, a nawet sprzętowo (naprawdę szybko), a podsystemy typu „dysk do pamięci” są wysoce zoptymalizowane pod kątem dostarczania ogromnych bloków plików do / z pamięci, wszystkie wykonywane równolegle i za pomocą sprzęt komputerowy. Jeśli twoja aplikacja robi takie rzeczy regularnie i jest to znane wąskie gardło wydajności, dobrze byłoby zaimplementować to w dobrze napisanym wielowątkowym kodzie, który korzysta z możliwości paralelizacji twojego systemu operacyjnego i sprzętu (być może użyj języka, który jest zaprojektowany dla to).
Tylko wtedy, gdy chcesz przetworzyć każdy plik raz i wykonać wiele porównań później (gdy pamiętasz [„pamięć podręczną”] podsumowany lub „skompresowany” [jak to określa JohnFX] wynik analizy), będzie to miało znaczącą korzyść, i nawet wtedy, aby udowodnić różnicę (prawdopodobnie); aby udowodnić identyczność, nadal musisz wykonać porównanie bajt po bajcie.
źródło