a

Všimnime si, že v reťazci "AAAAAAAAAAAAUAAAAAAAAAAAAUUUAAAAAAAAAAAAAAAAAAAAAAAAUAAAAAAAAAAAAAA" máme veľa po sebe idúcich znakov A, raz za čas preuršovaných krátkou postupnosťou U. Ku každému znaku si teda vieme pripísať číslo - počet koľko krát sa daný znak zopakuje. Tak vieme skrátiť spŕavu na: "A12U1A12U3A24U1A14" - čo má dĺžku 18 znakov. Takýto spôsob skacovania (“kompresie”) rôznych postupností s veľa dlhými sekvenciami rovnakých znakov sa nazýva run length encoding.

b

Keď máme namiesto reťazca z a reťazec AUAUAUAU... alebo ľubovolný iný reťazec, kde sa znaky neopakujú po dlhých súvislých skupinách, ale sa častejšie nachádzajú “náhodne” premiešane po jednom alebo po dvoch po sebe idúcich znakoch, použiť run length encoding nám reťazec neskráti, ale naopak predĺži, keďže popridávame 1-ky a 2-ky za viac znakov ako skrátime dlhých opakujúcich sa postupností. Preto sa run length ecnoding nepoužíva na skracovanie obyčajného textu, keďže vo väčšine jazykov sa málokedy nachádza to isté písmeno 2- alebo viac-krát po sebe.

c

Síce všeobecne nevieme, aké slová to presne sú, ale vieme, že v reťazci sa nám budú často opakovať rôzne podreťazce. Stačí nám preto, aby sme ich pri prvom výskyte zapísali celé a pri každom ďalšom výskyte na ne odkázali párom dvoch čísel — vzdialenosťou od aktuálnej pozície k začiatku predchádzajúceho výskytu a dĺžkou podreťazca. Takým párom nahradíme každý ďalší výskyt daného podreťazca. Správu zo zadania by sme teda mohli upraviť napríklad takto: AhojDvaŤUŤMÁKtrLINUXHALDAktoakMOJKO(5,5)(34,6)kdeVZDUCH(35,5)velkaŠLAMASTIKA. Pôvodnú správu potom dešifrujeme zľava, takže pri čítaní odkazu už vždy existuje celý text, na ktorý sa odkazujeme. Spôsob kompresie založený na tomto princípe sa nazýva LZ77.

d

Jednoduchá verzia algoritmu by vyzerala nasledovne: Nastavíme si dolnú hranicu $w$, ktorá určuje, aký dlhý musí byť opakujúci sa podreťazec, aby sa oplatilo ho zapísať ako odkaz. Potom prechádzame pôvodný reťazec zľava doprava. Nech $i$ je aktuálna pozícia. Pre každé $i$ skúšame všetky predošlé pozície $j$ < $i$ a porovnávame znaky $c_{j+t}$ a $c_{i+t}$ pre $t = 0, 1, 2, \dots$, kým sa zhodujú a kým sme neprekročili koniec reťazca. Potom nech $k$ je dĺžka najdlhšej zhody pre dané $j$.

• Ak platí $k \geq w$, zapíšeme do skráteného reťazca pár $\left(i-j; k\right)$, teda vzdialenosť k začiatku zhody a jej dĺžku.
• Ak platí $k < w$, zapíšeme doslova znak $c_i$ a pokračujeme na pozíciu $i+1$.

Takýto algoritmus dosahuje v najhorších prípadoch časovú náročnosť $O\left(n^3\right)$. Prakticky sa zvykne zlepšovať tým, že ak vieme napríllad odhadnúť frekvenciu opakujúcich sa slov, tak si povieme, že nebudeme hladať pre každú pozíciu zhodu až úplne od začiatku, ale iba od pozície o nejakých $s$ indexov dozadu, kde $s$ si vieme nastaviť ako konštantu. Ak $s \ll n$, časová náročnosť bude v podstate lineárna.

e

V Lukášovom slovníku vidíme, že slová v ňom sa začínajú po nejakých skupinách veľmi podobne. Môžeme si teda slová zoradiť tak, aby po sebe následovali vždy slová, s čo najväčšou zhodou v prvých niekoľko znakoch. Napríklad takto:

• lukosprava
• lukostrelba
• luk
• luka
• lukas
• myxa
• myxopod
• myxophyta
• kucapaca
• kucho
• kuchar
• kucharka
• kucharkaKSP

Teraz využijeme podobnú myšlienku ako v d. Nebudeme však odkazovať na predošlé znaky, ale vždy iba na predošlé slovo. Potom namiesto prvých $m$ znakov každého slova napíšeme iba m, kde $m$ je počet, na koľko znakov sa začiatok (“prefix”) slova zhoduje s predošlím. Teda tento konkrétny príklad by sme zapísali:

• 0lukosprava
• 5trelba
• 3
• 3a
• 4s
• 0myxa
• 3opod
• 5hyta
• 0kucapaca
• 3ho
• 4ar
• 6ka
• 8KSP

Myšlienka takejto kompresie sa nazýva incremental encoding. Zvykne sa používať napríklad v rôznych implementáciach dátovej štruktúry dictionary (“slovník”).

f

Zo slov v zozname si môžeme zostaviť písmenkový strom. Ten vieme následne prehľadávať do hĺbky. Teda vždy ideme po jednej vetve stromu a keď prídeme na koniec do jej listového (posledného) vrcholu, až vtedy sa presunieme na najposlednejšie odvetvenú neprejdenú vetvu. Slová do zoradeného zoznamu budeme zapisovať postupne, ako sa dostaneme do ich listových vrcholov.

g

Zišlo by sa nám nájsť nejakú inú postupnosť $n$ čísel, v ktorej členy $b_1,b_2,\dots,b_n < k$. Zadanie nám prezradilo, že pre každé $i$ v pôvodnej postupnosti platí $a_{i + 1} - a_i < k$. Tak prečo si nezapamätať iba tieto rozdiely dvoch po sebe idúcich čísel v postupnosti? Teda pre $b$-čkovú postupnosť bude platiť

[ b_1 = 0,\ b_2 = a_2-a_1,\ b_3 = a_3-a_2,\ \dots,\ b_{n-1} = a_{n}-a_{n-1}. ]

Zapamätáme si ešte $a_1$, keďže môžeme si pamätať najviac jedno číslo väčšie ako $k$. Potom vieme zistiť každé pôvodné $a_i$ spočítaním súčtu $a_i = a_1 + b_1 + b_2 + \dots + b_i$. Kompresia pomocou rozdielov sa nazúva delta encoding.

h

V tejto postupnosti máme oproti g výhodu, že rozdiel každých dvoch po sebe idúcich členov je konštantný, a to $1$. Stačí tak uložiť iba prvý člen $a$ a dĺžku $n$, pretože z týchto dvoch čísel vieme celú postupnosť jednoznačne zrekonštruovať. Obe hodnoty majú zároveň najviac $n$ číslic: číslo $a$ je najviac $10^n-+$ , takže má najviac $n$ číslic, a aj samotné $n$ má najviac $n$ číslic. Keďže zoznam vieme prechádzať len raz, počas jedného prechodu si teda stačí zapamätať prvý prvok a priebežne počítať počet členov.