LZW

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

Lempel-Ziv-Welch, LZW – metoda strumieniowej bezstratnej kompresji słownikowej, będąca modyfikacją metody LZ78.

Kompresja bezstratna (ang. lossless compression) – ogólna nazwa metod kompresji informacji do postaci zawierającej zmniejszoną liczbę bitów, pod warunkiem, że metoda ta gwarantuje możliwość odtworzenia informacji z postaci skompresowanej do identycznej postaci pierwotnej.PNG (ang. Portable Network Graphics) – rastrowy format plików graficznych oraz system bezstratnej kompresji danych graficznych.

Pomysłodawcą algorytmu jest Terry A. Welch. Metodę opisał w 1984 roku, w artykule A technique for high-performance data compression opublikowanym w numerze 6. Computer (str. 8-19).

Metoda LZW jest względnie łatwa do zaprogramowania, daje bardzo dobre rezultaty. Wykorzystywana jest m.in. w programach ARC, PAK i UNIX-owym compress, w formacie zapisu grafiki GIF, w formatach PDF i PostScript (filtry kodujące fragmenty dokumentu) oraz w modemach (V.42bis). LZW było przez pewien czas algorytmem objętym patentem, co było przyczyną podjęcia prac nad nowym algorytmem kompresji obrazów, które zaowocowały powstaniem formatu PNG.

LZ78 – słownikowa metoda bezstratnej kompresji danych. Została opracowana w 1978 roku przez Jacoba Ziva i Abrahama Lempela i opisana w IEEE Transactions on Information Theory, w artykule pt. "Compression of individual sequences via variable-rate encoding" (str. 530-536).LZMW - algorytm kompresji słownikowej będący modyfikacją algorytmu LZW, zaproponowany w 1985 roku przez V. Millera i M. Wegmana w artykule Variations on a theme by Ziv and Lempel.

LZW - to także rozszerzenie do programu LHA i algorytmu bezstratnej kompresji danych stworzony przez Haruyasu Yoshizakiego. Inne rozszerzenia: .LHW .LZH .LZS

Zmiany w stosunku do LZ78[ | edytuj kod]

W pojedynczym kroku kompresji LZ78 wyszukiwane jest w słowniku najdłuższe słowo będące prefiksem niezakodowanych jeszcze danych. Na wyjście wypisywany jest indeks tego słowa oraz pierwszy symbol z wejścia znajdujący się za dopasowaniem. Np. jeśli w słowniku pod indeksem 2 zapisane jest słowo "wiki", a kodowany jest ciąg "wikipedia", na wyjście zostanie wypisana para (2, 'p'); do zakodowania pozostanie jeszcze ciąg "edia". Jeśliby nie udało się zlokalizować niczego w słowniku, na wyjście wypisywana jest para (0, pierwsza litera) – oznacza to, że w słowniku nie ma jeszcze słowa jednoliterowego równego tej pierwszej literze.

compress - uniksowy program kompresujący wykorzystujący wariant algorytmu kompresji LZW nazywany LZC. Tworzy pliki z rozszerzeniem .Z i może być używany jako kompresor w programie tar.GIF (ang. Graphics Interchange Format) – format pliku graficznego z kompresją bezstratną (opis niżej) stworzony w 1987 roku przez firmę CompuServe. Pliki tego typu są powszechnie używane na stronach WWW, gdyż pozwalają na tworzenie animacji dwustanową przezroczystością.

Przewaga LZW nad LZ78 to krótsze wyjście kodera – wypisywany jest wyłącznie indeks słowa. Uzyskano to dzięki pierwszemu etapowi algorytmu, tj. wstępnemu wypełnieniu słownika alfabetem (wszystkimi symbolami, jakie mogą pojawić się w danych), gwarantując w ten sposób, że zawsze uda się znaleźć dopasowanie, przynajmniej jednoliterowe.

PostScript – uniwersalny język opisu strony opracowany przez firmę Adobe Systems, będący obecnie standardem w zastosowaniach poligraficznych.PDF (ang. Portable Document Format, przenośny format dokumentu) – format plików służący do prezentacji, przenoszenia i drukowania treści tekstowo-graficznych, stworzony i promowany przez firmę Adobe Systems. Język opisu pliku PDF jest okrojoną wersją języka programowania PostScript wzbogaconą o elementy hipertekstowe.

Algorytm kompresji (kodowania)[ | edytuj kod]

W pojedynczym kroku algorytmu wyszukiwany jest w słowniku najdłuższy prefiks niezakodowanych jeszcze danych. Na wyjście wypisywany jest wówczas kod związany z tym słowem, zaś do słownika dodawana nowa pozycja: konkatenacja słowa i pierwszej niedopasowanej litery.

Algorytm przebiega następująco:

