МИНОБРНАУКИ РОССИИ

Федеральное государственное бюджетное образовательное учреждение

высшего образования

«Омский государственный педагогический университет»

(ФГБОУ ВО «ОмГПУ»)

Факультет математики, информатики, физики и технологии

Кафедра прикладной информатики и математики

Курсовая работа

Словарные методы сжатия

Направление: педагогическое образование

Профиль: Информатика и Технология

Дисциплина: Теоретические основы информатики

Выполнил: студент

32 группы

Таранин Антон Викторович

___________(подпись)

Научный руководитель:

Курганова Наталья Александровна,

к.п.н.,  

Оценка________________

«__» _______________ 2015г.

                ________

_______________ (подпись)

Омск, 2015

Оглавление

Введение        

Глава 1.        Теоретические основы  словарных методах сжатия.................

1.1        Словарные методы сжатия, история,  основные понятия, применение        

1.2        Классические алгоритмы Зива-Лемпела        

Выводы по главе 1        

Глава 1.        Практические основы словарных методов сжатия.................

2.1        Пример использования алгоритма  LZ–77        

2.2        Пример использования алгоритма LZSS        

2.3        Пример использования алгоритма LZ–78        

Вывод по главе 2        

Заключение        

Список литературы        

Введение

В современном, постоянно  развивающемся информационном обществе возрастает объем информации и достаточно остро стоит вопрос о её хранения и передачи. Сжатие данных – обеспечит компактное представление данных, вырабатываемых источником, для их более экономного сохранения и передачи по каналам связи.

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

В связи с вышеизложенным вытекает актуальность нашей курсовой работы.

Цель курсовой работы: изучить алгоритм работы словарных методов сжатия данных.

Задачи:

1) изучить характеристики  словарных методов сжатия;

2) рассмотреть содержание ключевых понятий;

3) изучить классические алгоритмы Зива-Лемпела;

4) рассмотреть примеры использования алгоритмов LZ77, LZSS, LZ78.

Объект: словарные алгоритмы сжатия.

Предмет:  алгоритм сжатия.

Методы исследования –  анализ современной, научно-методической литература, учебников и учебных пособий по информатике. Изучение словарных методов сжатия данных.

1. Теоретические основы  словарных методах сжатия

1. Словарные методы сжатия, история, основные понятия, применение

Сжатие информации – проблема, имеющая достаточно давнюю историю, гораздо более давнюю, нежели история развития вычислительной техники, которая (история) обычно шла параллельно с историей развития проблемы кодирования и шифровки информации. Все алгоритмы сжатия оперируют входным потоком информации, минимальной единицей которой является бит, а максимальной – несколько бит, байт или несколько байт. Целью процесса сжатия, как правило, есть получение более компактного выходного потока информационных единиц из некоторого изначально некомпактного входного потока при помощи некоторого их преобразования. Основными техническими характеристиками процессов сжатия и результатов их работы являются:

• степень сжатия (compress rating) или отношение (ratio) объемов исходного и результирующего потоков;
• скорость сжатия – время, затрачиваемое на сжатие некоторого объема информации входного потока, до получения из него эквивалентного выходного потока;
• качество сжатия – величина, показывающая на сколько сильно упакован выходной поток, при помощи применения к нему повторного сжатия по этому же или иному алгоритму.

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

Величина сжатия определяется избыточностью обрабатываемого массива бит. Каждый из естественных языков обладает определенной избыточностью. Среди европейских языков русский обладает одной из самых высоких уровней избыточности. Об этом можно судить по размерам русского перевода английского текста. Обычно он примерно на 30% больше.

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

В 1977 году Абрахам Лемпель и Якоб Зив предложили алгоритм сжатия данных, названный позднее LZ77. Этот алгоритм используется в программах архивирования текстов compress, lha, pkzip и arj. Модификация алгоритма LZ78 применяется для сжатия двоичных данных. Эти модификации алгоритма защищены патентами США. Алгоритм предполагает кодирование последовательности бит путем разбивки ее на фразы с последующим кодированием этих фраз.

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

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

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

Все методы этой группы базируются на алгоритме, разработанном и опубликованном, как уже отмечалось, в 1977 году Абрахамом Лемпелем и Якобом Зивом, – LZ77. Наиболее совершенным представителем этой группы, включившим в себя все достижения, полученные в данном направлении, является алгоритм LZSS, опубликованный в 1982 году Сторером и Шимански.

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

Все методы этой группы базируются на алгоритме, разработанном и опубликованном Лемпелем и Зивом в 1978 году, – LZ78. Наиболее совершенным на данный момент представителем этой группы словарных методов является алгоритм LZW, разработанный в 1984 году Терри Вэлчем.

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

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

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

