Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

в 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).

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

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

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

p(А₁)p(А₂)..р(А_I-1)P(А_I), I=1, 2, 3, …… K

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

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

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

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

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

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

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

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

Знаки упорядочиваются по возрастанию их частот и образуют частичные суммы S_i = p_j (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 шагЗ

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

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

Например,

З

}F

}G

наки pi Знаки pi

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

}H

Знаки pi Знаки pi

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)

Заключение.

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

Список литературы

Каган и Каневский “Цифровые вычислительные машины и системы”.

Газета “Компьютер - инфо”.

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

Характеристики

Список файлов реферата