Willkommen bei Entwickler-Forum.
Seite 1 von 2 1 2 LetzteLetzte
Ergebnis 1 bis 10 von 19
  1. #1
    Aufsteiger
    Registriert seit
    23.11.2014
    Beiträge
    56

    Standard Dateien inhaltlich vergleichen

    Moin Leute,

    ich möchte Dateien inhaltlich vergleichen, um so vllt eine nur 90%ige Übereinstimmung zu ermitteln. Hierfür schiebe ich die jeweiligen Byteblöcke einer Datei über andere Ähnliche Dateien. Bei den Tests mit simplen kurzen .txt-Dateien klappt das wunderbar. Wenn ich jetzt aber eine .pdf-Datei mit einer .docx-Datei vergleiche, die vom Text und Format identisch sind, denn erhalte ich nicht mal eine 1%ige Übereinstimmung.

    Das Speichern der Byteblöcke habe ich wie folgt geregelt:
    Code C:
    byte[] pufferNextFile = new byte[byteStep];
     
    using (BinaryReader breaderCurrentFile = new BinaryReader(new FileStream(nextFile.FullName, FileMode.Open)))
    {
        breaderCurrentFile.BaseStream.Seek(positionNextFile, SeekOrigin.Begin);
        breaderCurrentFile.Read(pufferNextFile, 0, pufferNextFile.Length);
    }

    Wenn ich mir den Text-Inhalt beider Dateien nun mit Hilfe von ASCIIEncoding().GetString(pufferNextFile) anschaue, denn wird auch nirgendwo ein leserlicher string erkenntlich. Woran kann das liegen? Werden die bytes aufgrund der unterschiedlichen Dateitypen wirklich komplett anders hinterlegt? Denn müsste ich mir ja wahrscheinlich für jedes Dokument eine weitere Bibliothek zulegen (wie zB https://www.codeproject.com/Articles...m-PDF-in-C-NET). Oder habe ich falsch entwickelt?

    Der Algorithmus ist ziemlich komplex, deswegen lasse ich ihn erst mal außen vor. Falls er für die Frage doch noch relevant sein sollte, füge ich ihn mit samt der anderen Klassen hinzu.

    VG

  2. #2
    Forenheld
    Registriert seit
    26.02.2003
    Beiträge
    16.093

    Standard

    Wie kommst du auf die Idee, dass eine *.pdf mit einer *.docx Datei in irgendeiner Form identisch sein könnte?

    Warum sollte man Binärdateien mit ASCII vergleichen?

    Die Dateien könnten kodiert sein, verschlüsselt sein, oder die Bytes liegen in einem Codeschema vor (bsp. UTF-8,16 o.a.).
    Die unterschiedlichen Anwendungen, werden auch die Daten in unterschiedlichen Formaten speichern.
    Wenn bsp. zu jedem geschriebenen Buchstaben/Buchstabenblock vorab die Formatdaten liegen, wirst du keinen Text erkennen können.

    Diese Art des Vorgehens würde ich überdenken.
    Geändert von Christian Marquardt (22.12.2016 um 07:13 Uhr)
    Christian

  3. #3
    Zaungast
    Registriert seit
    03.06.2016
    Beiträge
    23

    Standard

    Wie mein Vorredner andeutete:
    .TXT liegen "plain" - also Kalrtext - auf der Platte.

    Bei anderen Dateiarten ist der Inhalt in irgendeiner Form codiert. Es liegt ja nicht nur der Text vor, sondern auch Formatierungsinformationen, Seiteninformationen, Meta Daten (Autor, ..) etc. Als Beispiel einfach mal eine .docx nehmen und zu "zip" umbennen und dann mal reinsehen. Hier sieht man sehr schön, was alles abgespeichert wird. ACHTUNG! Der "Trick" geht nur bei bestimmten Dateien! Andere Formate werden anders abgespeichert - je nachdem, was sich der Hersteller gedacht hat. Anderer Tip: öffne mal ein PDF in Notepad. Da sieht man teilweise Anweisungen. Noch ein Tip: öffne mal verschiedene Dateien in Notepad (oder besser: In einem Hex-Editor) uns sieh dir die ersten paar Zeichen an (und dann google mal nach "Magic Numbers"). Vergleich spaßeshalber mal die ersten beiden Zeichen von .EXE und .DLL -> ja, das sind die gleichen Dateitypen!

    Zum Thema: Da - von TXT Dateien abgesehen - die Dateien nicht als Klartext abliegen, sondern in irgendeiner Form codiert sind, kann man nicht so naiv die Texte laden. Es kann durchaus sein, dass zwei verschiedene Speicherungen hintereinander eine (binär) komplett andere Datei ergeben! Wenn du also ein Textvergleich machen willst, musst Du vorher die Datei entsprechend dem Format laden und den Text extrahieren. Entweder findest du Bibliotheken die das können (wie schon bei dem einen Link), oder du implementierst das selber. Letzeres ist harte Kost (zumal die Dokumentation zu .docx Dateien wohl einige Tausend Seiten umfasst und nicht vollständig geklärt ist. Und dass es eine Dokumentation gibt liegt daran, dass MS das Dateiformat Standardisieren will / wollte (wie ist da eigentlich der Stand?) um den OpenDocument Format (.od?) Konkurrenz zu machen. Es gibt für viele Formate schlicht keine Dokumentation).

    Viel Erfolg bei dem Vorhaben! Auch ich arbeite z.Zt. an einem Projekt, bei dem andere Leute mir den Scheibenwischer zeigen... :-)

  4. #4
    Stammgast
    Registriert seit
    24.10.2011
    Beiträge
    1.175

    Standard

    Zitat Zitat von Ralph Erdt (2) Beitrag anzeigen
    Wie mein Vorredner andeutete:
    .TXT liegen "plain" - also Kalrtext - auf der Platte.
    Auch "Klartext" ist codiert. Wobei der Unterschied mit bloßem Auge tw. kaum zu erkennen ist, aber verschieden codierte Dateien (also binär unterschiedlich) zum gleichen Anzeigetext führen können.

    Man ist (hier in D) wahrscheinlich daran gewöhnt, ASCII oder eine 8 Bit Erweiterung davon als "Urzustand" eines Textes wahrzunehmen. In Amerika reicht etwas weniger eben der 7er Code und die Chinesen können das kaum gebrauchen.
    Gruß, defo

  5. #5
    Zaungast
    Registriert seit
    03.06.2016
    Beiträge
    23

    Standard

    Zitat Zitat von defo Beitrag anzeigen
    Auch "Klartext" ist codiert. Wobei der Unterschied mit bloßem Auge tw. kaum zu erkennen ist, aber verschieden codierte Dateien (also binär unterschiedlich) zum gleichen Anzeigetext führen können.
    ASCII, ANSI, CP437, CP850, CP1252, CP1000, ISO-8859-1, ISO-8859-15, UTF16, UTF32, UTF8, ...
    Nur um die wichtigsten zu nennen, mit denen ich mich schon aktiv rumschlagen musste. Da ich anhand der Frage annehme, dass der OP noch am Anfang seiner Informatik-Karriere steht, habe ich mal den Teil übersprungen und etwas "Grundlagen" erläutert.

    @OP: Was wir gerade diskutieren:
    Eine Computer kennt nur Zahlen. Text im dem Sinne kennt ein Computer nicht! Aber um von Zahlen zu Text zu kommen (ganz platt ausgedrückt) gibt es Listen, welche Zahl welches Bild (!!) erzeugen soll. Ein Computer geht also nur hin und setzt dann entsprechende Bilder auf dem Monitor. Und es gibt zig unterschiedliche Listen (siehe meine kleine Aufzählung oben).
    Zum besseren Verständnis eine kurze Historie (@Geeks: Wenn ich Fehler mache, bitte korrigieren!):
    Historisch hat sich irgendwann rausgebildet, dass ein Byte 8 Bit sind (ursprüngliche Fernschreiber (18xx) haben noch mit 6 Bit gearbeitet!). Anfang hatte man aber ein Bit als Sicherheit definiert (Parity Bit), so dass man 7 Bit = 128 Zahlen (0-127) hatte. Somit konnte man 128 Zeichen definieren. Anfang hatte jede Firma seine eigenen Zeichen definiert. Dann wurde der ASCII Code definiert. 0-31 waren Steuerzeichen (z.B. 'neue Zeile' (line feed), 'Wagenrücklauf' (carrige return)). Darüber kamen die Zahlen, Buchstaben, Satzzeichen und einige graphische Elemente.
    Später war der Speicher so gut, dass man kein Sicherheitsbit mehr brauchte. Dadurch hatte man doppelt so viel Zahlen / Zeichen zur Verfügung: 2^8 = 256 Zahlen / Zeichen. Im ANSI Code wurden der obere (neue) Bereich hauptsächlich mit graphischen Schnick/Schnack gefüllt.

    Aber es hatten schon lange die Länder mit Sprachen, die zwar vom Lateinischen kommen aber erweitert wurden Probleme mit ASCII/ANSI. Deren 'Sonderzeichen' kamen in dem Code nicht vor. Z.B. im deutschen die Umlaute (äöüÄÖÜ) (Das 'Esszet' (ß) wurde mit dem griechischen Beta Zeichen umgesetzt). Daher haben die Informatiker in diesen Ländern einfach einige Zeichen im oberen Bereich umdefiniert. Also neues Bild für die Zahl.

    VGA Karten, die damals aktuell waren, haben es erlaubt, dass man die Bilder dynamisch ändern konnte (hatte ich damals für ein Spiel genutzt!). MS-DOS konnte daher unterschiedliche "Codepages" für die unterschiedlichen Länder laden. (CP437, CP850 für Deutschland - unterschied war IMHO das 'ß'. Wie genau, weiß ich jetzt nicht mehr). Windows (3.x) hatte dann die CP1252 verwendet.

    Irgendwann wurden dann verschiedene Codepages ISO standardisiert (8859). Diese wurden dann im dem aufkommenden Internet verwendet, indem man am Anfang der Web Seite geschrieben hat, in welcher Codepage die Seite ist, so dass der Browser die verschiedenen "Bilder" nutzen konnte. Wichtigste (für uns): -1 für Latin1 (Westeuropa) und später -15 (Latein 1 mit Euro-Symbol).

    Da es aber krampfig ist, für jede Webseite einen anderen Bilderset zu haben, hat sich ein Gremium/Konsortium gebildet, welches ALLE Zeichen auf der Welt in einem Zeichensatz vereinigen wollte (Englisch, Europäische Zusatzzeichen, kyrillisch, griechisch, chinesisch, etc.): Unicode. Dafür hat man dann gesagt, wir nehmen 2 Byte (16 Bit) pro Zeichen und hat munter definiert (UTF-16). Leider hat das nicht ausgereicht, so dass man a) UTF-32 (4 Byte pro Zeichen) definiert hat und b) UTF-16 umdefiniert hat, so dass es nun variable Länge hat und so auch alle Zeichen speichern kann. Und bei dem Schwachsinn (persönliche Meinung) den die da aktuell noch hinzufügen, wird das auch nicht reichen.

    Problem für uns Europäer: 4 (2) Byte für Text, wo 99,9..% des Textes nur Ein Byte braucht und der Rest der Byte Null ist: Platzverschwendung hoch vier. Daher hatte man UTF-8 definiert, bei dem die Anzahl der Zeichen dynamisch ist. Aber DAS zu erklären führt hier und jetzt zu weit.

    State of the Art ist bei Windows UTF-16 (Wide Character). Moderne FS in Linux etc. nutzen UTF-8.

    Dies ist nur eine sehr kurze und stark unvollständige Übersicht. Unicode für sich ist weitere "Übersichten" wert..

    Was bleibt für Dich (den OP) zu beachten: Erstmal nichts. Mach einfach weiter wie gehabt. Wenn du später Probleme mit Umlauten bekommst (die werden falsch dargestellt), dann lohnt sich da weiterdenken.


    Edit:
    * "Parity Bit" eingefügt - ist mir jetzt eingefallen
    * Codepagenummern nach Hinweisen von Wernfried korrigiert. Danke. "Dies ist nur eine sehr kurze und stark unvollständige Übersicht. Unicode für sich ist weitere "Übersichten" wert.." eingebaut
    * UTF-16 längenvariabel eingebaut.
    Geändert von Ralph Erdt (2) (11.01.2017 um 14:31 Uhr) Grund: "Parity Bit" eingefügt - ist mir jetzt eingefallen

  6. #6
    Forenheld
    Registriert seit
    26.02.2003
    Beiträge
    16.093

    Standard

    Was bleibt für Dich (den OP) zu beachten: Erstmal nichts.Mach einfach weiter wie gehabt.
    ??
    Das sicherlich nicht. Das Vorgehen Inhalte von Binärformaten per ASCII vergleichen zu wollen ist.....wenig sinnvoll. Zumal zu der Zeichsatzproblematik die Problematik des Formates kommt.

    Des Weiteren wäre es interessant zu wissen, warum nun ein *.doc mit einem *.pdf verglichen werden muss. Warum hat da offenbar jemand (oder mehrere?) einmal ein Worddokument und ein identisches PDF-Dokument zu Fuß erzeugt ohne eines von andern erzeugen zu lassen (PDF-Druck).
    Christian

  7. #7
    Zaungast
    Registriert seit
    03.06.2016
    Beiträge
    23

    Standard

    Zitat Zitat von Christian Marquardt Beitrag anzeigen
    ??
    Das sicherlich nicht. Das Vorgehen Inhalte von Binärformaten per ASCII vergleichen zu wollen ist.....wenig sinnvoll. Zumal zu der Zeichsatzproblematik die Problematik des Formates kommt.
    Wegen Binärformat hatte ich ja vorher was geschrieben. Und selbst wenn es unterschiedliche Codierungen sind (was mit guten Libs eigentlich einstellbar ist) - so ist das IMHO erstmal ein untergeordnetes Problem. Erstmal muss man an den Plain-Text kommen. Wenn das geschafft ist, dann sollte man schon was machen können (zumal er ja nur einen Fuzzy Vergleich machen will, bei dem die Sonderzeichen nur wenige Prozent ausmachen sollten).

    Zitat Zitat von Christian Marquardt Beitrag anzeigen
    Des Weiteren wäre es interessant zu wissen, warum nun ein *.doc mit einem *.pdf verglichen werden muss. Warum hat da offenbar jemand (oder mehrere?) einmal ein Worddokument und ein identisches PDF-Dokument zu Fuß erzeugt ohne eines von andern erzeugen zu lassen (PDF-Druck).
    Sorry, aber ich HASSE Motivationsfragen! Sicherlich kann man über andere Wege diskutieren wenn man die Motivation wüsste, aber er hat sich sicherlich überlegt, warum er es so machen will - auch wenn die Antwort nur "lernen" heißt. Er hat mit seiner Frage IMHO Verständnisprobleme in der konkreten technischen Umsetzung (wie andere das machen) gezeigt, und daher kann man meines Erachtens ruhig mal etwas den Erklärbär machen (ich hoffe, ich habe das brauchbar gemacht?). In meinen Anfangszeiten hatte ich auch häufig so hilfreiche Antworten wie "Wieso willst Du das machen?" anstatt "Das geht so nicht, versuch mal den Weg X.". Die Diskussionen waren unsinnig und nur bremsend. Aus diesem Grund handel ich so.

  8. #8
    Forenheld
    Registriert seit
    26.02.2003
    Beiträge
    16.093

    Standard

    Zitat Zitat von Ralph Erdt (2) Beitrag anzeigen
    Wegen Binärformat hatte ich ja vorher was geschrieben. Und selbst wenn es unterschiedliche Codierungen sind (was mit guten Libs eigentlich einstellbar ist) - so ist das IMHO erstmal ein untergeordnetes Problem. Erstmal muss man an den Plain-Text kommen. Wenn das geschafft ist, dann sollte man schon was machen können (zumal er ja nur einen Fuzzy Vergleich machen will, bei dem die Sonderzeichen nur wenige Prozent ausmachen sollten).


    Sorry, aber ich HASSE Motivationsfragen! Sicherlich kann man über andere Wege diskutieren wenn man die Motivation wüsste, aber er hat sich sicherlich überlegt, warum er es so machen will - auch wenn die Antwort nur "lernen" heißt. Er hat mit seiner Frage IMHO Verständnisprobleme in der konkreten technischen Umsetzung (wie andere das machen) gezeigt, und daher kann man meines Erachtens ruhig mal etwas den Erklärbär machen (ich hoffe, ich habe das brauchbar gemacht?). In meinen Anfangszeiten hatte ich auch häufig so hilfreiche Antworten wie "Wieso willst Du das machen?" anstatt "Das geht so nicht, versuch mal den Weg X.". Die Diskussionen waren unsinnig und nur bremsend. Aus diesem Grund handel ich so.
    Nein, das ist kein untergeordnetes Problem. Im Gegenteil es kommt noch vor dem Codierungsproblem. Was nützt mir das ev. gelöste Codierungsroblem, wenn ich den Aufbau der Binärdatei nicht verstehe.

    Tja, wenn man natürlich nicht diskutieren will, ob es nicht bessere oder einfachere Werkzeuge oder Frameworks gibt...dann mal los. Da geht es nach dem Motto "Warum einfach, wenn es auch kompliziert geht"

    Hmm, warum gibt es wohl entsprechende Objekte unter MS um auf Word Excel usw. zugreifen zu können?

    Warum gibt es Libs. die einem aus einem PDF-Dokumenet den reinen Text liefern?

    Was könnte man dann vergleichen?


    Es gibt sinnvolle Vorgehenweisen und auch weniger sinnvolle Vorgehensweisen. Und bei letzterem dürfte doch wohl die Frage erlaubt sein, warum so vorgegangen wird.
    Geändert von Christian Marquardt (23.12.2016 um 17:19 Uhr)
    Christian

  9. #9
    Aufsteiger
    Registriert seit
    23.11.2014
    Beiträge
    56

    Standard

    Hallo Leute,

    vielen Dank für eure vielen tollen Anregungen! Es tut mir auch leid, dass es hier nun zu Missverständnissen kam!

    Ich muss Christian Marquardt an dieser Stelle leider Recht geben. Mein Ziel ist es primär nicht gewesen, unterschiedliche Codierungen miteinander zu vergleichen. Das war wohl ein blöder Ausrutscher von mir, das hätte ich wissen müssen.. Trotzdem ist der Exkurs von Ralph Erdt sehr interessant gewesen. Spannend fande ich vor allem auch dass Windows die Dateien mit samt ihren Metadaten archiviert vorlegt. Aber das ist wohl nun auch ein anderes Thema..

    Ich bin mittlerweile immer noch dabei Dateien (diesmal mit gleicher Codierung) miteinander zu vergleichen. Bei sehr kleinen Textdateien verläuft alles reibungslos, aber sobald es an die 2000Bytes ran geht, tauchen schon die Probleme auf.

    Mein erster Feldversuch war es, 10% der Datei als Byteblock zu nehmen und diesen byteweise über eine zweite Datei zu schieben. Sollte keine Gleichheit vorhanden sein, so wird der Byteblock aus Datei 1 ein Byte weiter gesetzt und wieder über Datei 2 geschoben:

    http://fs5.directupload.net/images/161225/keruq7vj.png

    Im worst case bei einer 2000Byte-Datei (und Byteblöcken von 25%) dauert das über 2 Minuten.. Klar, es wird ja auch über zwei Millionen mal verglichen:
    (Dateigröße – Byteblockgröße * Dateigröße – Byteblockgröße) = (2000 – 500) * (2000 - 500) = ~2,3 Mio.

    Für nur 1,95KB könnt ihr euch mein Entsetzen sicher vorstellen. Darum habe ich mir eine andere Strategie ausgedacht: ich zerstückel die erste Datei wieder byteweise in Byteblöcke, packe diese nun aber verschlüsselt in eine MD5-Liste. Jetzt durchlaufe ich die zweite Datei byteweise und schaue, ob der Byteblock der zweiten Datei in MD5-verschlüsselter Form in der MD5-Liste der ersten Datei liegt. Bei 2000Bytes geht das nun innerhalb einer halben Sekunde. Juhu! Habe ich mich gefreut! Doch wenn ich nun statt der zuvorrigen 1,95KB-Datei die Größe erhöhe auf 600KB, dann dauert allein das Einlesen und Verschlüsseln der Datei über 2 Minuten:

    Code C:
    FileInfo currentFile = new FileInfo(@"C:/test.txt");
    int positionCurrentFile = 0;
    int byteStep = (int)((currentFile.Length * 25) / 100); //25% der aktuellen Dateilänge
    MD5 md5 = new MD5CryptoServiceProvider();
    List<byte[]> md5s = new List<byte[]>();
     
    //So lange Byte in aktueller Datei vorhanden
    while (((positionCurrentFile + byteStep) < currentFile.Length))
    {
        byte[] pufferCurrentFile = new byte[byteStep];
     
        //Byteblock aus aktueller Datei in byteArray "pufferCurrentFile" zwischenspeichern
        using (BinaryReader breaderCurrentFile = new BinaryReader(new FileStream(currentFile.FullName, FileMode.Open)))
        {
            breaderCurrentFile.BaseStream.Seek(positionCurrentFile, SeekOrigin.Begin);
            breaderCurrentFile.Read(pufferCurrentFile, 0, pufferCurrentFile.Length);
        }
     
        //Bytearray als md5 in Liste speichern
        md5s.Add(md5.ComputeHash(pufferCurrentFile));
        positionCurrentFile++;
    }

    Einerseits verständlich. Ich führe für 600KB wieder 614.400 Operationen(Bytepositionierung, Zwischenspeichern, Verschlüsseln) durch... Mein Ansatz wäre nun, die Byteblöcke nicht byteweise zu verschieben, sondern die Schrittweise auf Basis der Dateigröße anzupassen. Das heißt, ich springe nicht 1 Byte weiter und erzeuge den Block, sondern vielleicht jeweils immer 10KB in der 600KB-Datei. Dann hätte ich mit 60 Operationen zwar eine imens kürzere Rechenzeit, würde das Ergebnis jedoch verfälschen, da mit hoher Wahrscheinlichkeit keine Gleichheit heraus käme.

    Ein anderer Ansatz wäre vielleicht das Multithreading. Ich könnte die Byteblöcke ja vielleicht von vorne wie von hinten abspeichern, und sobald sich die beiden Threads kreuzen, beende ich das Verfahren. Wobei ich dies an der Stelle für etwas zu "doll" geeignet finde. Ich bin mit dem Thema noch nicht so vertraut und befürchte ein schwereres Handling von Deadlocks. Bei zwei Threads statt einem wäre die Rechenzeit dann auch "nur" doppelt so schnell und wieder problematisch bei größeren Dateien.

    Nun gut... Ich hoffe, das war nicht zu viel für euch.

    Habt ihr einen Rat wie ich die Analyse beschleunigen könnte? Gibt es noch einen besseren Schritt Richtung MD5's? Oder muss ich Multithreading einsetzen? Geht es sonst vielleicht noch irgendwo anders lang?

    Für Hinweise wäre ich echt dankbar..

    MfG
    Geändert von kogen (25.12.2016 um 22:53 Uhr)

  10. #10
    Stammgast
    Registriert seit
    26.02.2003
    Beiträge
    4.769

    Standard

    Ohne dein Verfahren genau analysiert zu haben kannst du vermutlich nur durch passende Wahl der Blockblöcke alles als ähnlich oder nicht ähnlich definieren das sieht doch mehr nach Voodoo aus als nach einem brauchbaren Verfahren um Ähnlichkeit festzustellen.

    Auch wenn hier schon jemand seinen Unmut über Motivationsfragen geäußert hat stelle ich so'ne Frage trotzdem, ohne konkreter Zieldefinition sehe ich keine vernünftige Hilfemöglichkeit. Was ist das Ziel dieses Verfahren? Wie definierst du ähnlich. In welchem Kontext soll diese Art der Ähnlichkeit helfen?

 

 
Seite 1 von 2 1 2 LetzteLetzte

Lesezeichen

Berechtigungen

  • Neue Themen erstellen: Nein
  • Themen beantworten: Nein
  • Anhänge hochladen: Nein
  • Beiträge bearbeiten: Nein
  •