Файл: 2.1.2.1 - Схема двоичного кодирования текстов по Р. Фано.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 14.02.2021
Просмотров: 118
Скачиваний: 1
Схема
двоичного
кодирования
текстов
по
Р
.
Фано
Предложенная
американским
специалистом
Р
.
Фано
схема
двоичного
кодирования
сводится
к
выполнению
следующих
операций
.
1)
Составить
список
букв
алфавита
(
исходное
множество
букв
)
в
порядке
убывания
значений
соответствующих
им
вероятностей
.
2)
Разбить
этот
список
на
два
подсписка
(
подмножества
букв
)
таким
образом
,
чтобы
значения
вероятностей
того
,
что
наугад
взятая
из
рассматриваемого
текста
буква
окажется
в
первом
или
во
втором
из
этих
подмножеств
,
были
бы
по
возможности
близки
.
3)
Приписать
произвольному
одному
из
этих
подмножеств
(
подсписков
)
символ
"0",
а
другому
- "1".
4)
Рассматривая
каждое
из
этих
подмножеств
(
подсписков
)
как
исходное
,
применительно
к
каждому
из
них
осуществить
операции
,
указанные
в
пунктах
(2)
и
(3).
5)
Этот
процесс
продолжать
до
тех
пор
,
пока
в
каждом
из
очередных
подмножеств
не
окажется
по
одной
букве
.
6)
Каждой
букве
приписать
двоичный
код
,
состоящий
из
последовательности
нулей
и
единиц
,
встречающихся
на
пути
из
исходного
множества
букв
ко
множеству
,
состоящему
из
одной
этой
буквы
.
Пользуясь
схемой
Р
.
Фано
(
см
.
рис
. 2.1)
применительно
к
приведенному
выше
примеру
,
легко
установить
наборы
двоичных
символов
,
соответствующие
буквам
исходного
текста
:
Буква
Двоичный
код
Буква
Двоичный
код
А
00
Е
1011
В
01
F
110
С
100
G
1110
D
1010
Н
1111
Если
обозначить
через
L
A
=
2
,
L
B
= 3, L
C
= 3,...
числа
двоичных
символов
в
кодовых
наборах
,
соответствующих
буквам
А
,
В
,
С
, ...,
то
среднее
число
двоичных
символов
,
отводимых
под
одну
букву
исходного
алфавита
,
можно
определить
по
формуле
l
=
р
(
А
)l
А
+
p(
В
)l
B
+...+
p(
Н
)l
H
=
2,8
.
Таким
образом
,
с
переходом
к
переменной
длине
кодовых
наборов
,
отводимых
под
каждую
букву
исходного
текста
,
удается
на
7% (2,8
вместо
трех
символов
на
одну
букву
)
сократить
число
двоичных
символов
в
закодированном
тексте
.
Правда
,
это
связано
с
некоторым
усложнением
процедур
кодирования
и
декодирования
.
Будучи
достаточно
эффективной
,
схема
кодирования
Р
.
Фано
не
всегда
гарантирует
,
что
при
заданном
наборе
значений
вероятностей
средняя
длина
кодовых
наборов
l
окажется
наименее
возможной
.
Такую
гарантию
дает
другая
схема
кодирования
,
предложенная
американским
математиком
Д
.
Хаффманом
.
Исходные
соображения
здесь
те
же
,
что
и
при
рассмотрении
схемы
Р
.
Фано
,
однако
,
оперируя
более
тонким
механизмом
кодирования
,
Д
.
Хаффману
удалось
достичь
наименьшего
возможного
при
побуквенном
кодировании
значения
средней
длины
кодовых
наборов
.
