Простейшие алгоритмы сжатия информации методы лемпела зива кратко

Обновлено: 05.07.2024

В статье рассматриваются основные методы сжатия данных, приводится классификация наиболее известных алгоритмов, и на простых примерах обсуждаются механизмы работы методов CS&Q, RLE-кодирования, Хаффмана, LZW, дельта-кодирования, JPEG и MPEG. Статья представляет собой авторизованный перевод [1].

Передача данных и их хранение стоят определенных денег. Чем с большим количеством информации приходится иметь дело, тем дороже обходится ее хранение и передача. Зачастую данные хранятся в наиболее простом виде, например в коде ASCII (American Standard Code for Information Interchange — американский стандартный код для обмена информацией) текстового редактора, в исполняемом на компьютере двоичном коде, в отдельных файлах, полученных от систем сбора данных и т.д. Как правило, при использовании этих простых методов кодирования объем файлов данных примерно в два раза превышает действительно необходимый размер для представления информации. Ее сжатие с помощью алгоритмов и программ позволяет решить эту задачу. Программа сжатия используется для преобразования данных из простого формата в оптимизированный по компактности. Наоборот, программа распаковки возвращает данные в исходный вид. Мы обсудим шесть методов сжатия данных в этом разделе. Первые три из них являются простыми методами кодирования: кодирование длин серий с передачей информации об их начале и длительности; кодирование Хаффмана и дельта-кодирование. Последние три метода являются сложными процедурами сжатия данных, которые стали промышленными стандартами: LZW, форматы JPEG и MPEG.

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

Без потерь

С потерями

Передаваемые по интернету изображения служат наглядным примером того, почему необходимо сжатие данных. Предположим, что требуется загрузить из интернета цифровую цветную фотографию с помощью 33,6-Кбит/с модема. Если изображение не сжато (например, это файл TIFF-формата), его объем составит около 600 Кбайт. При сжатии фото без потерь (в файл GIF-формата) его размер уменьшится примерно до 300 Кбайт. Метод сжатия с потерями (JPEG-формат) позволит уменьшить размер файла до 50 Кбайт. Время загрузки этих трех файлов составляет 142, 72 и 12 с, соответственно. Это большая разница. JPEG идеально подходит для работы с цифровыми фотографиями, тогда как GIF используется только для рисованных изображений.

Второй способ классификации методов сжатия данных проиллюстрирован в таблице 2. Большинство программ сжатия работает с группами данных, которые берутся из исходного файла, сжимаются и записываются в выходной файл. Например, одним из таких методов является CS&Q (Coarser Sampling and Quantization — неточные выборка и дискретизация). Предположим, что сжимается цифровой сигнал, например звуковой сигнал, который оцифрован с разрядностью 12 бит. Можно прочесть две смежные выборки из исходного файла (24 бит), отбросить одну выборку полностью, отбросить наименее значащие 4 бита из другой выборки, затем записать оставшиеся 8 битов в выходной файл. При 24 входных битах и 8 выходных коэффициент сжатия алгоритма с потерями равен 3:1. Этот метод высокоэффективен при использовании сжатия с преобразованием, составляющего основу алгоритма JPEG.

Метод

Размер группы

входной

выходной

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

Файлы данных содержат одни и те же символы, повторяющиеся множество раз в одном ряду. Например, в текстовых файлах используются пробелы для разделения предложений, отступы, таблицы и т.д. Цифровые сигналы также содержат одинаковые величины, указывающие на то, что сигнал не претерпевает изменений. Например, изображение ночного неба может содержать длинные серии символов, представляющих темный фон, а цифровая музыка может иметь длинную серию нулей между песнями. RLE-кодирование (Run-length encoding — кодирование по длинам серий) представляет собой метод сжатия таких типов файлов.
На рисунке 1 проиллюстрирован принцип этого кодирования для последовательности данных с частым повторением серии нулей. Всякий раз, когда нуль встречается во входных данных, в выходной файл записываются два значения: нуль, указывающий на начало кодирования, и число нулей в серии. Если среднее значение длины серии больше двух, происходит сжатие. С другой стороны, множество одиночных нулей в данных может привести к тому, что кодированный файл окажется больше исходного.

