Моделирование при сжатии текстовых данных lz77

Содержание

Алгоритмы сжатия и компрессии

Опрос

Новички

LZ77 (скользящее окно)

Основная идея этого метода (его еще часто называют методом LZ1, см. [Ziv 77]) состоит в использовании ранее прочитанной части входного файла в качестве словаря. Кодер создает окно для входного файла и двигает его справа налево в виде строки символов, требующих сжатие. Таким образом, метод основан на скользящем окне. Окно разбивается на две части. Часть слева называется буфером поиска. Она будет служить текущим словарем, и в ней всегда содержатся символы, которые недавно поступили и были закодированы. Правая часть окна называется упреждающим буфером, содержащим текст, который будет сейчас закодирован. На практике буфер поиска состоит из нескольких тысяч байт, а длина упреждающего буфера равна нескольким десяткам символов. Вертикальная черта | между символами t и е означает текущее разделение между двумя буферами. Итак, предположим, что текст «sir_sid_eastman_easily_t» уже сжат, а текст «eases_sea_sick_seals» нуждается в сжатии.

Кодер просматривает буфер поиска в обратном порядке (справа налево) и ищет в нем первое появление символа е из упреждающего буфера. Он обнаруживает такой символ в начале слова easily. Значит, е находится (по смещению) на расстоянии 8 от конца буфера поиска. Далее кодер определяет, сколько совпадающих символов следует за этими двумя символами е. В данном случае совпадение по символам eas имеет длину 3. Кодер продолжает поиск, пытаясь найти более длинные совпадающие последовательности. В нашем случае имеется еще одна совпадающая последовательность той же длины 3 в слове eastman со смещением 16. Декодер выбирает самую длинную из них, а при совпадении длин — самую удаленную, и готовит метку (16, 3, «е»).

Выбор более удаленной ссылки упрощает кодер. Интересно отметить, что выбор ближайшего совпадения, несмотря на некоторое усложнение программы, также имеет определенные преимущества. При этом выбирается наименьшее смещение. Может показаться, что в этом нет преимущества, поскольку в метке будет предусмотрено достаточно разрядов для хранения самого большого смещения. Однако, можно следовать LZ77 с кодированием Хаффмана или другого статистического кодирования меток, при котором более коротким смещениям присваиваются более короткие коды. Этот метод, предложенный Бернардом Хердом (Bernard Herd), называется LZH. Если получается много коротких смещений, то при LZH достигается большее сжатие.

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

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

. . sir _sid_eastman_easily_tease s_sea_sick_seals. .

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

Ясно, что метки вида (0,0. ), которые кодируют единичные символы, не обеспечивают хорошее сжатие. Легко оценить их длину. Размер смещения равен \log2S] , где S — длина буфера поиска. На практике этот буфер имеет длину в несколько сотен байт, поэтому смещение имеет длину 10 — 12 бит. Поле «длина» имеет размер

86 Глава 2. Словарные методы

равный [log2(L — I)] , где L — длина упреждающего буфера (в следующем абзаце будет объяснено почему надо вычитать 1). Обычно упреждающий буфер имеет длину нескольких десятков байтов. Поэтому длина этого поля равна нескольким битам. Размер поля «символ», обычно, равен 8 бит, но в общем случае — flog2А] , где Л

размер алфавита. Полный размер метки (0,0. ) одиночного символа равен 11-1-5-1-8=24 бит, что много больше длины 8 «сырого» символа без нулевых элементов кода.

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

. . .Mr._ alf_eastman_easily_grows_alf alfa_in_his_ garden. .

Первый символ а в упреждающем буфере совпадает с 5-ым а буфера поиска. Может показаться, что оба крайних а подходят с длиной совпадения 3, поэтому кодер выберет самый левый символ и создаст метку (28,3,«а»). На самом деле кодер образует метку (3,4,«_>>). Строка из четырех символов «alf а» из упреждающего буфера совпадает с тремя символами «alf» буфера поиска и первым символом «а» упреждающего буфера. Причина этого заключается в том, что декодер может обращаться с такой меткой очень естественно безо всяких модификаций. Он начинает с позиции 3 буфера поиска и копирует следующие 4 символа, один за другим, расширяя буфер вправо. Первые 3 символа копируются из старого содержимого буфера, а четвертый является копией первого из этих новых трех. Следующий пример еще более убедителен (хотя он немного надуман):

alf _eastman_easily_yells_A АААААААААА АААААН. . .

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

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

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

Базисный метод LZ77 улучшался исследователями и программистами многими способами в течение 80-х и 90-х годов прошлого века. Один возможный путь — это использование кодов переменной длины при кодировании полей смещения и длины в метке. Другой путь — увеличение размеров обоих буферов. Увеличение буфера поиска дает возможность искать больше совпадений, но ценой будет служить увеличение времени поиска. Очевидно, большой буфер поиска потребует более изощренной структуры данных для ускорения поиска (см. § 2.4.2). Третье улучшение относится к скользящему окну. Простейший подход заключается в перемещении всего текста влево после каждого совпадения. Более быстрый прием заключается в замене линейного окна на циклическую очередь, в которой скольжение окна делается переустановкой двух указателей (см. § 2.1.1). Еще одно улучшение состоит в добавлении одного бита (флага) в каждую метку, что исключает третье поле (см. § 2.2).

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

Алгоритмы сжатия данных

Энтропия и количество информации

Комбинаторная, вероятностная и алгоритмическая оценка количества информации

Моделирование и кодирование

Некоторые алгоритмы сжатия данных

BWT — преобразование и компрессор

Алгоритм арифметического кодирования

Реализация алгоритма арифметического кодирования

Доказательство правильности декодирования

Приращаемая передача и получение

Переполнение и завершение

Адаптивная модель для арифметического кодирования

Приложение 1. Программный код

Приложение 2. Интерфейс программы

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

Первые алгоритмы сжатия были примитивными в связи с тем, что была примитивной вычислительная техника. С развитием мощностей компьютеров стали возможными все более мощные алгоритмы. Настоящим прорывом было изобретение Лемпелем и Зивом в 1977 г. словарных алгоритмов. До этого момента сжатие сводилось к примитив­ному кодированию символов. Словарные алгоритмы позволяли кодир­овать повторяющиеся строки символов, что позволило резко повысить степень сжатия. Важную роль сыграло изобретение примерно в это же время арифметического кодирования, позволившего воплотить в жизнь идею Шеннона об оптимальном кодировании. Следующим прорывом было изобретение в 1984 г. алгоритма РРМ. Следует отметить, что это изобретение долго оставалось незамеченным. Дело в том, что алгоритм сложен и требует больших ресурсов, в первую очередь больших объемов памяти, что было серьезной проблемой в то время. Изобретенный в том же 1984 г. алгоритм LZW был чрезвычайно популярен благодаря своей простоте, хорошей рекламе и нетребовательности к ресурсам, несмотря на относительно низкую степень сжатия. На сегодняшний день алгоритм РРМ является наилучшим алгоритмом для сжатия текстовой информации, aLZW давно уже не встраивается в новые приложения (однако широко используется в старых).