Algorytm – w matematyce skończony ciąg jasno zdefiniowanych czynności, koniecznych do wykonania pewnego rodzaju zadań. Słowo "algorytm" pochodzi od starego angielskiego słowa algorism, oznaczającego wykonywanie działań przy pomocy liczb arabskich (w odróżnieniu od abacism – przy pomocy abakusa), które z kolei wzięło się od nazwiska, które nosił Muhammad ibn Musa al-Chuwarizmi (أبو عبد الله محمد بن موسى الخوارزمي), matematyk perski z IX wieku.Modem (od ang. MOdulator-DEModulator) – urządzenie elektroniczne, którego zadaniem jest zamiana danych cyfrowych na analogowe sygnały elektryczne (modulacja) i na odwrót (demodulacja) tak, aby mogły być przesyłane i odbierane poprzez linię telefoniczną (a także łącze telewizji kablowej lub fale radiowe). Jest częścią DCE (Data Communications Equipment), które w całości wykonuje opisane wyżej czynności. Nieodzowne do współpracy jest DTE (Data Terminal Equipment) i to dopiero stanowi całość łącza przesyłania danych. Dzięki modemowi można łączyć ze sobą komputery i urządzenia, które dzieli znaczna odległość.
  1. Wypełnij słownik alfabetem źródła informacji.
  2. c := pierwszy symbol wejściowy
  3. Dopóki są dane na wejściu:
  4. Wczytaj znak s.
  5. Jeżeli ciąg c + s znajduje się w słowniku, przedłuż ciąg c, tj. c := c + s
  6. Jeśli ciągu c + s nie ma w słowniku, wówczas:
  7. wypisz kod dla c (c znajduje się w słowniku)
  8. dodaj ciąg c + s do słownika
  9. przypisz c := s.
  10. Na końcu wypisz na wyjście kod związany c.

O efektywności kompresji w dość dużym stopniu decyduje sposób zapisu kodów (liczb).

Pixmapa, mapa pikseli – plik wykorzystujący rastrowy sposób reprezentacji komputerowej grafiki dwuwymiarowej polegający na określeniu położenia każdego piksela obrazu, oraz przypisaniu mu wartości określającej kolor w danym trybie koloru.LZC - wariant słownikowej metody kompresji LZW, wykorzystywany w programie compress. Ogólną ideą działania metody LZW jest zapisywanie na osobnej liście (w tzw. słowniku) ciągów bajtów, które pojawiły się w kompresowanych danych - kolejne wystąpienie ciągu znajdującego się na liście powodują zapisanie wyłącznie jego numeru (indeksu), który zajmuje mniej bitów niż dany ciąg. W metodzie LZC liczba bitów potrzebna na zapisanie indeksu rośnie od 9 do 16 bitów, wraz ze zwiększaniem liczby pozycji w słowniku; liczba pozycji jest ograniczona do ok. 65 tysięcy (2). Charakterystyczne jest postępowanie w sytuacji, gdy w słowniku nie ma już miejsca na nowe ciągi. Program nie modyfikuje listy słów, lecz wykorzystuje ją do dalszej kompresji, jednocześnie monitorując współczynnik kompresji - dopiero gdy spadnie on poniżej pewnego progu, lista słów jest zerowana i budowana od początku.


Podstrony: 1 [2] [3] [4]




Warto wiedzieć że... beta

Oprogramowanie (ang. software) – całość informacji w postaci zestawu instrukcji, zaimplementowanych interfejsów i zintegrowanych danych przeznaczonych dla komputera do realizacji wyznaczonych celów. Celem oprogramowania jest przetwarzanie danych w określonym przez twórcę zakresie. Oprogramowanie to dział informatyki. Oprogramowanie jest synonimem terminów program komputerowy oraz aplikacja, przy czym stosuje się go zazwyczaj do określania większych programów oraz ich zbiorów.
Kodowanie słownikowe - kodowanie danych, w którym podciągi komunikatu występujące w słowniku (tj. zbiorze słów) są zastępowane symbolami jednoznacznie opisującym ich pozycję w słowniku, zwykle indeksami (liczbami). Takie metody dobrze kompresują dane, w których podciągi powtarzają się, np. w przypadku tekstów naturalnych (teksty książek, czasopism itp.) wiele słów a nawet całych fraz występuje wielokrotnie.
Lempel-Ziv 77, skracane zwykle do LZ77 (algorytm LZ77) – metoda strumieniowej słownikowej kompresji danych. Metoda LZ77 wykorzystuje fakt, że w danych powtarzają się ciągi bajtów (np. w tekstach naturalnych będą to słowa, frazy lub całe zdania) – kompresja polega na zastępowaniu powtórzonych ciągów o wiele krótszymi liczbami wskazującymi, kiedy wcześniej wystąpił ciąg i z ilu bajtów się składał; z punktu widzenia człowieka jest to informacja postaci "taki sam ciąg o długości 15 znaków wystąpił 213 znaków wcześniej".

Reklama