Тезисы лекции Дәрістер тезистері Аbstracts of lectures про уа 03-09-20 Стр из 67



бет22/27
Дата21.10.2022
өлшемі99,96 Kb.
#44753
түріТезисы
1   ...   19   20   21   22   23   24   25   26   27
Байланысты:
Контенты лекции- комп графика

Лекция 12-13

LWZ сжатие


Этот метод сжатия данных без потерь применяется в различных форматах файловых изображений, в частности gif, tif, //включен в стандартное сжатие для модемов.// Был разработан в 1977г. в Израиле Абрахамом Лемпелом и Джеком Зивом, и назывался он LZ-77.
Алгоритм сжатия LZ-77 стал основой архивирующих программ, таких как compress, zip,// jpg.//
В 1978 алгоритм был модифицирован и стал применяться для сжатия двоичных данных.
В 1984 алгоритм был доработан Терри Велчем, и он стал называться LZW
LZW позволяет работать с любым типом данных, //так как обеспечивает быструю распаковку и сжатие данных.//
Алгоритм LZW основан на поиске шаблонов в заданной структуре изображения и сохранении этих шаблонов.
Программа считывает значение символа или пикселя и строит таблицу кодов, которая представляет повторяющиеся символьные комбинации или пиксельные узоры, найденные программой.
Степень сжатия 3:1 или 4:1. Хорошо сжимаются сильно насыщенные узорами изображения, содержащие большие блоки однотипной окраски или повторяющиеся цветные узоры.
Метод LZW, как и RLE, не является форматом, но включается в различные форматы файлов.
Алгоритм LZW относится к методу адаптивного кодирования. Этот алгоритм из данных входного потока строит словарь. Образцы данных, поступающих для кодирования идентифицируются и сопоставляются с записями словаря. Если подстрока не представлена в словаре, то создается и записывается в словарь кодовая фраза. Затем эта фраза записывается в выходной поток сжатых данных.
Для LZW необязательно сохранять словарь для последующего декодирования входных потоков данных. Декодирование данных осуществляется в порядке, обратном кодированию. Декомпрессор читает из потока закодированных данных код. Если его еще нет в словаре, добавляет его туда. Затем этот код переводится в строку и записывается в выходной поток несжатых данных.
При сжатии текстовых файлов LZW инициализирует первые 256 записей словаря 8-ибитовых символов ASCII. Эти фразы представляют все возможные значения, которые могут встретиться в потоке данных. Из этих же данных строятся все подстроки.
Т.к. LZW кодировщик и декодер начинают с инициализации словаря, то декодеру не нужен оригинальный словарь, он строит словарь-дубликат в процессе кодирования.

Пример:
/WED/WE/WEE/WEB/WET


Алгоритм сжатия



Выходной поток

Код

/

/W – 256

W

WE – 257

E

ED – 258

D

D/ – 259

256

/WE – 260

E

E/ – 261

260

/WEE – 262

261

E/W – 263

257

WEB – 264

B

B/ – 265

260

/WET – 266

T




Алгоритм распаковки





Входной поток

Код

/

/W – 256

W

WE – 257

E

ED – 258

D

D/ – 259

256

/WE – 260

E

E/ – 261

260

/WEE – 262

261

E/W – 263

257

WEB – 264

B

B/ – 265

260

/WET – 266







T



Каждому алгоритму сжатия соответствует алгоритм распаковки. Алгоритм распаковки добавляет новую строку в таблицу строк каждый раз как читает…….


//Алгоритм распаковки аналогичен сжатию с точностью до наоборот.
Работа алгоритмов начинается с проверки наличия строки (очередного символа из входящего потока в библиотеку, так как первые 255 символов уже определены, то если не находится строка в таблице символов, в выходном потоке пишется значение по таблице ASCII, а в таблицу добавляется следующее значение, равное строка + символ. Этот процесс продолжается до тех пор пока не запишутся все входящие данные и не записаны все коды.//


Достарыңызбен бөлісу:
1   ...   19   20   21   22   23   24   25   26   27




©emirsaba.org 2024
әкімшілігінің қараңыз

    Басты бет