Будущее алгоритмов сжатия тесно связано с будущим компью­терных технологий. Современные алгоритмы уже вплотную приблизи­лись к Шенноновской оценке 1.3 бита на символ, но ученые не видят причин, по которым компьютер не может предсказывать лучше, чем человек. Для достижения высоких степеней сжатия приходится использовать более сложные алгоритмы. Однако существовавшее одно время предубеждение, что сложные алгоритмы с более высокой степенью сжатия всегда более медленны, несостоятельно. Так, существуют крайне быстрые реализации алгоритмов РРМ для текстовой информации и SPIHT для графики, имеющие очень высокую степень сжатия.

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

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

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

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

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

При реализации алгоритма арифметического кодирования использовался язык C# и визуальная среда программирования MicrosoftVisualStudio 2005. Язык C# имеет следующие преимущества: простота, объектная ориентированность, типовая защищенность, “сборка мусора”, поддержка совместимости версий, упрощение отладки программ.

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

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

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

Таким образом, для передачи состояния объекта достаточно I=log2 Nбит информации. Заметим, что количество информации может быть дробным. Разумеется, дробное количество информации невозможно сохранить на носителе или передать по каналам связи. В то же время, если необходимо передать либо сохранить большое количество блоков информации дробной длины, их всегда можно сгруппировать таким образом, чтобы полностью исключить потери (например, посредством арифметического кодирования).

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

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

Приведенные формулы показывают, что вне зависимости от того, как были получены вероятности наступления следующих событий, для кодирования события с вероятностью р достаточно — log2 pбит (в полном соответствии с теоремой Шеннона об оптимальном кодировании).

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

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

Моделирование обеспечивает предсказание вероятности наступ­ления возможных событий, кодирование обеспечивает представление события в виде -log2 pбит, где р — предсказанная вероятность наступ­ления события. Задача моделирования, как правило, более сложная. Это обусловлено высокой сложностью современных моделей данных. В то же время кодирование не является серьезной проблемой. Существует большое количество стандартных кодеров, различающихся по степени сжатия и быстродействию. Как правило, в системах сжатия исполь­зуемый кодер при необходимости может быть легко заменен другим.

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

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

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

■ последовательности длины W=N-nуже закодированных символов, которая и является словарем;

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

Пусть к текущему моменту времени мы уже закодировали tсимволов S1 , S2 , . St . Тогда словарем будут являться Wпредшествующих символов 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) кодируется с помощью двух чисел:

1) смещения (offset) от начала буфера, i;

2) длины соответствия, или совпадения (matchlength), j;

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

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

Алгоритм LZ78, предложенный в 1978 г. Лемпелом и Зивом, нашел свое практическое применение только после реализации LZW84, предложенной Велчем в 1984 г.

Словарь является расширяющимся (expanding). Первоначально в нем содержится только 256 строк длиной в одну букву-все коды ASCII. В процессе работы словарь разрастается до своего максимального объема |Vmax | строк (слов). Обычно, объем словаря достигает нескольких десятков тысяч слов. Каждая строка в словаре имеет свою известную длину и этим похожа на привычные нам книжные словари и отличается от строк LZ77, которые допускали использование подстрок. Таким образом, количество слов в словаре точно равно его текущему объему. В процессе работы словарь пополняется по следующему закону:

1. В словаре ищется слово str, максимально совпадающее с текущим кодируемым словом в позиции posисходного текста. Так как словарь первоначально не пустой, такое слово всегда найдется;

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

. Длина кода равна |position|+|B||=[logVmax]+8 (бит);

3. Если словарь еще не полон, новая строка strВ добавляется в словарь по адресу last_position, размер словаря возрастает на одну позицию;

4. Указатель в исходном тексте posсмещается на |strB|=|str|+l байт дальше к символу, следующему за В.

В таком варианте алгоритм почти не нашел практического применения и был значительно модернизирован. Изменения коснулись принципов управления словарем (его расширения и обновления) и способа формирования выходного кода:

Птак как словарь увеличивается постепенно и одинаково для кодировщика и декодировщика, для кодирования позиции нет необходимости использовать [logVmax ] бит, а можно брать лишь [logV] бит, где V-текущий объем словаря.

Самая серьезная проблема LZ78-переполнение словаря: если словарь полностью заполнен, прекращается его обновление и процесс сжатия может быть заметно ухудшен (метод FREEZE). Отсюда следует вывод-словарь нужно иногда обновлять. Самый простой способ как только словарь заполнился его полностью обновляют. Недостаток очевиден кодирование начинается на пустом месте, как бы с начала, и пока словарь не накопится сжатие будет незначительным, а дальше-замкнутый цикл опять очистка словаря. Поэтому предлагается словарь обновлять не сразу после его заполнения, а только после того, как степень сжатия начала падать (метод FLUSH). Более сложные алгоритмы используют два словаря, которые заполняются синхронно, но с задержкой на |V|/2 слов один относительно другого. После заполнения одного словаря, он очищается, а работа переключается на другой (метод SWAP). Еще более сложными являются эвристические методы обновления словарей в зависимости от частоты использования тех или иных слов (LRU, TAG).

Выходной код также формируется несколько иначе (сравните с предыдущим описанием):

1. В словаре ищется слово str, максимально совпадающее с текущим кодируемым словом в позицииposисходного текста;

2. В выходной файл помещается номер найденного слова в словаре

. Длина кода равна |position|=[logV] (бит);

3. Если словарь еще не полон, новая строка strВ добавляется в словарь по адресу last_position, размер словаря возрастает на одну позицию;

4. Указатель в исходном тексте posсмещается на |str| байт дальше к символу В.

Алгоритм PPM (predictionbypartialmatching) — это метод контекстно-ограниченного моделирования, позволяющий оценить вероятность символа в зависимости от предыдущих символов. Строку символов, непосредственно предшествующую текущему символу, будем называть контекстом. Модели, в которых для оценки вероятности используются контексты длиной не более чем N, принято называть моделями порядка N.

Вероятность символа может быть оценена в контекстах разных порядков. Например, символ «о» в контексте «tobeornott» может быть оценен в контексте первого порядка «t», в контексте второго порядка «_t», в контексте третьего порядка «t_t» и т.д. Он также может быть оценен в контексте нулевого порядка, где вероятности символов не зависят от контекста, и в контексте минус первого порядка, где все символы равновероятны. Контекст минус первого порядка используется для того, чтобы исключить ситуацию, когда символ будет иметь нулевую вероятность и не сможет быть закодирован. Это может случиться, если вероятность символа не будет оценена ни в одном из контекстов (что возможно, если символ в них ранее не встречался).

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

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

BWT — преобразование и компрессор

BWT-компрессор (Преобразование Барроуза – Уиллера) — сравнительно новая и революционная техника для сжатия информации (в особенности-текстов), основанная на преобразовании, открытом в 1983 г. и описанная в 1994 г.. BWT является удивительным алгоритмом. Во-первых, необычно само преобразование, открытое в научной области, далекой от архиваторов. Во-вторых,даже зная BWT, не совсем ясно, как его применить к сжатию информации. В-третьих, BW преобразование чрезвычайно просто. И, наконец, сам BWT компрессор состоит из «магической» последовательности нескольких рассмотренных ранее алгоритмов и требует, поэтому, для своей реализации самых разнообразных программных навыков.

