Josef Troch (troch@mail.ru)
29.8.2000 (poslední změna 8.11.2000)

• Pokud jsou první 4 bity nulové, pak tento kód je kódem literal tokenu a další 4 bity kódují délku řetězce x v rozmezí [1..16]. Za tímto kódem tedy musí následovat x kódů ASCII znaků.
• V opačném případě (alespoň jeden z prvních 4 bitů nenulový) se jedná o kód copy tokenu a první 4 bity udávají délku x v rozmezí [2..16] a dalších 12 bitů je vzdálenost y (odkud kopírovat) v rozmezí [1..4096].

• Pokud je kompresor v "počátečním" stavu (právě dokončil copy token nebo ukončil literal token kvůli limitu na 16 znaků či jde o úplný začátek komprese):
  • Pokud nejdelší shoda (s předponou slova v aktuálním okně), kterou se kompresoru podaří najít (v prohlížecím okně) je délky alespoň 2, bude zapsán copy token.
  • Jinak začneme zapisovat literal token.
• V opačném případě (tedy kompresor je někde uprostřed zapisování literal tokenu) literal token budeme prodlužovat dokud neobjevíme shodu délky alespoň 3, nebo dokud nedosáhneme délkového limitu na délku literal tokenu (16).
  Pozn.: Zapsáním literal tokenu myslím samozřejmě zapsání vlastního tokenu (= 8 bitů) + zapsání příslušných ASCII kódů.

Obrázek 1

Obrázek 2

• Řetězce v závorkách nejsou reprezentovány přímo v datové struktuře, ale mohou být získány z dvojic [position,level] v uzlech.
• Position označuje, na které pozici v souboru začíná slovo reprezentované na obrázku celou cestou od kořene.
• Level udává kolik písmen se má použít pro vytvoření příslušného slova (Pozn.: všechny listy odpovídají slovům, která začínají na různých místech v souboru, ale pokračují až do konce souboru)
• Tučná šipka na obrázku znázorňuje "suffix pointer", o kterém se zmíním později

Obrázek 3

• Listy stromu dáme do cyklického bufferu (fronty), takže bude snadné identifikovat a odstranit nejstarší list.
• Vnitřním vrcholům přidáme položku "počet synů". Když nějakému vnitřnímu vrcholu tato položka klesne na 1, tento vrchol smažeme a z hrany vedoucí do tohoto vrcholu a z hrany vedoucí z tohoto vrcholu vytvoříme hranu jedinou.
  Lze ukázat, že výše uvedené odstanění vnitřního uzlu nikdy nezpůsobí to, že by nějaký existující suffix pointer ukazoval na tento (již smazaný) uzel.

• Každému vnitřnímu uzlu přidáme "update bit".
• Pokud je update bit=1 při aktualizaci uzlu, změníme update bit na 0 a pokračujeme v aktualizaci (rekursivně) u otce tohoto uzlu.
• V opačném případě (update bit=0 při updatu uzlu), změníme update bit na 1 a skončíme s aktualizací pointerů.

• Máme vytvořen list v₁
• Použijeme suffix pointer otce uzlu v₁ k nalezení uzlu v₃.
• Odtud jdeme ve stromě dolů do v₄ (rescanning - máme hledaný suffix pointer) a pak "scanning".
• Odtud provedeme částečný update (pohybujíce se směrem ke kořeni) - nastavujeme "position" na aktuální pozici v souboru a nastavujeme update bity na 0, dokud nenajdeme uzel, jehož update bit je roven 0.
• V cyklickém bufferu listů nahradíme nejstarší list novým listem.
• Pokud otec (označme ho p) nejstaršího listu má teď pouze jediného syna, musí být p rovněž smazán a zbylý syn je připojen k bývalému otci vrcholu p.
  Pak provedeme částečný update začínajíce s pozicí smazaného vnitřního uzlu s tím rozdílem, že v každém kroku porovnáme pozici, kterou propagujeme z dola s pozicí, která už ve zkoumaném uzlu je a s tou novější z nich pokračujeme výše do stromu (tedy vůbec nepoužíváme aktuální pozici v souboru).

void sss(int start,int step,int stop,int cislo)
       //start, step, stop: jaky kod pouzit; cislo: cislo k zakodovani
{int k=start;
 while (cislo>=(1<<k))    //(1<<k) je jiny zapis pro 2 na k
              //zde kontroluji, zda se cislo vejde uz do teto
   {zapisbit(1);          //skupiny kodu, jinak zvetsuji n
    cislo-=(1<<k);
    k+=step;
   }                      //mam prislusny unarni kod
 if (k!=stop) zapisbit(0);
 putchar(':');
 zapbin(cislo,k);         //zapisu prislusne binarni cislo
}

