LZMA Algorithmus

[daemon777]

Hallo Leute,

in letzter Zeit beschäftige ich mich ein bisschen mit den Basics der Datenkompression und bin hier auf die LZ-Familie gestoßen. Während man über die simplen Varianten (bisher LZ77, LZ78, LZSS und LZW) eine Menge Informationen und Beispiele findet habe ich jetzt beim LZMA so meine Schwierigkeiten überhaupt irgendetwas zu finden.
Was es natürlich gibt ist die Referenzimplementierung aber das kostet natürlich viel Zeit und Mühe hieraus Rückschlüsse zu ziehen wie und warum das Ganze funktioniert.

Deshalb wollte ich hier mal nachfragen, ob sich hier schonmal jemand mit dem Thema beschäftigt hat und mir hier vielleicht ein paar Infos zum Start geben kann. Mir geht es vor allem um das Verstehen des Algorithmus. An einer Implementierung, die bestenfalls auch kompatibel zur Referenzimplementierung ist, will ich mich (wenn überhaupt) erst später machen.

Also falls hier jemand Schriften, Beispiele, irgendwas dazu hat wäre ich sehr dankbar

Derzeit ist die englische Wikipedia tatsächlich das brauchbarste Dokument, was ich finden konnte.

viele Grüße
daemon

 

[e-Funktion]

http://en.wikipedia.org/wiki/Lempel–Ziv–Markov_chain_algorithm ?

 

[black90]

Hab eine Vorlesung aus dem 1.Semester dazu, da ist es Schrittweise dargestellt.
(0,A) -> Die 0 zeigt die Position, das A ist was noch an den String an dieser Position angehängt wird.
Die 0 zeigt dabei nirgends hin, 1 an die erste Stelle.

A A A B A A B A A B A A A B B ...
Wörterbuch und erzeugter Code:
Eintrag # 1 2 3 4 5 6
Phrase    A    AA      B    AAB   AABA  AABB
Codewort (0,A) (1,A) (0,B) (2,B) (4,A) (4,B)

Dann fängst an:
(0,A) weil du noch kein A kennst.
(1,A) weil du das A bereits an erster Position kennst, also in (0,A) und du fügst noch ein A an -> AA
(0,B) da kein B bekannt
(2,B) da AA an Position 1 und zusätzlich ein B anhängen
(4,A) zeigt auf AAB und zusatzlich ein A
(4,B) zeigt auch auf AAB und zusätzlich ein B
usw.

Das ergibt deine Kodierung, am Ende hast du "Pakete" mit Zeichen. Genug davon gemacht, hast du lauter Pakete aus denen du eine Sprache bauen kannst. Du merkst dir einfach wo was steht und setzt es durch Verweis zusammen. Daher kommt auch die Kompression, da man man sich durch die Verweise viele "Buchstaben" spart.

Sowas mit Wiki oder Büchern lernen ist absoluter Horror, da die Mathematiker einfach nicht auf Formeln verzichten wollen, obwohl die Logik dahinter ein Kleinkind verstehen würde.

Lern mit Youtube, die erklären besser als Bücher :>

 

[daemon777]

@e-Funktion
Ich hab doch schon geschrieben, dass ich den englischen wikipediaArtikel kenne. Der ist ja ganz nett aber er reicht mir nicht wirklich aus, um hier ein Verständnis für den Algorithmus zu bekommen.

@black90
Das sieht mir sehr nach einer Variante des LZ77 aus, wobei Wörterbuch für den LZ78 sprechen würde. Das kommt dann ein bisschen auf die Details an. Allerdings sieht es für mich nicht wie der LZMA aus.
Infos auf youtube beschränken sich auch auf LZ77, LZ78 und LZW. Den LZSS habe ich noch anderweitig gefunden aber beim LZMA hört es irgendwie auf, was einfache Quellen angeht.

 

[black90]

Hat einen Grund, steht hier: http://mattmahoney.net/dc/dce.html#Section_523
und führt zu dem: http://cbloomrants.blogspot.de/2010/08/08-20-10-deobfuscating-lzma.html

Wirst wohl ein Buch kaufen müssen, hat wohl noch keiner so recht dokumentiert

 

[daemon777]

Dann wird mir wohl nichts übrig bleiben als mich durch die Referenzimplementierung zu quälen, wenn ich das verstehen will.

Der LZ-Teil scheint ja auch gar nicht mal so komplex zu sein. Bei der Bereichskodierung sieht das aber wohl leider etwas anders aus.

EDIT:
Aah cool. Den zweiten Link habe ich bisher noch nicht gefunden. Vielleicht finde ich da ja ein paar Infos. Selbst Bücher habe ich jetzt keine gefunden, die wirklich Infos über den LZMA beinhalten ^^

 

[e-Funktion]

@e-Funktion
Ich hab doch schon geschrieben, dass ich den englischen wikipediaArtikel kenne.

Oh, irgendwie hat dein Beitrag nach "dankbar" vor dem geistigen Auge geendet ^^