kompression: Wiederholungen finden / RLC mit beliebiger Wortlänge
-
Hallo,
Ich habe eine Frage zu Datenkompression bzw. finden von Wiederholungen.Speziell habe ich ein Array (stl::vector) das Signale enthält. Außerdem weis ich, dass sich Teile der Daten oft wiederholen. d.h. der Datenstrom sieht evtl so aus:
abababababababcccabcccabcccabcccababababababefcccabdddefcccabddd...Ich möchte jetzt versuchen möglichst die wiederholungen rauszufiltern und einen neuen Stream erzeugen, der in etwa so aufgebaut ist:
[7ab][4abccc]cabccc[7ab][2efcccabddd]...Mein Problem ist, wie finde ich (möglichst einigermaßen effizient) die wiederholungen im stream.
Hier geht es nicht drum, wirklich alles zu finden, sondern nur die "großen" Teile rauszusuchen, die man auch schnell per Auge finden würde.Der erste Gedanke war ein 'Fenster' der Größe stream.size()/2 darüberzulegen, dann um die Fenstergröße weiterschieben und testen ob die selben Inhalte im Fenster liegen.
Dannach die Fenstergröße um eins verkleinern, wieder schieben, vergleichen, .....
Solange, bis ich mit einem möglichst großen Fenster eine oder mehr Wiederholung engefunden habe...Sprich im Endeffekt ergibt sich ungefähr sowas wie eine RunLenghtCodierung, allerdings nicht auf Bitebene mit 0/1 mit suchstringlänge 1, sondern eine Codierung die sowohl in der Auswahl der Daten als auch der Auswahl der Datenfeldgröße variabel ist.
Irgend jemand eine Idee wie obiges Format einigermaßen effizient erzeugt werden kann? Bzw. obs ähnliche Verfahren zur Kompression gibt, an die ich mich anlehnen kann?
-
-
Ich denke mit rolling checksums müsste man hier was reissen können.
