Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

LZ77-алгоритм распаковки данных. Пример 12.4


1. LZ77, длина словаря - 8 байт (символов). Коды сжатого сообщения

-

 

 

Недостатки LZ77:

LZ77 обладает следующими очевидными недостатками:

1. длина подстроки, которую можно закодировать, ограничена размером буфера.

2. с ростом размеров словаря скорость работы алгоритма-кодера пропорционально замедляется;

3. кодирование одиночных символов очень неэффективно.

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

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

 

12.3 LZ-алгоритмы упаковки данных :LZ78

В 1978 г. авторами LZ77 был разработан алгоритм LZ78, лишенный названных недостатков.

LZ78 не использует "скользящее" окно, он хранит словарь из уже просмотренных фраз. При старте алгоритма этот словарь содержит только одну пустую строку (строку длины нуль). Алгоритм считывает символы сообщения до тех пор, пока накапливаемая подстрока входит целиком в одну из фраз словаря. Как только эта строка перестанет соответствовать хотя бы одной фразе словаря, алгоритм генерирует код, состоящий из индекса строки в словаре, которая до последнего введенного символа содержала входную строку, и символа, следующего за совпадением. Затем в словарь добавляется введенная подстрока. Если словарь уже заполнен, то из него предварительно удаляют менее всех используемую в сравнениях фразу.

Ключевым для размера получаемых кодов является размер словаря во фразах, потому что каждый код при кодировании по методу LZ78 содержит номер фразы в словаре. Из последнего следует, что эти коды имеют постоянную длину, равную округленному в большую сторону двоичному логарифму размера словаря +8 (это количество бит в байт-коде расширенного ASCII).

Пример 12.5.

Закодировать по алгоритму LZ78 строку "КРАСНАЯ КРАСКА", используя словарь длиной 16 фраз.

 

 

Указатель на любую фразу такого словаря - это число от 0 до 15, для его кодирования достаточно четырех бит.

<== предыдущая лекция | следующая лекция ==>
Подстановочные или словарно-ориентированные алгоритмы сжатия информации. Методы Лемпела-Зива | LZ-алгоритмы распаковки данных. Пример 13.6

Дата добавления: 2014-01-04; Просмотров: 1465; Нарушение авторских прав?


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Рекомендуемые страницы:

Читайте также:

  1. I. Затрудненный выброс крови из желудочков (например, стеноз аорты, клапанный стеноз a, pulmonalls и коарктация аорты)
  2. IV. Примеры расчетов потребностей в сырье по индивидуальным и среднегодовым нормам.
  3. LZ-алгоритмы распаковки данных. Пример 13.6
  4. LZ-алгоритмы распаковки данных. Примеры
  5. Абстрактные типы данных. Методы представления множеств.
  6. Архив — это форма организации длительного хранения данных.
  7. Базы данных. Их применение для решения экономических задач
  8. Билет№5:Методологические основы менеджмента. Ситуационный, системный и процессный подход к принятию управленческих решений (привести примеры).
  9. В приведенном примере укажите тезис (если тезис явно не выражен, сформулируйте его), определите способ аргументации.
  10. В ст.131 ГК установлены основные положения о примерном перечне вещных прав, подлежащих регистрации, обязательности государственной регистрации и органе, ее осуществляющем.
  11. Виды и примерная структура документов

studopedia.su - Студопедия (2013 - 2021) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление
Генерация страницы за: 0.002 сек.