LZW метод алгоритъм за компресиране - изпълнение LZW алгоритъм за компресиране, използвайки възможностите
- избран първия символ от входния поток;
- избран съответния двоично дърво в речника;
- избира следващия знак от входния поток;
- Освен това, за всеки връх на двоично дърво, ако символът съвпада със символа на върха, за да се премине към следващия връх съобщенията <равно>; извадете следващия знак на входния сигнал;
в противен случай преминете към следващия връх съобщенията <не равно>, продължи със същия символ;
Процесът на сгъстяване е съвсем проста. алгоритъм на сгъстяване е както следва:
· Инициализация на масата от 256 ASCII символи.
· Инициализация на текущия ред от един празен ред.
· Докато входа не е празна е извършено:
о четене следващия знак от входния файл.
• Ако таблицата съдържа комбинация от "ток линия + символ (а" + "се отнася до конкатенацията низ)" се извършва:
о Проверка за маса от по-голяма верига, която започва с това, обаче отдават на реда със символ.
· В противен случай (ако е символ на текущия ред + не е включена в таблицата, но на текущия ред в таблицата.)
· Вземи текущата код линия в таблицата.
· Отпечатване на кода в изходния файл.
· Добавяне на комбинация от текущия ред + символ в таблицата.
· Текущия ред е сега - последния знак чете от потока (всичко, което бе прочетено него, вече се показва в изходния файл).
· След напускане на линия текущата линия, не е празна, е необходимо също така да донесе код за изходния файл.
· Отпечатване на кода в изходния файл.
Четем сериен поток въвеждане на символи и да се провери дали има маса низ ние създадохме тази линия. Ако низът е, а след това четем следващия знак, а ако линията не е налице, ние разчитаме на поток от код за предишния, който се намира, Skid Row на масата и да започне търсенето отново. LZW изпълнява в GIF и TIFF формати.
LZW - този метод за компресиране на данни, която извлича предимства в повтарящи се данни вериги. Тъй като данните за растерни обикновено съдържат много повторения, LZW е добър метод за тяхното компресия и разширяване.
Аритметика компресия изисква познаване на вероятностите за възникване на входния поток вход азбука знаци. вход от азбуката са подредени в определен ред. Интервалът от 0 до 1 се разделя между символи на интервали от начални стойности според техните вероятности. Оптималната ширината на първоначалния интервал за вероятността на символ на поява при входен поток е равно на р -log2 стр.
Теоретично, на изхода на алгоритъма може да бъде всяко число, включени в работния диапазон след последното въвеждане на символ. На практика, за всеки интервал намаляване на изходния поток се поставят всички съвпадение незначителните битове на горната и долната граница на работния диапазон. Очевидно е, че когато един характер се получава от по-голяма вероятност за поява и по-широк работен диапазон първоначален интервал се свие по-малки и по-малки парчета попадат в изходен поток. Така символи с по-голяма вероятност за поява са кодирани по-малко битове. На практика често се използва разнообразие от динамичен алгоритъм, когато в началото на работата си вероятността за вход от азбуката са неизвестни, и те се оценяват и се променя динамично, като алгоритъма. Различни стратегии могат да бъдат динамично изчисляване на вероятности, характеризираща се с увеличаване на вероятността за намиране на стойността в входен символ. Ще се обадим на модела, по който се увеличава вероятността да се случи много, модели с висока адаптивност и модели, в които тя се увеличава малко - и модели с ниска адаптивност. Очевидно е, че за всеки случай има своя собствена оптимална стойност на адаптивност.
LZW + аритметика компресия:
Точно както в алгоритмите и LZH LZARI LZSS алгоритъм изходящите потоци се компресира чрез статистически методи, може да се опита да сложи свиване на изходен поток LZW-аритметично кодиране алгоритъм. Input азбука аритметика кодиране в този случай е различно, като мощността му ще се люлее на захранващия вход азбука LZW-алгоритъм на алгоритми LZW-лексика размер.
В зависимост от степента на компресия на нивото на адаптивност.
Алгоритъмът може да бъде променена като вероятността определя на новите елементи на речника, и кодът на нарастване вероятно да отговорят на изходящите потоци LZW-алгоритъм. Резултатът е приблизително една и съща за различни типове набори от данни за вход и се различава само по общото ниво на компресия.
В момента, ние смятаме, нормалната кодиране и декодиране с помощта LZW-алгоритъм. В GIF използва вариант на този алгоритъм.
Първото нещо, което правя с LZW-компресия е инициализира ни низ от символи. За да направите това, вие трябва да изберете размера на кода (броя на битовете), и да се знае колко е възможно стойностите може да отнеме нашите герои. Нека да поставим размера на код на 12 бита, което означава възможност за съхраняване на 0FFF, или 4096, елементи в нашите трапезни вериги. Да предположим също, че имаме възможни 32 различни символи. (Това отговаря, например, на снимка с 32 възможни цветове за всеки пиксел.) За да се инициализира на масата, ние се установи съответствие код символ # 0 # 0, # 1 код символ # 1, и т.н. до кодиране # 31 и # 31. В действителност, ние казахме, че всеки код 0-31, е коренът. Още в таблицата няма да е други кодове, които имат този имот.
LZW особеност е, че декомпресия ние не трябва да се съхранява редовете на таблицата във файла, за да се декомпресира. Алгоритъмът е конструирана по такъв начин, че ние сме в състояние да се възстанови таблицата с низ се използват само потока на кода.
Ние знаем, че за всеки код трябва да се добавят към таблицата низ от вече присъства там линии и герои, от която започва на следния ред в потока.
Трябва да се отбележи, че за да спаси маса низ паметта на компютъра може да бъде ефективно момента, като се има следния своята функция: ако, например, ASDFK низ в таблицата с низ, на ASDF също е включен в нея. Този факт показва, че вместо за съхраняване на цялата верига в таблицата, само не забравяйте, кодът за ASDF са, следвани от символ следящ К.
За да се увеличи степента на компресия на изображението по този метод често се използва за "трик" за изпълнението на този алгоритъм. Някои изображения са компресирани с LZW, имат обща верига на еднакви стойности, като 12 12 12 или 32, 32 ... 32 ... и така нататък. P. им директно пресоване ще генерира изходен код 258 и 12 декември, и т.н.
Кодиране на такива вериги ще се извършва по следния начин. Първият цвят 12 записа с собствения си код от таблица 12. На следващия цвят също е 12, а след това добавете ред в таблицата, 12, 12 с код 258 и потока на изхода веднага преспи този код, т.е. 258. Поглед от входния поток. Ако на входа на цвета се връща 12, той е в таблицата, погледнете следното - 12, 12, 12, последователност и има маса, търсейки по - 12 12 12 12 последователност задали код 259, и го избутва в изходен поток. В резултат на това изходът е последователността 12258259 ..., което е много по-кратък, отколкото директно кодиране метод стандарт LZW.
Може да се покаже, че такава последователност ще бъде правилно възстановена. Decoder първо чете първия код - е 12, което съответства на цвета на 12. След това прочетете кода 258, но този код не е в неговата маса. Това е възможно само в случаите, когато добавената характер е първият знак на наскоро прочетох последователност, т.е. 12. Ето защо, тя ще добави към своята низ маса 12, 12 с код 258, и на потока на изхода ще постави 12 12. И така, тя може да бъде да се декодира цялата верига кодове.
Кодиране правило е описано по-горе може да се прилага по принцип не само за последователни еднакви цветни точки, но също така и към последователности, които имат следващия знак се добавя към първия буквена поредица.
Работа LZW декодиране.
Характеристики LZW алгоритъм:
Компресия: Около 1000 4, 5/7 (най-добри, средни, най-лошите съотношения). Компресиране на 1000 пъти се постига само при един размер множествена цветно изображение на около 7 MB.
Изображение Клас: Фокусира върху LZW 8-битови изображения, изградени на компютъра. Компресиране поради идентични subchains в поток.
Симетрия: почти симетрични, с уговорката, оптимално функциониране търсене низ изпълнение в таблицата.
Особености: ситуация, при която алгоритъм увеличава изображението, е изключително рядко. LZW е универсална - тя е неговите варианти се използват в конвенционалните данни дървар.