Уменьшение размера возможно в первую очередь за счет того, что обычно в сжимаемых данных встречается лишь малая толика всех возможных строк длины n, поэтому для представления индекса фразы требуется, как правило, меньшее число битов, чем для представления исходной строки. Например, рассмотрим количество взаимно различных строк длины от 1 до 5 в тексте на русском языке (роман Ф.М. Достоевского «Бесы», обычный неформатированный текст, размер около 1.3 Мбайт) (табл. 1.1).

Таблица 1.1.

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

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

Таблица 1.2.

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

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

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

С тех пор методы данного семейства неизменно являются самыми популярными среди всех методов сжатия данных, хотя в последнее время ситуация начала меняться в пользу BWT и PPM, как обеспечивающих лучшее сжатие. Кроме того, практически все реально используемые словарные алгоритмы относятся к семейству Зива-Лемпела.

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

Ниже будут рассмотрены алгоритмы словарного сжатия, относимые к классу методов Зива-Лемпела. Методы Зива-Лемпела ориентированы на сжатие качественных данных, причем эффективность применения достигается в том случае, когда статистические характеристики обрабатываемых данных соответствуют модели источника с памятью.

2. Классические алгоритмы Зива-Лемпела

LZ77 и LZ78 являются универсальными алгоритмами сжатия, в которых словарь формируется на основании уже обработанной части входного потока, т.е. адаптивно. Принципиальным отличием является лишь способ формирования фраз. В модификациях первоначальных алгоритмов это свойство сохраняется. Поэтому словарные алгоритмы Зива-Лемпела разделяют на два семейства – алгоритмы типа LZ77 и алгоритмы типа LZ78. Иногда также говорят о словарных методах LZ1 и LZ2.

Алгоритм LZ77

Этот словарный алгоритм сжатия является самым старым среди методов LZ. Описание было опубликовано в 1977 году, но сам алгоритм разработан не позднее 1975 года.

Идея метода: словарь ограниченной длины (несколько килобайт) «скользит» по сообщению(рис.1). Цепочки знаков, которые уже есть в словаре, заменяются короткими ссылками: «адрес начала + длина», за счет чего и достигается сжатие кода.

Рисунок 1.1 – Алгоритм LZ77

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

Скользящее окно имеет длину N, т.е. в него помещается N символов, и состоит из 2 частей:

• последовательности длины W = N-n уже закодированных символов, которая и является словарем;
• упреждающего буфера, или буфера предварительного просмотра (lookahead), длины n ; обычно n на порядки меньше W.

Пусть к текущему моменту времени мы уже закодировали t символов  s1, s2, ..., st. Тогда словарем будут являться W предшествующих символов s1, st-(W-1), st-(W-1)+1, ..., st. Соответственно, в буфере находятся ожидающие кодирования символы st+1, st+2, ..., st+n. . Очевидно, что если W≥t , то словарем будет являться вся уже обработанная часть входной последовательности.

Идея алгоритма заключается в поиске самого длинного совпадения между строкой буфера, начинающейся с символа st+1 и всеми фразами словаря. Эти фразы могут начинаться с любого символа st-(W-1), st-(W-1)+1, ..., st и выходить за пределы словаря, вторгаясь в область буфера, но должны лежать в окне. Следовательно, фразы не могут начинаться с st+1 поэтому буфер не может сравниваться сам с собой. Длина совпадения не должна превышать размер буфера. Полученная в результате поиска фраза st-(i-1),st-(i-1)+1,..., st-(i-1)+(j-1) кодируется с помощью двух чисел:

• смещения (offset) от начала буфера, i ;        
• длины соответствия, или совпадения (match length), j.

Смещение и длина соответствия играют роль указателя (ссылки), однозначно определяющего фразу. Дополнительно в выходной поток записывается символ s, непосредственно следующий за совпавшей строкой буфера.

Таким образом, на каждом шаге кодер выдает описание трех объектов: смещения и длины соответствия, образующих код фразы, равной обработанной строке буфера, и одного символа s (литерала). Затем окно смещается на j+1 символов вправо и осуществляется переход к новому циклу кодирования. Величина сдвига объясняется тем, что мы реально закодировали именно j+1 символов: j с помощью указателя на фразу в словаре, и 1 с помощью тривиального копирования. Передача одного символа в явном виде позволяет разрешить проблему обработки еще ни разу не виденных символов, но существенно увеличивает размер сжатого блока.

