Algoritmy komprese dat Slovníkové metody
Phillip Walter Katz (1962 - 2000)
2.12.2015
NSWI072 - 10
Slovníkové metody komprese dat ☀ Idea • opakující se fráze uloženy do slovníku • výskyty fráze v textu → ukazatel do slovníku
Problémy a v praxi používaná řešení: • NP-těžký problém konstrukce optimálního slovníku ⇒ hladový algoritmus • slovník musí znát i dekodér ⇒ dynamické metody
Jacob Ziv, Abraham Lempel [LZ77] A universal algorithm for data compression. IEEE Trans. Inform. Theory, IT-23(3):337-343, 1977. [LZ78] A compression of individual sequences via variable-rate coding. IEEE Trans. Inform. Theory, IT-24(5):530-536, 1978. 2
LZ77 Posuvné okno prohlížecí okno (search buffer)
aktuální okno (look-ahead buffer)
Inicializace • •
prohlížecí okno vyplníme mezerami do aktuálního okna načteme začátek vstupu
V posuvném okně vyhledáme co nejdelší slovo S takové, že • •
S začíná v prohlížecím okně S je shodné s nějakou předponou slova v aktuálním okně 3
LZ77 Posuvné okno prohlížecí okno
aktuální okno
Slovo S je zakódováno trojicí 〈i,j,z〉, kde • • •
i je vzdálenost začátku slova S od začátku aktuálního okna j = |S| z je znak následující S
〈7,4,r〉 Celé okno je posunuto o j+1 znaků doprava 4
LZ77 Posuvné okno prohlížecí okno
aktuální okno
Velikosti posuvného okna 212 až 216 • gzip 215 B
Velikost aktuálního okna desítky až stovky B • gzip 256 B
5
☀ Příklad
〈0,0,d〉
〈7,4,r〉
〈3,5,d〉 6
☀ Příklad:
dekódování
〈0,0,d〉 , 〈7,4,r〉 , 〈3,5,d〉
〈7,4,r〉 , 〈3,5,d〉
7
☀ Příklad:
dekódování
〈3,5,d〉
8
Analýza Pomalá komprese, rychlá dekomprese Rychlost komprese lze zvýšit • použitím speciálních datových struktur • současně však rostou paměťové nároky
Typická aplikace • jedna komprese • vícenásobná dekomprese
9
Varianta LZSS Storer, Szymanski (1982) • místo trojice (i,j,z) buďto (i,j) nebo z • bitový indikátor k rozlišení: dvojice ukazatelů × znak • dvojice ukazatelů potřebuje stejnou paměť jako p znaků ⇒ kóduj dvojicemi jen fráze délky >p » jinak kopíruj na výstup jednotlivé znaky
• prohlížecí okno → cyklická fronta [0..N] 5
6
7 8 9 10 0 1 2 3 4
Možná implementace
– kódové slovo 16b, | i| = 11, |j|=5 – bitové indikátory vždy po 8 v 1B 10
N=10
Variace na téma LZ77 LZB (Bell, 1987) • •
LZSS s úspornějším kódováním ukazatelů (i,j) i → binární kód rostoucí délky -
•
nejprve 1b po načtení 2. znaku 2b po načtení 4. znaku 3b atd.
j → kód γ
11
Variace na téma LZ77 LZH (Brent, 1987) • • •
LZSS s Huffmanovým kódem pro ukazatele 1. průchod: LZSS + výpočet četností 2. průchod: statický Huffmanův kód
Problém velké tabulky četností • •
číslo i ve dvojici (i,j) je rozděleno na dvě části (každá s max hodnotou √N) jedna tabulka četností pro položky všech 4 typů
12
Co mají společné? .zip .gz .jar .cab .png Metoda Deflate • autor Phil Katz, 1991 • původně pro PKZIP 2 • kombinace slovníkové metody LZ77 a Huffmanova kódování 13
Metoda Deflate Phil Katz (1991) • Jean-loup Gailly, Mark Adler: zlib (1996)
http://www.gzip.org/zlib/rfc-deflate.html • LZSS + Huffmanův kód • velikost posuvného okna N = 32kB • velikost aktuálního okna F = 258B » délka shody 3..258
Vstup rozdělen do bloků, 3b hlavička • 1 bit: poslední blok ANO/NE • 2 bity: typ bloku 14
Deflate (pokračování) 3 typy bloků • 1: bez komprese • 2: fixní kódovací tabulky pro Huffmanův kód • 3: Huffmanův kód dle statistiky ze vstupních dat
Blok typu 3 • na začátku bloku 2 Huffmanovy stromy • jeden pro literály (0..255) a délky shody (3..258) » jediná abeceda 0..285 » 0..255 pro literály, 256 = end-of-block » 257..285 pro délku shody (+ extra bity)
• druhý pro posunutí 15
Deflate: kódování délky shody Code ---257 258 259 260 261 262 263 264 265 266
Extra Extra Bits Length(s) Code Bits Lengths ---- --------- ---- ------0 3 267 1 15,16 0 4 268 1 17,18 0 5 269 2 19-22 0 6 270 2 23-26 0 7 271 2 27-30 0 8 272 2 31-34 0 9 273 3 35-42 0 10 274 3 43-50 1 11,12 275 3 51-58 1 13,14 276 3 59-66
16
Extra Code Bits Length(s) ---- ---- ------277 4 67-82 278 4 83-98 279 4 99-114 280 4 115-130 281 5 131-162 282 5 163-194 283 5 195-226 284 5 227-257 285 0 258
Deflate: kódování posunutí Extra Code Bits Dist ---- ---- ---0 0 1 1 0 2 2 0 3 3 0 4 4 1 5,6 5 1 7,8 6 2 9-12 7 2 13-16 8 3 17-24 9 3 25-32
Extra Code Bits Dist ---- ---- -----10 4 33-48 11 4 49-64 12 5 65-96 13 5 97-128 14 6 129-192 15 6 193-256 16 7 257-384 17 7 385-512 18 8 513-768 19 8 769-1024
17
Extra Code Bits Distance ---- ---- -------20 9 1025-1536 21 9 1537-2048 22 10 2049-3072 23 10 3073-4096 24 11 4097-6144 25 11 6145-8192 26 12 8193-12288 27 12 12289-16384 28 13 16385-24576 29 13 24577-32768
Deflate (pokračování) Vyhledávání řetězců v prohlížecím okně -> hašování • tabulka obsahuje řetězce délky 3 • řetězce ve spojových seznamech uspořádány dle stáří • parametr omezující max délku seznamu
Rozšíření hladové strategie • nejprve se hledá primární shoda • posun okna o 1 znak, sekundární shoda, je-li výhodnější, kóduje se literál + sekundární shoda • rychlý režim: je-li primární shoda dostatečná, sekundární se neprovádí
Kompresní poměr 30 - 40 % pro textové soubory 18
Phillip Walter Katz 1962 – 2000 198? archivační program ARC (SEA) • shareware • distribuce včetně zdrojového kódu v C
Katz: shareware PKARC • stejný formát jako ARC • rychlejší, kritické funkce v asembleru
SEA podává žalobu • Katz použil zdrojový kód ARC • včetně komentářů a chyb • uživatelé stranili Katzovi ← jeho software rychlejší 19
Phillip Walter Katz 1989 PKZip 1993 PKZip 2 = Deflate • otevřený formát • standard pro kompresi souborů na různých platformách
U 2000 (alkohol) 2004 PKWARE: SecureZIP • PKZIP + 256 Bit AES Encryption
20
Datové struktury pro posuvné okno trie (information retrieval) – stromová reprezentace slovníku sufixový trie pro slovo x – reprezentuje všechny přípony slova x x = tata$ $ x = tata t a 5 t 5 a 4 a t t 3 a a 2 1
a t a $
t $
3
$
a
4 $
2
1
zarážka zajistí, aby každý list reprezentoval příponu slova x 21
Patricia – kompaktní trie Nevýhoda trie: kvadratická prostorová složitost Practical Algorithm to Retrieve Information Coded in Alphanumeric (D.R.Morrison, 1968) • obdržíme eliminací všech vrcholů různých od kořene, které mají jediného syna $ a 5 $ t 4
t a t a $
$
3
a
$ a 5 $
ta
$
ta 2
$ 1
1
$ 3
4 ta$ 2
Sufixový strom pro slovo x = kompaktní sufixový trie pro x 22
Sufixový strom T(abaabaab) 1 2 3 4 5 6 7 8 9
abaabaab$ baabaab$ aabaab$ abaab$ baab$ 3 aab$ ab$ b$ $
1,1 a 4,5 ab
b 2,2 9,9
b 2,2
9,9 $ 3,5 aab
$
8
6,9 9,9 aab$ $ 6
3,5 aab
6,9 aab$ $ 9,9 1 4
$
9,9 7
9
9,9
$
5
1 2 3 4 5 6 7 8 9 a b a a b a a b $ 23
6,9 aab$
2
Sufixový strom v posuvném okně Reprezentace textu v posuvném okně → sufixový strom Ukkonen (1992) • z T(x) vytvoří T(xa) pro a ∈ Σ v amortizovaném čase O(log α)
Fiala, Greene (1989) • z T(ax) vytvoří T(x) pro a ∈ Σ v amortizovaném čase O(1) • vyžaduje ukazatele z dětí na rodiče
M.Senft (2005) • komprese řízená sufixovým stromem 24
LZP (prediction, C.Bloom, 1996)
hašovací funkce
kontext délky N prohlížecí okno
aktuální okno
25
Komprese P:= hash(C); hash(C):= Q; L :=0; hašovací funkce Q
P
if P ≠ nil then L := max. délka shodné předpony řetězců P↑ a Q↑ fi if L = 0 then output znak Q↑ jako literál; posuň okno o 1 políčko doprava else output(L); posuň okno o L políček doprava fi 26
✎Problémy Start: prohlížecí okno:= prvních N znaků na vstupu for i:=1 to N do read(z); output(z)
Co když se řetězec P↑ neshoduje s kontextem C? Posun okna ⇒ nutná aktualizace všech ukazatelů v hašovací tabulce (a) vstup rozdělen do bloků, délka okna = délka bloku (b) okno = cyklická fronta C.Bloom: LZP: A new data compression algorithm, DCC‘96, p.425. http://www.cbloom.com/src/index_lz.html
27
LZP1 kontext délky N = 3 H = ((C>>11)^C) & 0xFFF
velikost tabulky = 212, 14b položky ⇒ délka okna = 214 příznak literál × délka L • • • •
1 dva literály 01 literál, L 00 L příznaky a délky v 1B, následují literály
literál - 8b ASCII délka L - kód v tabulce 28
LZP1 - příklad vstup: xyabcabcabxy výstup: "x""y""a""b""c""a""b"3"x""y" 11101101 "xyabcabxy"
LZP2 Literály kódovány statickým Huffmanovým kódem
29
LZP3 kontext délky N = 4, 16b hodnota hašovací funkce H = ((C >> 15)^C) & 0xFFFF
velikost tabulky = 216, položka tabulky = (ukazatel P, kontext C) while N>1 and (H(C) = nil or kontext H(C)↑ ≠ C) do H(C) := nil; N-if N=1 then output(literál)
30
LZP4 kontext C délky N = 5 I := kontext délky 4 H = ((I>>15)^I) & 0xFFFF bcde
nopq
a H P
31
Nevýhody LZ77 Omezený výhled prohlížecího okna • větší délka => » lepší komprese » náročnější prohledávání
Omezená délka aktuálního okna => • omezení délky shody
32
