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

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

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

  Содержание

  Введение

  Общие сведения

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

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

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

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

       Алгоритм LZ77

       Алгоритм LZ78-LZW84

       Алгоритм PPM

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

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

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

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

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

       Реализация  модели

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

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

       Отрицательное переполнение

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

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

  Эффективность сжатия

  Заключение

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

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

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

  Введение 

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

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

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

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

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

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

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

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

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

  Общие сведения 

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

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

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

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

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

  H(x) = log2 N.

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

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

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

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

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

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

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

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

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

  Алгоритм LZ77 

  Этот словарный  алгоритм сжатия является самым старым среди методов 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) длины  соответствия, или совпадения (match length), j;

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

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

  Алгоритм LZ78-LZW84 

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

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

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

  2. В выходной  файл помещается номер найденного  слова в словаре position и следующий символ из входного текста В (на котором обнаружилось различие) - <position,B>. Длина кода равна |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. В выходной  файл помещается номер найденного  слова в словаре <positior>. Длина кода равна |position|=[logV] (бит);

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

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

  Алгоритм PPM 

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

  Вероятность символа может быть оценена в  контекстах разных порядков. Например, символ "о" в контексте "to be or not t" может быть оценен в контексте первого порядка «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 является префиксом для соответствующего символа из F.

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

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

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

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

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

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

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

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

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

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

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

  15 7 6 6 5

  А Б В Г Д

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

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

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

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

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

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

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

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

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

  А       0

  Б       100

  В       101

  Г       110

  Д       111

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

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