Рассмотрим работу LZ77 на примере сообщения, приведенного в табл. 1.

Таблица 1.3

«Скользящее окно» в алгоритме LZ77

Алгоритм LZ77 выдает коды, состоящие из трех элементов:

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

В нашем примере, просматривая словарь, алгоритм обнаружит, что совпадающей подстрокой будет «<МАХ». в словаре она расположена по смещению 14, имеет длину 4 символа, а следующим символом в буфере является ';'. Таким образом, выходной код будет представлять собой тройку <14, 4, ';'>.

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

Декодирование в LZ77 еще проще, так как не нужно осуществлять поиск в словаре.

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

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

Помимо проблем с быстродействием, у алгоритма LZ77 возникают проблемы с самим сжатием. Они появляются, когда кодер не может найти совпадающую подстроку в словаре и выдает стандартный 3-компонентный код, пытаясь закодировать один символ. Если словарь имеет длину 4К, а буфер – 16 байтов, то код <0, 0, символ> будет занимать 3 байта. Кодирование одного байта в три имеет мало общего со сжатием и существенно понижает производительность алгоритма.

Алгоритм LZSS.

В 1982 г. Сторером (Storer) и Шиманским (Szimanski) на базе LZ77 был разработан алгоритм LZSS, который отличается от LZ77 производимыми кодами.

Этот алгоритм получил свое название по именам своих  разработчиков: Lempel, Ziv, Storer, Szimansky. Существенный вклад в развитие алгоритма внес Т. С. Bell.

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

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

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

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

Длина кода вычисляется следующим образом: длина подстроки не может быть больше размера буфера, а смещение не может быть больше размера словаря –1. Следовательно, длина двоичного кода смещения будет округленным в большую сторону n=log2(размер словаря), а длина двоичного кода для длины подстроки будет округленным в большую сторону m=log2(размер буфера). Каждый символ кодируется 8 битами (например, ASCII+). Т.е., для кодирования каждой подстроки исходного сообщения нужно n+m+8 бит.

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

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

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

Дерево поиска представляет собой двоичное лексикографически упорядоченное дерево. Каждый узел в дереве соответствует одной подстроке словаря и содержит ссылки на родителя и двух потомков: “большего” и “меньшего” в смысле лексикографического сравнения символьных строк.

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

Алгоритм последовательно выполняет следующие действия:

• кодирует содержимое буфера;
• считывает очередные символы в буфер, удаляя при необходимости наиболее “старые” строки из словаря;
• вставляет в дерево новые строки, соответствующие считанным символам.

Для того чтобы декодер смог вовремя остановиться, декодируя сжатое сообщение, кодер помещает в сжатый файл специальный символ “КОНЕЦ ФАЙЛА” после того, как он обработал все символы сообщения.

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

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

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

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

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

При удалении узла из дерева возможны два варианта. Если узел имеет не более одного потомка, то удаление узла осуществляется простым исправлением ссылок “родитель-потомок”. Если узел имеет два потомка, то необходимы другие действия. Для этого найдем следующий меньший узел в дереве, удалим его из дерева и заменим им текущий удаляемый узел. Следующий меньший узел находится выбором меньшего потомка и последующим перемещением от него по дереву до листа по большим ветвям.

Алгоритм LZSS, вообще говоря, является очень асимметричным. Если процедура сжатия достаточно сложна и совершает большой объем работы при обработке каждого символа сжимаемого сообщения, то декодер LZSS тривиально прост и может работать со скоростью, приближающейся к скорости процедуры обычного копирования информации.

Декодер читает один бит сжатой информации и решает - это символ или пара <смещение, длина>. Если это символ, то следующие 8 битов выдаются как раскодированный символ и помещаются в скользящее окно. Иначе, если это не закодированный конец файла, то соответствующее количество символов словаря помещается в окно и выдается в раскодированном виде. Поскольку это все, что делает декодер, понятно, почему процедура декодирования работает так быстро.

Алгоритм LZ78

Алгоритм LZ78 был опубликован в 1978 году и впоследствии стал «отцом» семейства словарных методов LZ78.

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

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

Кодер порождает только последовательность кодов фраз. Каждый код состоит из номера (индекса) n «родительской» фразы S, или префикса, и символа s.

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

Например, строка «aaabbabaabaaabab» делится на 7 фраз. Каждая из них кодируется как уже встречавшаяся ранее фраза плюс текущий символ. Например, последние три символа кодируются как фраза номер 4 («ba»), за которой следует символ «b». Фраза номер 0 - пустая строка(табл.1.4).

Таблица 1.4

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

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

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

