fbpx
0.2 C
София

Основите на LZW компресията на данни

Оригиналът е на Sooraj Bhat. много популярен преподавател по информатика от близкото минало

Най-четени

Даниел Десподов
Даниел Десподовhttps://www.kaldata.com/
Новинар. Увличам се от съвременни технологии, информационна безопасност, спорт, наука и изкуствен интелект.

Ако отворите който и да е файл в своя компютър и го прегледате байт след байт, със сигурност ще ви направи впечатление, че има голям брой повтарящи се елементи. LZW е метод за компресия на данни, който използва именно това повтаряне на големи и малки поредици от байтове. Оригиналният алгоритъм на LZW компресията е създаден от именитите  Ейбрахам Лемпел и Якоб Зив и се нарича LZ78 компресия. През 1984 година алгоритъмът е усъвършенстван от Тери Уелч, откъдето идва и неговата абревиатура LZW (Lempel, Ziv and Welch).

Както при всеки адаптивен и динамичен метод за компресия, идеята в основни линии е следната. Първо, получаване на обекта за компресиране – обикновено файл. Второ, прочитане на данните на части и трето, обновяване на вече изградения модел и кодиране на данните при придвижването от начало до към края на файла. LZW е алгоритъм за компресия на данни, при който се използва речник. Това означава, че вместо бройките на всички символи в даден файл да бъдат сведени в таблица и да бъде изградено дърво на техните количества (както е при компресията на Хъфман), LZW кодира данните с помощта на речник.

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

Компресията

LZW започва с речник от 256 символа, което в случая е 8 бита, като ги използва във вид на стандартния комплект от ASCII символи. След това започва да прочита данните по 8 бита наведнъж (например ‘t’, ‘r’ и т.н.) и ги кодира във вид на число, което оставя като индекс в речника. Всеки път, когато се срещне нова поредица от символи (например  „tr“), той я добавя в речника. От друга страна, ако бъде прочетена поредица, която вече е срещана, то алгоритъмът просто прочита нов символ и го свързва с текущия низ, за да се получи нов подниз.

Следващият път, когато LZW отново срещне същата поредица от символи, то тя ще бъде кодирана с помощта на число. Обикновено за използвания речник твърдо се задава максималното число на възможните записи – примерно 4096, за да не се изчерпи паметта на компютърното устройство. По този начин кодовете, които заемат мястото на поднизовете в този пример, са с дължина 12 бита (2^12 = 4096). За да бъде осъществена компресията е необходимо кодовете да имат по-голяма битова дължина в сравнение с символите (12 бита срещу 8 бита). На пръв поглед изглежда, че има излишък, но в крайна сметка вместо големия брой често срещащите се поднизове се използва само един код, и по този начин се постига значителна компресия на данните.

Ето как описаното до тук може да бъде представено във вид на псевдокод:

string s;
char ch;
...

s = empty string;
while (there is still data to be read)
{
    ch = read a character;
    if (dictionary contains s+ch)
    {
	s = s+ch;
    }
    else
    {
	encode s to output file;
	add s+ch to dictionary;
	s = ch;
    }
}
encode s to output file;

Нека сега да предположим, че нашият входен поток, който искаме да компресираме, е поредицата символи „banana_bandana“, като при това искаме да използваме само следния начален речник:

Index   Entry
  0       a
  1       b
  2       d
  3       n
  4       _ (space)

Фазите на самата компресия ще изглеждат по следния начин:

Входен поток Текущ стринг Имало ли го е досега? Кодираният изход Нов запис в речника/индекс
b b yes nothing none
ba ba no 1 ba / 5
ban an no 1,0 an / 6
bana na no 1,0,3 na / 7
banan an yes no change none
banana ana no 1,0,3,6 ana / 8
banana_ a_ no 1,0,3,6,0 a_ / 9
banana_b _b no 1,0,3,6,0,4 _b / 10
banana_ba ba yes no change none
banana_ban ban no 1,0,3,6,0,4,5 ban / 11
banana_band nd no 1,0,3,6,0,4,5,3 nd / 12
banana_banda da no 1,0,3,6,0,4,5,3,2 da / 13
banana_bandan an yes no change none
banana_bandana ana yes 1,0,3,6,0,4,5,3,2,8 none

Обърнете внимание, че след прочитането на последния символ – „a“, трябва да бъде изведен последния подниз „ana“.

Декомпресията

Процесът на декомпресията на LZW също е съвсем лесен. Освен това, той има сериозно преимущество пред статичните методи за компресия, понеже за алгоритъма за декомпресиране не се изисква речник или каквато и да било друга допълнителна информация. При декомпресирането автоматично се създава речник, идентичен на речника, който е използван по време на компресията. Важен момент е, че програмите за компресия и декомпресия задължително трябва да започнат с един и същ начален речник, който в дадения случай включва всичките 256 символа на ASCII таблицата.

