Индивидуальные задания по информатике
Рефераты >> Программирование и компьютеры >> Индивидуальные задания по информатике

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

№ варианта

Объект сжатия

Метод сжатия

1

2

3

1

Числовые данные

Разностное кодирование (разность двух смежных чисел)

2

То же

Разностное кодирование (отклонение числа из массива от среднего значения массива чисел)

3

То же

Кодирование повторений (повторяется один символ)

4

То же

Кодирование повторений (повторяется один или два символа)

5

То же

Подавление незначащих нулей

6

Словарь

Разностное кодирование

7

То же

С помощью словаря суффиксов (задается априори)

8

То же

С помощью словаря префиксов (задается априори)

9

То же

С помощью словаря префиксов, который создается динамически, в зависимости от обрабатываемого текста; длина префикса – не более 4 символов

10

То же

С помощью словаря суффиксов (задается априори, делится на подсловари)

11

То же

С помощью словаря префиксов (задается априори, делится на подсловари)

12

Специальный текст – Паскаль-программа

Кодовый словарь

Продолжение таблицы 3

1

2

3

13

Структурированные данные

Индексация структурных единиц

14

Естественно-языковый текст

Адаптивный с указателями назад

15

То же

Адаптивный с указателями вперед

16

То же

Метод Шеннона-Фано, глобальный словарь символов

17

То же

Метод Хаффмена, локальный словарь символов

18

То же

Метод Хаффмена, глобальный словарь биграмм

19

То же

Метод Шеннона-Фано, локальный словарь биграмм

20

То же

Метод Хаффмена, глобальный словарь триграмм

21

То же

Метод Шеннона-Фано, локальный словарь триграмм

22

То же

Метод Хаффмена, локальный словарь триграмм

23

То же

Арифметические коды, К=5

24

То же

Метод Шеннона-Фано для словоформ

25

То же

Метод Хаффмена для словоформ


Страница: