Wpisy otagowane ‘LZW’

Postanowiłam spróbować poszukać informacji na temat tego rodzaju kompresji, gdyż spotkałam się z nią niedawno i jak dotąd miałam o tej kompresji niewielką wiedzę, a dzięki próbie zorientowania się w temacie na pewno udało mi się ją choć trochę pogłębić.

Kilka słów

Kompresja LZW powstała w 1984r. Jest metodą bezstratnej kompresji słownikowej, będącą modyfikacją metody LZ78. Metoda ta wykorzystuje fakt, że w grafice występują powtarzające się ciągi punktów. Algorytm ten oparty jest nie tylko na powtarzalności pojedynczych elementów o takiej samej barwie (informacja nadmiarowa), ale potrafi także „zapamiętywać” różne połączenia znaków. Jest to możliwe dzięki temu, że w trakcie kompresji tworzy się słownik takich połączeń. Interesujące jest to, że słownik nie musi być przesłany wraz ze skompresowanym plikiem, bowiem podczas dekompresji dekoder potrafi otworzyć taki słownik w trakcie dekompresowania informacji. Powtarzające się znaki czy też zbitki znaków zastępowane są przez kody liczbowe i zapisywane w tablicy kodowej.

Kompresja jest tym lepsza, im więcej jest w obrazie informacji nadmiarowej. Kompresja LZW pozwala uzyskać stopień kompresji od 20% nawet do 80% pierwotnej wielkości kompresowanego pliku (zależy to od wielkości i rodzaju grafiki).

Przez pewien czas LZW objęte było patentem. To spowodowało rozpoczęcie prac nad nowym algorytmem kompresji obrazów. Dzięki temu powstał format PNG.

Nazwa

Twórcami kompresji są Abraham Lempel (izraelski informatyk), Jacob Ziv (izraelski informatyk) oraz Terry A. Welch (skrót LZW pochodzi od nazwisk twórców Lempel-Ziv-Welch). Lempel i Ziv opracowali podstawy teoretyczne, a Welch opisał jej implementację.

Lempel i Ziv są najbardziej znani dzięki stworzeniu bezstratnej kompresji Lempel-Ziv (LZ77 i LZ78), której modyfikacją jest metoda LZW.

Zastosowanie LZW w praktyce

Algorytm LZW znalazł praktyczne zastosowanie w:

  • format *.gif zapisu plików graficznych (dzięki dużej kompresji format ten odniósł sukces i zyskał popularność, obok formatu *.jpg jest najważniejszym formatem graficznym w Internecie),
  • formaty PostScript i PDF (kompresja bitmap, filtry kodujące fragmenty dokumentu),
  • programy do kompresji plików – ARC, PAK, UNIX-owy compress,
  • transmisja modemowa.

Zasada działania

Pojęcia używane w teorii kompresji bezstratnej:

Alfabet  kompresora – zestaw wszystkich znaków, jakie mogą się pojawić w danych nieskompresowanych (czyli na wejściu). W określonym zastosowaniu kompresora alfabet jest zwykle stały i znany z góry.

Słownik kompresora – jest to struktura (np. tablica) zawierająca części wiadomości wejściowej oraz przypisane im kody na wyjściu kompresora. Słownik powstaje zwykle dynamicznie w trakcie kodowania wiadomości (nie jest stały i znany z góry), zatem zależy on od kompresowanej  treści. W zależności od algorytmu kompresji słownik jest bądź też nie jest przesyłany w skompresowanej wiadomości.

Przypadek kompresji LZW

Kompresja LZW nie wymaga przesłania słownika wraz ze skompresowaną wiadomością, gdyż dynamicznie jest w stanie odtworzyć słownik w trakcie dekompresji. Po określeniu ile bitów zajmą zakodowane wszystkie symbole z alfabetu cały alfabet jest wstawiany do słownika. Zarówno kompresor jak i dekompresor „znają” alfabet, dlatego też nie ma potrzeby przesyłania go do dekompresji. Pozostała część słownika zawierająca symbole złożone jest odtwarzana przez dekoder na bieżąco, także też nie ma potrzeby jej przesyłania. Zatem słownik w ogóle nie musi być przesłany do procesu dekompresji.