Ето как работи всичко това. LZW алгоритъмът за декомпресия първоначално прочита индекса, който винаги е цяло число, след което търси този индекс в началния речник и извежда съответния подниз, който съответства на този индекс. Първият символ на този подниз се добавя към текущата поредица от символи. Тази нова конкатенация се добавя в речника (процесът е подобен на това, което става при компресирането). След това декомпресираният низ става текущия работен низ, а текущият индекс с неговия подниз, се запомня. Този процес се повтаря до приключване на декомпресията.

Ето как може да изглежда това във вид на псевдокод:

string entry;
char ch;
int prevcode, currcode;
...

prevcode = read in a code;
decode/output prevcode;
while (there is still data to read)
{
    currcode = read in a code;
    entry = translation of currcode from dictionary;
    output entry;
    ch = first char of entry;
    add ((translation of prevcode)+ch) to dictionary;
    prevcode = currcode;
}

Съществува изключение, когато LZW алгоритъмът не работи. Това се случва когато кодът извиква индекс, който все още не е въведен – например индекс 31, когато индексът 31 в настоящия момент се обработва и все още го няма в речника. Един пример от Sayood добре показва този момент. Да предположим, че работите със стринга ababababab….. и начален речник съответно с индекси само 0 и 1. Започва процеса на компресия:

Входен поток Текущ стринг Имало ли го е досега? Кодираният изход Нов запис в речника/индекс
a a yes nothing none
ab ab no 0 ab / 2
aba ba no 0,1 ba / 3
abab ab yes no change none
ababa aba no 0,1,2 aba / 4
ababab ab yes no change none
abababa aba yes no change none
abababab abab no 0,1,2,4 abab / 5

И така, изходният поток започва с индексите 0, 1, 2 , 4… Когато започнем декомпресията възниква проблем (за показаната по-горе таблица трябва да се знае, че текущият стринг е просто подниз, който е бил декодиран при последната итерация на цикъла. Освен това новият запис в речника се създава чрез добавяне на текущия низ с първия символ на новия речник):

Входен поток

Входен поток Преобразуване чрез речника декодиран изход Текущ стринг Нов запис в речника/индекс
0 0 = a a none none
0,1 1 = b ab a ab / 2
0,1,2 2 = ab abab b ba / 3
0,1,2,4 4 = ??? abab??? ab  

Виждаме, че декодерът на декомпресиращият алгоритъм се сблъсква с индекса 4, като в същото време низът на този индекс 4 все още се обработва. За да разберем защо става така, нека да погледнем таблицата на компресирането. Веднага след като низът „aba“ с индекс 4 се записва в речника, следващият подниз отново е „aba“ – тоест следващият код, записан в компресирания изходен файл, ще бъде 4. Получава се така, че този сценарий може да възникне само в случай, че поднизът започва из завършва с един и същи символ („aba“ има вид на <char><string><char> или <символ><низ><символ>. Тоест, за да се справим с това изключение е необходимо да се вземе подниза, който вече е получен – „ab“ и неговият първи символ да се добави към самия него – тоест, „ab „+“a“ = „aba“, вместо да се следва стандартната процедура на алгоритъма. Ето защо показаният по-горе псевдокод трябва да бъде леко променен, за да се избегне това изключение.

Достойнства и недостатъци на LZW алгоритъма за компресиране на данни

+ Не се изисква изчисляване вероятността на срещаните символи или байтове
+ При декомпресирането не се налага да се съхранява речник с голям размер. Алгоритъмът работи по такъв начин, че речникът автоматично се възстановява, като се използват само данните от компресирания файл
+Този тип компресия е компресия без загуби, която не прави никакви промени, ако се използва за намаляване размера на графичните файлове. Алгоритъмът е изключително подходящ за компресиране на растерни изображения от всякакъв вид
– алгоритъмът не прави анализ на входните данни и не е оптимален

Използване на LZW алгоритъма

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

Популярността на LZW алгоритъма до голяма степен се дължи на изключително успешната програма compress. Публикуваният сорс-код на тази програма осъществява както компресия, така и декомпресия, като неговата дължина е едва 1200 реда. Ядрото на кода за компресия е с дължина едва стотина реда, а сорс кодът на ядрото за декомпресия е само с няколко реда по-дълъг.

LZW дава възможност за постигането на една от най-добрите компресии в сравнение с другите методи за компресия на графични данни, при пълното отсъствие на каквито и да било изкривявания и промени. Към днешен ден той се използва във файловите формати TIFF, PDF, GIF, PostScript и други. LZW частично се използва и в редица популярни програми за компресия на всякакви файлове – ZIP, ARJ, LHA и т.н.

 


Коментирайте статията в нашите Форуми. За да научите първи най-важното, харесайте страницата ни във Facebook, и ни последвайте в Telegram и Viber или изтеглете приложението на Kaldata.com за Android, iOS и Huawei!

Абонирай се
Извести ме за
guest

0 Коментара
Отзиви
Всички коментари

Нови ревюта

Подобни новини