Этот метод был разработан Хаффманом в 1950-х гг. Метод основан на использовании относительной частоты встречаемости индивидуальных элементов. Часто встречающиеся элементы кодируются более короткой последовательностью битов. На рисунке 2 представлена гистограмма байтовых величин большого файла ASCII. Более 96% этого файла состоит из 31 символа: букв в нижнем регистре, пробела, запятой, точки и символа возврата каретки.

Алгоритм, назначающий каждому из этих стандартных символов пятибитный двоичный код по схеме 00000 = a, 00001 = b, 00010 = c и т.д., позволяет 96% этого файла уменьшить на 5/8 объема. Последняя комбинация 11111 будет указывать на то, что передаваемый символ не входит в группу из 31 стандартного символа. Следующие восемь битов в этом файле указывают, что представляет собой символ в соотоветствии со стандартом присвоения ASCII. Итак, 4% символов во входном файле требуют для представления 5 + 8 = 13 бит.

Принцип этого алгоритма заключается в присвоении часто употребляемым символам меньшего числа битов, а редко встречающимся символам — большего количества битов. В данном примере среднее число битов, требуемых из расчета на исходный символ, равно 0,96 . 5 + 0,04 . 13 = 5,32. Другими словами, суммарный коэффициент сжатия составляет 8 бит/5,32 бит, или 1,5 : 1.

На рисунке 3 представлена упрощенная схема кодирования Хаффмана. В таблице кодирования указана вероятность употребления символов с A по G, имеющихся в исходной последовательности данных, и их соответствия. Коды переменной длины сортируются в стандартные восьмибитовые группы. При распаковке данных все группы выстраиваются в последовательность нулей и единиц, что позволяет разделять поток данных без помощи маркеров. Обрабатывая поток данных, программа распаковки формирует достоверный код, а затем переходит к следующему символу. Такой способ формирования кода обеспечивает однозначное чтение данных.

Буква

Вероятность

Код Хаффмана

Дельта-кодирование используется для сжатия данных, если значения исходного файла изменяются плавно, т.е. разность между следующими друг за другом величинами невелика. Это условие не выполняется для текста ASCII и исполняемого кода, но является общим случаем, когда информация поступает в виде сигнала. Например, на рисунке 5а показан фрагмент аудиосигнала, оцифрованного с разрядностью 8 бит, причем все выборки принимают значения в диапазоне –127–127. На рисунке 5б представлен кодированный вариант этого сигнала, основное отличие которого от исходного сигнала заключается в меньшей амплитуде. Другими словами, дельта-кодирование увеличивает вероятность того, что каждое значение выборки находится вблизи нуля, а вероятность того, что оно значительно больше этой величины, невелика. С неравномерным распределением вероятности работает метод Хаффмана. Если исходный сигнал не меняется или меняется линейно, в результате дельта-кодирования появятся серии выборок с одинаковыми значениями, с которыми работает RLE-алгоритм. Таким образом, в стандартном методе сжатия файлов используется дельта-кодирование с последующим применением метода Хаффмана или RLE-кодирования.

Механизм дельта-кодирования можно расширить до более полного метода под названием кодирование с линейным предсказанием (Linear Predictive Coding, LPC).
Чтобы понять суть этого метода, представим, что уже были закодированы первые 99 выборок из входного сигнала и необходимо произвести выборку под номером 100. Мы задаемся вопросом о том, каково наиболее вероятное ее значение? В дельта-кодировании ответом на данный вопрос является предположение, что это значение предыдущей, 99-й выборки. Это ожидаемое значение используется как опорная величина при кодировании выборки 100. Таким образом, разность между значением выборки и ожиданием помещается в кодируемый файл. Метод LPC устанавливает наиболее вероятную величину на основе нескольких последних выборок. В используемых при этом алгоритмах применяется z-преобразование и другие математические методы.

LZW-сжатие — наиболее универсальный метод сжатия данных, получивший распространение благодаря своей простоте и гибкости. Этот алгоритм назван по имени его создателей (Lempel-Ziv-Welch encoding — сжатие данных методом Лемпела-Зива-Велча). Исходный метод сжатия Lempel-Ziv был впервые заявлен в 1977 г., а усовершенствованный Велчем вариант — в 1984 г. Метод позволяет сжимать текст, исполняемый код и схожие файлы данных примерно вполовину. LZW также хорошо работает с избыточными данными, например табличными числами, компьютерным исходным текстом и принятыми сигналами. В этих случаях типичными значениями коэффициента сжатия являются 5:1. LZW-сжатие всегда используется для обработки файлов изображения в формате GIF и предлагается в качестве опции для форматов TIFF и PostScript.
Алгоритм LZW использует кодовую таблицу, пример которой представлен на рисунке 6. Как правило, в таблице указываются 4096 элементов. При этом кодированные LZW-данные полностью состоят из 12-битных кодов, каждый из которых соответствует одному табличному элементу. Распаковка выполняется путем извлечения каждого кода из сжатого файла и его преобразования с помощью таблицы. Табличные коды 0—255 всегда назначаются единичным байтам входного файла (стандартному набору символов). Например, если используются только эти первые 256 кодов, каждый байт исходного файла преобразуется в 12 бит сжатого LZW-файла, который на 50% больше исходного. При распаковке этот 12-битный код преобразуется с помощью кодовой таблицы в единичные байты.

Пример кодовой таблицы

Метод LZW сжимает данные с помощью кодов 256—4095, представляя последовательности байтов. Например, код 523 может представлять последовательность из трех байтов: 231 124 234. Всякий раз, когда алгоритм сжатия обнаруживает последовательность во входном файле, в кодируемый файл ставится код 523. При распаковке код 523 преобразуется с помощью таблицы в исходную последовательность из трех байтов. Чем длиннее последовательность, назначаемая единичному коду и чем чаще она повторяется, тем больше коэффициент сжатия.
Существуют два основных препятствия при использовании этого метода сжатия: 1) как определить, какие последовательности должны указываться в кодовой таблице и 2) как обеспечить программу распаковки той же таблицей, которую использует программа сжатия. Алгоритм LZW позволяет решить эти задачи.

Когда программа LZW начинает кодировать файл, таблица содержит лишь первые 256 элементов — остальная ее часть пуста. Это значит, что первые коды, поступающие в сжимаемый файл, представляют собой единичные байты исходного файла, преобразуемые в 12-бит группы. По мере продолжения кодирования LZW-алгоритм определяет повторяющиеся последовательности данных и добавляет их в кодовую таблицу. Сжатие начинается, когда последовательность обнаруживается вторично. Суть метода в том, что последовательность из входящего файла не добавляется в кодовую таблицу, если она уже была помещена в сжатый файл как отдельный символ (коды 0—255). Это важное условие, поскольку оно позволяет программе распаковки восстановить кодовую таблицу непосредственно из сжатых данных, не нуждаясь в ее отдельной передаче.

Из множества алгоритмов сжатия с потерями кодирование с преобразованием оказалось наиболее востребованным. Наилучший пример такого метода — популярный стандарт JPEG (Joint Photographers Experts Group — Объединенная группа экспертов по машинной обработке фотографических изображений). Рассмотрим на примере JPEG работу алгоритма сжатия с потерями.

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

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

