Анализ алгоритма Лемпеля-Зива

Размещено на 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ⁿ), то этот метод достигает теоретической энтропийной границы эффективности сжатия для методов такого типа.

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

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

Для второй группы можно назвать следующие алгоритмы [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 бит. Максимальная длина кода зависит от объема словаря - количества различных фрагментов, которые туда можно поместить. Если объем словаря измерять в байтах (символах), то очевидно, что максимальное количество фрагментов равно числу символов, а, следовательно, максимальная длина кода равна log₂(объем_словаря_в_байтах).

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

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

Input:	A	aa	b	ba	baa	baaa	bab
Phrase number:	1	2	3	4	5	6	7
Output:	(0,a)	(1,a)	(0,b)	(3,a)	(4,a)	(5,a)	(4,b)

Дальность продвижения вперед указателя неограниченна (т.е. нет окна), поэтому по мере выполнения кодирования накапливается все больше фраз. Допущение произвольно большого их количества требует по мере разбора увеличения размера указателя. Когда разобрано p фраз, указатель представляется [log p] битами. На практике, словарь не может продолжать расти бесконечно. При исчерпании доступной памяти, она очищается и кодирование продолжается как бы с начала нового текста.

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

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

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

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

1) поиск в словаре фрагмента;

2) вставка в словарь новых фрагментов.

Необходимо, чтобы эти две операции были максимально быстрыми.

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

В 1984 году Терри Уэлч (Terry Welch) предложил адаптивный сброс словаря для алгоритма LZ78 [3]. В этом случае при заполнении словаря сброс словаря не производится и новые фрагменты в словарь не добавляются, пока степень сжатия данных остается «достаточно» высокой. Степень «достаточности» определяется субъективно, но простейший вариант «достаточности»: пока степень сжатия не меньше, чем на момент заполнения словаря. В этом случае резко возрастает скорость компрессии, поскольку операция вставки новых фрагментов в словарь не производится.

Алгоритм известен под названием LZW. Алгоритм на удивление прост. Если в двух словах, то LZW-сжатие заменяет строки символов некоторыми кодами. Это делается без какого-либо анализа входного текста. Вместо этого при добавлении каждой новой строки символов просматривается таблица строк. Сжатие происходит, когда код заменяет строку символов. Коды, генерируемые LZW-алгоритмом, могут быть любой длины, но они должны содержать больше бит, чем единичный символ. Первые 256 кодов (когда используются 8-битные символы) по умолчанию соответствуют стандартному набору символов. Остальные коды соответствуют обрабатываемым алгоритмом строкам.

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

Алгоритм LZW-сжатия в простейшей форме приведен на рис. 2.

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

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

Каждый раз, когда генерируется новый код, новая строка добавляется в таблицу строк. LZW постоянно проверяет, является ли строка уже известной, и, если так, выводит существующий код без генерации нового.

Простая строка, использованная для демонстрации алгоритма, приведена на рис.3.

Рис. 3. Процесс сжатия

Входная строка : abacabadabacabae

Сначала создадим начальный словарь единичных символов. В стандартной кодировке ASCII имеется 256 различных символов, поэтому, для того, чтобы все они были корректно закодированы (если нам неизвестно, какие символы будут присутствовать в исходном файле, а какие -- нет), начальный размер кода будет равен 8 битам. Если нам заранее известно, что в исходном файле будет меньшее количество различных символов, то вполне разумно уменьшить количество бит. Чтобы инициализировать таблицу, мы установим соответствие кода 0 соответствующему символу с битовым кодом 00000000, тогда 1 соответствует символу с кодом 00000001, и т.д., до кода 255.

Больше в таблице не будет других кодов, обладающих этим свойством.

По мере роста словаря, размер групп должен расти, с тем чтобы учесть новые элементы. 8-битные группы дают 256 возможных комбинации бит, поэтому, когда в словаре появится 256-е слово, алгоритм должен перейти к 9-битным группам. При появлении 512-ого слова произойдет переход к 10-битным группам, что дает возможность запоминать уже 1024 слова и т.д.

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

Символ	Битовый код	Код
a	000	0
b	001	1
c	010	2
d	011	3
e	100	4

§ Шаг 1: Тогда, согласно изложенному выше алгоритму, мы добавим к изначально пустой строке a и проверим, есть ли строка a в таблице. Поскольку мы при инициализации занесли в таблицу все строки из одного символа, то строка a есть в таблице.

§ Шаг 2: Далее мы читаем следующий символ b из входного потока и проверяем, есть ли строка ab в таблице. Такой строки в таблице пока нет.

Добавляем в таблицу (5) ab. В поток: (0);

§ Шаг 3: ba -- нет. В таблицу: (6) ba. В поток: (1);

§ Шаг 4: ac -- нет. В таблицу: (7) ac. В поток: (0);

§ Шаг 5: ca -- нет. В таблицу: (8) ca. В поток: (2);

§ Шаг 6: ab -- есть в таблице; aba -- нет. В таблицу: (9) aba. В поток: (5);