BWT не сжимает данные, но преобразует блок данных в формат, исключительно подходящий для компрессии. Рассмотрим его работу на упрощенном примере. Пусть имеется словарь V из N символов. Циклически переставляя символы в словаре влево, можно получить N различных строк длиной N каждая. В нашем примере словарь-это слово V=»БАРАБАН» и N=7. Отсортируем эти строки лексикографически и запишем одну под другой:

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

Фактический «выход» преобразования состоит из строки L=»РББАНАА» и первичного индекса I, показывающего, какой символ из L является действительным первым символом словаря V (в нашем случае I=2). Зная L и I можно восстановить строку V.

Этот алгоритм кодиро­вания информации был предложен Д.А. Хаффманом в 1952 году. Идея алгоритма состоит в следующем: зная вероятности вхождения символов в сообщение, можно описать процедуру построения кодов переменной длины, состоящих из целого количества битов. Символам с большей вероятностью присваиваются более короткие коды. Коды Хаффмана имеют уникальный префикс, что и позволяет однозначно их декодировать, несмотря на их переменную длину.

Классический алгоритм Хаффмана на входе получает таблицу частот встречаемости символов в сообщении. Далее на основании этой таблицы строится дерево кодирования Хаффмана (Н-дерево). Алгоритм построения Н-дерева прост и элегантен.

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

2. Выбираются два свободных узла дерева с наименьшими весами.

3. Создается их родитель с весом, равным их суммарному весу.

4. Родитель добавляется в список свободных узлов, а двое его детей удаляются из этого списка.

5. Одной дуге, выходящей из родителя, ставится в соответствие бит 1, другой — бит 0.

6. Шаги, начиная со второго, повторяются до тех пор, пока в списке свободных узлов не останется только один свободный узел. Он и будет считаться корнем дерева.

Допустим, у нас есть следующая таблица частот:

Название: Алгоритмы сжатия данных
Раздел: Рефераты по информатике, программированию
Тип: курсовая работа Добавлен 02:50:21 26 июля 2009 Похожие работы
Просмотров: 1052 Комментариев: 14 Оценило: 3 человек Средний балл: 5 Оценка: неизвестно Скачать
15 7 6 6 5
А Б В Г Д

На первом шаге из листьев дерева выбираются два с наименьшими весами — Г и Д. Они присоединяются к новому узлу-родителю, вес которого устанавливается в 5+6 = 11. Затем узлы Г и Д удаляются из списка свободных. Узел Г соответствует ветви 0 родителя, узел Д — ветви 1.

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

Рис. 2. Дерево кодирования Хаффмана после второго шага

На следующем шаге «наилегчайшей» парой оказываются узлы Б/В и Г/Д. Для них еще раз создается родитель, теперь уже с весом 24. Узел Б/В соответствует ветви 0 родителя, Г/Д—ветви 1.

На последнем шаге в списке свободных осталось только два узла — это А и узел (Б/В)/(Г/Д). В очередной раз создается родитель с весом 39 и бывшие свободными узлы присоединяются к разным его ветвям.

Поскольку свободным остался только один узел, то алгоритм построения дерева кодирования Хаффмана завершается. Н-дерево представлено на рис. 3.

Рис. 3. Окончательное дерево кодирования Хаффмана

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

Дня данной таблицы символов коды Хаффмана будут выглядеть следующим образом.

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

Классический алгоритм Хаффмана имеет один существенный недостаток. Дня восстановления содер­жимого сжатого сообщения декодер должен знать таблицу частот, которой пользовался кодер. Следовательно, длина сжатого сообщения увеличивается на длину таблицы частот, которая должна посылаться впереди данных, что может свести на нет все усилия по сжатию сообщения. Кроме того, необходимость наличия полной частотной статистики перед началом собственно кодирования требует двух проходов по сообщению: одного для построения модели сообщения (таблицы частот и Н-дерева), другого для собственно кодирования.

Арифметическое сжатие — достаточно изящный метод, в основе которого лежит очень простая идея. Мы представляем кодируемый текст в виде дроби, при этом строим дробь таким образом, чтобы наш текст был представлен как можно компактнее. Для примера рассмотрим построение такой дроби на интервале [0, 1) (0 — включается, 1 — нет). Интервал [0, 1) выбран потому, что он удобен для объяснений. Мы разбиваем его на подынтервалы с длинами, равными вероятностям появления символов в потоке. В дальнейшем будем называть их диапазонами соответствующих символов.

Пусть мы сжимаем текст «КОВ.КОРОВА» (что, очевидно, означает «коварная корова»). Распишем вероятности появления каждого символа в тексте (в порядке убывания) и соответствующие этим символам диапазоны:

Символ Частота Вероятность Диапазон
О 3 0.3 [0.0; 0.3)
К 2 0.2 [0.3; 0.5)
В 2 0.2 [0.5; 0.7)
Р 1 0.1 [0.7; 0.8)
А 1 0.1 [0.8; 0.9)
“.” 1 0.1 [0.9; 1.0)

Будем считать, что эта таблица известна в компрессоре и декомпрессоре. Кодирование заключается в уменьшении рабочего интервала. Для первого символа в качестве рабочего интервала берется [0, 1). Мы разбиваем его на диапазоны в соответствии с заданными частотами символов (см. таблицу диапазонов). В качестве следующего рабочего интервала берется диапазон, соответствующий текущему кодируемому символу. Его длина пропорциональна вероятности появления этого символа в потоке. Далее считываем следующий символ. В качестве исходного берем рабочий интервал, полученный на предыдущем шаге, и опять разбиваем его в соответствии с таблицей диапазонов. Длина рабочего интервала уменьшается пропорционально вероятности текущего символа, а точка начала сдвигается вправо пропорционально началу диапазона для этого символа. Новый построенный диапазон берется в качестве рабочего и т. д.

Используя исходную таблицу диапазонов, кодируем текст «КОВ.КОРОВА»:

Исходный рабочий интервал [0,1).

Символ «К» [0.3; 0.5) получаем [0.3000; 0.5000).

Символ «О» [0.0; 0.3) получаем [0.3000; 0.3600).

Символ «В» [0.5; 0.7) получаем [0.3300; 0.3420).

Символ «.» [0.9; 1.0) получаем [0,3408; 0.3420).

Графический процесс кодирования первых трех символов можно представить так, как на рис. 4.

Рис. 4. Графический процесс кодирования первых трех символов

Таким образом, окончательная длина интервала равна произведению вероятностей всех встретившихся символов, а его начало зависит от порядка следования символов в потоке. Можно обозначить диапазон символа с как [а[с]; b[с]), а интервал для i-го кодируемого символа потока как [li , hi ).

Большой вертикальной чертой на рисунке выше обозначено произвольное число, лежащее в полученном при работе интервале [/i , hi ). Для последовательности «КОВ.», состоящей из четырех символов, за такое число можно взять 0.341. Этого числа достаточно для восстановления исходной цепочки, если известна исходная таблица диапазонов и длина цепочки.

Рассмотрим работу алгоритма восстановления цепочки. Каждый следующий интервал вложен в предыдущий. Это означает, что если есть число 0.341, то первым символом в цепочке может быть только «К», поскольку только его диапазон включает это число. В качестве интервала берется диапазон «К» — [0.3; 0.5) и в нем находится диапазон [а[с]; b[с]), включающий 0.341. Перебором всех возможных символов по приведенной выше таблице находим, что только интервал [0.3; 0.36), соответствующий диапазону для «О», включает число 0.341. Этот интервал выбирается в качестве следующего рабочего и т. д.

