Введение в Алгебраическую теорию информации - Гоппа В.Д.
Скачать (прямая ссылка):
4'
У"2) = 1обШТУ = 2 бита-
Для слова а>ъ = (аЪаЪ) имеем композицию (2, 2) и
4'
/0(ш) = log^y = log 6.
Таким образом, чем меньше симметрий в слове, тем больше его 0-информация.
Термин "0-информация" подсказывает, что далее будут даны обобщения
понятия информации, основанного на изучении симметрий в расположении
букв. Наличие симметрий позволяет эффективно кодировать (сжимать) это
слово. С другой стороны, случайно выписанная последовательность букв не
содержит симметрий.
Минимально возможное значение 0-информации равно нулю. Это значение
достигается только для слов, состоящих из одной и той же буквы.
Максимальное значение 0-информация принимает на словах, в которых все
буквы встречаются одинаково часто (это следует из известных свойств
полиномиальных коэффициентов).
1.6. Условная 0-информация слова
Рассмотрим наряду с алфавитом X и множеством Хп еще один алфавит Y
(который может совпадать с X ) и соответственно
множество слов У".
Пусть у е У", Gy-стационарная подгруппа этого слова. Группа G^, являясь
подгруппой симметрической группы Sn, также
действует на Хп, так что Хп является G -множеством и разбивается на
"условные орбиты". Информацию, связанную с этим разбиением, назовем
условной 0-информацией слова х Е Хп при условии у е У" и обозначим
I^x/y). Ясно, что
I0(x/y) = log [Gy:(Gx П Gpi.
Введем еще одно определение. Декартово произведение Хп <8> У1 можно
трактовать как множество слов Zn в алфавите X <8> Y = = Z. Если х = (ар
..., ап), у = (й^..., й ), то слово х <8> у =
= ((aj, ftj), ..., (а , й )) будем называть произведением слов х и у.
Предложение 1.3.
У* (r) У) = У*) + уУ/х) = У>') + у*/у).
Доказательство. Легко проверяется, что =
= G П G . Далее применяем теорему Лагранжа о подгруппах: х у
[G:(GxnGy)] = tG:Gx] [Gx:(Gx П Ср] = [G:Gy] [Gy:(Gx П G^].
Переходя к логарифмам, получаем требуемый результат. Предложение1.4.
JQ(y/x) < JQ(y), /0 (х (r) з-) < /(*) + 1(у).
Доказательство. Первое неравенство очевидно, поскольку условная орбита
элемента у является подорбитой безусловной орбиты (Gp> С С>). Второе
неравенство является
следствием первого и предложения 1.3.
Предложен и е 1.5.
У х/у <8 z) <, /"(х/у), I0(x (r) y/z) = /"(х/z) + 10(у/х (r) z).
9
Доказательство. Gy e z = Gy П GzQGy. Отсюда следует, что орбита любого
элемента х под действием Gy ^ z является подорбитой орбиты этого элемента
под действием Gy Тем самым
доказано первое неравенство. Доказательство второго утверждения следует
из цепочки равенств:
[Gz=(Gz П (r) р] = <*,)] -
= [GI:(GI n Gx)] x l(Gz П Gx):(Gx ПСуП Gz)].
Предложение 1.6 (функциональная зависимость). Следующие утверждения
равносильны:
1) Ux/у) = О, 2) G С G , 3) Ь = Ь =*• а = а , 4) у =* *.
Л J2 Ч J2
Доказательство. Если
IQ(x/y) = log [Gy:(Gx n GJ] = О,
то
G = G П G , т. е. G ? G .
уху ух
Это означает, что каждая буква b слова у, на какой бы позиции y'j она ни
стояла, всегда переходит в одну и ту же букву а слова
х. Это значит, что существует функциональная зависимость у -* х между
словами х и у.
Пример 1.2.
х = (ас с babe с), у = (d а а е d е а Ь).
Мы видим, что всегда d => а, а=> с, е => Ь, Ь=> с.
Таким образом, значение каждой координаты слова х однозначно определяется
соответствующей координатой слова у, что и называется, по определению,
функциональной зависимостью у -* X.
Обратной зависимости х -* у в данном примере не существует, поскольку
буква с переходит иногда в букву а, а иногда в букву b слова у. Поэтому
*0(у/х) * 0.
IQ(x/у) и IQ(y/х) одновременно равны нулю тогда и только
тогда, когда слово у получено из слова х в результате переименования
букв, причем разные буквы слова х имеют различные, новые названия.
Два слова хну, связанные, взаимной функциональной зависимостью, будем
называть эквиваленщными:
X * у <=>10(у/х) = 1ц(х/у) = о <=>х у, у=> X.
10
Предложение^. IQ(y/х) является метрикой на орбите.
Доказательство. Докажем неравенство треугольника: /0(х/у) + IQ(y/z) >
IQ(x/y(r)z) + I0(y/z) = IQ(x(r)y/z) > I0(x/z).
Отсюда следует, что
IQ(x/z) < JQ(x/y) + IQ(y/z).
Далее, если x и у принадлежат одной и той же орбите, то
10Ыу) = Ifp/x).
Действительно, в этом случае у*) = У^) > а
У* (r) У) = У*) + 10(у/х) = ф) + IQ(x/y).
Поэтому IQ(x/y) симметрична относительно ха у. Наконец,
IQ(x/y) = 0 означает, что х " у. Таким образом, IQ(x/y) является
метрикой на классах эквивалентных слов.
Метрику 1^(х/у) будем называть информационной. Если * и
у не принадлежат одной орбите, то IQ(y/х) не равно IQ(x/у).
Можно положить
я О. у) = \ (У>*/х) + У */>>)).
и эта величина будет метрикой уже для любых слов одной и той же длины.
Введем, наконец, следующее определение. Величину
J0(x-y) = У*) + У?) - У* (r) У)
назовем взаимной 0-информацией слов х и у, или информацией, содержащейся
в слове х относительно слова у.
Из предложения 1.4 следует, что эта величина неотрицательна, а из
предложения 1.3 следует, что
УХ-У) = У*) - Уxh) = У?) - у?/*)-
1.7. Вычисление условной информации