Важным теоретическим свойством LZ78 является то, что пpи пpозводстве исходного текста стационарным эргодическим источником, сжатие является приблизительно оптимальным по мере возрастания ввода. Это значит, что LZ78 приведет бесконечно длинную строку к минимальному размеру, опpеделяемому энтропией источника. Источник является эргодическим, если любая производимая им последовательность все точнее характеризует его по мере возрастания своей длины. Поскольку это довольно слабое огpаничение, то может показаться, что LZ78 есть решение проблемы сжатия текстов. Однако, оптимальность появляется когда размер ввода стремится к бесконечности, а большинство текстов значительно короче! Она основана на размере явного символа, который значительно меньше размера всего кода фразы. Т.к. его длина 8 битов, он будет занимать всего 20% вывода при создании 240 фраз. Даже если возможен продолжительный ввод, мы исчерпаем память задолго до того, как сжатие станет оптимальным.

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

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

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

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

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

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

Очевидно, что чем больше словарь, тем (при прочих равных условиях) большую степень сжатия можно достичь. С другой стороны, важным практическим моментом является скорость упаковки, этот параметр тоже зависит от устройства словаря. Основные операции при упаковке: 1) поиск в словаре фрагмента; 2) вставка в словарь новых фрагментов. Необходимо, чтобы эти две операции были максимально быстрыми.

Выводы по главе 1

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

Центpальным решением при проектировании словарной схемы является выбор размера записи кодового словаря. Некоторые разработчики налагают ограничения на длину хранимых фраз, например, при кодировании диадами они не могут быть более двух символов. Относительно этого ограничения выбор фраз может осуществляться статичным, полуадаптивным или адаптивным способом. Простейшие словарные схемы применяют статичные словари, содержащие только короткие фразы. Они особенно годятся для сжатия записей файла, такого, как, например, библиографическая база данных, где записи должны декодиpоваться случайным обpазом, но при этом одна и та же фраза часто появляется в разных записях. Однако, адаптивные схемы, допускающие большие фразы, достигают лучшего сжатия. Рассматpиваемое сжатие Зива-Лемпела есть общий класс методов сжатия, соответствующих этому описанию и превосходящих остальные словарные схемы.

Алгоритмы семейства LZ в 1.3-1.7 раза уступают методам статистического моделирования по качеству сжатия, однако обладают очень высокой скоростью кодирования при сравнительно небольшом объеме требуемой памяти.

Огромное преимущество алгоритмов семейства LZ – чрезвычайно высокая скорость декодирования. Это позволяет применять их в тех случаях, когда декодирование осуществляется гораздо чаще кодирования или скорость декодирования очень важна (например, при хранении данных на CD-ROM, в файловых системах со сжатием и т. д.).

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

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

1.  Практические основы словарных методов сжатия

1. Пример использования алгоритма  LZ–77

Рассмотрим работу LZ77 на примере текстовых  сообщений.

Пример 1. Закодируем  по алгоритму LZ77 строку «красная краска».

Таблица 2.1

В последней строчке, буква «А» берется не из словаря, т.к. она последняя.

Длина кода вычисляется следующим образом: длина подстроки не может быть больше размера буфера, а смещение не может быть больше размера словаря -1 . Следовательно, длина двоичного кода смещения будет округленным в большую сторону  log2(размер словаря ), а длина двоичного кода для длины подстроки будет округленным в большую сторону log2размер буфера +1. А символ кодируется 8 битами (например, ASCII+).

В последнем примере длина полученного кода равна  9·(3+3+8) бит, против 14·8=112 бит исходной длины строки.

Пример 2. Попробуем сжать строку «кот_ломом_колол_слона» длиной 21 символ. Пусть длина буфера равна 7 символам, а размер словаря больше длины сжимаемой строки. Условимся также, что:

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

Таблица 2.2.

Для кодирования i нам достаточно 5 битов, для j нужно 3 бита, и пусть символы требуют 1 байта для своего представления. Тогда всего мы потратим 12·(5+3+8) = 192 бита. Исходно строка занимала 21·8 = 168 битов, т.е. LZ77 кодирует нашу строку еще более расточительным образом. Не следует также забывать, что мы опустили шаг кодирования конца последовательности, который потребовал бы еще как минимум 5 битов (размер поля i = 5 битам).

2. Пример использования алгоритма LZSS

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

Пример 1. Закодируем по алгоритму LZSS строку «красная краска».

Таблица 2.3.

Здесь длина полученного кода равна  7·9+4·7=91 бит.

Пример 2. Закодируем строку «кот_ломом_колол_слона»  с помощью алгоритма LZSS.

