Коды Закса

Материал из WikiGrapp
Версия от 16:07, 27 октября 2009; Glk (обсуждение | вклад) (Создана новая страница размером '''Коды Закса''' (''Zaks' schemes'') - относятся к классу ''линейных кодов'' деревьев. Пу...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

Коды Закса (Zaks' schemes) - относятся к классу линейных кодов деревьев. Пусть дано бинарное или [math]\displaystyle{ k }[/math]-ичное дерево [math]\displaystyle{ T }[/math] с [math]\displaystyle{ n }[/math] вершинами такое, что каждая внутренняя вершина дерева помечена числом 1, а каждая висячая --- числом 0. Рассматриваются следующие способы кодирования дерева [math]\displaystyle{ T }[/math]:

1) [math]\displaystyle{ x }[/math]-кодом Закса дерева [math]\displaystyle{ T }[/math] называется последовательность пометок его вершин, перечисленных в инфиксном порядке;

2) [math]\displaystyle{ z }[/math]-кодом Закса дерева [math]\displaystyle{ T }[/math] называется последовательность номеров единиц в [math]\displaystyle{ x }[/math]-коде дерева [math]\displaystyle{ T }[/math], перечисленных в порядке их возрастания;

3) [math]\displaystyle{ y }[/math]-кодом Закса дерева [math]\displaystyle{ T }[/math] называется последовательность номеров нулей в [math]\displaystyle{ x }[/math]-коде дерева [math]\displaystyle{ T }[/math], перечисленных в порядке их возрастания.

См. также Коды Ли, Коды, свободные от повторений, Коды с дублированием номеров вершин, Коды с использованием ограничителей, Линейный код, Уровневые коды корневых деревьев, Ротационный код.

Литература

[Евстигнеев-Касьянов/94]