Komprese textu

Jak komprimuje počítač text? Zde je nápověda: text komprimuje denně spousta lidí, když píšou textové zprávy a nechce se jim moc psát.

Například: Pokud chci říct "Great, see you later!" (česky Super, uvidíme se později), můžu jednoduše napsat "Gr8, see u l8r!"

Text jsem zkrátil tak, že jsem vyhledal opakované sekvence a nahradil je kratšími sekvencemi ("8" a "u").

Počítače mohou text zkomprimovat podobným způsobem. Naleznou opakované sekvence a nahradí je kratšími reprezentacemi. Nemusí se přitom obávat, aby konečný výsledek zněl stejně jako originál, jak to dělají lidé, takže toho můžou zkomprimovat mnohem víc.

Pojďme si to vyzkoušet na následujícím citátu od Williama Shakespeara:

to be or not to be, that is the question (být nebo nebýt, to je otázka)

Nejzjevnější opakované sekvence jsou "to" a "be", takže je může počítač reprezentovat znakem, který není součástí původního textu, a to následovně:

Jakákoli opakovaná sekvence může být nahrazena, i když se nejedná o celé slovo, počítač může nahradit i "th":

Počítač si potřebuje ukládat tabulku se změnami, které provedl, aby mohl rekonstruovat originál.

Jak vidíš, některé texty lze zkomprimovat docela hodně — více opakovaných sekvencí znamená větší kompresi.

Nějaké texty nelze zkomprimovat vůbec, jako například abecedu:

Ve skutečnosti by "komprimovaná" verze abecedy zabrala více bajtů než původní verze, v závislosti na tom, zda algoritmus do souboru vloží další metadata (to jsou data, která poskytují informaci o jiných datech).

🤔 Napadá tě nějaký jiný příklad textu, který by se kompresí nezmenšil? A co příklad textu, který by šel zkomprimovat hodně dobře?

Vůbec nám nevadí, že komprese nezaručuje menší soubor, protože obecně většina souborů obsahuje opakované sekvence a z komprese benefituje.

🔍 Pokud se chceš dozvědět více o tomto typu komprimace, můžeš si prozkoumat Lempelův-Zivův-Welchův algoritmus.