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

Алгоритм Хаффмена

Статистические алгоритмы сжатия

Теоретическую основу данных алгоритмов заложил американский ученый Клод Элвуд Шеннон своей теоремой о кодировании для дискретного канала без помех. Статистические алгоритмы сжимают данные с использованием того факта, что частоты встречаемости (в теоретических исследованиях используется понятие вероятности появления) различных символов в сжимаемых данных не одинаковы, следовательно можно сокращать объем данных присвоением часто встречающимся символам коротких кодов, а редко встречающимся – длинных. Важная особенность статистических алгоритмов сжатия состоит в том, что они не учитывают никаких взаимосвязей между символами и кодируют каждый символ вне зависимости от других. Можно как угодно менять порядок символов в сообщении – степень сжатия от этого никак не изменится.

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

Широко применяются в практике сжатия данных алгоритм Хаффмена и алгоритм арифметического кодирования.

На зачете про него не рассказывать, т.к. на него есть задача!

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

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

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