Splošno stiskanje

Splošne metode stiskanja morajo biti brez izgub, saj ne moremo domnevati, da uporabnika ne bo motilo, če bodo podatki spremenjeni. Najpogosteje uporabljeni algoritmi za stiskanje splošnega namena (npr. ZIP, GZIP in RAR) temeljijo na metodi, imenovani »Kodiranje Ziv-Lempel«, ki sta jo 1970-ih letih izumila Jacob Ziv in Abraham Lempel.

To metodo si bomo ogledali na primeru besedilne datoteke. Glavna ideja kodiranja Ziv-Lempel je, da se v datotekah zaporedja znakov pogosto ponavljajo, zato namesto shranjevanja ponavljajočega se zaporedja preprosto shranimo samo sklic na mesto, kjer se je zaporedje nazadnje pojavilo. Dokler je sklic manjši od zamenjanega zaporedja, bomo na ta način prihranili prostor. S tem pristopom lahko zmanjšamo besedilne datoteke na eno četrtino prvotne velikosti, kar je približno tako dobro kot katera koli metoda, ki je prilagojena samo za stiskanje besedila.

Interaktivna vaja ti omogoča raziskovanje te ideje. Prazna polja so zamenjana s sklici na prejšnje dele besedila. V posamezno polje lahko klikneš, da vidiš, kam kaže sklic ter, da lahko v polje vneseš referenčne črke za odkodiranje besedila. Kaj se zgodi, če sklic kaže drugam? Dokler sklice odkodirate od prvega do zadnjega, bodo informacije na voljo, preden jih potrebuješ. Svoje besedilo lahko vneseš tudi tako, da klikneš zavihek »Besedilo« in svoje besedilo prilepiš ter si ogledaš, koliko znakov bo zamenjanih s sklici.

Sklici so dejansko sestavljeni iz dveh številk: prvo število, ki pove, koliko znakov nazaj je treba prešteti do začetka prejšnje fraze, in drugo število, ki pove, kako dolga je fraza, na katero se sklicujemo. Vsak sklic običajno zavzame prostor enega ali dveh znakov, torej metoda privarčuje prostor, dokler s sklici zamenjuje vsaj dva znaka. Interaktivna vaja omogoča tudi, da s sklici zamenjujemo vsaj dva znaka ter se tako izognemo zamenjavam enega znaka. Pri stiskanju štejejo vsi znaki, ne samo črke, zato se metoda lahko sklicuje tudi na presledke med besedami. Pravzaprav je eno izmed najbolj pogostih zaporedij, na katera se sklicujemo, zaporedje pike in presledka.