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

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

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

Коэффициент сжатия текстовых данных этим методом лежит в пределах 1,8 - 2,5.

1.5.2. Статистические алгоритмы.

1.5.2.1. Кодирование фрагментов фиксированной длины

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

пробел 0,174 ы 0,016

о 0,080 з 0,016

е, ё 0,071 ъ 0,014

а 0,061 ь 0,014

и 0,061 б 0,014

т 0,052 г 0,013

м 0,052 ч 0,012

с 0,045 й 0,010

р 0,040 у 0,009

в 0,038 ж 0,007

л 0,035 ю 0,006

к 0,028 ш 0,006

н 0,026 ц 0,003

д 0,025 щ 0,003

п 0,023 э 0,003

у 0,021 ф 0,002

я 0,018 х 0,002

Сами коды рассчитываются на основании частот отдельных символов (в случае таблицы символов) или их комбинаций (в этом случае общая частота рассчитывается как произведение частот отдельных символов, входящих в комбинацию) с помощью методов Шеннона-Фано или Хаффмена (описание методов см. в приложении 1).

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

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

Дальнейшим развитием метода Хаффмена являются арифмети­ческие коды. Они происходят из так называемых конкатенационных, или блочных, кодов. Суть их заключается в том, что выход­ной код генерируется для цепочки входных символов фиксирован­ной длины без учета межсимвольных корреляций. В основе метода лежит представление вероятности каждой цепочки К входных символов (А1, А2, . АК ) в виде числа, получаемого как сумма К слагаемых вида

p(А1)p(А2) р(АI-1)P(АI), I=1, 2, 3, …… K

где р (S) - вероятность символа S,

Р(S)- куммулятивная вероятность символа S, равная сумме вероятностей всех символов AI, для которых р(АI) больше р(S).

1.5.2.2. Кодирование фрагментов переменной длины

Другой формой словаря может являться словарь фрагментов переменной длины. Словари фрагментов переменной длины строятся из словоформ, которые выделяются в тексте по естественным разделителям – пробелам и знакам пунктуации. Затем рассчитываются частоты каждой словоформы как отношение числа ее повторений к общему количеству словоформ. Используя эти частоты, применяют метод Хаффмена или Шеннона-Фано для кодирования словоформ кодом переменной длины.

Выводы по части 3.

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

ПРИЛОЖЕНИЕ 1. Методы сжатия данных

Метод Шеннона-Фано

Знаки упорядочиваются по возрастанию их частот и образуют частичные суммы Si = Spj (j = 1, 2, 3, … i), где рj - частота j-того знака. Далее процесс разбивается на несколько шагов. В первом шаге столбец знаков рассекается на две части так, чтобы частичная сумма сечения была близка к 0,5. Процесс деления подстолбцов повторяется так, чтобы каждый раз частичная сумма в точке сечения оказывалась ближе к среднему арифметическому частичных сумм на нижнем и верхнем краях разделяемого подстолбца. При каждом разбиении элементам верхней части ставится в соответс­твие 1, нижней - 0. Например: пусть

знаки рi

A 0,11

B 0,15

C 0,20

D 0,24

E 0,30

Тогда процедура разбиения складывается из шагов:

Знаки pi коды

A 0,11 1 1 111

B 0,15 1 0 110

C 0,20 0 10

D 0,24 0 1 01

E 0,30 0 00

шаг1 шаг2 шагЗ

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

Знаки упорядочиваются по возрастанию частоты. Два самых редких знака объединяются в один класс, и их частоты складываются. Полученные частоты переупорядочиваются и процесс повторяется до тех пор, пока все знаки ни будут объединены в один класс.

Например,

A 0,11 (0) C 0,20 (0)