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

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

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

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

Алгоритмы kwe

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

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

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

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

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

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

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