Основно съдържание

Компютрите и интернет

Курс: Компютрите и интернет > Раздел 1

Урок 7: Компресия на данни

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[Дискусия]

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

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

[Източници ]

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

[Къде е това?]

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

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

Сортирай по:

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

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