Министерство науки и высшего образования Российской Федерации
Федеральное государственное бюджетное образовательное учреждение
высшего образования
ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)
Кафедра безопасности информационных систем(БИС)
Построение префиксного кода на примере текста
Отчет по самостоятельной работе
по дисциплине «Теория информации и кодирования»
Выполнил:
Студент гр. 739-1
_______Климанов М. Д.
4.06.2021
Научный руководитель:
Доктор физико-математических наук
_______ Немирович-Данченко М. М.
4.06.2021
Томск 2021
Содержание
Y
1. Введение 3
2. Ход работы 4
2.1 Работа с художественным текстом, частотный анализ, построение кода 4
2.2 Работа с научным текстом, частотный анализ, построение кода 7
3. Заключение 10
10
4. Ссылки на полные тексты 11
Введение
Цель работы: закрепить практические навыки по построению префиксного кода Ш-Ф на примере художественного и научного текстов.
Постановка задачи:
1. Выбрать два различных текста (отрывков из книг, статьей, энциклопедий) - один текст художественный (повесть, роман, поэма), второй текст - научный (может быть монография, учебник по любой технической (физико-математической) дисциплине.
2. Провести частотный анализ, рассчитать вероятности вхождения различных букв (для каждого текста)
3. Построить код Ш-Ф (или Хаффмена) (для каждого текста)
4. Выполнить анализ результатов работы (рассчитать количественные характеристики алфавитов и кодов)
4 а) Если есть возможность программировать, рассчитать блочные коды - для 2 и 3 букв. Комбинаций много. По желанию.
4 б) Сравнить эффективность блочного кодирования с обычным.
Краткие теоретические сведенья: Алгоритм Шеннона - Фано - один из первых алгоритмов сжатия, который впервые сформулировали американские учёные Клод Шеннон и Роберт Фано. Данный метод сжатия имеет большое сходство с алгоритмом Хаффмана, который появился на несколько лет позже и является логическим продолжением алгоритма Шеннона. Алгоритм использует коды переменной длины: часто встречающийся символ кодируется кодом меньшей длины, редко встречающийся - кодом большей длины. Коды Шеннона - Фано -префиксные, то есть никакое кодовое слово не является префиксом любого другого.
Ход работы
Работа с художественным текстом, частотный анализ, построение кода
Для работы с художественным текстом выбран в качестве примера отрывок из поэмы А.С. Пушкина «Руслан и Людмила». Ссылка на полный текст находится в списке источников. Данный текст содержит 11861 слово, 63257 символов без пробелов и 75144 символов с ними. Для расчетов будет учитываться первый вариант.
Для расчета вероятностей необходимо воспользоваться формулой для определения частоты (она является оценкой вероятности) и на этих значениях в дальнейшем будут построены все вычисления. Формула частоты появления символа в тексте приведена ниже.
W – частота появления символа;
n – количество повторения символа в данном тексте;
N – общее количество символов;
На рисунке 1 приведена гистограмма, которая показывает количество повторений для каждой буквы.
Рисунок 1 – Гистограмма для художественного текста
Из рисунка 1 видно, что наиболее часто встречаемая буква это «О», а реже всего встречается «Э».
Все символы были отсортированы и с учетом этого построена таблица 1.
Таблица 1 – Построение кода Шеннона – Фано
Буква |
Кол-во |
Частота |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
Код |
о |
5555 |
0,356478 |
0 |
0 |
0 |
0 |
|
|
|
|
0 0 0 0 |
е |
5045 |
0,32375 |
0 |
0 |
0 |
1 |
|
|
|
|
0 0 0 1 |
а |
4346 |
0,278894 |
0 |
0 |
1 |
|
|
|
|
|
0 0 1 |
н |
4332 |
0,277995 |
0 |
1 |
0 |
0 |
|
|
|
|
0 1 0 0 |
и |
3662 |
0,235 |
0 |
1 |
0 |
1 |
|
|
|
|
0 1 0 1 |
т |
3299 |
0,211705 |
0 |
1 |
1 |
0 |
|
|
|
|
0 1 1 0 |
с |
3203 |
0,205545 |
0 |
1 |
1 |
1 |
|
|
|
|
0 1 1 1 |
л |
3056 |
0,196111 |
1 |
0 |
0 |
0 |
0 |
|
|
|
1 0 0 0 0 |
р |
2966 |
0,190336 |
1 |
0 |
0 |
0 |
1 |
|
|
|
1 0 0 0 1 |
в |
2781 |
0,178464 |
1 |
0 |
0 |
1 |
|
|
|
|
1 0 0 1 |
д |
2238 |
0,143618 |
1 |
0 |
1 |
0 |
0 |
|
|
|
1 0 1 0 0 |
м |
2140 |
0,137329 |
1 |
0 |
1 |
0 |
1 |
|
|
|
1 0 1 0 1 |
у |
1968 |
0,126291 |
1 |
0 |
1 |
1 |
|
|
|
|
1 0 1 1 |
к |
1636 |
0,104986 |
1 |
1 |
0 |
0 |
0 |
0 |
|
|
1 1 0 0 0 0 |
ы |
1592 |
0,102163 |
1 |
1 |
0 |
0 |
0 |
1 |
|
|
1 1 0 0 0 1 |
п |
1487 |
0,095425 |
1 |
1 |
0 |
0 |
1 |
|
|
|
1 1 0 0 1 |
й |
1439 |
0,092344 |
1 |
1 |
0 |
1 |
0 |
0 |
|
|
1 1 0 1 0 0 |
я |
1250 |
0,080216 |
1 |
1 |
0 |
1 |
0 |
1 |
|
|
1 1 0 1 0 1 |
з |
1128 |
0,072387 |
1 |
1 |
0 |
1 |
1 |
|
|
|
1 1 0 1 1 |
ь |
1093 |
0,070141 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
|
1 1 1 0 0 0 0 |
г |
1086 |
0,069691 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
|
1 1 1 0 0 0 1 |
б |
1058 |
0,067895 |
1 |
1 |
1 |
0 |
0 |
1 |
|
|
1 1 1 0 0 1 |
ч |
748 |
0,048001 |
1 |
1 |
1 |
0 |
1 |
0 |
|
|
1 1 1 0 1 0 |
ж |
682 |
0,043766 |
1 |
1 |
1 |
0 |
1 |
1 |
|
|
1 1 1 0 1 1 |
х |
634 |
0,040685 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
|
1 1 1 1 0 0 0 |
ш |
500 |
0,032086 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
|
1 1 1 1 0 0 1 |
ю |
481 |
0,030867 |
1 |
1 |
1 |
1 |
0 |
1 |
|
|
1 1 1 1 0 1 |
ц |
207 |
0,013284 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
|
1 1 1 1 1 0 0 |
щ |
141 |
0,009048 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
|
1 1 1 1 1 0 1 |
ф |
62 |
0,003979 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
1 1 1 1 1 1 0 0 |
ъ |
38 |
0,002439 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 1 1 1 1 1 0 1 |
ё |
36 |
0,00231 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
1 1 1 1 1 1 1 0 |
э |
12 |
0,00077 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 1 1 1 1 1 1 1 |
Количество символов в тексте было посчитано с помощью функций ПО Microsoft Word 2010.
С помощью формул для средней длины и вектора Крафта (он нужен для проверки на правильность построения кода). Посчитаны избыточность и соответственно средняя длина. Формулы представлены ниже.
;
где li – длина i кода;
k – общее количество кодов;
pi – вероятность i кода;
;
v(S) – вектор Крафта;
Для того, чтобы найти энтропию необходимо воспользоваться формулой, которая приведена ниже:
;
Где H – энтропия;
n – Количество элементов;
p – вероятность i элемента;
Для вычисления избыточности кода можно воспользоваться следующей формулой:
;
Формула для вычисления эффективности:
;
Средняя длина получилась: 17,81556825;
Энтропия: 9,863392729;
Избыточность кода: 0,446361037;
Эффективность кода: 0,553638963;
Вектор Крафта получился равный единице: v(S) = 2^-3+7*2^-4+8*2^-5+10*2^-6+2*2^-7+3*2^-8+2*2^-9 = 1;
Это означает, что код построен верно.
Аналогичные вычисления нужно произвести с научным текстом.