23. juni 2001 - 10:57Der er
28 kommentarer og 2 løsninger
Checksumme af binære filer og sandsynligheder
Hej alle sammen,
Antag, at man har to filer, som man gerne vil undersøge om de er ens - så kunne man selvfølgelig bare sammenligne dem - har man derimod 200000 (læs: rigtigt mange) filer er denne løsning ikke holdbar.
Derfor ville jeg gerne have en mulighed for at lave en eller anden checksum af filerne og så sammenligne checksummerne.
Er der nogle algoritmer/matematiske udregninger, der siger noget om, at hvis man udregner en checksum sådan eller sådan, så er der f.eks. 90% sandsynlighed for, at to filer er ens, hvis deres checksum er ens?
Du skal ikke regne med sandsynlighed her.... Lav en checksum på filerne, og hvis checksummerne er foreskellige er filerne 100% sikkert forskellige.
Har du 2 med ens checksummer, så løber du de filer igennem, for at se om de er ens. Det er overkommeligt, for det sker kun hvis de faktisk er ens, og så med 0.0000001% (note) sandsynlighed hvis de er forskellige.
Det er direkte i propotion med længden af checksummen. dvs med en 16bit CRC check er der en 1/64K risiko for at filerne ikke er ens. Hvis du sammenligner på fillængde også er det ganske pænt.
Om det er brugbart afhænger så af hvor forfærdeligt det er hvis testen giver galt resultat :)
Du har sådan set ret - men nu er jeg tilfældigvis interesseret i at opnå en mulighed for at beregne sandsynligheden for om filerne er ens, når checksummerne er ens. Jeg er ikke kun interesseret i bare at finde ud af om de er ens, for så ville jeg også bruge din fremgangsmåde.
Jakoba: Du har ganske givet ret i, at længden af checksummen har noget at sige - men har filen som checksummen ikke også en indflydelse på sandsynligheden???
CRC checksummer er \"lavet\" til datatransmission, hvor man også kigger på sandsynligheden for at fange/opdage små klumper af fejl. Når du bare siger filer, og de ellers ikke indholdsmæssigt har noget med hinanden at gøre på bitniveau, så er det længden af checksummen, der er afgørende, som vores gode ven jakoba, så korrekt anfører.
Mit Delphiprogram \"snød\". Af effektivitetshensyn tog det kun den første 1k af filen og længden, og beregnede vist kun en xor-checksum. Dem der så var ens blev checket igennem. Så kunne jeg ret nemt finde dubletter på min harddisk.
Tja, men typisk har man jo netop i datatransmission en fast bloklængde hvoraf man tager checksummen, hvorfor det selvfølgeligt kun er checksummens længde, der er afgørende, ikke??
Rent logisk må f.eks. en 16 bit checksum af en 1K fil være mere \"præcis\" end af en 2K fil.
Det jeg savner er en metode til at beregne sandsynligheden for om de to filer er ens, når checksummerne er ens - hvilket selvfølgelig afhænger af checksumstypen, hvorfor en specifik checksumsmetode også er et godt svar :-)
e.j./jakoba:> Det der med CRC checksummer .. nu har jeg ikke læst SÅ meget om det, ej heller brugt det særligt meget (kun een gang i et VB program), men hvis du har en 32bits CRC checksum på en fil, så vil der da aldrig være en anden, forskellig, fil der har den samme checksum!?
Er det ikke det der er hele meningen med et CRC check - at se om en fil er blevet ændret ?
Jo, tdaugaard, der *vil* være milliarder af andre filer med samme checksum. Bare usandsynligt de vil findes på din maskine. Men seriøst - det er grove usandsynligt at det skulle ske, men det kan ske.
Almindelige mennesker forstår ikke sandsynlighed. Se bare hvor mange, der spiller lotto...
Jo, men hvis det skal være 100% matematisk sikkert skal checksummen være ligeså lang som selve filen. + det skal en ekstra checksum på (ligesålang) for at sikre der ikke er en fejl i den første checksum. + en checksum-3 for at sikre checksum-2. osv. osv. :-)). I den virkelige verden kan man aldrig være HELT sikker.
Jeg læste engang i en populærbog om relativitet at en gang i fantasillioner af fantasillioner af gange hvor man slap en sten ville stenen falde opad istedet for nedad. Det KAN ske.
men det er ikke ret sandsynligt af det sker for en af os :)
jakoba:> Læste du at en sten KAN falde opad en gang ud af en frygteligt masse gange ? Oookay .. og hvordan forklarede bogen så det ? Det kunne være sjovt at vide ..
Stenen er ikke EEN sten. der er en grusom masse individueller atomer og elektroner og kvarker osv osv, og hvis de nu allesammen \"tilfældigvis\" zigger igstedet for at zagge på et givet tispunkt så gør stenen noget uventet.
Nu jeg tænker lidt nærmere over det - så har du selvfølgeligt ret i, at sandsynligheden er den samme, uanset fillængden - det var lige det med procentregningen, der smuttede :-/
Så nu mangler vi bare at få leveret en eller anden checksums/CRC-algoritme og lidt matematik, så vil jeg være tilfreds.
Forøvrigt lidt morsomt med den sten - håber jeg er der, den dag det sker ;-)
Har det mon forøvrigt noget at gøre med, at den ene sok så tit forsvinder i vasken??? :-)
Tilladte BB-code-tags: [b]fed[/b] [i]kursiv[/i] [u]understreget[/u] Web- og emailadresser omdannes automatisk til links. Der sættes "nofollow" på alle links.
