Введение в Алгебраическую теорию информации - Гоппа В.Д.
Скачать (прямая ссылка):
84
получить описанным способом, равно ^ т'.\ ^ (т. - 1)!
П m.т! "11 т.,!...(т., - 1)!...т. ! "
/ /1 iq i /1 v ik 7
т,...т , -I -I т.. !...т. !'
1 q-\ i il iq
Таким образом,
9-1
log N^ > 10(х/Тх) - 2 log mi > /,(х) - (? - 1) log п.
(=1
С другой стороны, если в (r) не фиксировать дерево D, а
подействовать на у. подстановкой из G , то получим все слова 0 хо
условной орбиты слова >'Q. Логарифм мощности этой орбиты равен
7оО'о/хо) = iq(x/Tx) = 7iW-
Таким образом,
log < /j(x).
Следовательно,
/,(х) - (q - 1) log п < log TV< /,(х).
5.2. 1-сжатие по Фитингофу
В п. 1.10 был описан способ сжатия слов (назовем его
0-сжатием), при котором длина кодового слова асимптотически равна его 0-
информации. Этот способ эффективен в том случае, когда буквы в слове
распределены неравномерно. Для слова
х = (01010101)
этот способ не дает эффекта сжатия, поскольку /Q(x) = п. В то
же время сильная зависимость на один шаг между буквами этого слова
наводит на мысль применить следующий способ сжатия (назовем его 1 -
сжатием): кодовое слово состоит из двух частей: префикса фиксированной
длины, в котором записывается номер
1-орбиты, и переменной части, в которой записывается номер слова внутри
1-орбиты.
Каждая 1-орбита полностью определяется переходной мат-
рицей х -" Тх. Для ее записи потребуется место для q чисел ш... Поскольку
каждое из чисел т.. потребует не больше log п
бит, всего для префикса нужно будет отвести q2 log (п) бит. Для
85
записи же номера слова внутри 1-орбиты потребуется не больше /j(jc) бит
вследствие теоремы 5.1. Таким образом, справедлив
следующий результат:
Т е о р е м а 5.2. Существует префиксный код, у
которого
длина кодового слова асимптотически равна I-информации слова:
1(х) = /Дх) + о(п),
где
| о(п) | < q2 log п.
Практически сжатие удобно осуществлять сведением к 0-
сжатию. Допустим, что
х = (acabcabbc).
Используя отображение <р, получаем пару слов <8> У0'-
х facabcabbc\ laaabbbccc
Tx cabcabbcaj \cbbcbcaaaj y0'
Сначала кодируем ту часть у^ слова yQ, которая соответствует
фиксированной букве а вверху, т.е. записываем в сжатой форме слово (ebb).
Для этого применяем 0-сжатие, так что кодовое слово состоит из двух
частей: префикса длины q log п, в котором записываем числа m^, т]2, ...,
Затем идет переменная часть длины /Q (у^ ^. Далее записываем в
аналогичной форме
ту часть у^ слова >>0, которая соответствует фиксированной
букве b вверху, и т.д. В результате получаем переменную часть длины
4>(^0 ¦*) + А)(>0 ^ + ••• = ^о(Уо^хо) = W-
5.3. m-информация слова
В слове может отсутствовать память на один шаг, но пара соседних букв
может однозначно определять следующую букву. Введем понятие 2-информации
слова следующим образом:
I2(x) = Iq(x/ Тх <8> Т2х),
где 7*х означает сдвиг на к шагов. Более общим образом, m-информацией
слова назовем величину
Im(x) = IQ(x/Tx (r)Т2х(r)... (r) Ттх).
86
Вычислим для примера 12(х) для слова
х = (010011110010).
2
Переходная матрица Тх(r)Т х -* х имеет вид
0 1
00 3 3
01 2 1 3
10 3 3
11 1 2 3
6 6 12
12(х) = I0(x/Tx (r) TLx) = ЗЯ l ^j + ЗЯ = 2 • 3 • 0.92 = 5.52 бит.
Каждой паре букв (диграмме) присвоим новое обозначение:
00 - .4
01 - В
10 - с
11 - D
Тогда слову х ставится в соответствие новое слово из большего алфавита:
X = (BCABDDDCABCA).
Чтобы по слову X восстановить слово х, нужно каждую букву слова X
выписать в виде столбца:
/010011110010\ _х~Тх л - (^OOllllOOlOOj - х-
Верхняя строка совпадает со словом х. Очевидно,
1\(Х) = 10(Х/ТХ) = I0(x <g> Гх/Тх <g> Т2х) = IQ(x/Tx (r) Т2х) = 12(х).
Таким образом, понятие 2-информации слова х сводится к
1-информации слова X.
Например, переходная матрица X ¦* ТХ имеет вид
А В С D
А 3 3
В 2 1 3
С 3 3
D 1 2 3
3 3 3 3 12
/,(*) = 6Я з
Точно так же, когда речь идет о вычислении т-информации, можно по слову m
из ^-ичного алфавита построить слово X в
87
(?т-ичном алфавите, считая каждый блок из т соседних букв новой буквой.
Тогда
/"(*) = Л w.
1-орбиту слова X назовем в этом случав т-орбитой слова х.
Из теорем 5.1 и 5.2 получаем:
Теорема 5.3. Логарифм числа слов т-орбиты асимптотически равен т-
информации слова:
log A^m) = Im(x) - о(п),
| о(п) | < qm log n.
Существует префиксный код, у которого длина кодового слова асимптотически
совпадает с т-информацией слова:
l(x) = IJx) + о(п),
| о(п) | < ^m+1log п.
5.4. Информационная характеристика слова
Для каждого слова х можно составить невозрастающую цепочку величин:
/<>(*) S /,(*) > /2(х) > ...
Эту последовательность назовем информационной характеристикой слова.
Последовательность обычно стабилизируется при некотором значении т. При
этом величина 1т(х) характеризует
ту степень сжатия, которая может быть достигнута с помощью симметрий
слова (симметрий в расположении букв).
Существуют двоичные последовательности с идеальной информационной
характеристикой:
1 2 3 4 ... m
У этой последовательности
7о(*) = Л(*) = ••• = ;mW-
что означает следующее:
1) Число единиц равно числу нулей.