Ниже показан фрагмент псевдокода процедур кодирования и декодирования. Символы в нем нумеруются как 1,2,3. Частотный интервал для i-го символа задается от cum_freq[i] до cum_freq[i-1]. Пpи убывании i cum_freq[i] возрастает так, что cum_freq[0] = 1. (Причина такого «обpатного» соглашения состоит в том, что cum_freq[0] будет потом содеpжать ноpмализующий множитель, котоpый удобно хpанить в начале массива). Текущий pабочий интеpвал задается в [low; high] и будет в самом начале pавен [0; 1) и для кодиpовщика, и для pаскодиpовщика.

С каждым символом текста обpащаться к пpоцедуpе encode_symbol(). Пpовеpить, что «завеpшающий» символ закодиpован последним. Вывести полученное значение интеpвала [low; high).

range = high — low

high = low + range*cum_freq[symbol-1]

low = low + range*cum_freq[symbol]

Value — это поступившее на вход число. Обpащение к пpоцедуpе decode_symbol() пока она не возвpатит «завеpшающий» символ.

//поиск такого символа, что

Из выражения (1) имеем:

В отличие от псеводокода, программа представляет low и high целыми числами. В псевдокоде текущий интеpвал пpедставлен чеpез [low; high), а в пpогpамме это [low; high] — интеpвал, включающий в себя значение high. Hа самом деле более пpавильно, хотя и более непонятно, утвеpждать, что в пpогpамме пpедставляемый интеpвал есть [low; high + 0.1111. ) по той пpичине, что пpи масштабитовании гpаниц для увеличения точности, нули смещаются к младшим битам low, а единицы смещаются в high.

По меpе сужения кодового интеpвала, стаpшие биты low и high становятся одинаковыми, и поэтому могут быть пеpеданы немедленно, т.к. на них будущие сужения интеpвала все pавно уже не будут влиять. Поскольку мы знаем, что low≤high, это воплотится в следующую пpогpамму:

low = 2 * (low — Half);

high = 2 * (high — Half) + 1;

гаpантиpующую, что после ее завеpшения будет спpеведливо неpавенство: low Half)

value = 2 * (value — Half) + input_bit();

low = 2 * (low — Half);

high = 2 * (high — Half) + 1;

Как показано в псевдокоде, арифметическое кодирование работает при помощи масштабирования накопленных вероятностей, поставляемых моделью в интервале [low; high] для каждого передаваемого символа. Пpедположим, что low и high настолько близки дpуг к дpугу, что опеpация масштабиpования пpиводит полученные от модели pазные символы к одному целому числу, входящему в [low; high]. В этом случае дальнейшее кодиpование пpодолжать невозможно. Следовательно, кодиpовщик должен следить за тем, чтобы интеpвал [low; high] всегда был достаточно шиpок. Пpостейшим способом для этого является обеспечение шиpины интеpвала не меньшей max_frequency — максимального значения суммы всех накапливаемых частот.

Как можно сделать это условие менее стpогим? Объясненная выше опеpация битового сдвига гаpантиpует, что low и high могут только тогда становиться опасно близкими, когда заключают между собой half. Пpедположим, они становятся настолько близки, что

first_qtr ≤low 14 — 1 и top_value = 2 16 — 1.

Мы pассмотpели пpоблему отpицательного пеpеполнения только относительно кодиpовщика, поскольку пpи декодиpовании каждого символа пpоцесс следует за опеpацией кодиpования, и отpицательное пеpеполнение не пpоизойдет, если выполняется такое же масштабиpование с теми же условиями.

Теперь рассмотрим возможность переполнения при целочисленном умножении. Переполнения не произойдет, если произведение range*max_frequency вмещается в целое слово, т.к. накопленные частоты не могут превышать max_frequency. range имеет наибольшее значение в top_value + 1, поэтому максимально возможное произведение в программе есть 2 16 *(2 14 — 1), которое меньше 2 30 .

При завершении процесса кодирования необходимо послать уникальный завершающий символ (EOF-символ), а затем послать вслед достаточное количество битов для гарантии того, что закодированная строка попадет в итоговый рабочий интервал. Т.к. пpоцедуpа done_encoding() может быть увеpена, что low и high огpаничены либо выpажением (1a), либо (1b), ему нужно только пеpедать 01 или 10 соответственно, для удаления оставшейся неопpеделенности. Удобно это делать с помощью пpоцедуpы bit_plus_follow(). Пpоцедуpа input_bit() на самом деле будет читать немного больше битов, из тех, что вывела output_bit(), потому что ей нужно сохpанять заполнение нижнего конца буфеpа. Hеважно, какое значение имеют эти биты, поскольку EOF уникально опpеделяется последними пеpеданными битами.

Программа должна работать с моделью, которая предоставляет пару перекодировочных таблиц index_to_char[] и char_to_index[], и массив накопленных частот cum_freq[]. Причем к последнему предъявляются следующие требования:

никогда не делается попытка кодиpовать символ i, для котоpого

cum_freq[0] — 4 битов/символ.

Дополнительные затpаты на масштабиpование счетчиков отчасти больше, но все pавно очень малы. Для коpотких текстов (меньших 2 14 байт) их нет. Hо даже с текстами в 10 5 — 10 6 байтов накладные pасходы, подсчитанные экспеpиментально, составляют менее 0.25% от кодиpуемой стpоки.

Адаптивная модель, пpи угpозе пpевышения общей суммой накопленных частот значение max_frequency, уменьшает все счетчики. Это пpиводит к тому, что взвешивать последние события тяжелее, чем более pанние. Т.о. показатели имеют тенденцию пpослеживать изменения во входной последовательности, котоpые могут быть очень полезными.

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

В курсовой работе был реализован алгоритм арифметического кодирования и создана программа «Архиватор» со всеми необходимыми функциями.

Для реализации использовался язык C# и визуальная среда программирования MicrosoftVisualStudio 2005. В результате программное обеспечение очень компактно, интуитивно понятно и эффективно в работе.

1. Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. — М.: ДИАЛОГ-МИФИ, 2002. — 384 с.

2. Сэломон Д. Сжатие данных, изображений и звука. Data Compression Methods. Серия: Мир программирования. Издательство: Техносфера, 2004. — 368 с.

3. Артюшенко В. М., Шелухин О. И., Афонин М. Ю. Цифровое сжатие видеоинформации и звука. Издательство: Дашков и Ко, 2004. — 426 с.

4. Седжвик Р. Фундаментальные алгоритмы на C++. Части 1-4. Анализ. Структуры данных. Сортировка. Поиск. Издательство: ДиаСофт, 2002. — 688 с.

// Количество бит для кода

// Максимально возможное значениекода

