Компресия на текст без загуби

Как компютър може да компресира текст? Една подсказка – много хора компресират текст ежедневно, когато пишат текстови съобщения и не искат да пишат много.

Например: Ако искам да кажа "Здравей, какво правиш?", мога да напиша "здр кп?"

Намалих текста, като замених често използваната в началото на разговор фраза със съкратения ѝ вариант от съвременната чат-култура ("здр кп").

Алгоритъм за компресиране

Компютрите могат да компресират текст по сходен начин, като намират повтарящи се последователности и ги заменят с техни по-кратки аналози.

Да опитаме с този цитат от Иван Вазов:

...син съм на земя прекрасна,
син съм на юнашко племе.

Най-очевидните повтарящи се последователности са "син" и "съм", така че компютърът може да ги представи чрез символ, който не е част от оригиналния текст, като:

...⊜ ⬗ на земя прекрасна, ⊜ ⬗ на юнашко племе.

Всяка повтаряща се последователност може да бъде заменена, дори и да не е цяла дума, така че компютърът може да замени и "на":

⊜ ⬗ ⟡ земя прекрас⟡,
⊜ ⬗ ⟡ ю⟡шко племе

Компютърът трябва да запази и таблицата със замествания, която е създал, за да може да пресъздаде оригинала.

заместване	оригинал
⊜	син
⬗	съм
⟡	на

Провери наученото

Потърси начини да компресираш част от "Аз съм българче" на Иван Вазов:

Аз съм българче. Обичам
наште планини зелени,
българин да се наричам -
първа радост е за мене.
Аз съм българче свободно,
в край свободен аз живея,
всичко българско и родно
любя, тача и милея.

Кои последователности могат да се заменят, за да се компресира текстът?

Размер на компресията

Както виждаш, някои текстове могат да се компресират доста — повече повторения означават по-голяма компресия.

Някои текстове изобщо не могат да се компресират, като азбуката например:

АБВГДЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЬЮЯ

Всъщност "компресирана" версия на азбуката може да заеме повече байтове за представяне, отколкото оригиналната версия, в случай че алгоритъмът добави допълнителна мета-информация във файла.

🤔 Можеш ли да се сетиш за други примери за текст, който няма да стане по-малък при компресия? А за примери, които ще се компресират наистина добре?

Ако си в класната стая, има страхотни въпроси, които могат да бъдат обсъдени с твоите съученици.

Ако не си, можеш да споделиш мислите си в дискусионния форум на Кан Академия. Първо се увери, че статията е отворена в страницата на урока, а не като изскачащ прозорец. После се придвижи надолу по страницата и намери областта "Съвети и благодарности", където можеш да публикуваш твоите мисли.

Не е проблем, че компресията не ни гарантира по-малък файл, тъй като в общия случай повечето файлове съдържат повтарящи се последователности и компресията върши работа.

🔍 Ако искаш да научиш повече за този тип компресия, можеш да проучиш алгоритъма на Лемпел-Зив-Уелч (Lempel-Ziw-Welch LZW).

Тази статия е адаптирана от "Кодиране - компресия" от Наръчник по Компютърни науки (CC BY-NC-SA 3.0). Виж оригиналата пълна статия на http://csfieldguide.org.nz/en/chapters/coding-compression.html.

Допълнителни препратки:

Кодиране на Хъфман. (19.08.2018). Извлечено на 02.10.2018 от Wikipedia: https://en.wikipedia.org/wiki/Huffman_coding
Преносими мрежови графики. (26.09.2018). Извлечено на 02.10.2018 от Wikipedia: https://en.wikipedia.org/wiki/Portable_Network_Graphics
Кодиране по дължина. (25.10.2018). Извлечено на 02.10.2018 от Wikipedia: https://en.wikipedia.org/wiki/Run-length_encoding

🙋🏽🙋🏻‍♀️🙋🏿‍♂️Имаш ли въпроси по темата? Ще се радваме да ти отговорим, просто задай въпросите си по-долу!

Ако не виждаш въпросите по-долу, или използваш мобилното приложение, или четеш тази статия в изскачащ прозорец. Ако използваш мобилното приложение, отвори статията в някакъв браузър. Ако си в изскачащ прозорец, щракни върху заглавието на статията отгоре.

Искаш ли да се присъединиш към разговора?

Вписване в профила

Сортирай по:

Все още няма публикации.

Разбираш ли английски? Натисни тук, за да видиш още дискусии в английския сайт на Кан Академия.