§ Шаг 7: ad -- нет. В таблицу: (10) ad. В поток: (0);

§ Шаг 8: da -- нет. В таблицу: (11) da. В поток: (3);

§ Шаг 9: aba -- есть в таблице; abac -- нет. В таблицу: (12) abac. В поток: (9);

§ Шаг 10: ca -- есть в таблице; cab -- нет. В таблицу: (13) cab. В поток: (8);

§ Шаг 11: ba -- есть в таблице; bae -- нет. В таблицу: (14) bae. В поток: (6);

§ Шаг 12: И, наконец последняя строка e, за ней идет конец сообщения, поэтому мы просто выводим в поток

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

3* 16=48 бит.

Закодированное же сообщение так же сначала кодировалось трехбитными группами, а при появлении в словаре восьмого слова -- четырехбитными, итого длина сообщения составила 4*3+7*4=40 бит, что на 8 бит короче исходного.

Конечно, этот пример был выбран только для демонстрации.

В действительности сжатие обычно не начинается до тех пор, пока не будет построена достаточно большая таблица, обычно после прочтения порядка 100 входных байт.

Алгоритму сжатия соответствует свой алгоритм распаковки. Он получает выходной поток кодов от алгоритма сжатия и использует его для точного восстановления входного потока. Одной из причин эффективности LZW-алгоритма является то, что он не нуждается в хранении таблицы строк, полученной при сжатии. Таблица может быть точно восстановлена при распаковке на основе выходного потока алгоритма сжатия. Это возможно потому, что алгоритм сжатия выводит СТРОКОВУЮ и СИМВОЛЬНУЮ компоненты кода прежде чем он поместит этот код в выходной поток. Это означает, что сжатые данные не обременены необходимостью тянуть за собой большую таблицу перевода.

Алгоритм распаковки представлен на рис. 4.

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

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

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

На рис. 5 приведена схема работы алгоритма на основе сжатых данных, полученных в выше приведенном примере.

Рис. 5. Процесс распаковки

Выходные коды: 01025039864

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

Выходной поток идентичен входному потоку алгоритма сжатия.

К несчастью прекрасный, простой алгоритм распаковки, приведенный на рис. 4, является все таким слишком простым. В алгоритме сжатия существуют некоторые исключительные ситуации, которые создают проблемы при распаковке. Если существует строка, представляющая пару (СТРОКА СИМВОЛ) и уже определенную в таблице, а просматриваемый входной поток содержит последовательность СТРОКА+СИМВОЛ+СТРОКА +СИМВОЛ+СТРОКА, алгоритм сжатия выведет код прежде, чем распаковщик получит возможность определить его.

Простой пример иллюстрирует это. Предположим, строка "JOEYN" определена в таблице с кодом 300. Когда последовательность "JOEYNJOEYNJOEY" появляется в таблице, выходной поток алгоритма сжатия выглядит подобно тому, как показано на рис. 6.

Вход(символы)	Выход(коды)	Новые коды и соотв. Строки
JOEYN	288 = JOEY	300 = JOEYN
A	N	301 = NA
.	.	.
.	.	.
.	.	.
JOEYNJ	300 = JOEYN	400 = JOEYNJ
JOEYNJO	400	401 = JOEYNJO

Рис. 6. Некоторые проблемы

Входная строка: ...JOEYNJOEYNJOEY...

Когда распаковщик просматривает входной поток, он сначала декодирует код 300, затем выводит строку "JOEYN" и добавляет определение для, скажем, кода 399 в таблицу, хотя он уже мог там быть. Затем читает следующий входной код, 400, и обнаруживает, что его нет в таблице. Это уже проблема. К счастью, это произойдет только в том случае, если распаковщик встретит неизвестный код. Так как это фактически единственная коллизия, то можно без труда усовершенствовать алгоритм.

Модифицированный алгоритм предусматривает специальные действия для еще неопределенных кодов. В примере на рис. 7 распаковщик обнаруживает код 400, который еще не определен. Так как этот код не известен, то декодируется значение СТАРОГО_КОДА, равное 300. Затем распаковщик добавляет значение СИМВОЛА, равное "J", к строке. Результатом является правильный перевод кода 400 в строку "JOEYNJ".

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

Рис. 7. Модифицированный алгоритм распаковки

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



ЗАКЛЮЧЕНИЕ

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



СПИСОК ЛИТЕРАТУРЫ

1. Компрессия данных или измерение и избыточность информации. Метод Лемпеля-Зива: Методические указания к лабораторной работе /О. Е. Александров, Екатеринбург: УГТУ, 2001. 49 с.

2. Описание алгоритмов LZ77 и LZ78. Материал из Википедии. -- URL: http://ru.wikipedia.org/wiki/LZ77

3. Алгоритм Лемпеля-Зива-Велча. Материал из Википедии. -- URL: http://ru.wikipedia.org/wiki/LZW

4. Мастрюков Д. Краткое описание алгоритма LZW и его реализации. Алгоритмы сжатия информации. Часть 4. Алгоритм LZW// Монитор, N3, 1994. С8-11.

Размещено на Allbest.ru