Введение в Алгебраическую теорию информации - Гоппа В.Д.
Скачать (прямая ссылка):
кода является средняя длина кодовых слов
~1 = " 2 *>(*) *(*)•
Для префиксного кода всегда
7 > Н(х)
(следствие неравенства между средним арифметическим и средним
геометрическим), и можно как угодно близко подойти к этой границе,
устремляя п -* °о. Для этого нужно упорядочить все слова по собственной
информации:
5(х,) > S(x2) > ... > S(xN),
и наименее вероятному слову приписывать слово из префиксного кода,
имеющее наибольшую длину. Такой принцип применялся ранее в коде Морзе, а
после работы Шеннона стало возможным сравнивать подобные коды по их
эффективности. В частности, оказалось, что код Морзе близок к
оптимальному.
Были предложены регулярные методы построения оптимальных кодов (код
Шеннона-Фано, код Хаффмена). В этих методах предполагается, что
вероятности сообщений (слов) известны точно. Если статистика не точна или
же меняется в процессе передачи, то методы приводят к кодам, далеким от
оптимальных.
104
Кодовые слова определяются вероятностной структурой, поэтому кодирование
связано с экспоненциальным объемом вычислений.
Когда речь идет об эффективном кодировании отдельных букв с учетом
неравномерной частоты их появления, упомянутые методы приводят к очень
быстрым и красивым алгоритмам. На практике обычно ставится задача сжатия
слова большой длины, причем в исходной постановке ничего не говорится о
какой-либо вероятности.
Б.М. Фитингоф [16] обнаружил существование методов кодирования источника,
устойчивых по отношению к распределению вероятностей. Он предложил
упорядочить слова по величине Н(х), названной им квазиэнтропией. Эта
величина применялась ранее как выборочная энтропия (статистическая оценка
для энтропии). Б.М. Фитингоф впервые применил ее как вес, по которому
следует упорядочить сообщения. Если слову с наименьшей энтропией
приписать кодовое слово наименьшей длины, то получится код, оптимальный
для целого класса вероятностных распределений.
При кодировании по методу Фитингофа вовсе не требуется знание статистики
сообщений. А если распределение вероятностей меняется, то код по-прежнему
остается оптимальным. Энтропия слова Н(х) или /^(х) выполняет при этом ту
же функцию, что
и собственная информация по Шеннону. В своей следующей статье Фитингоф
назвал эту величину информацией слова. Задача кодирования источника была
сведена им к нумерации слов одной и той же орбиты.
Реализация этого метода с использованием треугольника Паскаля принадлежит
В.Ф. Бабкину. В результате был получен метод кодирования источника
полиномиальной трудоемкости. Поскольку упорядоченность по Jq(x) заменяет
упорядоченность по
вероятности, возникает мысль применить IQ для целей декодирования в
канале с шумом.
В шенноновской теории декодирование определяется в терминах р(х).
Декодирование максимального правдоподобия заключается в том, что слово у
декодируется в такое слово х на входе, для которого апостериорная
вероятность
р(х/у) = р(х, у)/р(у)
максимальна (байесовский подход). Декодер при этом настраивается на
вероятности, которые известны неточно и могут меняться в процессе
передачи.
Абонентам кажется, что декодирование осуществляется оптимальным способом,
а на самом деле ввиду изменившейся статистики эффективность декодирования
давно уже не поддается контролю. Если же для целей декодирования
использовать метрику 1ц(х/у), то получается декодирование, оптимальное
для
105
целого класса распределений вероятностей (устойчивое декодирование) [7 ].
Возникла мысль ввести вместо вероятностного канала с шумом более простую
модель-алгебраический канал [7 ]. Если научиться строить оптимальный код
для алгебраического канала, то тем самым будет решена задача построения
оптимального кода в вероятностной модели (конструктивное доказательство
теоремы кодирования Шеннона).
Впрочем, надобность в вероятностной модели отпадает, поскольку теория
информации оказывается достаточно интересной и богатой приложениями в
алгебраической постановке. Одним из таких приложений является
распознавание образов.
Описанный в гл. 2 метод распознавания является развитием хорошо
известного подхода М.М. Бонгарда [4]. Когда М.М. Бон-гард создавал свой
алгоритм, не было известно, как вычислять информацию одного признака
(слова), содержащуюся в другом признаке. Алгебраический подход к теории
информации дает естественное решение двух ключевых проблем распознавания
образов-определения информативности признаков и кластерного анализа.
Программная реализация описанного метода распознавания была выполнена
И.С. Борейко. Ряд специалистов в Московском геологоразведочном институте
применили этот метод распознавания для решения различных геологических
задач [12, 15, 16].
Реляционная модель базы данных была первоначально изложена в статье Е.Ф.
Кодда [21 ]. Он обратил внимание на важность понятия функциональной
зависимости для целей нормализации (декомпозиции). Правила вывода для /'-
зависимостей были предложены К. Делобелем и Кейси, их полноту доказал
