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

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

Лекция 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; просмотров: 58 | Поможем написать вашу работу | Нарушение авторских прав




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