В чем идея алгоритма сжатия лемпеля зива

Основная идея алгоритма Лемпеля-Зива состоит в замене появления фрагмента в данных (группы байт) ссылкой на предыдущее появление этого фрагмента. Существуют два основных класса методов, названных в честь Якоба Зива (Jakob Ziv) и Абрахама Лемпеля (Abraham Lempel), впервые предложивших их в 1977 (алгоритм LZ77) и 1978 годах (алгоритм LZ78).

LZ77 [2] использует уже просмотренную часть сообщения как словарь. Чтобы добиться сжатия, он пытается заменить очередной фрагмент сообщения на указатель в содержимое словаря. Алгоритм LZ77 предлагает оригинальное решение для устройства словаря. Вместо построения словаря для хранения фрагментов в виде отдельной структуры данных LZ77 предлагает использовать предшествующий фрагмент исходных данных конечной длины как готовый словарь.

Метод LZ77 оперирует двумя элементами данных:

  • 1) Буфер предыстории — уже обработанный фрагмент исходных данных фиксированной длины;
  • 2) Буфер предпросмотра — еще не обработанный фрагмент данных, следующий за буфером предыстории.

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

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

Рис. 1. Упрощенный алгоритм кодирования LZ77

LZ77 передвигает окно фиксированного размера (буфер предыстории) по данным. Очевидно, что наилучшего результата можно было бы достичь, если бы буфер предыстории был бы по размеру равен данным, но на практике используют ограниченный буфер (обычно16 или32 кБайт). Это обусловлено, как очевидными ограничениями по размерам ОЗУ, так и необходимостью ограничить время поиска фрагмента в буфере.

Поскольку метод не требует построения словаря, а для поиска фрагмента в буфере существуют очень эффективные алгоритмы, то LZ77 широко применяется на практике. Большинство коммерческих архиваторов (ace, arj, lha, zip, zoo) являются комбинацией LZ77 и метода Хаффмана (или арифметического кодирования). Наиболее используемые алгоритмы происходят от метода LZSS, описанного Джеймсом Сторером (James Storer) и Томасом Шимански (Thomas Szymanski) в 1982 г.

Способы сжатия информации. Алгоритмы сжатия без потерь. Сжатие с потерями, когда часть данных утрачивается и полное восстановление невозможно. Идея алгоритма Лемпеля-Зива. Алгоритм LZ77, LZ78. Модификация алгоритма Лемпеля-Зива, предложенная Терри Уэлчем.

РубрикаПрограммирование, компьютеры и кибернетика
Видкурсовая работа
Языкрусский
Дата добавления14.10.2016
Размер файла240,9 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

1. Способы сжатия информации

2. Алгоритмы сжатия без потерь

2.1 Обзор алгоритмов

2.2 Идея алгоритма Лемпеля-Зива

2.3 Алгоритм LZ77

2.4 Алгоритм LZ78

2.5 Модификация алгоритма Лемпеля-Зива, предложенная Терри Уэлчем Заключение

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

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

На практике возможно сжатие практически любой, т.н. «обычной» информации. Прежде всего потому, что «обычное» представление информации, которым люди привыкли пользоваться, почти всегда избыточно. Избыточность присутствует текстах, так как в них обязательно есть повторяющиеся слова, фразы, а то и целые абзацы. Избыточность информации присуща звуковой речи, так как в ней обязательно есть частоты, не слышимые человеком, или несущественные для восприятия. Избыточно представление информации в электронном виде, обязательно есть какие-то повторяющиеся символы, цепочки символов. Удалив избыточность, мы можем уменьшить потребности в емкостях и пропускных способностях линий передачи, необходимых для хранения и передачи информации, и при этом не уменьшив содержательную сторону информации, т.е. сохранив возможность восстановления ее к исходному виду (такое сжатие называется обратимым).

В данной работе я рассмотрела алгоритм Лемпеля-Зива. Объектом исследования являются алгоритмы Лемпеля-Зива. Предмет исследования: построение алгоритмов Лемпеля-Зива. Цель исследования: исследовать алгоритм Лемпеля-Зива, подобрать задачи с использованием алгоритм Лемпеля-Зива. Для реализации поставленной цели необходимо решить следующие задачи:

1) Изучить литературу по теме исследования;

2) Изучить состав и принцип работы алгоритма Лемпеля-Зива;

3) Научиться составлять алгоритмы;

1. Способы сжатия информации

Сжатие данных можно разделить на два основных типа:

1) Сжатие без потерь или полностью обратимое;

2) Сжатие с потерями, когда несущественная часть данных утрачивается и полное восстановление невозможно.

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

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

