Коэффициент сжатия текстовых данных этим методом лежит в пределах 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. Кодирование фрагментов переменной длины

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

2. Задания

1. Создать файл с информацией, соответствующей объекту сжатия.

2. Разработать алгоритмы и программы сжатия и разжатия информации по вариантам из таблицы. Исходные данные после выполнения обеих процедур должны соответствовать результату.

3. Определить результативность алгоритмов сжатия, соотнеся объем сжатого и исходного текста.

Варианты заданий

Таблица 3