Forum: Jämföra 2 filer?

Forum huvudsida -> Programmering -> Jämföra 2 filer?

Sidor: 1

Till botten

Dread 19:24 - 10:e Oktober 2007 | Post #1
Medlem
Inlägg: 135


Skicka PM 		Jag tänkte snickra ihop ett program som jämför alla filer på en hårdisk med alla filer på en annan hårdisk, och ifall där finns en kopia så raderas den ena på vald hårdisk. Frågan är hur jag ska kunna jämföra dem på ett effektivt sätt?

Jag tänkte mig en "fullscan" och en "smartscan", fullscan jämför varenda fil med alla filer på andra hårdisken. Smartscan skulle då först scanna efter fil-namns kopior, och sedan jämföra eventuella filer med lika namn med varandra, är dem då lika så ska den ena "kopian" raderas.

Men då behöver jag fortfarande dels en sökmotor, och dels en jämförelse algoritm. En kompis snackade om en algoritm som nästan aldrig ger samma värde om inte filerna är lika (har för mig att det kom på tal i samband med ubuntu live-cdn, när den kollar ifall skivan är korrekt). Kommer inte ihåg vad det sättet heter, men tycker det låter som ett smidigt sätt att jämföra filer.

Fast vet inte hur jag ska gå till väga, är ganska säker på att "fullscan" inte kommer att funka, eller snarare kommer att ta år att köra, så därför är det kanske bättre att "bara" koda ihop smart-scan?
iofs om jag använder "jämförelse-algoritmen" så borde det inte ta så lång tid bara att koppla ett visst nummer till en viss fil och sen jämföra alla nummer.

Hur som helst tror ni "jämförelse-algoritmen" kommera att funka, och kan någon vara vänlig att upplysa mig om namnet?

-------------------------
c++


ozamosi 20:44 - 10:e Oktober 2007 | Post #2
Administratör
Inlägg: 1129


Skicka PM 		Ubuntu-skivor använder en md5-hash för att kontrollera att skivan inte är skadad.

En hash är i praktiken en form av extremt destruktiv komprimering. Eftersom den är destruktiv kan man inte vara HELT säker på att det är olika filer - en md5-hash är på 128 bitar, vilket ger 2**128 olika hashar. Det är en ganska så liten siffra (liten och liten... 340 282 366 920 938 463 463 374 607 431 768 211 456 eller 3.4*10**38 - ganska stor är den allt) , jämfört med antalet möjliga filer, som ju är oändligt. Dock, när någon för ca en månad sedan gjorde en undersökning bland de ca 20 000 paketen som finns i Debians förråd (de Ubuntus är baserade på) så finns det inte ett enda paket som ger samma md5-summa som något annat paket - sannolikheten för att krockar ska inträffa är med andra ord små, även om de existerar.

Det finns många typer av hashar, varav md5 är en av de populärare. Efter att man ett par gånger har hittat sätt att generera filer med samma hash som en annan fil är md5 en hashtyp som säkerhetsexperter rekomenderar att man låter bli att använda - huruvida du tror att det är ett problem får du själv avgöra (kommer någon försöka trycka in filer med identisk hash, men med annat innehåll?). Eftersom hashar är mindre än själva filerna finns det Alltid en risk för kollisioner, oavsett hashtyp. Dock är den Liten.

En personlig hypotes, som förmodligen är felaktig, är att man kan eliminera många potentiella kollisioner genom att jämföra filstorlek - om filerna både är exakt lika stora och har samma hash borde sannolikheten för att det är kollisioner raskt minska ofantligt mycket. Om inte annat brukar det gå snabbare att fråga operativsystemet om filstorleken, jämfört med att läsa in hela filen, köra en hash-algoritm på den, läsa in den andra filen, köra en hash-algoritm på den, och sedan jämföra. På min lagom välutrustade laptop, som dock har en vanlig, långsam laptopdisk, tar det en minut och tio sekunder (tog nyss iaf) att ta fram md5-summan för en 700mb iso. Jag är inte säker på hur tiden för att ta fram md5-summor växer, men med tanke på att algoritmen arbetar i 512-bytes-chunks (enligt wikipedia) borde den vara väsentligen linjär - alltså borde det ta nästan 1 000 minuter att md5-summa en 500GB-disk. stat kan å andra sidan ta fram filstorlekar på ett helt gäng iso:s (eller andra filer) på under en sekund. Det bör alltså kunna ge rejäla tidssparningar att börja med storlekar och bara undersöka checksums om flera filer är lika stora - speciellt med tanke på att större filer som inte är scene-releasade rar-filer mycket sällan är Exakt lika stora.

Vill man vara extra super-anal med att se till att inga filer som inte är olika får samma hashar kan man alltid använda två olika hashalgoritmer.

Edit: wikipedia vet mer: http://en.wikipedia.org/wiki/Md5

-------------------------
Ljusblå

Senast redigerad 20:57 - 10:e Oktober 2007


Dread 23:19 - 10:e Oktober 2007 | Post #3
Medlem
Inlägg: 135


Skicka PM 		Jo, det stämmer nog att det är effektivare att jämföra namn och filstorlek först, och sedan köra checksum om det behövs. eventuellt att man kan spara en lista med samma namn, men olika filstorlekar också (torde inte bli för lång).

Läste igenom wikipedia artikeln, var ganska intressant, har dock problem med att tolka pseudokoden.

Hittade ett sourceforge project för hash-ning, Hash-Calculator. Blir till att kolla hur dem har byggt upp funktionerna för att få det fungera.

-------------------------
c++

Senast redigerad 23:19 - 10:e Oktober 2007


FunkyChicken 23:20 - 10:e Oktober 2007 | Post #4
Nyhetsredaktör
Inlägg: 800


Skicka PM 		Att räkna ut hashar för varje fil är endast motiverat om du tänker dig att spara undan checksummorna i nån databas för framtida bruk och hoppas att filerna inte ändras på. (Förutsatt att filerna har samma namn då alltså, om du ska jämföra alla filer med alla så måste de förstås hashas först. Det finns nog färdiga md5-algoritmer till de flesta språk, helst ska du ju ha nån tokoptimerad färdigkompilerad lågnivåkod.)
Annars är det ju bättre att jämföra filerna direkt, dvs kolla om innehållet är likadant.
Om du vill ha upp hastigheten kan du ju fula lite och först kolla storlek som ozamosi sa och sedan sampla några random kb på olika platser i filerna (med motiveringen att många filer har tex likadana headers, så det är dumt att börja från början).

För övrigt:
1) Om du håller på med något högnivåspråk finns det garanterat redan färdiga funktioner för att jämför två filer på hårddisken (men de är väl inte särskilt snabba kanske).
2) Kolla om du inte kan åstadkomma det du vill med nåt magiskt shellskript med rsync på nåt vis (har för mig man kan köra rsync så att den bara rapporterar skillnader/likheter i filsystemen, sen kan man kanske awk:a fram nån användbar info ur det och radera de filer som var samma... hänvisar till närmsta *nix-geek för mer info).


Independence 09:43 - 11:a Oktober 2007 | Post #5
Administratör
Inlägg: 1800


Skicka PM 		Har man tillgång till rsync känns hela poängen med det här programmet förlorat redan från börjanSmiley

-------------------------

Vi är riddarna som säger fiskbulle!


FunkyChicken 22:08 - 11:a Oktober 2007 | Post #6
Nyhetsredaktör
Inlägg: 800


Skicka PM 		just min poäng


Sidor: 1

Forum huvudsida -> Programmering -> Jämföra 2 filer?
Atom feed

Du får inte posta i den här tråden | Till toppen