Schemat kodowania danych z wykorzystaniem kompresji LZW:

Test

Chcąc zobaczyć jaki wpływ na wielkość obrazu ma kompresja LZW (w jak dużym stopniu zmienia się wielkość pliku po zastosowaniu tej kompresji) zrobiłam prosty test. W programie GIMP dokonałam różnych wariantów zapisu plików.

W teście badałam 3 pliki:

cały obraz jednolitego koloru – białego,

obraz zawierający 1 element – na białym tle czarny prostokąt,

obraz zawierający wiele elementów – na białym tle linie o przypadkowym kształcie i przebiegu będące w różnych barwach.

Warianty te przedstawia poniższa tabela:

Wariant 1 : Rozdzielczość 72 dpi, obraz o wymiarach 10 cm x 10 cm

Badany plik

Rozmiar pliku *.tif bez kompresji [Kb]

Rozmiar pliku *.tif z kompresją LZW [Kb]

Udział % pliku skompresowanego w stosunku do nieskompresowanego

A.

235

3

1,3 %

B.

4

1,7 %

C.

18

7,7 %

Wariant 2 : Rozdzielczość 508 dpi, obraz o wymiarach 10 cm x 10 cm

A.

11720

39

0,3 %

B.

46

0,4 %

C.

144

1,2 %

Wariant 3 : Rozdzielczość 72 dpi, obraz o wymiarach 100 cm x 100 cm

A.

23548

64

0,3 %

B.

75

0,3 %

C.

272

1,2 %

Wnioski:

Z powyższego testu ciężko wyciągnąć konkretne wnioski. Dodatkowo fakt, że poszczególne plik (A, B, C) nie były identyczne, a zawsze rysowane od nowa sprawia, że niewłaściwe jest porównywanie ich między sobą (wariant 1, wariant 2, wariant 3). Mimo wszystko myślę, że można spróbować pewne prawidłowości wyszukać, a mianowicie:

–  w przypadku plików nieskomplikowanych kompresja LZW jest bardzo wskazana, gdyż fakt, że kompresuje ona ciągli powtarzających się znaków sprawia, że wielkość pliku skompresowanego jest o wiele mniejsza niż pliku nie poddanego kompresji (w teście wielkość skompresowanego obrazu to max. ok. 8% pliku nieskompresowanego),

– im większe wymiary obrazu lub jego rozdzielczość tym kompresja ta jest bardziej widoczna.

Oczywiście, aby pokusić się o konkretniejsze wnioski powinno się przeprowadzić o wiele więcej wariantów, ale myślę, że już teraz widać, iż kompresja ta warta jest uwagi.

Bibliografia:

http://pl.wikipedia.org/wiki/LZW

http://www.digipedia.pl/def/doc/id/575824065/name/LZW/

http://teleinfo.pb.edu.pl/krashan/files/syst_mult_wyklad_2.pdf


Wariant 1 : Rozdzielczość 72 dpi, obraz o wymiarach 10 cm x 10 cm

Badany plik

Rozmiar pliku *.tif bez kompresji [Kb]

Rozmiar pliku *.tif z kompresją LZW [Kb]

Udział % pliku skompresowanego w stosunku do nieskompresowanego

A.

235

3

1,3 %

B.

4

1,7 %

C.

18

7,7 %

Wariant 2 : Rozdzielczość 508 dpi, obraz o wymiarach 10 cm x 10 cm

A.

11720

39

0,3 %

B.

46

0,4 %

C.

144

1,2 %

Wariant 3 : Rozdzielczość 72 dpi, obraz o wymiarach 100 cm x 100 cm

A.

23548

64

0,3 %

B.

75

0,3 %

C.

272

1,2 %