1. Protože za řetězcem literálů kratším než maximální možná délka (63) nemůže následovat ani další literal token, ani copy token délky 2, posuneme kód délky v následujícím copy tokenu o 2 dolů - tedy kódy 000, 001, 010 budou znamenat shodu v 3, 4, 5 znacích (místo literal, 2, 3). Tímto způsobem se zvětší (ve výše uvedeném případě) maximální zakódovatelná délka v copy tokenu na 2046 bytů.
   
   
2. Jelikož pro kódování začátků souborů, či souborů krátkých nepotřebujeme velikost okna celých 21K, použijeme pro ukládání odkazu na pozici v copy tokenu kód se vzrůstající délkou, tedy (10 - x, 2, 14 - x) kód, kde x je na začátku 10 a klesá až na 0 podle toho, jak se prohlížecí okno postupně zaplňuje.
   Tedy kód, kde x = 10 (který se použije na začátku) má 21 hodnot, v okamžiku, kdy počet znaků v okně (tedy platných pozic) přesáhne 21, snížíme x na 9 atd.
   Je dobré si uvědomit, že toto vylepšení se použije jen na začátku komprese, dokud celé 21K velké okno není zaplněno - výrazné zkrácení se tedy projeví jen u malých souborů.
   
   
3. Každý z výše uvedených kódů je schopen adresovat pevný počet pozic (od 21 pro x=10 po 21504 pro x=0). Pokud ještě okno není zcela zaplněno, či uživatel se rozhodne použít prohlížecí okno menší velikosti, nejdelší z kódů by nebyly nikdy použity (protože by to byly odkazy na neplatné pozice v prohlížecím okně - t.j. zatím nezaplněné, či při menší velikosti okna pozice za levým okrajem okna).
   Z tohoto důvodu se zde používá fázování při zápisu binární části start-step-stop kódu odkazu na pozici. Tedy místo zapsání všech hodnot k-bitově, nižší hodnoty jsou zapsány jako kratší (k-1 bitová) čísla a vyšší hodnoty jako k bitová.
   Přesněji (už jen pro binární čísla) - potřebujeme-li používat čísla 0..p-1, kde 2^k-1 < p < 2^k, číslo i zapíšeme takto: je-li i < 2^k - p, použijeme k - 1 bitový binární kód čísla i; v opačném případě použijeme k bitový binární kód čísla i + 2^k - p.
   Příklad: uživatel se rozhodne používat prohlížecí okno velikosti 16384 B, tedy je nutno použít (10, 2, 14) kód ( (9, 2, 13) kód má jen 10752 hodnot). Tento má 21504 hodnot, tedy nejdelších 5120 by nebylo nikdy použito. Poslední skupina kódů ("11" následováno 14 bitovým číslem) má 16384 různých hodnot, ze kterých by se použilo jen prvních 11264. Místo toho budeme zapisovat prvních 5120 z nich jako "11" a 13 bitové číslo a zbylých 6144 jako "11" a 14 bitové číslo.

Obrázek 4

1. "abcc..."
   Pak se použije NodeCopy, protože nejdelší shoda pro tento řetězec ve stromě je "abc" - tento řetězec končí jeden znak za uzlem 3 na hraně do uzlu 2. Tedy po bitovém identifikátoru bude zakódována dvojice (2, 1) příslušnými binárními kódy.
2. "abcaaacb..."
   Pak bude použito LeafCopy - nejdelší shoda končí na hraně mezi uzlem 2 a listem 3, proto po bitovém identifikátoru bude zapsána (start-step-stop kódy) dvojice (2, 3).
3. "cacbaac..."
   Pak bude následovat řetězec literálů - tedy zapíše se flag pro LeafCopy, pak příslušný (1, 1, 11) start-step-stop kód pro 0, pak (0, 1, 5) kód délky řetězce (až dokud se nenajde shoda alespoň 2 znaky), tedy zde kód pro 3 a pak následují příslušné znaky - zde "cac".

Použitá literatura:

1. E.R.Fiala, D.H.Greene: Data compression with finite windows. Communications of ACM, 32(4), 490-505, April 1989.
2. T:C.Bell, J.G.Cleary, I.H.Witten: Text Compression. Prentice Hall, Englewood CLiffs, NJ, 1992, odstavec 8.3.12.
3. Salomon D. - Data Compression, Springer, New York 1997, odstavec 3.6.

Zhodnocení literatury