http://www.multimediaexpo.cz/mmecz/index.php?action=history&feed=atom&title=LZW84 2026-06-09T19:27:55Z Historie editací této stránky MediaWiki 1.16.5 http://www.multimediaexpo.cz/mmecz/index.php?title=LZW84&diff=517460&oldid=prev 2014-02-01T09:34:23Z

<p>1 revizi</p> <table style="background-color: white; color:black;"> <tr valign='top'> <td colspan='1' style="background-color: white; color:black;">← Starší verze</td> <td colspan='1' style="background-color: white; color:black;">Verze z 1. 2. 2014, 09:34</td> </tr></table>

Sysop http://www.multimediaexpo.cz/mmecz/index.php?title=LZW84&diff=517459&oldid=prev 2012-05-05T05:23:22Z

<p>+ Nový článek...</p> <p><b>Nová stránka</b></p><div>'''LZW84''' ('''Lempel-Ziv-Welch 84''') je [[Bezeztrátová komprese|bezeztrátový]] kompresní [[algoritmus]] vyvinutý [[Abraham Lempel|Abrahamem Lempelem]], [[Jacob Ziv|Jacobem Zivem]] a [[Terry Welch]]em. Byl publikován v roce [[1984]] jako vylepšení algoritmů [[LZ77]] a [[LZ78]] publikovaných v letech [[1977]] a [[1978]]. Je relativně jednoduchý a rychlý, ale nedosahuje zdaleka tak dobré komprese jako náročnější algoritmy jako [[LZMA]], je většinou horší než [[Deflate]] a neprovádí analýzu dat. Data prošlá algoritmem LZW84 jsou dále nekomprimovatelná, toto je rozdíl oproti algoritmu [[LZ77]], po kterém lze data dále komprimovat pomocí algoritmu [[Huffmanovo kódování|Huffman]] nebo podobného. Algoritmus byl až do roku 2004 zatížený [[patent]]em, dnes je patent prošlý, ale algoritmus byl mezitím překonán. Byl využíván (a je částečně dodnes) v archívech ARC, starých verzích ZIPu (PKZIP 0.x a 1.x), unixovém komprimačním programu compress (soubory s příponou „Z“), grafickém formátu [[GIF]] a dokumentech [[Portable Document Format|PDF]].<br /> <br /> == Popis algoritmu ==<br /> Kódovací algoritmus si postupně vytváří kódovací tabulku ze slov použitých v již zakódovaném textu. Tato tabulka mapuje vstup na slova/stringy s pevně stanovenou délkou. Na počátku je tabulka inicializována pomocí všech jednoznakových slov použité abecedy (typicky 256 znaků [[ASCII]]). A dále algoritmus sériově prohledává text, ukládá si do tabulky každé unikátní dvouznakové slovo jako zřetězení vzoru a kódu (něco jako slovník). Jakmile má uložena všechna dvouznaková slova, pošle na výstup kód prvního na vstupu. Algoritmus pokračuje v kódování, jakmile je na vstupu nalezeno již známé slovo (tj. je již v tabulce), na výstup se pošle odpovídající kódový znak plus před ním první znak kódovaného slova.<br /> <br /> Dekompresnímu algoritmu stačí jen zkomprimovaný text, slovník si vytváří stejně jako u komprimace „za chodu“.<br /> <br /> ''Vysokoúrovňový popis algoritmu v krocích:''<br /> <br /> # Inicializuj slovník na všechny řetězce dlouhé jeden znak.<br /> # Najdi nejdelší možný řetězec Ř ve slovníku, který odpovídá aktuálnímu vstupu.<br /> # Na výstup pošli index Ř a odstraň řetězec Ř ze vstupu.<br /> # Přidej řetězec Ř + následující znak ze vstupu do slovníku.<br /> # Běž na krok 2.<br /> <br /> Pozn.: tedy jak vidíte, nově zakódované podřetězce se mohou na výstup dostat až na druhý výskyt, protože při prvním výskytu ještě nejsou ve slovníku. Fakticky tento první výskyt slouží k uložení informace o jejich složení do výstupních dat.<br /> <br /> == Související články ==<br /> * [[LZ77]]<br /> * [[Deflate]]<br /> * [[LZMA]]<br /> * [[Huffmanovo kódování]]<br /> * [[GIF]]<br /> <br /> == Literatura ==<br /> * SOBOTA, Branislav, MILIÁN, Ján: ''Grafické formáty'', nakl. Kopp, ISBN 80-85828-58-8, zejm. str. 37 a 75.<br /> <br /> <br /> {{Článek z Wikipedie}}<br /> [[Kategorie:Kompresní algoritmy]]<br /> [[Kategorie:Zkratky]]</div>

Sysop