ПРИЛОЖЕНИЕ 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)

B 0,15 (1) D 0,24 (1)

C 0,20 F 0,26

D 0,24 E 0,30

E 0,30

F 0,26 (0) G 0,44 (0)

E 0,30 (1) H 0,56 (1)

G 0,44

Тогда коды исходных символов (они «собираются» из частных кодов дополнительных обозначений – F, G, H- в обратном относительно хода кодировки порядке):

Исходные Коды Пояснения

символы

A 100 (А вошел в F с кодом 0; F вошел в H с кодом 0; у H код 1. Тогда обратный порядок - 100)

B 101 (B вошел в F с кодом 1; F вошел в H с кодом 0; у H код 1. Тогда обратный порядок – 101)

С 00 (С вошел в G с кодом 0; у G код 0)

D 01 (D вошел в G с кодом 1; у G код 0. Тогда обратный порядок – 01)

E 11 (E вошел в H с кодом 1, у H код 1)

ПРИЛОЖЕНИЕ 2. Правила оформления индивидуальных заданий

Оформление индивидуальных заданий должно быть выполнено аккуратно от руки или отпечатано на принтере, на листах формата А4, включать блок-схемы алгоритмов и рисунки, описывающие структуры информационных массивов, используемых при решении задачи (например, индексов, словарей, кодовых таблиц), а также, возможно, различные иллюстрации к происходящим процессам, выполненные в текстовом процессоре WinWord, тексты (возможно, распечатки) программ.

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

Для заданий, связанных с автокоррекцией текстов, включить распечатки словарей, если они используются.

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

Структура отчета:

1. Титульный лист (оформление см. далее).

2. Задание (из соответствующей таблицы заданий).

3. Основной текст, отвечающий на следующие вопросы:

· функциональное назначение программы,

· для какого компьютера, операционной системы она предназначена. Требуемые ресурсы компьютера,

· какие данные являются входными, как они вводятся и есть ли ограничения на их значения; как организован контроль вводимых данных в программу,

· какие данные являются выходными, в каком формате они представлены и на каком носителе,

· какие информационные структуры используются при решении задачи (включить их описание в виде рисунков с пояснениями),

· состав программ программного обеспечения: какие программные модули входят и какие функции каждый из них выполняет (комментарии к модулям представить в виде блок-схем),

· взаимосвязь модулей и данных. Отразить ее в таблице следующей структуры:

· организация диалога с программой: какие вопросы и в каком формате задает программа и как на них отвечает пользователь. Оценить диалог в соответствии с критериями хорошего диалога.

[1] Добавление незначащего нуля обусловлено требованием четности числа цифр