Algorithmus zur String-Spielen in einem Schiebefenster zu finden

Question

Eine der Kernschritte in Dateikomprimierung wie ZIP ist den vorherigen decodierte Text als Referenzquelle zu verwenden. Zum Beispiel könnte sagen, dass der kodierten Strom „vor den nächsten 219 ausgegebenen Zeichen die gleichen wie die Zeichen aus dem decodierten Strom 5161 Bytes sind.“ Auf diese Weise können Sie 219 Zeichen repräsentieren mit nur 3 Bytes oder so. (Es gibt mehr als das, ZIP, wie Huffman-Komprimierung, aber ich spreche nur über die Referenz-Matching.)

Meine Frage ist, was die Strategie (n) für den String-Matching-Algorithmus ist. Selbst bei Quellcode von zlib suchen und so scheint nicht eine gute Beschreibung des Kompressions Matching-Algorithmus zu geben.

Das Problem könne wie festgestellt werden: Bei einem Textblock, sagt 30K davon, und eine Eingabezeichenfolge, finden Sie die längste Referenz in der 30K von Text, entspricht genau den vor dem Eingang String.“der Algorithmus muss effizient sein, wenn iterativ, dh der 30K Textblock durch das Löschen einige Bytes von der Front aktualisiert werden und neue nach hinten und ein neues Spiel ausgeführt hinzugefügt wird.

Ich bin viel mehr daran interessiert, in den Diskussionen des Algorithmus (s), dies zu tun, nicht Quellcode oder Bibliotheken. (Zlib hat eine sehr gute Quelle!) Ich vermute, es mit unterschiedlichen Vor- und Nachteilen mehrere Ansätze sein kann.

Answer 1

Sie auf den Details des LZMA-Algorithmus von 7-zip . Der 7-zip Autor behauptet, auf dem von zlib et al Algorithmus verbessert haben.

Answer 2

Nun, ich merke, dass Sie ausführlich über das Problem gehen in, aber nicht erwähnen, die in Abschnitt bereitgestellten Informationen 4 von RFC 1951 (die Spezifikation für die DEFLATE Druckdatenformat, das heißt das Format, in ZIP verwendet), die mich führt zu glauben, dass Sie diese Ressource verpasst haben könnte.

Ihr grundlegender Ansatz ist eine verkettete Hash-Tabelle Drei-Byte-Sequenzen als Schlüssel verwendet wird. Solange die Kette nicht leer ist, werden alle Einträge entlang es zu einem überprüft werden) beseitigen falschen Kollisionen, b) beseitigen Begegnungen, die zu alt sind, und c) aus jenen verbleibenden um die längste Übereinstimmung auswählen.

(Beachten Sie, dass ihre Empfehlung mit dem Faktor von Patenten geformt ist,. Es kann sein, dass sie von einer effektiveren Technik wussten, konnte aber nicht sicher sein, dass es nicht von jemandem Patent bedeckt war persönlich habe ich mich immer gefragt, warum eine konnte nicht die längsten Übereinstimmungen finden, indem Sie die Spiele für die drei-Byte-Sequenzen untersucht, die auf dem zweiten Byte der eingehenden Daten, das dritte Byte usw. und Ausmerzung Matches beginnen, die bis nicht übereinstimmen. dh wenn Ihre eingehenden Daten „ABCDEFG ...“ und Sie haben Hash-Treffer für „ABC“ an Offsets 100, 302 und 416, aber Ihr nur für „BCD“ Hash-Übereinstimmung ist bei Offset 301, wissen Sie, dass es sei denn, Sie haben zwei ganz zufällig überlappende Hash-Spiele - unwahrscheinlich -. dann 302 ist Ihre längste Match)

Beachten Sie auch die Empfehlung von optionalen „lazy matching“ (die ironischerweise mehr Arbeit tut): anstatt automatisch die längste Match nehmen, die auf dem ersten Byte der eingehenden Daten beginnen, entspricht der Kompressor überprüft eine noch längeren bei dem Start nächster Byte. Wenn Ihre eingehenden Daten „ABCDE ...“ und die einzige in der Kurve Schiebefenster sind für „ABC“ und für „BCDE“, du bist besser dran Codierung des „A“ als wörtliche Byte und dem „BCDE“ als eine Übereinstimmung.

Answer 3

Ich denke, Sie beschreiben eine modifizierte Version des Längste gemeinsame Substring Problem .