Коды Закса: различия между версиями

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Коды Закса''' (''Zaks' schemes'') - относятся к классу ''линейных кодов'' деревьев. Пу...)
 
Нет описания правки
 
(не показаны 4 промежуточные версии 1 участника)
Строка 1: Строка 1:
'''Коды Закса''' (''Zaks' schemes'') -
'''Коды Закса''' (''[[Zaks' schemes]]'') относятся к классу ''[[линейный код|линейных кодов]]'' [[дерево|деревьев]]. Пусть дано ''[[бинарное дерево|бинарное]]'' или ''<math>k</math>-ичное дерево'' <math>T</math> с <math>n</math> вершинами такое, что каждая [[внутренняя вершина]] дерева помечена числом 1, а каждая [[висячая вершина|висячая]] — числом 0. Рассматриваются следующие способы кодирования дерева <math>T</math>:
относятся к классу ''линейных кодов'' деревьев. Пусть дано ''бинарное'' или ''<math>k</math>-ичное дерево'' <math>T</math> с <math>n</math> вершинами
[[Файл:Zaks' schemes.png|350px|right]]
такое, что каждая внутренняя вершина дерева помечена числом 1, а каждая висячая --- числом 0. Рассматриваются следующие
1) <math>x</math>-''кодом Закса'' дерева <math>T</math> называется последовательность [[пометка|пометок]] его вершин, перечисленных в [[инфиксный порядок обхода дерева|инфиксном порядке]];
способы кодирования дерева <math>T</math>:


1) <math>x</math>-''кодом Закса'' дерева <math>T</math> называется
2) <math>z</math>-''кодом Закса'' дерева <math>T</math> называется последовательность номеров единиц в <math>x</math>-коде дерева <math>T</math>, перечисленных в порядке их возрастания;
последовательность пометок его вершин, перечисленных в
инфиксном порядке;


2) <math>z</math>-''кодом Закса'' дерева <math>T</math> называется
3) <math>y</math>-''кодом Закса'' дерева <math>T</math> называется последовательность номеров нулей в <math>x</math>-коде дерева <math>T</math>, перечисленных в порядке их возрастания.
последовательность номеров единиц в <math>x</math>-коде дерева
<math>T</math>, перечисленных в порядке их возрастания;


3) <math>y</math>-''кодом Закса'' дерева <math>T</math> называется
последовательность номеров нулей в <math>x</math>-коде дерева
<math>T</math>, перечисленных в порядке их возрастания.


См. также  ''Коды Ли, Коды, свободные от повторений, Коды с дублированием номеров вершин, Коды с использованием ограничителей, Линейный код, Уровневые коды корневых деревьев, Ротационный код.''
 
==См. также==  
* ''[[Коды Ли]],''
* ''[[Коды, свободные от повторений]],''
* ''[[Коды с дублированием номеров вершин]],''
* ''[[Коды с использованием ограничителей]],''
* ''[[Линейный код]],''
* ''[[Уровневые коды корневых деревьев]],''
* ''[[Ротационный код]].''
==Литература==
==Литература==
[Евстигнеев-Касьянов/94]
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.
 
[[Категория: Коды деревьев]]

Текущая версия от 15:23, 9 октября 2019

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

Zaks' schemes.png

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], перечисленных в порядке их возрастания.


См. также

Литература

  • Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.