Diskussion:Lempel-Ziv-Welch-Algorithmus

Erstes Thema

Was mache ich, wenn die LZW-Komprimierung nicht unterstützt wird? (nicht signierter Beitrag von 217.247.6.39 (Diskussion) 18:05, 28. Mär. 2005 (CEST))

Etwas Erklärung zum Beispiel wäre schön. So richtig schlau wird man aus dem Beispiel nämlich nicht ... --Ahans 23:30, 28. Jul 2005 (CEST)

Funktionsweise

Die Bemerkung, dass ein Decoder richtig programmiert sein muss, um zu funktionieren, sagt doch nichts aus. Außer wenn man bestimmte Dinge ansprechen kann, die häufig falsch gemacht werden. Dann werden in der Mustertabelle nicht die am häufigsten vorkommenden Zeichenketten gespeichert, sondern (beinahe) alle irgendwo auftretenden Muster, in der Hoffnung, dass sie nochmal auftreten. Der Algorithmus kommt nämlich ohne look-ahead aus. Zum Dritten unterscheidet der Algorithmus nicht zwischen Symbolen und Verweisen. Der codierte Datenstrom besteht nur aus Verweisen. Um einzelne Zeichen darzustellen, wird die Mustertabelle mit allen Mustern der Länge eins initialisiert. Damit entsprechen die Muster 0 bis 255 genau den 256 Zeichen. Man kann dann natürlich durch einen (Bit-)Test (Musterindex kleiner 256) feststellen, ob es sich um ein Muster der Länge ein handelt oder nicht. Doch dies ist für den Algorithmus nicht relevant. (nicht signierter Beitrag von Mardur (Diskussion | Beiträge) 14:50, 22. Nov. 2005 (CET))

Clear Code

Im Compression Beispiel wird der erste gefundene String auf 256 eingetrage AFAIK ist das Clear Code 257 ist EOICode also ist 258 das erste freie zeichen, dass ins dictionary engetragen werden darf. Sehe ich das falsch? (nicht signierter Beitrag von 193.138.10.41 (Diskussion) 11:27, 12. Sep. 2008 (CEST)) Sorry, das ist GIF bzw. TIFF spezifisch, aber imho sollte das irgendwie trotzdem erwähnt werden. (nicht signierter Beitrag von 193.138.10.41 (Diskussion) 16:24, 15. Sep. 2008 (CEST))

Binärformat

Mir fehlt hier die Beschreibung der diversen physikalischen Ausprägungen des lzwcodierten Datenstromes. Grundsätzlich ist es ja so, dass das auf einen BITDATENSTROM hinausläuft der dann im Normalfall eine von 9 beginnend anwachsende Codelänge aufweist. In seltenen Fällen wird auch einfach auf 16, 14, 12 Bit Breite der Code ausgegeben, aber sowas ist bestenfalls akademisch weil nicht sinnvoll anwendbar. Teilweise wird dann noch zu früh auf die nächste Codelänge gewechselt usw (nicht signierter Beitrag von 193.138.10.41 (Diskussion) 10:46, 12. Sep. 2008 (CEST))

Beispiel zur Kompression

Es heißt dort "Es entsteht also die Zeichenkette „L Z W <256> 7 8 <259> 7 <256> C <256> M <258> Z A P“ („Ausgabe“ von oben nach unten gelesen), die mit 16 Zeichen anstatt ursprünglich 22 Zeichen dieselbe Information beinhaltet."

Es klingt so, als könne LZW den Beispielstring von 22 auf 16 Zeichen komprimieren. Das halte ich für nicht möglich, da die Verweise <256>, <259> und <258> nicht in einem Zeichen codiert werden können. (nicht signierter Beitrag von 91.106.177.202 (Diskussion) 16:20, 29. Jun. 2018 (CEST))

Höhö lol, ich frage mich auch, warum als Beispiel gerade dieses genommen wurde. Es wurde nichts komprimiert, sondern expandiert.

--131.169.233.86 17:14, 13. Jun. 2019 (CEST)

Im Beispiel wird ja erwähnt, dass die 16 Zeichen mit 12 bit kodiert 24 bytes (8bit) ergeben, das ist allerdings falsch. LZW benutzt eine variable index Länge. Der Artikel ist in dieser Beziehung sehr inkonsistent. Zum einen wird gesagt, dass ein variabler index benutzt wird der mit 9 bit beginnt, zum anderen wird behauptet es werden "üblicherweise 12 bit benutzt". Was unter "Varianten" als LZC bezeichnet wird ist eigentlich normales LZW. Ich hab von LZC noch nie gehört und wenn man danach sucht bekommt man auch nur wenige Treffer. Es scheint aber einfach eine variante von LZW zu sein, die vom "compress" Programm benutzt wurde / wird.

Ich habe schon selbst einen GIF Dekoder geschrieben (nur Aufgrund der GIF Spezifikation) und kann bestätigen, dass ein variabler index benutzt wird und dieser sogar mit weniger als 9 bits beginnen kann, je nachdem, wie viele Farben in der Palette enthalten sind. Erst wenn das Wörterbuch die nächste 2er Potenz erreicht, wird um 1 bit erhöht. D.h. das Beispiel hier auf der Seite benötigt 16*9 bits also 16*9/8 bytes und das sind 18 bytes. Also hat man 4 bytes eingespart. Es sollte klar sein, dass bei so kurzen Texten / Daten die Kompression relativ sinnfrei ist. Ein Text mit maximaler Entropie wie z.B. "ABCDEFGHIJKLMNOP" wird auf jeden Fall größer werden, da man ja mindestens 9 bits pro Zeichen braucht. Also bräuchte man 2 bytes mehr. Das ist natürlich unter der Annahme, dass wir mit einem Wörterbuch mit 256 Einträgen beginnen. Im englischen Wiki haben sie ein Beispiel, das mit einem 5bit Index beginnt, da es sich nur um Text in Großbuchstaben handelt.

--Bunny99s (Diskussion) 02:49, 7. Okt. 2020 (CEST)

Patente

Das Unisys Patent trägt im Abschnitt über Patente einmal die Nummer 4.464.650 und sonst die Nummer 4.558.302. Welche Nummer ist richtig? --Uwe W. 09:49, 23. Sep 2006 (CEST)

Links

Zwei Links wurden entfernt, da der eine tot war (Marek Tomczyk) und der andere inhaltlich falsche Beispiele und Erläuterungen gab (Sascha Seidel). (nicht signierter Beitrag von 84.174.194.144 (Diskussion) 15:38, 3. Okt. 2006 (CEST))

nochmal Patente

Sollten wir die Patente-Geschichte nicht lieber in den LZ78-Artikel verschieben, da es die ganze LZ78-Familie (oder zumindest mehrere Abkömmlinge) betrifft?--Speck-Made 00:42, 8. Dez. 2007 (CET)

Funktioniert mit bestimmtem Beispiel nicht?

Mit dem Beispiel ABAAABACCCAA funktioniert die Dekodierung nach dem angegebenen Schema nicht. Bei Gelegenheit werde ich das Beispiel hier abtippen. 143.93.92.13 10:06, 25. Mai 2011 (CEST)

Schwer zu glauben.

--131.169.233.86 17:17, 13. Jun. 2019 (CEST)

Algorithmus Dekodierung

Der Pseudo-Code zur Dekodierung ist schwer zu verstehen.

Ich nehme an, mit "Muster VON xxx" ist der Eintrag von xxx in der Mustertabelle gemeint. Was soll dann aber "Muster VON next" im "SONST"-Fall sein, also wenn next gerade nicht in der Mustertabelle vorhanden ist? Oder soll in beiden Fällen ein neuer Eintrag in der Mustertabelle __für next__ hinzugefügt werden?

Bitte Algorithmus überarbeiten. (nicht signierter Beitrag von 89.247.46.40 (Diskussion) 14:22, 23. Feb. 2020 (CET))

Algorithmus Dekodierung II

Hinzu kommt noch die unklare Bedeutung von erstes_Zeichen_von. Im Beispiel werden neue Symbole wie <256> als Schlüssel für die Tabelle verwendet und nicht das Anfangszeichen eines bestimmten Musters. Bitte überarbeitet dringend diese Algorithmendarstellung, oder entfernt sie lieber ganz. (nicht signierter Beitrag von 2001:9E8:385A:8800:937:B31C:2F4F:B307 (Diskussion) 15:24, 21. Feb. 2022 (CET))