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

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

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

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

Как компютър може да компресира текст? Една подсказка – много хора компресират текст ежедневно, когато пишат текстови съобщения и не искат да пишат много.
Например: Ако искам да кажа "Здравей, какво правиш?", мога да напиша "здр кп?"
Намалих текста, като замених често използваната в началото на разговор фраза със съкратения ѝ вариант от съвременната чат-култура ("здр кп").

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

Компютрите могат да компресират текст по сходен начин, като намират повтарящи се последователности и ги заменят с техни по-кратки аналози.
Да опитаме с този цитат от Иван Вазов:
...син съм на земя прекрасна, син съм на юнашко племе.
Най-очевидните повтарящи се последователности са "син" и "съм", така че компютърът може да ги представи чрез символ, който не е част от оригиналния текст, като:
...⊜ ⬗ на земя прекрасна, ⊜ ⬗ на юнашко племе.
Всяка повтаряща се последователност може да бъде заменена, дори и да не е цяла дума, така че компютърът може да замени и "на":
⊜ ⬗ ⟡ земя прекрас⟡, ⊜ ⬗ ⟡ ю⟡шко племе
Компютърът трябва да запази и таблицата със замествания, която е създал, за да може да пресъздаде оригинала.
заместванеоригинал
син
съм
на
Провери наученото
Потърси начини да компресираш част от "Аз съм българче" на Иван Вазов:
Аз съм българче. Обичам
наште планини зелени,
българин да се наричам -
първа радост е за мене.
Аз съм българче свободно,
в край свободен аз живея,
всичко българско и родно
любя, тача и милея.
Кои последователности могат да се заменят, за да се компресира текстът?
Избери всички правилни отговори:

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

Както виждаш, някои текстове могат да се компресират доста — повече повторения означават по-голяма компресия.
Някои текстове изобщо не могат да се компресират, като азбуката например:
АБВГДЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЬЮЯ
Всъщност "компресирана" версия на азбуката може да заеме повече байтове за представяне, отколкото оригиналната версия, в случай че алгоритъмът добави допълнителна мета-информация във файла.
🤔 Можеш ли да се сетиш за други примери за текст, който няма да стане по-малък при компресия? А за примери, които ще се компресират наистина добре?
Не е проблем, че компресията не ни гарантира по-малък файл, тъй като в общия случай повечето файлове съдържат повтарящи се последователности и компресията върши работа.
🔍 Ако искаш да научиш повече за този тип компресия, можеш да проучиш алгоритъма на Лемпел-Зив-Уелч (Lempel-Ziw-Welch LZW).
🙋🏽🙋🏻‍♀️🙋🏿‍♂️Имаш ли въпроси по темата? Ще се радваме да ти отговорим, просто задай въпросите си по-долу!

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

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