сжатие информация лемпель зива

2. Алгоритмы сжатия без потерь

2.1 Обзор алгоритмов

В настоящее время существует несколько алгоритмов сжатия без потерь, частично это открытые алгоритмы, частично коммерческие алгоритмы. Открытые алгоритмы обычно рассматривают только саму идею, не останавливаясь на проблемах ее реализации в виде программы или реализованы в виде «демонстрационной» (не очень эффективной) программы. Коммерческий алгоритм обычно включает в себя не только идею алгоритма сжатия, но и эффективную реализацию алгоритма в виде программы. Коммерческие алгоритмы не публикуются и познакомится с ними невозможно, за исключением ознакомления с результатами работы программ на базе этих алгоритмов. Соответствующие программы (ZIP, ARJ, RAR, ACE и др.) достаточно известны и с ними можно познакомиться самостоятельно.

Алгоритмы обратимого сжатия данных можно разделить на две группы:

1) Алгоритмы частотного анализа для подсчета частоты различных символов в данных и преобразование кодов символов с соответствии с их частотой.

2) Алгоритмы корреляционного анализа для поиска корреляций (в простейшем случае точных повторов) между различными участками данных и замена коррелирующих данных на код(ы), позволяющая восстановить данные на основе предшествующих данных. В простейшем случае точных повторов, кодом является ссылка на начало предыдущего вхождения этой последовательности символов в данных и длина последовательности.

Можно отметить следующие алгоритмы обратимого сжатия данных из первой группы [1]:

1) Метод Хаффмана — замена кода равной длины для символов на коды неравной длины в соответствии с частотой появления символов в данных. Коды минимальной длины присваиваются наиболее часто встречающимся символам. Если частоты появления символов являются степенью двойки (2 n ), то этот метод достигает теоретической энтропийной границы эффективности сжатия для методов такого типа.

2) Метод Шеннона-Фано — сходен с методом Хаффмана, но использует другой алгоритм генерации кодов и не всегда дает оптимальные коды (оптимальный код — код дающий наибольшее сжатие данных из всех возможных для данного типа преобразования).

3) Арифметическое кодирование — усовершенствование метода Хаффмана, позволяющее получать оптимальные коды для данных, где частоты появления символов не являются степенью двойки (2 n ). Этот метод достигает теоретической энтропийной границы эффективности сжатия этого типа для любого источника.

Для второй группы можно назвать следующие алгоритмы [1]:

1) Метод Running (или RLE) — заменяет цепочки повторяющихся символов на код символа и число повторов. Это пример элементарного и очень понятного метода сжатия, но, к сожалению, он не обладает достаточной эффективностью.

2) Методы Лемпеля-Зива — это группа алгоритмов сжатия объединенная общей идеей: поиск повторов фрагментов текста в данных и замена повторов ссылкой (кодом) на первое (или предыдущее) вхождение этого фрагмента в данные. Отличаются друг от друга методом поиска фрагментов и методом генерации ссылок(кодов).

В настоящее время, в различных модификациях и сочетаниях, два алгоритма — метод Хаффмана (или арифметическое кодирование) и метод Лемпеля-Зива — составляют основу всех коммерческих алгоритмов и программ.

Далее будут подробно рассмотрены несколько вариантов алгоритма сжатия Лемпеля-Зива и на основе модификации этого алгоритма Терри Уэлчем разработана действующая программа для архивирования и разархивирования файлов.

2.2 Идея алгоритма Лемпеля-Зива

Основная идея алгоритма Лемпеля-Зива состоит в замене появления фрагмента в данных (группы байт) ссылкой на предыдущее появление этого фрагмента. Существуют два основных класса методов, названных в честь Якоба Зива (Jakob Ziv) и Абрахама Лемпеля (Abraham Lempel), впервые предложивших их в 1977 (алгоритм LZ77) и 1978 годах (алгоритм LZ78).

2.3 Алгоритм LZ77

LZ77 [2] использует уже просмотренную часть сообщения как словарь. Чтобы добиться сжатия, он пытается заменить очередной фрагмент сообщения на указатель в содержимое словаря. Алгоритм LZ77 предлагает оригинальное решение для устройства словаря. Вместо построения словаря для хранения фрагментов в виде отдельной структуры данных LZ77 предлагает использовать предшествующий фрагмент исходных данных конечной длины как готовый словарь.

Метод LZ77 оперирует двумя элементами данных:

1) Буфер предыстории — уже обработанный фрагмент исходных данных фиксированной длины;

2) Буфер предпросмотра — еще не обработанный фрагмент данных, следующий за буфером предыстории.

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

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

Размещено на http://www.allbest.ru/

