Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Лекция 10. LWZ сжатие

Читайте также:
  1. Амплитудная селекция
  2. Архиваторы – это программы (комплекс программ) выполняющие сжатие и восстановление сжатых файлов в первоначальном виде. Процесс сжатия файлов называется архивированием.
  3. Беседа как метод обучения детей дошкольного возраста диалогической речи (лекция).
  4. Вводная лекция
  5. Вопрос 1.Лекция.
  6. Воскресная лекция Шрилы Радханатхи Свами в Киеве о Бхакти Тиртхе Свами
  7. Временная селекция
  8. Вступительная лекция.
  9. Вступительная лекция.
  10. Дәріс (лекция), зертханалық және зертханалық сабақтар жоспары

Этот метод сжатия данных без потерь применяется в различных форматах файловых изображений, в частности 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
/WE — 260
E E/ — 261
/WEE — 262
E/W — 263
WEB — 264
B B/ — 265
/WET — 266
T  

 

Выходной поток Код
/ /W — 256
W WE — 257
E ED — 258
D D/ — 259
/WE — 260
E E/ — 261
/WEE — 262
E/W — 263
WEB — 264
B B/ — 265
/WET — 266
T  

 

 

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

Алгоритм распаковки аналогичен сжатию с точностью до наоборот.

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

Кодирование по алгоритму Хаффмена

Международный консультативный комитет по телефонии и телеграфии (CCITT) разработал серию протоколов для факсимильной передачи изображений. Эти протоколы основываются на алгоритме, предложенном Д. Хаффменом в 1952г., и используются для обработки черно-белых изображений.

Метод Хаффмена строит таблицы кодов, базирующихся на частоте повторения элементов. Чем чаще встречается тот или иной элемент, тем короче будет заменяющий его код.

Степень сжатия 2:1 и 3:1.

По алгоритму Хаффмена для сжатия файла необходимо прочитать его полностью и подсчитать сколько раз встречается каждый элемент, подлежащий кодированию.

Этот алгоритм разрабатывался для факсовых передач черно-белых изображений передачи данных. Также называется кодирование по алгоритму Хаффмана.

Он является неадаптивным, то есть не настраивается для кодирования каждого реестра оптимальным образом , используется фиксирование таблицы кодовых значений , которые были выбраны заранее для представления данных в степень сжатия по этим алгоритмам 5:1-8:1.

Загрузка...

Кодирование:Кодировщик определяет длину пиксельных групп в строке развертке и выводит двоичное кодовое слово, представляющее длину и цвет группы . Кодированное слова берутся из таблицы значений представляемых группами белых и черных пикселей. Двоичное кодовое слово по этому алгоритму бывает переменной длины. Размер каждого слова определяется на основе статистически усредненной частоты черно-белых групп, появляется в течение печатных документов. Длины групп, встречающиеся наиболее часто, присваивается наименьшее кодированное слово , чем длины групп, которые появляются менее часто.

Алгоритм Хаффмена для символьных группПодсчитаем вхождение каждого символа в файл и получим следующие характеристики

Файл длиной 100 байт, имеет различные символы, длина каждого 1 байт.

Символ A B C D E F
Число вхожд-ий

 

 

на 100 символовСначала рассматриваются те символы, которые имеют самую низкую частоту вхождений.Например D и F или D и A. Для них формируется узел, частота вхождения которого равна сумме частот вхождений этих символов.

A B C D E F

10 20 30 5 25 10

| | | | | |

| | | |______|______|

| | | 15 |

|_____|_____|_________| |

| 25 |___________|

|___| 55

45 |

|__________|

Если из вершины дерева идти по левой ветке, то присваиваем значение 0, по правой — 1.

C 10 E 11 B 00 A 010 F 0111 D 0110

Базируется на частоте повторений величин: чем чаще встречается величина, тем короче будет её код.Существует целая группа протоколов, разработанных с использованием алгоритма Хаффмена. За счет модификации этого алгоритма достигается степень сжатия 4:1 и 5:1.


Дата добавления: 2014-12-15; просмотров: 19 | Нарушение авторских прав




lektsii.net - Лекции.Нет - 2014-2018 год. (0.01 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав