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


Содержание

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

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

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

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

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

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

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—) ;

Алгоритмы сжатия данных (стр. 1 из 6)

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

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

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

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

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

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бит (в полном соответствии с теоремой Шеннона об оптимальном кодировании).

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

Это интересно!

Увеличение ресурсов сети

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

Управление ориентацией поля в электроприводах

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

Основы теории демодулирующих логарифмических усилителей

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

1 сентября

Форматы сжатия данных

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

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

Методы сжатия данных

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

Табл. 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.

Табл. 2. Классификация методов сжатия: фиксированный и переменный размер группы

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

RLE-кодирование

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

Рис. 1. Пример RLE-кодирования


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

Кодирование Хаффмана

Этот метод был разработан Хаф­фманом в 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.

Рис. 2. Гистограмма значений ASCII фрагмента текста из этой статьи


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

Рис. 3. Пример кодирования Хаффмана

Дельта-кодирование

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

Рис. 4. Пример дельта-кодирования

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

Рис. 5. Пример дельта-кодирования


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

Алгоритм LZW

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-битный код преобразуется с помощью кодовой таблицы в единичные байты.

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

Рис. 6. Пример сжатия в соответствии с таблицей кодирования

Метод 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, тогда как практическая реализация данного метода намного сложнее описанной. Например, кадры P-picture могут использовать изображение I-picture как опорное, которое претерпело изменение при перемещении объектов в последовательности изображений. Существуют также двунаправленные предиктивно-кодированные изображения, или B-pictures. Эти видеокадры формируются способом предсказания «вперед» и «назад» на основе I-picture. При этом обрабатываются участки изображения, которые постепенно меняются на протяжении множества кадров. Отдельные кадры также хранятся без соблюдения последовательности в сжатых данных, чтобы облегчить упорядочение изображений I-, P- и B-pictures. Наличие цвета и звука еще больше усложняет реализацию этого алгоритма.

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

АЛГОРИТМЫ СЖАТИЯ

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

  1. Неискажающие (loseless) методы сжатия гарантируют, что декодированные данные будут в точности совпадать с исходными;
  2. Искажающие (lossy) методы сжатия (называемые также методами сжатия с потерями) могут искажать исходные данные, например за счет удаления несущественной части данных, после чего полное восстановление невозможно.

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

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

Кроме того, можно выделить:

  • методы сжатия общего назначения (general-purpose), которые не зависят от физической природы входных данных и, как правило, ориентированы на сжатие текстов, исполняемых программ, объектных модулей и библиотек и т. д., т. е. данных, которые в основном и хранятся в ЭВМ;
  • специальные (special) методы сжатия, которые ориентированны на сжатие данных известной природы, например, звука, изображений и т. д. И за счет знания специфических особенностей сжимаемых данных достигают существенно лучшего качества и/или скорости сжатия, чем при использовании методов общего назначения.

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

Критерии оценки методов сжатия

Основными свойствами какого-либо алгоритма сжатия данных являются:

  • качество сжатия, т. е. отношение длины (в битах) сжатого представления данных к длине исходного представления;
  • скорость кодирования и декодирования;
  • объем требуемой памяти.

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

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

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

Надежность программ и сложность алгоритмов

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

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

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

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

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

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

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

Наилучшие по качеству сжатия алгоритмы статистического моделирования источников Маркова семейств PPM (от англ. Prediction by Partial Matching), DMC (от англ. Dynamic Markov Compression), ACB (от англ. Associative Coding by Buyanovski) предсказывают вероятность появления следующего символа на основе анализа частоты появления различных последовательностей символов в ранее закодированной части сообщения.

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

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

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

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

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

Обычно для ускорения поиска совпадающих подстрок и ограничения объема требуемой памяти область поиска ограничивается определенным количеством последних символов закодированной части: такая модификация LZ77 называется LZ77 со скользящим окном (LZ77 with sliding window).

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

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

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

Алгоритмы сжатия сортировкой блоков

Алгоритмы сжатия сортировкой блоков семейства BWT/BS, разработанные в 1994г. Барроузом и Уилером, разбивают кодируемую последовательность на блоки символов, представляют (обратимым образом) символы каждого блока так, что появляется много повторений одного и того же символа, а затем сжимают преобразованные данные каким-либо достаточно простым способом.

По качеству сжатия они приближаются к методам статистического моделирования (уступая им в 1.2-1.3 раза), а по скорости – к алгоритмам семейства LZ77, при меньшем по сравнению с методами статистического моделирования объеме требуемой памяти; скорость декодирования также достаточно высока.

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

Методы энтропийного кодирования

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

Такие методы кодирования известны с конца 40-х гг. и хорошо изучены. Их можно разбить на два больших класса: префиксные (методы Хаффмана, Шеннона, Шеннона-Фано) и арифметические.

Префиксные коды

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

Известно много способов построения префиксных кодов: коды Шеннона и Шеннона-Фано почти идеальны, а код Хаффмана – оптимален среди префиксных кодов.

Так как длина каждого кодового слова выражается целым числом битов, то префиксные коды неэффективны на алфавитах малой мощности (2-8 символов) или при наличии символов с очень большой (более 30-50%) вероятностью появления и по качеству сжатия могут уступать арифметическим.

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

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

Арифметические коды

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

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

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

Арифметические коды обычно применяются в сочетании с методами статистического моделирования для кодирования символов в соответствии с предсказанными вероятностями.

Сжатие данных в примерах

Теория и стратегия представления данных

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

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


Что понимается под сжатием данных? Если говорить кратко, то сжатие устраняет из данных избыточность; в терминах же теории информации сжатие увеличивает энтропию сжатого текста. Однако оба этих утверждения по существу по существу верны в силу определения самих понятий. Избыточность может быть выражена в самых разных формах. Одним типом является последовательности повторяющихся битов ( 11111111 ). Вторым – последовательности повторяющихся байтов ( XXXXXXXX ). Однако чаще избыточность проявляется в более крупном масштабе и выражается либо закономерностями в наборе данных, взятом как единое целое, либо последовательностями различной длины, имеющими общие признаки. По существу, цель сжатия данных заключается в поиске алгоритмических преобразований представлений данных, которые позволят получить более компактные представления «типовых» наборов данных. Это описание может показаться несколько туманным, но мы постараемся раскрыть его суть на практических примерах.

Сжатие без потерь и с потерями

Фактически существуют два в корне различающихся подхода к сжатию данных: сжатие с потерями и без потерь. Эта статья, в основном, посвящена методам сжатия без потерь, но для начала полезно изучить различия. Сжатие без потерь предусматривает преобразование представления набора данных таким образом, чтобы затем можно было в точности воспроизвести первоначальный набор данных путем обратного преобразования (распаковки). Сжатие с потерями – это представление, которое позволяет воспроизводить нечто «очень похожее» на первоначальный набор данных. Преимущество использования методов сжатия с потерями заключается в том, что они зачастую позволяют получать намного более компактные представления данных по сравнению с методами сжатия без потерь. Чаще всего методы сжатия с потерями применяются для обработки изображений, звуковых файлов и видео. Сжатие с потерями в этих областях может оказаться уместным благодаря тому, что человек воспринимает битовую комбинацию цифрового изображения/звука не с «побитовой» точностью, а скорее оценивает музыку или изображение в целом.

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

Пример набора данных

В данной статье будет использоваться специально подготовленное гипотетическое представление данных. Приведем простой для понимания пример. В городе Гринфилд (штат Массачусетс, США) используются префиксы телефонных номеров 772- , 773- и 774- . (К сведению читателей за пределами США: в США местные телефонные номера являются семизначными и традиционно представляются в виде ###-####; префиксы назначаются в соответствии с географическим местоположением). Также предположим, что из всех трех префиксов чаще всего используется первый. Частями суффикса могут быть любые другие цифры с приблизительно равной вероятностью. Набор интересующих нас данных находится в «списке всех телефонных номеров, которые в настоящее время находятся в активном пользовании». Можно попробовать подобрать причину, почему это могло бы быть интересным с точки зрения программирования, но в данном случае это не важно.

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

Таблица 1. Многоколоночный отчет

Сжатие пустых мест

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

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

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

Групповое кодирование

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

Если в обрабатываемом формате данных преобладают повторяющиеся байты, то может быть уместным и эффективным использование алгоритма, в котором один или несколько байтов указывают количество повторений, а затем следует повторяемый символ. Однако если имеются строки символов единичной длины, для их кодирования потребуются два (или более) байта. Другими словами, для одного символа ASCII «X» входного потока мог бы потребоваться выходной битовый поток 00000001 01011000 . С другой стороны, для кодирования ста следующих друг за другом символов «X» использовалось бы то же самое количество битов: 01100100 01011000 , что весьма эффективно.

В различных вариантах RLE часто применяется избирательное использование байтов для указания числа повторений, в то время как остальные байты просто представляют сами себя. Для этого должно быть зарезервировано как минимум одно однобайтовое значение, которое в случае необходимости может удаляться из выходных данных. Например, в нашем образце отчета по телефонным номерам известно, что вся информация во входном потоке состоит из простых символов ASCII. В частности, у всех таких символов первый бит ASCII-значения равен 0. Мы могли бы использовать этот первый бит ASCII для указания на то, что байт указывает число повторений, а не обычный символ. Следующие семь битов байта итератора могли бы использоваться для указания числа повторений, а в следующем байте мог бы содержаться повторяющийся символ. Так, например, мы могли бы представить строку «YXXXXXXXX» следующим образом:

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

Кодирование по методу Хаффмана

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

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

Таблица 2. Результаты кодирования по методу Хаффмана

Исходный набор символов (состоящий из чисел) может быть легко закодирован (без сжатия) в виде 4-х битных последовательностей (полубайтов). Приведенное кодирование по методу Хаффмана будет использовать до 5 битов для символов в наихудшем случае, что очевидно хуже кодирования с помощью полубайтов. Однако в лучшем случае потребуется всего 1 бит; при этом известно, что именно лучший случай будет использоваться чаще всего (так как именно этот символ чаще всего встречается в данных). Таким образом, мы могли бы закодировать конкретный телефонный номер следующим образом:

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

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

Сжатие по алгоритму Лемпеля-Зива

Вероятно, самым значимым методом сжатия без потерь является алгоритм Лемпеля-Зива. В этой статье речь пойдет о варианте LZ78, но LZ77 и другие варианты работают схожим образом. Идея, заложенная в алгоритме LZ78, заключается в кодировании потоковой последовательности байтов с использованием некоторой динамической таблицы. В начале сжатия битового потока таблица LZ заполняется фактическим набором символов, наряду с несколькими пустыми слотами. В алгоритме применяются таблицы разных размеров, но в данном примере с телефонными номерами (со сжатием пустых мест) используется таблица из 32 элементов (этого достаточно для данного примера, но может оказаться мало для других типов данных). Вначале мы заполняем первые десять слотов символами используемого алфавита (цифрами). По мере поступления новых байтов сначала выводится значение из таблицы, соответствующее самой длинной подходящей последовательности, а затем в следующий доступный слот записывается последовательность длиной N+1. В наихудшем случае мы используем 5 битов вместо 4 для отдельного символа, однако в большинстве случаев мы сможем обойтись 5 битами на несколько символов. Рассмотрим пример работы этого алгоритма (слот таблицы указан в квадратных скобках):

До сих пор мы не извлекли из этого никакой пользы, но давайте перейдем к следующему телефонному номеру:

Приведенных операций должно быть достаточно для демонстрации работы модели. Хотя никакого заметного сжатия пока не достигнуто, уже видно, что мы повторно использовали слоты 11 и 16, закодировав по два символа одним выходным символом. Кроме того, мы уже накопили крайне полезную последовательность байтов 772 в слоте 18, которая впоследствии неоднократно будет встречаться в потоке.

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

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

Правильная постановка задачи

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

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

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

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

Посвящается памяти Клода Шеннона (Claude Shannon).

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

Цель лекции: изучить основные виды и алгоритмы сжатия данных и научиться решать задачи сжатия данных по методу Хаффмана и с помощью кодовых деревьев.

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

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

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

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

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

Алфавит кода – множество всех символов входного потока. При сжатии англоязычных текстов обычно используют множество из 128 ASCII кодов. При сжатии изображений множество значений пиксела может содержать 2, 16, 256 или другое количество элементов.

Кодовый символ – наименьшая единица данных, подлежащая сжатию. Обычно символ – это 1 байт , но он может быть битом, тритом <0,1,2>, или чем-либо еще.

Кодовое слово – это последовательность кодовых символов из алфавита кода. Если все слова имеют одинаковую длину (число символов), то такой код называется равномерным (фиксированной длины), а если же допускаются слова разной длины, то – неравномерным (переменной длины).

Код – полное множество слов.

Токен – единица данных, записываемая в сжатый поток некоторым алгоритмом сжатия. Токен состоит из нескольких полей фиксированной или переменной длины.

Фраза – фрагмент данных, помещаемый в словарь для дальнейшего использования в сжатии.

Кодирование – процесс сжатия данных.

Декодирование – обратный кодированию процесс, при котором осуществляется восстановление данных.

Отношение сжатия – одна из наиболее часто используемых величин для обозначения эффективности метода сжатия.

Коэффициент сжатия – величина, обратная отношению сжатия.

Средняя длина кодового слова – это величина, которая вычисляется как взвешенная вероятностями сумма длин всех кодовых слов.

где – вероятности кодовых слов;

Существуют два основных способа проведения сжатия.

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

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

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

Метод Хаффмана

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

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

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

Оптимальный префиксный код – это префиксный код , имеющий минимальную среднюю длину.

Алгоритм Хаффмана можно разделить на два этапа.

  1. Определение вероятности появления символов в исходном тексте.

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

Далее находятся два символа a и b с наименьшими вероятностями появления и заменяются одним фиктивным символом x , который имеет вероятность появления, равную сумме вероятностей появления символов a и b . Затем, используя эту процедуру рекурсивно, находится оптимальный префиксный код для меньшего множества символов (где символы a и b заменены одним символом x ). Код для исходного множества символов получается из кодов замещающих символов путем добавления 0 или 1 перед кодом замещающего символа, и эти два новых кода принимаются как коды заменяемых символов. Например, код символа a будет соответствовать коду x с добавленным нулем перед этим кодом, а для символа b перед кодом символа x будет добавлена единица.

Коды Хаффмана имеют уникальный префикс , что и позволяет однозначно их декодировать, несмотря на их переменную длину.

Пример 1. Программная реализация метода Хаффмана.

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

Сжатие информации: как это делается

Мы каждый день пользуемся различными архиваторами: zip, rar, ace окружают нас повсюду.
Графические и звуковые файлы тоже содержат сжатые данные. Если же нам нужно использовать
сжатие в своей проге, то мы используем различные dll’ки, многие из которых платные.
Шареварность — это не единственное свойство программных компонентов, мешающих их нормальному
использованию. Если, например, сжимать waw или bmp-файл архиватором, то
он будет значительно уступать специальному методу для конкретного типа данных, т.е.
метод должен учитывать особенности конкретного типа данных. Поэтому полезно уметь реализовывать сжатие самостоятельно.
В этой статье я расскажу, как вообще сжимать информацию и рассмотрю один из методов сжатия.

Классификация методов сжатия

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

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

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

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

Отметим один момент, который почему-то неочевиден для некоторых «теоретиков».
Правило кодирования определяется вероятностной структурой данных, а значит, декомпрессор
должен до начала раскодирования уже знать её. Если же мы получаем её из статистики конкретного
сообщения (так оно сжимается лучше), то её придется передать явно или неявно вместе со сжатым
сообщением, и еще неизвестно, будет ли общий размер меньше.

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

H = -Sum(p[i] * log(p[i]))

где Sum — сумма по i, p[i] — вероятность i-го сообщения, log — логарифм по основанию 2.
Энтропия сложного сообщения равна сумме энтропий входящих в него простых сообщений.

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

Этот метод в корне отличается от всех рассмотренных ранее методов. Его главное
преимущество в том, что достигается теоретический предел сжатия. Рассмотрим этот метод подробно. Всё сообщение целиком представляется одним числом по следующему правилу. Число должно
находиться в интервале от 0 до 1. Этот интервал делится на части, пропорциональные вероятностям
значений первого символа. Выбирается часть, соответствующая символу и делится на части по
вероятностям значений второго символа и т.д.

новая_нижняя_граница = нижняя_граница + ширина * S[i]
новая_ширина = ширина * p[i]

где p[i] — вероятность i-го символа, S[i] — сумма вероятностей символов с номерами
меньше i.

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

Проект, прикрепленный к этой статье, компилируется на Visual Studio .NET.
Это реализация арифметического кодирования, сжимающая файлы, рассматривая байты как символы.
Содержимое файла рассматривается как марковский процесс 1-го порядка, т. е. распределение
вероятностей символов зависит от предыдущего символа. Класс CMarkovProcessDef обрабатывает
данные, сохраненные в ресурсе в специальном формате. Эти данные сгенерированы по результатам
обработки большого количества текстов, т. е. текстовые файлы, скорее всего, будут сжиматься
хорошо, а если попытаться сжать какой-нибудь бинарник, то размер «сжатого» файла будет больше
исходного. Для того, чтобы получить метод сжатия для своего типа данных, нужно заменить данные о
вероятностях символов. Кроме того, символ — это не обязательно байт несжатых данных. Например,
если есть столбец таблицы, где значения должны быть уникальными, то каждое значение — это
символ, а после того, как символ встречается, сбрасываем его вероятность в ноль. Нижняя граница и ширина интервала хранятся в целочисленных переменных dwBuf1 и dwBuf2.
Если после обработки очередного символа старшие байты границ окажутся равными
(заметим, что это не то же самое, что если старший байт ширины равен нулю), то
соответствующий байт окончательного результата будет равен этому значению, и его можно
записать в файл. Запишем его и сдвинем буферы на 1 байт. При распаковке кроме переменных, обрабатываемых так же, как при упаковке, нам
понадобится еще одна, где будет информация из файла. Для того, чтобы определить очередной символ, нужно
найти символ с наименьшим номером, такой, что S[n] * dwBuf2 >= dwBuf3, т.е. P[n] >= dwBuf3 / dwBuf2. При работе с целыми числами возникает проблема: мы представляем вероятности (дробные
числа от 0 до 1) целочисленными переменными (0x100000000 * p). Для умножения и деления на них нужны
особые процедуры: при умножении берем старшее 32-битное слово 64-битного результата, а при делении
делим число, умноженное на 2^32. Компилятор не может, умножитв DWORD на DWORD, поместить результат
в 64-битную переменную — это недостаток языка С++. Поэтому пришлось написать специальные процедуры
на ассемблере.

void CArithmCompressorDlg::OnBnClickedCompress()
<
CFileDialog dlg1(TRUE);
if (dlg1.DoModal() != IDOK) return;
CFileDialog dlg2(FALSE, «compressed», 0, OFN_HIDEREADONLY | OFN_OVERWRITEPROMPT, «*.compressed|*.compressed|All files|*.*||»);
if (dlg2.DoModal() != IDOK) return;

CFile file1(dlg1.GetPathName(), CFile::modeRead);
CFile file2(dlg2.GetPathName(), CFile::modeCreate | CFile::modeWrite);

BYTE b;
ULONGLONG fs = file1.GetLength();

file2.Write(&fs, 8); // Запишем размер исходного файла

// m_mpd — это объект класса CMarkovProcessDef
m_mpd.ResetProcess(); // Сбросим данные о предшествующих символах

// Здесь начинается сжатие
// Начальный интервал — от 0x00000000 до 0xFFFFFFFF
DWORD dwBuf1 = 0; // Нижняя граница
DWORD dwBuf2 = 0xFFFFFFFF; // Ширина
DWORD dww; // Временная переменная

Замените эту функцию на свою реализацию и получите метод сжатия для вашего типа данных.
*/
dwBuf1 += dww;
if (b Если старший байт буфера определен
<
file2.Write(((LPBYTE)&dwBuf1)+3, 1); // Записываем его
dwBuf1 = dwBuf1 И сдвигаем буфер
dwBuf2 = dwBuf2 PushSymbol(b, 0) перемещает внутренний указатель на распределение для следующего символа
*/
m_mpd.PushSymbol(b, 0);
>
file2.Write(((LPBYTE)&dwBuf1)+3, 1); // Записываем последний байт
// Вот и всё
// Закрываем файлы
file1.Close();
file2.Close();
>

void CArithmCompressorDlg::OnBnClickedDecompress()
<
CFileDialog dlg1(TRUE, «compressed», 0, 0, «*.compressed|*.compressed|All files|*.*||»);
if (dlg1.DoModal() != IDOK) return;
CFileDialog dlg2(FALSE);
if (dlg2.DoModal() != IDOK) return;

CFile file1(dlg1.GetPathName(), CFile::modeRead);
CFile file2(dlg2.GetPathName(), CFile::modeCreate | CFile::modeWrite);

if (file1.Read(&fs, 8) != 8) return; // Читаем длину извлекаемого файла

DWORD dwBuf1 = 0, dwBuf2 = 0xFFFFFFFF, dwBuf3, dww;

// Читаем первые 4 байта
// Нужно поместить байты в переменную не в том порядке, в каком они в файле,
// поэтому читаем их по отдельности
for (int j = 3; j >= 0; j—) if (file1.Read(((LPBYTE)&dwBuf3)+j, 1) == 0) ((LPBYTE)&dwBuf3)[j] = 0xFF;

// Поиск методом половинного деления
do
<
m = (l+h)/2;
if (h Вычисляем новый интервал
if (m > 0) dww = MulHigh(m_mpd.GetDistribution(m-1), dwBuf2); else dww = 0;
dwBuf1 += dww;
dwBuf3 -= dww;
if (m Пишем символ
m_mpd.PushSymbol(m, 0);

DWORD CArithmCompressorDlg::MulHigh(DWORD dw1, DWORD dw2)
<
/*
Эта функция возвращает старшее двойное слово
произведения данных двойных слов
*/
DWORD r;
_asm
<
mov eax, dw1;
mul dw2;
mov r, edx;
>
return r;
>

DWORD CArithmCompressorDlg::DivLarge(DWORD hi, DWORD lo, DWORD dw)
<
/*
Эта функция делит 64-битное беззнаковое целое (hi;lo)
на 32-битное
*/
DWORD r;
_asm
<
mov eax, lo;
mov edx, hi;
div dw;
mov r, eax;
>
return r;
>

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

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

Running — Это самый простой из методов упаковки информации . Предположите что Вы имеете строку текста, и в конце строки стоит 40 пробелов. налицо явная избыточность имеющейся информации. Проблема сжатия этой строки решается очень просто — эти 40 пробелов ( 40 байт ) сжимаются в 3 байта с помощью упаковки их по методу повторяющихся символов (running). Первый байт, стоящий вместо 40 пробелов в сжатой строке, фактически будет явлться пробелом ( последовательность была из пробелов ) . Второй байт — специальный байт «флажка» который указывает что мы должны развернуть предыдущий в строке байт в последовательность при восстановлении строки . Третий байт — байт счета ( в нашем случае это будет 40 ). Как Вы сами можете видеть, достаточно чтобы любой раз, когда мы имеем последовательность из более 3-х одинаковых символов, заменять их выше описанной последовательностью, чтобы на выходе получить блок информации меньший по размеру, но допускающий восстановление информации в исходном виде.

Оставляя все сказанное выше истинным , добавлю лишь то, что в данном методе основной проблемой является выбор того самого байта «флажка», так как в реальных блоках информации как правило используются все 256 вариантов байта и нет возможности иметь 257 вариант — «флажок». На первый взгляд эта проблема кажется неразрешимой , но к ней есть ключик, который Вы найдете прочитав о кодировании с помощью алгоритма Хаффмана ( Huffman ).

LZW — История этого алгоритма начинается с опубликования в мае 1977 г. Дж. Зивом ( J. Ziv ) и А. Лемпелем ( A. Lempel ) статьи в журнале » Информационные теории » под названием » IEEE Trans «. В последствии этот алгоритм был доработан Терри А. Велчем ( Terry A. Welch ) и в окончательном варианте отражен в статье » IEEE Compute » в июне 1984 . В этой статье описывались подробности алгоритма и некоторые общие проблемы с которыми можно столкнуться при его реализации. Позже этот алгоритм получил название — LZW ( Lempel — Ziv — Welch ).

Алгоритм LZW представляет собой алгоритм кодирования последовательностей неодинаковых символов. Возьмем для примера строку » Объект TSortedCollection порожден от TCollection.». Анализируя эту строку мы можем видеть, что слово «Collection» повторяется дважды. В этом слове 10 символов — 80 бит. И если мы сможем заменить это слово в выходном файле, во втором его включении, на ссылку на первое включение, то получим сжатие информации. Если рассматривать входной блок информации размером не более 64К и ограничится длинной кодируемой строки в 256 символов, то учитывая байт «флаг» получим, что строка из 80 бит заменяется 8+16+8 = 32 бита. Алгоритм LZW как-бы «обучается» в процессе сжатия файла. Если существуют повторяющиеся строки в файле , то они будут закодированны в таблицу. Очевидным преимуществом алгоритма является то, что нет необходимости включать таблицу кодировки в сжатый файл. Другой важной особенностью является то, что сжатие по алгоритму LZW является однопроходной операцией в противоположность алгоритму Хаффмана (Huffman), которому требуется два прохода.

Huffman — Сначала кажется что создание файла меньших размеров из исходного без кодировки последовательностей или исключения повтора байтов будет невозможной задачей. Но давайте мы заставим себя сделать несколько умственных усилий и понять алгоритм Хаффмана ( Huffman ). Потеряв не так много времени мы приобретем знания и дополнительное место на дисках.

Сжимая файл по алгоритму Хаффмана первое что мы должны сделать — это необходимо прочитать файл полностью и подсчитать сколько раз встречается каждый символ из расширенного набора ASCII. Если мы будем учитывать все 256 символов, то для нас не будет разницы в сжатии текстового и EXE файла. После подсчета частоты вхождения каждого символа, необходимо просмотреть таблицу кодов ASCII и сформировать мнимую компоновку между кодами по убыванию. То есть не меняя местонахождение каждого символа из таблицы в памяти отсортировать таблицу ссылок на них по убыванию. Каждую ссылку из последней таблицы назовем «узлом». В дальнейшем ( в дереве ) мы будем позже размещать указатели которые будут указывает на этот «узел». Для ясности давайте рассмотрим пример:

Мы имеем файл длинной в 100 байт и имеющий 6 различных символов в себе . Мы подсчитали вхождение каждого из символов в файл и получили следующее :

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

Мы возьмем из последней таблицы символы с наименьшей частотой. В нашем случае это D (5) и какой либо символ из F или A (10), можно взять любой из них например A.

Сформируем из «узлов» D и A новый «узел», частота вхождения для которого будет равна сумме частот D и A :

Номер в рамке — сумма частот символов D и A. Теперь мы снова ищем два символа с самыми низкими частотами вхождения. Исключая из просмотра D и A и рассматривая вместо них новый «узел» с суммарной частотой вхождения. Самая низкая частота теперь у F и нового «узла». Снова сделаем операцию слияния узлов :

Рассматриваем таблицу снова для следующих двух символов ( B и E ). Мы продолжаем в этот режим пока все «дерево» не сформировано, т.е. пока все не сведется к одному узлу.

Теперь когда наше дерево создано, мы можем кодировать файл . Мы должны всенда начнинать из корня ( Root ) . Кодируя первый символ (лист дерева С) Мы прослеживаем вверх по дереву все повороты ветвей и если мы делаем левый поворот, то запоминаем 0-й бит, и аналогично 1-й бит для правого поворота. Так для C, мы будем идти влево к 55 ( и запомним 0 ), затем снова влево (0) к самому символу . Код Хаффмана для нашего символа C — 00. Для следующего символа ( А ) у нас получается — лево,право,лево,лево , что выливается в последовательность 0100. Выполнив выше сказанное для всех символов получим

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

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

Таблица в нашем примере имеет 5 узлов плюс 6 вершин ( где и находятся наши символы ) , всего 11 . 4 байта 11 раз — 44 . Если мы добавим после небольшое количество байтов для сохранения места узла и некоторую другую статистику — наша таблица будет приблизительно 50 байтов длинны.
Добавив к 30 байтам сжатой информации, 50 байтов таблицы получаем, что общая длинна архивного файла вырастет до 80 байт . Учитывая , что первоначальная длинна файла в рассматриваемом примере была 100 байт — мы получили 20% сжатие информации.

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

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

Итак мы имеем итог из 256 различных комбинаций которыми можно кодировать байт . Из этих комбинаций лишь 2 по длинне равны 8 битам. Если мы сложим число битов которые это представляет, то в итоге получим 1554 бит или 195 байтов. Так в максимуме , мы сжали 256 байт к 195 или 33%, таким образом максимально идеализированный Huffman может достигать сжатия в 33% когда используется на уровне байта.

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

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

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

Сжатие текстовой информации

  • повторить и обобщить понятие о кодировании текстовой информации.

1. Организационный момент, проверка домашнего задания

2. Ознакомление учащихся с понятие «сжатие информации» на примерах (см. слайды №2 и №3).

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

3. Метод Шеннона-Фано (по презентации Приложение 2, см. слайды №№ 4-9)

Как мы уже видели при решении задач, информацию нельзя сжимать до бесконечности. То есть в какой-то момент должна появиться своего рода граница, при сжатии дальше которой восстановление информации неоднозначно или просто невозможно. То есть хотелось бы, чтобы выбранный нами способ кодирования был оптимальным: с одной стороны, чтобы обеспечивалось максимально возможное сжатие, с другой стороны, чтобы записанная таким образом информация не теряла свою полноту. Одним из методов, обеспечивающих такое оптимальное кодирование отдельных символов является метод Шеннона-Фано.
Суть метода состоит в следующем: пусть дан некоторый алфавит (конечный набор символов, который будет использован для написания текста). Пусть также дано сообщение. Какие-то символы в сообщении обычно встречаются чаще, какие-то – реже. Для часто используемых символов создадим более короткие коды, для реже используемых – длинные (слайд №4 – частота использования букв русского языка).
Для начала, в качестве повторения, оценим (например, по формуле Хартли) сколько бит необходимо отвести для записи кода одного символа, и создадим «обычные» коды равной длины (слайд №5).

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

Далее, разделим таблицу на две части, чтобы сумма долей всех символов в одной была как можно ближе к сумме долей всех символов другой. Пусть коды всех символов из первой части начинаются на 0, коды всех символов из второй – на 1 (слайд №7). Если в какой-то части находится более одного символа, то повторим для нее процесс деления, находя вторую, третью и так далее цифры кода. Как только для всех символов найдены коды – процесс завершен (слайды №8 и №9)
Осталось только подчитать количество бит, которые необходимы для представления сообщения в новом коде (слайд №10).


4. Закрепление пройденного материала, решение задач (слайд №11)

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

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

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

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

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

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

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—) ;

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