Diskussion:Lempel-Ziv-Welch-Algorithmus

Letzter Kommentar: vor 2 Jahren von 2001:9E8:385A:8800:937:B31C:2F4F:B307 in Abschnitt Algorithmus Dekodierung II

Erstes Thema

Bearbeiten

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))Beantworten

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

Bearbeiten

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))Beantworten

Clear Code

Bearbeiten

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))Beantworten

Binärformat

Bearbeiten

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))Beantworten

Beispiel zur Kompression

Bearbeiten

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))Beantworten

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)Beantworten
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)Beantworten

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)

Bearbeiten

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))Beantworten

nochmal Patente

Bearbeiten

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)Beantworten

Funktioniert mit bestimmtem Beispiel nicht?

Bearbeiten

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)Beantworten

Schwer zu glauben.
--131.169.233.86 17:17, 13. Jun. 2019 (CEST)Beantworten

Algorithmus Dekodierung

Bearbeiten

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))Beantworten

Algorithmus Dekodierung II

Bearbeiten

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))Beantworten