Из рисунка 7 видно, что JPEG-сжатие начинается путем разбиения изображения на группы размером 8×8 пикселов. Полный алгоритм JPEG работате с широким рядом битов на пиксел, включая информацию о цвете. В этом примере каждый пиксел является единичным байтом, градацией серого в диапазоне 0—255. Эти группы 8×8 пикселов обрабатываются при сжатии независимо друг от друга. Это значит, что каждая группа сначала представляется 64 байтами. Вслед за преобразованием и удалением данных каждая группа представляется, например, 2—20 байтами. При распаковке сжатого файла требуется такое же количество байтов для аппроксимации исходной группы 8×8. Эти аппроксимированные группы затем объединяются, воссоздавая несжатое изображение. Почему используются группы размерами 8×8, а не 16×16? Такое группирование было основано исходя из максимального возможного размера, с которым работали микросхемы на момент разработки стандарта.

Рис. 7. Пример применения метода сжатия JPEG. Три группы 8?8, показанные в увеличенном виде, представляют значения отдельных пикселов

Для реализации методов сжатия было исследовано множество различных преобразований. Например, преобразование Karhunen-Loeve обеспечивает наиболее высокий коэффициент сжатия, но оно трудно осуществляется. Метод преобразования Фурье реализуется гораздо проще, но он не обеспечивает достаточно хорошего сжатия. В конце концов, выбор был сделан в пользу разновидности метода Фурье — дискретного косинусного преобразования (Discrete Cosine Transform — DCT).

На примере работы алгоритма JPEG видно, как несколько схем сжатия объединяются, обеспечивая большую эффективность. Вся процедура сжатия JPEG состоит из следующих этапов:
– изображение разбивается на группы 8×8;
– каждая группа преобразуется с помощью преобразования DCT;
– каждый спектральный элемент 8×8 сжимается путем сокращения числа битов и удаления некоторых компонентов с помощью таблицы квантования;
– видоизмененный спектр преобразуется из массива 8×8 в линейную последовательность, все высокочастотные компоненты которой помещаются в ее конец;
– серии нулей сжимаются с помощью метода RLE;
– последовательность кодируется либо методом Хаффмана, либо арифметическим методом для получения сжатого файла.

MPEG (Moving Pictures Experts Group — Экспертная группа по кинематографии) — стандарт сжатия цифровых видеоданных. Этот алгоритм обеспечивает также сжатие звуковой дорожки к видеофильму. MPEG представляет собой еще более сложный, чем JPEG, стандарт с огромным потенциалом. Можно сказать, это ключевая технология XXI века.
У MPEG имеется несколько очень важных особенностей. Так например, он позволяет воспроизводить видеофильм в прямом и обратном направлениях, в режиме нормальной и повышенной скорости. К кодированной информации имеется прямой доступ, т.е. каждый отдельный кадр последовательности отображается как неподвижное изображение. Таким образом, фильм редактируется — можно кодировать его короткие фрагменты, не используя всю последовательность в качестве опорной. MPEG также устойчив к ошибкам, что позволяет избегать цифровых ошибок, приводящих к нежелательному прерыванию воспроизведения.

Используемый в этом стандарте метод можно классифицировать по двум типам сжатия: внутрикадровое и межкадровое. При сжатии по первому типу отдельные кадры, составляющие видеопоследовательность, кодируются так, как если бы они были неподвижными изображениями. Такое сжатие выполняется с помощью JPEG-стандарта с несколькими вариациями. В терминологии MPEG кадр, закодированный таким образом, называется внутрикодированным, или I-picture.

Наибольшая часть пикселов в видеопоследовательности изменяется незначительно от кадра к кадру. Если камера не движется, наибольшая часть изображения состоит из фона, который не меняется на протяжении некоторого количества кадров. MPEG использует это обстоятельство, сжимая избыточную информацию между кадрами с помощью дельта-кодирования. После сжатия одного из кадров в виде I-picture последующие кадры кодируются как изображения с предсказанием, или P-pictures, т.е. кодируются только изменившиеся пикселы, т.к. кадры I-picture включены в P-picture.

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

Аннотация: История происхождения, положительные и отрицательные стороны, сравнение и применение на практике таких алгоритмов, как: LZ77, LZ78, LZSS, LZW. Практические задания для укрепления основного материала лекции. Особенности программ архиваторов. Непосредственное применение алгоритмов кодирования в архиваторах для обеспечения продуктивной работы в MS-DOS и WINDOWS

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