Рис.1 Упрощенный алгоритм кодирования LZ77.

LZ77 передвигает окно фиксированного размера (буфер предыстории) по данным. Очевидно, что наилучшего результата можно было бы достичь, если бы буфер предыстории был бы по размеру равен данным, но на практике используют ограниченный буфер (обычно16 или32 кБайт). Это обусловлено, как очевидными ограничениями по размерам ОЗУ, так и необходимостью ограничить время поиска фрагмента в буфере.

Поскольку метод не требует построения словаря, а для поиска фрагмента в буфере существуют очень эффективные алгоритмы, то LZ77 широко применяется на практике. Большинство коммерческих архиваторов (ace, arj, lha, zip, zoo) являются комбинацией LZ77 и метода Хаффмана (или арифметического кодирования). Наиболее используемые алгоритмы происходят от метода LZSS, описанного Джеймсом Сторером (James Storer) и Томасом Шимански (Thomas Szymanski) в 1982 г.

2.4 Алгоритм LZ78

Этот алгоритм генерирует на основе входных данных словарь фрагментов, внося туда фрагменты данных (последовательности байт) по определенным правилам (см. ниже) и присваивает фрагментам коды (номера). При сжатии данных (поступлении на вход программы очередной порции) программа на основе LZ78 пытается найти в словаре фрагмент максимальной длины, совпадающий с данными, заменяет найденную в словаре порцию данных кодом фрагмента и дополняет словарь новым фрагментом. При заполнении всего словаря (размер словаря ограничен по определению) программа очищает словарь и начинает процесс заполнения словаря снова. Реализации этого метода различаются конструкцией словаря, алгоритмами его заполнения и очистки при переполнении [2].

Обычно, при инициализации словарь заполняется исходными (элементарными) фрагментами — всеми возможными значениями байта от 0 до 255. Это гарантирует, что при поступлении на вход очередной порции данных будет найден в словаре хотя бы однобайтовый фрагмент.

Алгоритм LZ78 резервирует специальный код, назовем его «Reset», который вставляется в упакованные данные, отмечая момент сброса словаря. Значение кода Reset обычно принимают равным 256.

Таким образом при начале кодирования минимальная длина кода составляет 9 бит. Максимальная длина кода зависит от объема словаря — количества различных фрагментов, которые туда можно поместить. Если объем словаря измерять в байтах (символах), то очевидно, что максимальное количество фрагментов равно числу символов, а, следовательно, максимальная длина кода равна log2(объем_словаря_в_байтах).

Рассмотрим алгоритм заполнения словаря на примере кодирования фрагмента. Для примера используем данные, состоящие только из символов (букв), кавычки «» не входят в данные: «aaabbabaabaaabab». Пример кодировки приведен в табл. 1

Таблица 1. LZ78-кодирование строки; где запись (i, a) обозначает копирование фразы i перед символом a.

Компьютерные сети. г.Котово

  1. Обзор подходов к сжатию информации

Как уже было сказано, дискретная форма представления информации является наиболее общей и универсальной. В виде совокупности символов, принадлежащих к ограниченному алфавиту, можно представить как текст или массивы чисел, так и оцифрованные звук и изображение. С учетом этого очевидно, что должны существовать универсальные методы сжатия данных (цифровой информации), применимые ко всем ее разновидностям. В силу своей универсальности эти методы должны исключать потерю информации (такая потеря может быть допустима при передаче, например мелкой детали изображения, но неприемлема, когда речь идет, скажем, о коде программы). С другой стороны, в ряде приложений общие методы наверняка не будут наиболее эффективными. Например, в силу особенностей зрительного и слухового восприятия, некоторое «огрубление» изображения или звука может оказаться малозаметным, при этом выигрыш в объеме передаваемых данных окажется значительным. В этих случаях уместно использовать специальные методы сжатия с потерями (рис.5.1).

При кодировании со сжатием без потерь выделяются две разновидности методов: Первая основана на раздельном кодировании символов. Основная идея состоит в том, что символы разных типов встречаются неодинаково части и если кодировать их неравномерно, – так, чтобы короткие битовые последовательности соответствовали часто встречающимся символам, – то в среднем объем, кода будет меньше. Такой подход, именуемый, статистическим кодированием, реализован, в частности, в широко распространенном коде Хаффмана, о котором мы расскажем подробно ниже.

Очевидно, что посимвольное кодирование не использует такого важного резерва сжатия данных, как учет повторяемости последовательностей (цепочек) символов.

Простейший вариант учета цепочек – так называемое «кодирование повторов» или код RLE, когда последовательность одинаковых символов заменяется парой – “код символа + количество его повторов в цепочке”. В большинстве случаев цепочки одинаковых символов встречаются нечасто. Однако, например, при кодировании черно-белых растровых изображений, каждая строка которых состоит из последовательных черных или белых точек, такой подход оказывается весьма эффективным (он широко применяется при факсимильной передаче документов). Кроме того, кодирование повторов нередко используется как составной элемент более сложных алгоритмов сжатия.

Гораздо более универсальным является алгоритм, позволяющий эффективно кодировать повторяющиеся цепочки разных символов, имеющие при этом произвольную длину. Такой алгоритм был разработан Лемпелем и Зивом и применяется в разных версиях в большинстве современных программ-архиваторов. Идея алгоритма состоит в том, что цепочка символов, уже встречавшаяся в передаваемом сообщении, кодируется ссылкой на боле раннюю (при этом указываются «адрес» начала такой цепочки в «словаре» сообщения и ее длина). Ниже мы обсудим особенности алгоритма Лемпеля-Зива.

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

К методам сжатия изображений относятся «блочный» алгоритм JPEG основанный на независимом «огрублении» небольших фрагментов изображений (квадраты 8х8 пикселей). Здесь с ростом степени сжатия проявляется мозаичность изображения. Блочный метод JPEG (разработанный специальной группой международного комитета по стандартизации) получил сейчас повсеместное распространение и ниже мы рассмотрим его подробнее. Достигается степень сжатия – в среднем в десятки раз.

При волновом сжатии в отличие от блочного изображение как бы «размывается» (чем выше степень сжатия, тем более нечетки границы и детали). При передаче данных получаемое изображение постепенно «проявляется» в деталях. Это позволяет получателю самому выбирать необходимый компромисс между качеством и скоростью получения изображения, что очень удобно, например в Интернет. К тому же «размытость» не столь резко воспринимается глазом как потеря качества по сравнению с «мозаичностью». Так что при субъективно близком уровне качества волновой метод дает большую степень сжатия по сравнению с «блочным». Именно такой подход реализован в новом стандарте JPEG 2000.

Наконец, фрактальное сжатие основывается на том, что в изображении можно выделить фрагменты, повороты и масштабирование которых позволяет многократно использовать их при построении всей «картинки». Выделение и построение математического описания таких элементов-фракталов – трудоемкая в вычислительном отношении задача. Зато высокая степень сжатия (в сотни раз) и быстрота построения изображения по его фрактальному описанию делают метод очень удобным, когда не требуется быстрота компрессии. Например, этот метод удобно использовать при записи изображений на CD-ROM.

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

Что касается методов сжатия звука от произвольного источника, мы рассмотрим их ниже.

  1. Эффективное посимвольное кодирование для сжатия данных.

Основные моменты сводятся к следующему:

  • идея такого кодирования базируется на том, чтобы использовать для часто встречающихся символов более короткие кодовые цепочки, а для редких – более длинные. В результате средняя длина кода будет меньше, чем при равномерном кодировании;
  • согласно теореме Шеннона, наилучшее кодирование позволяет сократить lср. до величены энтропии Н, подсчитанной для данного набора символов;
  • неравномерное кодирование позволяет автоматически устранить избыточность, связанную с тем, что количество символов в алфавите может быть не кратно степени двойки (так, например, чтобы закодировать одинаковым числом разрядов 5 разновидностей символов потребуется 3 бита, так же как и для 8 символов).

Идея неравномерного кодирования, в котором длина кодовой цепочки зависит от частоты появления соответствующего символа, реализована еще в знаменитой «азбуке Морзе». Однако там наряду с «точками» и «тире» использовался третий кодовый символ – разделитель «пауза». Если ограничиться только «O» и «1», то при построении кода необходимо учесть дополнительное требование: чтобы все кодовые цепочки однозначно выделялись в непрерывном потоке битов, ни одна из них не должна входить как начальный участок в кодовую, цепочку другого символа. Такое свойство кода называется префиксностью.

Наибольшее распространение получил способ построения эффективного кода предположенный Хаффменом. Рассмотрим его на примере. Пусть задан алфавит из 5 разновидностей символов Z1 – Z5, и их вероятности. В таблице 5.1 наряду с этими исходными данными приведены так же результаты кодирования по Хаффмену: кодовые цепочки Ki их длинны li. Процедуру построения кода иллюстрирует таблица и рисунок 1

На первом этапе символы упорядочивают по убыванию вероятностей, а затем выполняют несколько шагов «объединения», на каждом из которых суммируются вероятности наиболее редко встречающихся символов и столбец вероятностей пересортировывается .

Оцените статью
Добавить комментарий