Bezstratna kompresja tekstu

Jak komputer może skompresować tekst? Oto wskazówka: wiele osób codziennie kompresuje tekst, kiedy piszą SMS-y i nie chcą dużo pisać.

Na przykład: jeśli chcę powiedzieć "Great, see you later!", mógłbym wpisać Gr8, see u l8r!"

Skróciłem ten tekst, szukając powtarzających się ciągów i zastępując je krótszymi ciągami ("8" i "u").

Algorytm kompresji

Komputery mogą skompresować tekst w podobny sposób, poprzez znalezienie powtarzających się sekwencji i zastąpienie ich krótszymi reprezentacjami. Nie muszą się martwić, czy wynik końcowy będzie brzmiał tak samo, więc mogą skompresować go jeszcze bardziej.

Spróbujmy z tym cytatem Williama Shakespeare'a:

to be or not to be, that is the question

Najbardziej oczywiste powtarzające się sekwencje to "to" i "be", więc komputer może je przedstawić za pomocą znaku, który nie jest częścią oryginalnego tekstu, jak:

⊜ ⬗ or not ⊜ ⬗, that is the question

Każda powtarzająca się sekwencja może zostać zastąpiona, nawet jeśli nie jest to całe słowo, więc komputer może również zastąpić "th":

⊜ ⬗ or not ⊜ ⬗, ⟡at is ⟡e question

Komputer musi również przechowywać tabelę wykonanych przez siebie zamienników, aby móc zrekonstruować oryginał.

zastąpienie	oryginał
⊜	to
⬗	be
⟡	th

Sprawdź swoją wiedzę

Zobacz, czy znajdziesz sposób na skompresowanie tego fragmentu z Dr. Seussa:

I am Sam, 
Sam I am.
That Sam-I-am! That Sam-I-am!
I do not like that Sam-I-am! 
Do you like green eggs and ham?
I do not like them, Sam-I-am.
I do not like green eggs and ham.

Którą sekwencję można by zastąpić, aby skompresować tekst?

Wielkość kompresji

Jak widzisz, niektóre teksty mogą być dość mocno skompresowane - więcej powtórzeń oznacza większą kompresję.

Niektóre teksty nie mogą być w ogóle skompresowane, jak alfabet:

ABCDEFGHIJKLMNOPQRSTUVWXYZ

W rzeczywistości "skompresowana" wersja alfabetu może zajmować więcej bajtów niż wersja oryginalna, w zależności od tego, czy algorytm umieści w pliku dodatkowe metadane.

🤔 Czy możesz sobie wyobrazić inne przykłady tekstu, który nie zmniejszyłby się w wyniku kompresji? A co z przykładami, które naprawdę dobrze by się skompresowały?

Nie mamy nic przeciwko temu, że kompresja nie gwarantuje mniejszego pliku, ponieważ ogólnie rzecz biorąc, większość plików zawiera powtarzające się sekwencje i korzysta z kompresji.

🔍 Jeśli chciałbyś dowiedzieć się więcej na temat tego typu kompresji, możesz zbadać algorytm Lempel-Ziv-Welch (LZW).

Ten artykuł jest na podstawie "Coding - Compression," by CS Field Guide (CC BY-NC-SA 3.0). Zobacz oryginalny artykuł na http://csfieldguide.org.nz/en/chapters/coding-compression.html.

Dodatkowe źródła:

Huffman coding. (2018, September 19). Retrieved October 2, 2018 from Wikipedia: https://en.wikipedia.org/wiki/Huffman_coding
Portable Network Graphics. (2018, September 26). Retrieved October 2, 2018 from Wikipedia: https://en.wikipedia.org/wiki/Portable_Network_Graphics
Run-length encoding. (2018, September 25). Retrieved October 2, 2018 from Wikipedia: https://en.wikipedia.org/wiki/Run-length_encoding

🙋🏽🙋🏻‍♀️🙋🏿‍♂️Masz pytania związane z tym zagadnieniem? Możesz zadać swoje pytanie poniżej!

Chcesz dołączyć do dyskusji?

Zaloguj się

Sortuj według

Na razie brak głosów w dyskusji

Rozumiesz angielski? Kliknij tutaj, aby zobaczyć więcej dyskusji na angielskiej wersji strony Khan Academy.