Kompresné alogritmy

  • Lempel Ziv 77 a 78
  • Run Length Encoding

Kompresia

Vstup:: Sekvencia symbolov Výstup:: Kratšia sekvencia symbolov, ktorá vyjadruje pôvodnú sekvenciu

Entropia

  • Miera maximálnej možnej kompresie v bitoch
  • Vypočíta sa z početnosti (frekvencie symbolov)

Kompresia ASCII Art

  • Obsahuje veľa medzier za sebou

Aardvark

[https://www.asciiart.eu/animals/aardvarks](Art by Horroroso)

                    _,,......_
                 ,-'          `'--.
              ,-'  _              '-.
     (`.    ,'   ,  `-.              `.
      \ \  -    / )    \               \
       `\`-^^^, )/      |     /         :
         )^ ^ ^V/            /          '.
         |      )            |           `.
         9   9 /,--,\    |._:`         .._`.
         |    /   /  `.  \    `.      (   `.`.
         |   / \  \    \  \     `--\   )    `.`.___
-hrr-   .;;./  '   )   '   )       ///'       `-"'
        `--'   7//\    ///\

Run Length Encoding

  • kompresia ikon a jednoduchých bitmapovýćh obrázkov.
  • kompresia ASCII artu :-)

Run Length Encoding

  • Reťazec kóduje ako počet opakovaní symbolu v minulosti.
  • Kódové slovo je dvojica: symbol, počet opakovaní

Run Length Encoding

  • Zober symbol
  • Spočítaj počet jeho výskytov za sebou
  • Zapíš počet výskytov
  • Zapíš symbol

Run Length Encoding Príklad

WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW

12W1B12W3B24W1B14W

Kompresia pomocou slovníka

  • V dátach identifikujeme často opakujúce sa časti
  • Zakódujeme ich a zostavíme slovník
  • Slovník sa vytvára počas behu algoritmu, nie je známy dopredu.

Lempel Ziv 77

http://www.stringology.org/DataCompression/lz77/index_en.html

Podľa wiki:

  • Kódové slovo je trojica: posunutie, dĺžka, ďalší znak.
  • Kóduje sa výskyt reťazca v minulosti.

Lempel Ziv 77

Prebieha v plávajúcom okne, ktoré je rozdelené na minulosť a budúcnosť.

  • Hľadaj v budúcnosti čo najdlhší reťazec čo sa nachádza v minulosti
  • Nahraď ho trojicou: dĺžka, posunutie, ďalší znak.

zdroj

begin
  naplň nezakódovanou část okna ze vstupu
  while (nezakódovaná část není prázdná) do 
    begin
      najdi v okně předponu p nezakódované části začínající v zakódované části
      i := pozice předpony p v okně
      j := délka předpony p
      X := první znak za p v nezakódované části
      output(i,j,X)
      přidej do okna zprava i+1 znaků
    end
end

Dekódovanie Lempel Ziv 77

Prebieha v plávajúcom okne.

  • Zober kódové slovo.
  • Nahraď ho za reťazec podľa minulosti.

Deflate

Kombinácia LZ 77 a Huffman Encoding.

  • GIF
  • pkzip
  • gzip
  • zip

Lempel-Ziv-78

http://www.stringology.org/DataCompression/lz78/index_en.html

Jeho upravená verzia sa nazýva Lempel-Ziv-Welch

[quote,Wikipedia]

V každom kroku sa vstupné bajty zhromaždia do postupnosti, pokiaľ nasledujúci znak nevytvorí postupnosť ktorá sa nenachádza v slovníku. Kód postupnosti bez nového znaku sa pridá do výstupu a postupnosť spolu s novým znakom sa pridá do slovníka.

Kódové slovo LZ78

číslo záznamu v slovníku + symbol

Slovník Lempel-Ziv-Welch

  • Asociatívne pole:
    • reťazec -> kód
  • Na začiatku je určený počiatočný slovník, ktorý obsahuje napr. všetky reťazce dĺžky jedna.
  • Slovník nie je potrebné zapisovať, vytvára sa za behu kódovania aj dekódovania.

Kódovanie Lempel-Ziv-78

  1. Inicializuj slovník
  2. Zober znak zo vstupu.
  3. Ak sa buffer a znak nenachádza v slovníku, zapíš kód buffra. Pridaj buffer a znak do slovníka.
  4. Inak pridaj znak do buffra a pokračuj ďalším znakom.

zdroj

begin
    inicializace slovníku
     buffer := ""
      while (!konecVstupu()) do
       begin
         symbol := další nezpracovaný znak ze vstupu
         if ( ( buffer.symbol ) je ve slovníku ) then
            buffer := buffer.symbol;
         else
        begin
           output(indexDoSlovníku(buffer),symbol)
           přidej do slovníku ( buffer.symbol )
           buffer := ""
         end
     end
     if ( !prázdný(buffer) ) then
       output(indexDoSlovníku(buffer));
end

Dekódovanie Lempel-Ziv-Welch

Podľa blogu:

  1. Inicializuj slovník.
  2. Načítaj kódové slovo.
  3. Pridaj reťazec a znak do slovníka.
  4. vypíš reťazec a znak

Príklad LZW

Aplikácia LZW

  • Compress
  • GIF
  • TIFF
  • PDF

Zhrnutie

  • Algoritmy LZ sú široko používané.
  • Pracujú na princípe identifikácie opakujúcich sa častí.
Reload?