Алгоритм LZ77 был опубликован в 1977 г. Разработан израильскими математиками Якобом Зивом (Ziv) и Авраамом Лемпелом (Lempel). Многие программы сжатия информации используют ту или иную модификацию LZ77. Одной из причин популярности алгоритмов LZ является их исключительная простота при высокой эффективности сжатия.

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

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

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

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

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

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

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

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

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

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

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

Пример. Закодировать по алгоритму LZSS строку "КРАСНАЯ КРАСКА" .

Здесь длина полученного кода равна бит .

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

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

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

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

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

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

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

2.3 Алгоритм LZ77

2.4 Алгоритм LZ78

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 Алгоритм LZ77

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

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

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

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

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

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

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

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

2.4 Алгоритм LZ78

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

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

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

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

Несжатые данные могут занимать много места, что не подходит для ограниченного пространства на жестком диске и скорости загрузки через Интернет.
Хотя аппаратное обеспечение становится все лучше и дешевле, алгоритмы уменьшения размера данных также способствуют развитию технологий.
Пример: одна минута несжатого HD-видео может превышать 1 ГБ. Как мы можем поместить двухчасовой фильм на диск Blu-ray объемом 25 ГБ?

Методы сжатия с потерями включают DCT (дискретное косинусное преобразование), векторное квантование и кодирование с преобразованием, в то время как методы сжатия без потерь включают RLE (кодирование длин серий), сжатие таблицы строк, LZW (Lempel Ziff Welch) и zlib. Существует несколько алгоритмов сжатия, но мы концентрируемся на LZW.

Что такое алгоритм Лемпеля – Зива – Уэлча (LZW)?

Как это работает?

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

Сжатие LZW использует таблицу кодов, с 4096 в качестве общего выбора для числа записей таблицы. Коды 0-255 в таблице кодов всегда назначаются для представления отдельных байтов из входного файла.
Когда кодирование начинается, таблица кодов содержит только первые 256 записей, а оставшаяся часть таблицы является пробелами. Сжатие достигается путем использования кодов с 256 по 4095 для представления последовательностей байтов.
Когда кодирование продолжается, LZW идентифицирует повторяющиеся последовательности в данных и добавляет их в таблицу кодов.
Декодирование достигается путем извлечения каждого кода из сжатого файла и его перевода через таблицу кодов, чтобы найти, какой символ или символы он представляет.

Пример: код ASCII. Как правило, каждый символ хранится с 8 двоичными битами, что позволяет использовать до 256 уникальных символов для данных. Этот алгоритм пытается расширить библиотеку до 9-12 бит на символ. Новые уникальные символы состоят из комбинаций символов, которые ранее встречались в строке. Он не всегда хорошо сжимается, особенно с короткими, разнообразными струнами. Но это хорошо для сжатия избыточных данных и не требует сохранения нового словаря с данными: этот метод может как сжимать, так и распаковывать данные.
Уже написана отличная статья, вы можете посмотреть более подробно здесь, а также статья Марка Нельсона заслуживает высокой оценки.

Реализация

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

LZW ENCODING

Тестирование кода ниже:

Выход :

Также проверьте код , преобразованный Марк Нельсон в C ++ style.There еще одна вариация из 6 различных версий здесь . Кроме того, Rosettacode перечисляет несколько реализаций LZW на разных языках.

Сжатие с использованием LZW

Пример 1. Использование алгоритма LZW для сжатия строки: BABAABAAA
Эти шаги систематически показаны на диаграмме ниже.

LZW декомпрессия

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

Алгоритм декомпрессии LZW

Пример 2. Декомпрессия LZW: используйте LZW для декомпрессии выходной последовательности:
Эти шаги систематически показаны на диаграмме ниже.

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

Код C ++ для сжатия LZW как для кодирования, так и для декодирования представлен следующим образом:

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