const int top_value = (int)(((long)1 = 0; i—)

freq[i] = (freq[i] + 1) / 2;

/* Обновление перекодировочных таблиц в случае перемещения символа */

for (i = symbol; freq[i] == freq[i — 1]; i—) ;

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

Алгоритм LZSS

Алгоритм LZSS позволяет достаточно гибко сочетать в выходной последовательности символы и указатели (коды фраз), что до некоторой степени устраняет присущую LZ77 расточительность, проявляющуюся в регулярной передаче одного символа в прямом виде. Эта модификация LZ77 была предложена в 1982 году Сторером (Storer) и Жимански (Szymanski) [2.10].

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

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

Закодируем строку «кот_ломом_колол_слона» из предыдущего примера и сравним коэффициент сжатия для LZ77 и LZSS.

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

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

Таблица 2.5.
Шаг Скользящее окно Совпадающая фраза Закодированные данные
Словарь Буфер f i j s
1 кот_лом ‘к’
2 к от_ломо ‘о’
3 ко т_ломом ‘т’
4 кот _ломом_ ‘_’
5 кот_ ломом_к ‘л’
6 кот_л омом_ко о ‘о’
7 кот_ло мом_кол ‘м’
8 кот_лом ом_коло ом 8 2
9 кот_ломом _колол_ _ 2 ‘_’
10 кот_ломом_ колол_с ко 1
11 кот_ломом_ко лол_сло ло 1 2
12 . от_ломом_коло л_слона л ‘л’
13 . т_ломом_колол _слона _ ‘_’
14 . _ломом_колол_ слона ‘с’
15 . ломом_колол_с лона ло 1
16 . мом_колол_сло на ‘н’
17 . ом_колол_слон а ‘а’

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

Рассмотрим алгоритм сжатия подробнее.

Алгоритм LZ78

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

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

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

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

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

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

Ниже приведен пример реализации алгоритма сжатия LZ78.

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

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

Несмотря на относительную быстроту кодирования LZ78, при грамотной реализации алгоритма оно все же медленнее декодирования , соотношение скоростей равно обычно 3:2.

Интересное свойство LZ78 заключается в том, что если исходные данные порождены источником с определенными характеристиками (он должен быть стационарным 1 Многомерные распределения вероятностей генерации последовательностей (слов) из n символов не меняются во времени, причем n — любое конечное число и эргодическим 2 Среднее по времени равно среднему по числу реализаций; иначе говоря, для оценки свойств источника достаточно только одной длинной сгенерированной последовательности ), то коэффициент сжатия приближается по мере кодирования к минимальному достижимому [2.13]. Иначе говоря, количество битов, затрачиваемых на кодирование каждого символа, в среднем равно так называемой энтропии источника. Но, к сожалению, сходимость медленная, и на данных реальной длины алгоритм ведет себя не лучшим образом. Так, например, коэффициент сжатия текстов в зависимости от их размера обычно колеблется от 3.5 до 5 битов/символ. Кроме того, нередки ситуации, когда обрабатываемые данные порождены источником с ярко выраженной нестационарностью. Поэтому при оценке реального поведения алгоритма следует относиться с большой осторожностью к теоретическим выкладкам, обращая внимание на выполнение соответствующих условий.

Доказано, что аналогичным свойством сходимости обладает и классический алгоритм LZ77, но скорость приближения к энтропии источника меньше, чем у алгоритма LZ78 [2.12].

Подстановочные или словарно-ориентированные алгоритмы сжатия информации. Методы Лемпела-Зива

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

  1. GУметь использовать на практике современные технологии и методы менеджмента.
  2. III. Гидрометаллургичесие методы
  3. IV Методы установленных цен в маркетинге
  4. LZ-алгоритмы распаковки данных. Пример 13.6
  5. LZ-алгоритмы распаковки данных. Примеры
  6. V. Ценовая политика на предприятии. Методы ценообразования.
  7. X Методы изучения рынка с помощью инструментария маркетинга
  8. Абстрактные типы данных. Методы представления множеств.
  9. Адаптивные алгоритмы сжатия. Кодирование Хаффмена
  10. Административные (организационно-распорядительные) методы управления.
  11. АДМИНИСТРАТИВНЫЕ И СОЦИАЛЬНО-ПСИХОЛОГИЧЕСКИЕ МЕТОДЫ УПРАВЛЕНИЯ
  12. Административные методы управления.
Илон Маск рекомендует:  Что такое код mysql_field_flags

Лекция 12

Тема 8. Методы кодирования информации со сжатием.

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

Мы с вами, на самом деле, уже знакомы с кодами такого рода. Это коды Шеннона –Фано и Хаффмена которые называют оптимальным неравномерными кодами с переменной длиной слова. Если мы кодируем , например текстовое сообщение без учета вероятности появления символов, то на каждый знак мы можем тратить до 8 бит ( если знаки определяются таблицей ASCII). Знание статистики появления знаков позволяет сократить количество битов на знак алфавита в среднем до величины энтропии источника.

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

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

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

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

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

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

Первая группа с неявным видом словаря – основа алгоритм LZ77

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

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

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

Процедура кодирования в соответствии с алгоритмами этой группы иллюстрируется примером 12.1.

Вход А Б В Г Д А Б В Е

Выход А Б В Г Д 1 Е

произошло сжатие за счет повторяющегося куска текста А Б В.

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

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

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

Идею этой группы алгоритмов можно также пояснить с помощью примера 12.2.

Вход А Б В А Б В А Б Г Д Е

Словарь основной А-1, Б-2, В-3, Г-4, Д-5, Е-5, словарь фраз АБ-6, АБВ-7

Выход 12361645 плюс необходимо каким-то образом сохранять и основной словарь.

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

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

Основная идея LZ77 состоит в том, что второе и последующие вхождения некоторой строки символов в сообщении заменяются ссылками на ее первое вхождение.

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

LZ77 использует «скользящее» по сообщению окно, разделенное на две неравные части. Первая, большая по размеру, включает уже просмотренную часть сообщения. Это текущий словарь кодировщика, откуда он берет посторяющиеся куски. Вторая, намного меньшая, является буфером, содержащим еще незакодированные символы входного потока. Обычно размер окна словаря составляет несколько килобайт, а размер буфера — не более ста байт. Алгоритм пытается найти в скользящем по тексту словаре фрагмент, совпадающий с содержимым буфера или части буфера.

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

· смещение в словаре относительно его начала подстроки, совпадающей с началом содержимого буфера;

· длина этой подстроки;

· первый символ буфера, следующий за подстрокой.

Закодировать по алгоритму LZ77 строку «КРАСНАЯ КРАСКА».

В 9-й строке необходим сдвиг на5 позиций (длина совпадающей строки +1) и считывание стольких же символов в буфер.

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

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

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

| следующая лекция ==>
Пропускная способность канала связи с помехами для непрерывных сообщений | LZ77-алгоритм распаковки данных. Пример 12.4

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

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

Алгоритмы сжатия: описание, основные приемы, характеристики

Сжатие является частным случаем кодирования, основной характеристикой которого является то, что результирующий код меньше исходного. Процесс основан на поиске повторений в информационных рядах и последующем сохранении только одного рядом с количеством повторений. Таким образом, например, если последовательность появляется в файле, как «AAAAAA», занимая 6 байтов, он будет сохранен, как «6A», который занимает только 2 байта, в алгоритме сжатия RLE.

История возникновения процесса

Азбука Морзе, изобретенная в 1838 году — первый известный случай сжатия данных. Позже, когда в 1949 году мейнфрейм-компьютеры начали завоевывать популярность, Клод Шеннон и Роберт Фано изобрели кодирование, названного в честь авторов — Шеннона-Фано. Это шифрование присваивает коды символам в массиве данных по теории вероятности.

Только в 1970-х с появлением интернета и онлайн-хранилищ, были реализованы полноценные алгоритмы сжатия. Коды Хаффмана динамически генерировались на базе входной информации. Ключевое различие между кодированием Шеннона-Фано и кодированием Хаффмана состоит в том, что в первом дерево вероятности строилось снизу вверх, создавая неоптимальный результат, а во втором — сверху вниз.

В 1977 году, Авраам Лемпель и Джейкоб Зив издали свой инновационный метод LZ77, использующий более модернизированный словарь. В 1978 году, та же команда авторов, издала усовершенствованный алгоритм сжатия LZ78. Который использует новый словарь, анализирующий входные данные и генерирующий статический словарь, а не динамический, как у 77 версии.

Формы исполнения компрессии

Компрессия выполняется программой, которая использует формулу или алгоритм, определяющих, как уменьшить размер данных. Например, представить строку битов с меньшей строкой 0 и 1, используя словарь для преобразований или формулу.

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

Илон Маск рекомендует:  Что такое код fdf_get_status

Для передачи процесс выполняют в блоке передачи, включая данные заголовка. Когда информация отправляется или принимается через интернет, заархивированные по отдельности или вместе с другими большими файлами, могут передаваться в ZIP, GZIP или другом «уменьшенном» формате.

Преимущество алгоритмов сжатия:

  1. Значительно уменьшает объем памяти. При степени сжатия 2:1 файл в 20 мегабайт (МБ) займет 10 МБ пространства. В результате администраторы сети тратят меньше денег и времени на хранение баз данных.
  2. Оптимизирует производительность резервного копирования.
  3. Важный метод сокращения данных.
  4. Практически любой файл может быть сжат, но важно выбрать нужную технологию под конкретный тип файла. Иначе файлы могут быть «уменьшены», но при этом общий размер не изменится.

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

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

Алгоритм сжатия Хаффмана

Этот процесс, который можно использовать для «уменьшения» или шифрования.

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

Порядок создания алгоритмы сжатия данных:

  1. Просчитывают, сколько раз каждый символ повторяется в файле для «уменьшения».
  2. Создают связанный список с информацией о символах и частотах.
  3. Выполняют сортировку списка от наименьшего к наибольшему в зависимости от частоты.
  4. Преобразуют каждый элемент в списке в дерево.
  5. Объединяют деревья в одно, при этом первые два образуют новое.
  6. Добавляют частоты каждой ветви в новый элемент дерева.
  7. Вставляют новое в нужное место в списке, в соответствии с суммой полученных частот.
  8. Назначают новый двоичный код каждого символа. Если берется нулевая ветвь, к коду добавляется ноль, а если первая ветвь, добавляется единица.
  9. Файл перекодируется в соответствии с новыми кодами.
  10. Например характеристики алгоритмов сжатия для короткого текста:»ata la jaca a la estaca»
  11. Подсчитывают, сколько раз появляется каждый символ и составляют связанный список:» (5), a (9), c (2), e (1), j (1), l (2), s (1), t (2)
  12. Заказывают по частоте от низшей к высшей: e (1), j (1), s (1), c (2), l (2), t (2), » (5), a (9)

Как видно, корневой узел дерева создан, далее назначаются коды.

И осталось только упаковать биты в группы по восемь, то есть в байты:

Всего восемь байтов, а исходный текст был 23.

Демонстрация библиотеки LZ77

Алгоритм LZ77 рассмотрим на примере текста«howtogeek». Если повторить его три раза, то он изменит его следующим образом.

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

Это идеальный пример, когда большая часть текста сжимается с помощью нескольких символов. Например, слово «это» будет сжато, даже если оно встречается в таких словах, как «этом», «их» и «этого». С повторяющимися словами можно получить огромные коэффициенты сжатия. Например, текст со словом «howtogeek», повторенным 100 раз имеет размер три килобайта, при компрессии займет всего 158 байт, то есть с 95% «уменьшением».

Это, конечно, довольно экстремальный пример, но наглядно демонстрирует свойства алгоритмов сжатия. В общей практике он составляет 30-40% с текстовым форматом ZIP. Алгоритм LZ77, применяется ко всем двоичным данным, а не только к тексту, хотя последний легче сжать из-за повторяющихся слов.

Дискретное косинусное преобразование изображений

Сжатие видео и аудио работает совсем по-другому. В отличие от текста, где выполняют алгоритмы сжатия без потерь, и данные не будут потеряны, с изображениями выполняют «уменьшение» с потерями, и чем больше %, тем больше потерь. Это приводит к тем ужасно выглядящим JPEG-файлам, которые люди загружали, обменивали и делали скриншоты по несколько раз.

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

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

Видео работает немного иначе, чем изображения. Обычно алгоритмы сжатия графической информации используют тем, что называется «межкадровым сжатием», которое вычисляет изменения между каждым кадром и сохраняет их. Так, например, если есть относительно неподвижный снимок, который занимает несколько секунд в видео, он будет «уменьшен» в один. Межкадровое сжатие обеспечивает цифровое телевидение и веб-видео. Без него видео весило бы сотнями гигабайт, что больше среднего размера жесткого диска в 2005 году.

Сжатие аудио работает очень похоже на сжатие текста и изображений. Если JPEG удаляет детали из изображения, которое не видны человеческим глазом, сжатие звука делает, то же самое для звуков. MP3 использует битрейт, в диапазоне от нижнего уровня 48 и 96 кбит/с (нижний предел) до 128 и 240 кбит/с (довольно хороший) до 320 кбит/с (высококачественный звук), и услышать разницу можно только с исключительно хорошими наушниками. Существуют кодеки сжатия без потерь для звука, основным из которых является FLAC и использует кодирование LZ77 для передачи звука без потерь.

Форматы «уменьшения» текста

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

Прогоны значений кодируются, как символ, за которым следует длина прогона. Можно правильно восстановить оригинальный поток. Если длина серии 15 января, 2020

Моделирование при сжатии текстовых данных lz77

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

Принцип скользящего окна

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

Благодаря этому принципу алгоритмы LZ* иногда называются методами сжатия с использованием скользящего окна. Скользящее окно можно представить в виде буфера (или более сложной динамической структуры данных), который организован так, чтобы запоминать «сказанную» ранее информацию и предоставлять к ней доступ. Таким образом, сам процесс сжимающего кодирования согласно LZ77 напоминает написание программы, команды которой позволяют обращаться к элементам «скользящего окна», и вместо значений сжимаемой последовательности вставлять ссылки на эти значения в «скользящем окне». Размер скользящего окна может динамически изменяться и составлять 2, 4 или 32 килобайта. Следует также отметить, что размер окна кодировщика может быть менее или равен размеру окна декодировщика, но не наоборот.

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

Механизм кодирования совпадений

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

В стандартном алгоритме LZ77 совпадения кодируются парой:

  • длина совпадения (match length)
  • смещение (offset) или дистанция (distance)

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

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

Пример с командой копирования не совсем очевиден: «Вернуться на 1 символ назад в буфере и скопировать 7 символов, начиная с текущей позиции». Каким образом можно скопировать 7 символов из буфера, когда в настоящий момент в буфере находится только 1 символ? Однако следующая интерпретация кодирующей пары может прояснить ситуацию: каждые 7 последующих символов совпадают (эквивалентны) с 1 символом перед ними.

Это означает, что каждый символ можно однозначно определить, переместившись назад в буфере — даже если данный символ еще отсутствует в буфере на момент декодирования текущей пары длина-смещение. Такая кодируемая пара будет представлять собой многократное (определяемое значением смещения) повторение последовательности (определяемой значением длины) символов, что представляет собой более общую форму RLE.

Недостатки

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

Пример «abracadabra»

Выделенные символы отсутствуют в кодирующей последовательности.

Реализация LZ77 на Си

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

Ссылки

  • Jacob Ziv, Abraham Lempel. A Universal Algorithm for Sequential Data Compression IEEE Transactions on Information Theory, 23(3), pp.337-343, May 1977.
  • Пример работы алгоритма LZ77 (см. example «abracadabra»)
  • Описание алгоритма LZ77 в курсе лекций по теории кодирования информации
  • Описание алгоритма LZ78 в курсе лекций по теории кодирования информации
Это заготовка статьи о компьютерах. Вы можете помочь проекту, исправив и дополнив её.
Это примечание по возможности следует заменить более точным.
Методы сжатия
Теория
Информация Собственная · Взаимная · Энтропия · Условная энтропия · Сложность · Избыточность
Единицы измерения Бит · Нат · Ниббл · Хартли · Формула Хартли
Без потерь
Энтропийное сжатие Алгоритм Хаффмана · Адаптивный алгоритм Хаффмана · Алгоритм Шеннона — Фано · Арифметическое кодирование (Интервальное) · Коды Голомба · Дельта · Универсальный код (Элиаса · Фибоначчи)
Словарные методы RLE · Deflate · LZ ( LZ77/LZ78 · LZSS · LZW · LZWL · LZO · LZMA · LZX · LZRW · LZJB · LZT)
Прочее RLE · CTW · BWT · MTF · PPM · DMC
Аудио
Теория Свёртка · PCM · Алиасинг · Дискретизация · Теорема Котельникова
Методы LPC (LAR · LSP) · WLPC · CELP · ACELP · A-закон · μ-закон · MDCT · Преобразование Фурье · Психоакустическая модель
Прочее Компрессор аудиосигнала · Сжатие речи · Полосное кодирование
Изображения
Термины Цветовое пространство · Пиксель · Субдискретизация насыщенности · Артефакты сжатия
Методы RLE · DPCM · Фрактальный · Вейвлетный · EZW · SPIHT · LP · ДКП · ПКЛ
Прочее Битрейт · Test images · PSNR · Квантование
Видео
Термины Характеристики видео · Кадр · Типы кадров · Качество видео
Методы Компенсация движения · ДКП · Квантование · Вейвлетный
Прочее Видеокодек · Rate distortion theory (CBR · ABR · VBR)

Wikimedia Foundation . 2010 .

Смотреть что такое «LZ77» в других словарях:

LZ77 — ist ein Verfahren zur Datenkompression, das 1977 von Abraham Lempel und Jacob Ziv veröffentlicht wurde. Die Autoren machten sich erstmals zunutze, dass ganze Wörter, oder zumindest Teile davon, in einem Text mehrfach vorkommen. Im Gegensatz dazu… … Deutsch Wikipedia

LZ77 — et LZ78 LZ77 et LZ78 sont deux algorithmes de compression sans perte de données publiés par Abraham Lempel et Jacob Ziv en 1977 et 1978. Ces deux algorithmes forment la base de la plupart des algorithmes LZ comme LZW et LZSS. LZ77 présente… … Wikipédia en Français

LZ77/78 — … Википедия

LZ77 — ● np. m. ►PACK Première version de l algorithme de compression par substitution, publiée en 1977. Son principe est de garder en mémoire les données déjà rencontrées, et quand on rencontre une phrase déjà vue, on la supprime pour ne garder que la… … Dictionnaire d’informatique francophone

LZ77 and LZ78 — are the names for the two lossless data compression algorithms published in papers by Abraham Lempel and Jacob Ziv in 1977 and 1978. They are also known as LZ1 and LZ2 respectively [http://www.patentstorm.us/patents/5532693 description.html] .… … Wikipedia

LZ77 et LZ78 — sont deux algorithmes de compression de données sans perte proposés par Abraham Lempel et Jacob Ziv en 1977 et 1978 (d où leurs noms). Ces deux algorithmes posent les bases de la plupart des algorithmes de compression par dictionnaire, à tel… … Wikipédia en Français

LZ77 Et LZ78 — sont deux algorithmes de compression sans perte de données publiés par Abraham Lempel et Jacob Ziv en 1977 et 1978. Ces deux algorithmes forment la base de la plupart des algorithmes LZ comme LZW et LZSS. LZ77 présente certains défauts, en… … Wikipédia en Français

Lz77 et lz78 — sont deux algorithmes de compression sans perte de données publiés par Abraham Lempel et Jacob Ziv en 1977 et 1978. Ces deux algorithmes forment la base de la plupart des algorithmes LZ comme LZW et LZSS. LZ77 présente certains défauts, en… … Wikipédia en Français

LZ77 (Begriffsklärung) — LZ77 ist Bezeichnung für: ein Verfahren zur Datenkompression, siehe LZ77 zwei verschiedene Luftschiffe von Zeppelin während des Ersten Weltkrieges, siehe: Liste aller Zeppeline Baunummer LZ 47 trug die militärische Bezeichnung LZ 77 Baunummer LZ… … Deutsch Wikipedia

LZ 77 — LZ77 ist ein Verfahren zur Datenkompression, das 1977 von Abraham Lempel und Jacob Ziv veröffentlicht wurde. Die Autoren machten sich erstmals zu Nutze, dass ganze Wörter, oder zumindest Teile davon, in einem Text mehrfach vorkommen. Im Gegensatz … Deutsch Wikipedia

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

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

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

Скачать:

Вложение Размер
kursovaya_taranin_anton.docx 105.95 КБ

Предварительный просмотр:

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

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

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

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

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

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

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

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

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

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

«__» _______________ 2015г.

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • степень сжатия (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).

Количество различных строк

Использовано комбинаций, % от всех возможных

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

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

Количество строк длины 5, встретившихся ровно N раз

Количество относительно общего числа всех различных строк длины 5, %

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Обработанная часть сообщения (словарь)

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

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

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

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

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

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

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

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

В 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=log 2 (размер словаря), а длина двоичного кода для длины подстроки будет округленным в большую сторону m=log 2 (размер буфера). Каждый символ кодируется 8 битами (например, ASCII+). Т.е., для кодирования каждой подстроки исходного сообщения нужно n+m+8 бит.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Например, строка « aaabbabaabaaabab » делится на 7 фраз. Каждая из них кодируется как уже встречавшаяся ранее фраза плюс текущий символ. Например, последние три символа кодируются как фраза номер 4 ( «ba» ), за которой следует символ «b» . Фраза номер 0 — пустая строка(табл.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% вывода при создании 2 40 фраз. Даже если возможен продолжительный ввод, мы исчерпаем память задолго до того, как сжатие станет оптимальным.

Реальная задача – посмотреть как быстро 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 лучше всего раскрывается на примере текстовой информации, практика показывает, что они так же хорошо работают с любой, в принципе сжимаемой, информацией.

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

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

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

Практическая реализация алгоритма LZ77

Примечание: т.к. алгоритм был подробно рассмотрен в предыдущем разделе, все описание этого раздела находится внутри программы в виде комментариев.

Листинг 1. Реализация алгоритма LZ77 на языке С++

#define DICBITS 12 // Log(DICSIZE)

#define DICSIZE (1

FILE *first_file, *second_file;

long srcleng=0, fileleng;

unsigned char *srcbuf, *srcstart;

int putbits(int data, int nbits)

static int bitcounter=0;

static int outdata=0;

if( bitcounter == 8 )

printf(«Error writing to Second file.»);

printf(» Step — %d «,srcleng);

if((last == NO) && (srcleng = 0; i— )// Ищем самую длинную совпадающую строку в словаре

for( cnt=0; cnt maxleng ) // Если очередная строка длиннее уже найденных, сохраняеМ ее длину и позицию

if( (last == YES) && (maxleng > srcleng) ) // Проверяем, чтобы не было выхода за границы файла

maxleng=(int)srcleng; //обрезаем длину по границу буфера

if( maxleng > THRESHOLD )//Если строка достаточно длинная, формируем pointer-код

putbits(1,1); //помечаем как ссылку

putbits(dist,DICBITS); //записываем позицию

putbits(maxleng-THRESHOLD-1,STRBITS); //записываем длину

else // Иначе — chr-код

putbits(0,1); //помечаем как chr-код

putbits(*position,8); //записываем чар код

// Записываем оставшиеся биты

printf(» Compress completed! «,fileleng);

//Разархивирование Алгоритм LZ77

int getbits(int nbits)

static int bitcounter=8;

static int indata=0;

for( ; nbits > 0 ; nbits— )

if( bitcounter == 8 )

printf(«Error writing to First file.»);

if( (ch=getbits(1)) == 0 ) // Если chr-код, копируем в буфер текста символ

else // Иначе — копируем maxleng символов из словаря, начиная с позиции dist

for( i=0; i srcstart+TEXTSIZE ) // Если буфер заполнен, записываем его на диск и сдвигаем словарь в начало буфера

printf(» Decompress completed.»);

Сравнительная таблица результатов сжатия.

Размер после сжатия

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

Список используемых источников

1. Конспект лекций по дисциплине «Дискретный анализ»

3. Фомин А. А. «Основы сжатия информации»

4. Bell T., Witten I, Cleary J. «Modeling for Text Compression»

5. Ватолин Д., Ратушняк А., Смирнов М., Юкин В. «Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео»

[ Статья ] — Простейшие алгоритмы сжатия: RLE и LZ77

RLE — компактность единообразия

Алгоритм RLE является, наверное, самым простейшим из всех: суть его заключается в кодировании повторов. Другими словами, мы берём последовательности одинаковых элементов, и «схлопываем» их в пары «количество/значение». Например, строка вида «AAAAAAAABCCCC» может быть преобразована в запись вроде «8ЧA, B, 4ЧC». Это, в общем-то, всё, что надо знать об алгоритме.

LZ77 — краткость в повторении

LZ77 — один из наиболее простых и известных алгоритмов в семействе LZ. Назван так в честь своих создателей: Абрахама Лемпеля (Abraham Lempel) и Якоба Зива (Jacob Ziv). Цифры 77 в названии означают 1977 год, в котором была опубликована статья с описанием этого алгоритма.

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

Подстановочные или словарно-ориентированные алгоритмы сжатия информации. Методы Лемпела-Зива

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

  1. GУметь использовать на практике современные технологии и методы менеджмента.
  2. III. Гидрометаллургичесие методы
  3. IV Методы установленных цен в маркетинге
  4. LZ-алгоритмы распаковки данных. Пример 13.6
  5. LZ-алгоритмы распаковки данных. Примеры
  6. V. Ценовая политика на предприятии. Методы ценообразования.
  7. X Методы изучения рынка с помощью инструментария маркетинга
  8. Абстрактные типы данных. Методы представления множеств.
  9. Адаптивные алгоритмы сжатия. Кодирование Хаффмена
  10. Административные (организационно-распорядительные) методы управления.
  11. АДМИНИСТРАТИВНЫЕ И СОЦИАЛЬНО-ПСИХОЛОГИЧЕСКИЕ МЕТОДЫ УПРАВЛЕНИЯ
  12. Административные методы управления.

Лекция 12

Тема 8. Методы кодирования информации со сжатием.

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

Мы с вами, на самом деле, уже знакомы с кодами такого рода. Это коды Шеннона –Фано и Хаффмена которые называют оптимальным неравномерными кодами с переменной длиной слова. Если мы кодируем , например текстовое сообщение без учета вероятности появления символов, то на каждый знак мы можем тратить до 8 бит ( если знаки определяются таблицей ASCII). Знание статистики появления знаков позволяет сократить количество битов на знак алфавита в среднем до величины энтропии источника.

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

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

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

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

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

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

Первая группа с неявным видом словаря – основа алгоритм LZ77

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

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

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

Процедура кодирования в соответствии с алгоритмами этой группы иллюстрируется примером 12.1.

Вход А Б В Г Д А Б В Е

Выход А Б В Г Д 1 Е

произошло сжатие за счет повторяющегося куска текста А Б В.

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

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

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

Идею этой группы алгоритмов можно также пояснить с помощью примера 12.2.

Вход А Б В А Б В А Б Г Д Е

Словарь основной А-1, Б-2, В-3, Г-4, Д-5, Е-5, словарь фраз АБ-6, АБВ-7

Выход 12361645 плюс необходимо каким-то образом сохранять и основной словарь.

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

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

Основная идея LZ77 состоит в том, что второе и последующие вхождения некоторой строки символов в сообщении заменяются ссылками на ее первое вхождение.

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

LZ77 использует «скользящее» по сообщению окно, разделенное на две неравные части. Первая, большая по размеру, включает уже просмотренную часть сообщения. Это текущий словарь кодировщика, откуда он берет посторяющиеся куски. Вторая, намного меньшая, является буфером, содержащим еще незакодированные символы входного потока. Обычно размер окна словаря составляет несколько килобайт, а размер буфера — не более ста байт. Алгоритм пытается найти в скользящем по тексту словаре фрагмент, совпадающий с содержимым буфера или части буфера.

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

· смещение в словаре относительно его начала подстроки, совпадающей с началом содержимого буфера;

· длина этой подстроки;

· первый символ буфера, следующий за подстрокой.

Закодировать по алгоритму LZ77 строку «КРАСНАЯ КРАСКА».

В 9-й строке необходим сдвиг на5 позиций (длина совпадающей строки +1) и считывание стольких же символов в буфер.

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

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

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

| следующая лекция ==>
Пропускная способность канала связи с помехами для непрерывных сообщений | LZ77-алгоритм распаковки данных. Пример 12.4

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

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

Илон Маск рекомендует:  Определение ip адреса по домену
Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL