J tech 120. indd

Разработка алгоритма кодирования 
на основе неравенства Крафта
Входными данными для программы являются тек-
стовые данные, введенные с клавиатуры, либо тек-
стовый файл формата SLN, загруженный с компьютера.
1. Необходимо посчитать и запомнить частоту (вероят-
ности появления) каждого символа в сообщении по 
формуле
(2)
где q
i
— количество вхождений i-го символа в сооб-
щение, а n — количество символов в сообщении.
2. По посчитанным вероятностям считаем теоретиче-
ские длины кодовых слов по формуле
2
log
log
i
i
p
l
−
=
(3),
округляя их до целых чисел.
3. Проверяем длины кодовых слов 
N
i
l
l
l
,...,
,...,
1
на 
соответствие неравенству Крафта:
(4)
4. Если длины кодовых слов удовлетворяют неравенству 
Крафта, то переходим к следующему шагу. Иначе, 
необходимо вывести сообщение о том, что не суще-
ствует префиксного кода с заданными длинами ко-
довых слов.
5. Начиная с первого символа в сообщении i = 1 прове-
ряем его на соответствие условию: i ≤ N? Пока данное 
условие выполняется, переходим к следующему шагу. 
Если не выполняется, то это значит, что мы прошли 
по всем символам алфавита, и новых символов в ал-
фавите нет, после чего выходим из алгоритма и вы-
водим закодированное сообщение.
6. Условимся, что все правые ветви всегда — единицы, 
левые ветви — нули (дерево хранится в памяти в виде 
матрицы или двумерной таблицы точек c двумя коор-
динатами, где i — уровень дерева, k — порядковый 
номер точки на уровне.) Отмечаем концевую точку l
i 
на соответствующем уровне бинарного дерева, запо-
миная при этом координаты точки (l
i
— уровень де-
рева, k — порядковый номер точки на уровне), вы-
бирая при этом любой свободный узел на уровне.
7. Проверяем, не является ли уровень дерева l — ну-
левым (корнем дерева): l ≥ 1? Если данное условие 
не выполняется, то это означает, что мы находимся 
на нулевом уровне (в корне дерева). Возвращаемся к 
шагу 5. Если данное условие истинно, то переходим к 
следующему пункту алгоритма.
8. Проходим от концевой точки (листа) к корню дерева, 
запоминая путь (все узлы от листа до корня) по сле-
дующему алгоритму:
9. Находим остаток от деления порядкового номера кон-
цевой точки на 2 используя следующую операцию 
k mod 2. Если в остатке 1, то записываем в начало 
кодового слова 0, если в остатке 0, то записываем 1. 
После каждого действия возвращаемся к шагу 6.
Блок-схема алгоритма кодирования представлена на 
рисунке 1.