Fuzzy Hash?

[quirks]

Hm, folgendes Problem: Ich möchte die Ähnlichkeit von Dateien herausfinden, um sie als Dubletten zu kennzeichnen. Hab bis jetzt mit SHA-1 gearbeitet, aber der erwischt nur wirklich gleiche Dateien . Ich möchte so was ähnliches wie DoublePics machen, nur ohne Beschränkung auf Filetype.
Beispiel, damits deutlicher wird:
Wenn in einem MP3 die Tags nicht drin sind, aber die Audio-Information genau die gleiche ist, soll 99% Übereinstimmung als Ergebnis rauskommen.
Mein Ansatz: Die am häufigsten vorkommenden n-byte-Gruppen suchen, speichern, und dann mit denen anderer Dateien vergleichen. Wäre aber vermutlich extreeem langsam...
Irgendwelche Ideen da draußen?

[Chewie]

Zitat von quirks:

Wenn in einem MP3 die Tags nicht drin sind, aber die Audio-Information genau die gleiche ist, soll 99% Übereinstimmung als Ergebnis rauskommen.

Das Problem an Audio-Daten ist, dass Unterschiede in der Sample-Rate etc. eine total andere Dateistruktur verursachen. Speziell bei Audio-Daten bietet sich die Analyse einer Fourier-Transformation an. Such mal hier nach FFT

[quirks]

Ich glaub, ich hab mich beim Beschreiben meines Problems zu sehr auf MP3s festgeschossen.

Ich möchte damit genausogut ZIP/TXT/GIFs vergleichen können.
Aber mittlerweile hat sich das erledigt, denke ich. Ich hab nämlich noch ein bisschen bei Google rumgeschnüffelt und glaub, dass ich für jedes Format (also MP3/WAV->FFT, JPG auch ) ein eigenes Plugin basteln muss.

Ideen aber trotzdem immer noch willkommen!

[moritz]

Mehr als Bitweise vergleichen und ähnlichkeit berechnen wird dir nicht übrig beliebn. Da würde ich dir aber empfehlen mit Assembler zu arbeiten, oder sehr optimiert mit der Windows API. Da kommt es nämlich auf jede Millisekunde an.

[fiasko]

Hallo,

du könntest blockweise Hash's bilden und die vergleichen. Zum hashen würde ich tiger nehmen, der ist recht flott, geht natürlich auch jeder andere Algo.

[moritz]

Lohnt sich glaube ich nicht. Da muss er schon sehr kleine Blöcke nehmen, und dann geht die komplette Performacne flöten

[Chewie]

Zitat von quirks:

Ich möchte damit genausogut ZIP/TXT/GIFs vergleichen können.
Aber mittlerweile hat sich das erledigt, denke ich. Ich hab nämlich noch ein bisschen bei Google rumgeschnüffelt und glaub, dass ich für jedes Format (also MP3/WAV->FFT, JPG auch ) ein eigenes Plugin basteln muss.

Da führt kein Weg daran vorbei, denk ich. Die Formate sind teilweise so aufgebaut, dass ähnlicher Inhalt ein total anderes Bitmuster ezeugt. Denk z. B. mal an Prüfsummen in Archiven: Sind die Dateien zweier Archive bis auf ein Bit identisch, so ist die dazugehörige Prüfsumme dennoch total verschieden (zumindest sollte das so sein, sonst kann man sich die Prüfsumme schenken). und wenn dazu noch Metadaten wie Statistiken kommen, ist es ganz aus.