Пусть мы переписываем символ в явном виде, если текущая длина максимального совпадения буфера и какой-то фразы словаря меньше или равна 1. Если мы записываем символ, то перед ним выдаем флаг со значением 0, если указатель – то со значением 1. Если имеется несколько совпадающих фраз одинаковой длины, то выбираем ближайшую к буферу.

Процесс кодирования представлен в таблице 2.4.

Таблица 2.4.

Таким образом, для кодирования строки по алгоритму LZSS нам потребовалось 17 шагов: 13 раз символы были переданы в явном виде, и 4 раза мы применили указатели. Заметим, что при работе по алгоритму LZ77 нам потребовалось всего лишь 12 шагов. С другой стороны, если задаться теми же длинами для i и j, то размер закодированных по LZSS данных равен 13·(1+8) + 4·(1+5+3) = 153 битам. Это означает, что строка действительно была сжата, так как ее исходный размер 168 битов.

3. Пример использования алгоритма LZ–78

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

Пример 1. Закодировать по алгоритму LZ78 строку «красная краска», используя словарь длиной 16 фраз.

Таблица 2.5.

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

В последнем примере длина полученного кода равна 10·(4+8)=120 битам.

Пример 2. И еще раз закодируем строку «кот_ломом_колол_слона» длиной 21 символ. Для LZ78 буфер, в принципе, не требуется, поскольку достаточно легко так реализовать поиск совпадающей фразы максимальной длины, что последовательность незакодированных символов будет просматриваться только один раз. Поэтому буфер показан только с целью большей доходчивости примера. Фразу с номером 0 зарезервируем для обозначения конца сжатой строки, номером 1 будем задавать пустую фразу словаря.

Таблица 2.6.

Строку удалось закодировать за 13 шагов. Так как на каждом шаге выдавался один код, сжатая последовательность состоит из 13 кодов. Возможно использование 15 номеров фраз (от 0 до 14), поэтому для представления n посредством кодов фиксированной длины нам потребуется 4 бита. Тогда размер сжатой строки равен 13·(4+8) = 156 битам.

Вывод по главе 2

Приведенные примеры показали, что способ формирования кодов в LZ77 неэффективен и позволяет сжимать только сравнительно длинные последовательности. До некоторой степени сжатие небольших файлов можно улучшить, используя коды переменной длины для смещения i. Действительно, даже если мы используем словарь в 32 кбайт, но закодировали еще только 3 кбайт, то смещение реально требует не 15, а 12 битов. Кроме того, происходит существенный проигрыш из-за использования кодов одинаковой длины при указании длин совпадения j.

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

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

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

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

Заключение

В данной курсовой работе были рассмотрены вопросы алгоритм работы словарных методов сжатия данных. Подробно описаны словарные алгоритмы сжатия данных по мере появления и развития. Рассмотрены примеры использования алгоритмов LZ77, LZSS, LZ78.

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

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

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

Список литературы

1. Б.Д.Кудряшов Теория информации - Санкт-Петербург: СПбГУ ИТМО, 2010. –188 с.
2. Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. – М.: ДИАЛОГ-МИФИ, 2002. – 384 с.
3. Вернер М. Основы кодирования М.: Техносфера, 2004. – 288 с.
4. Основы теории информации: Учебное пособие / А.М. Маскаева. - М.: Форум: НИЦ ИНФРА-М,2014. –96 с.
5. Панин В.В. Основы теории информации: учебное пособие для вузов. – М.: БИНОМ. Лаборатория знаний, 2007. – 436с. 
6. Рябко Б.Я., Фионов А.Н. Основы современной криптографии и стега-нографии. 2-е изд. – М.: Издательство «ГОРЯЧАЯ ЛИНИЯ-ТЕЛЕКОМ». – 2013.
7. Сэломон, Д. Сжатие данных, изображения и звука. – М.: Техносфера, 2006. – 368 c. 
8. Алгоритмы сжатия [Электронный ресурс]//URL http://mf.grsu.by/UchProc/livak/en/po/comprsite/theory_contents.html(дата обращения: 7.04.2016).
9. Моделирование для сжатия текстов (Modeling for Text Compression) T. Bell, I.H. Witten, J.G. Cleary [Электронный ресурс]//URL http://www.compression.ru/download/articles/rev_univ/bell_1989_modeling/bell_1989_modeling_part2.html#343  (дата обращения: 7.04.2016).
10. Обратимое сжатие или сжатие без наличия помех [Электронный ресурс] // URL http://citforum.ru/programming/theory/szhatie.shtml  (дата обращения: 7.04.2016).