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

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

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

  Содержание

  Введение

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

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

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

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

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

       Алгоритм 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) кодируется с помощью двух чисел: