Коды Закса: различия между версиями
Glk (обсуждение | вклад) (Создана новая страница размером '''Коды Закса''' (''Zaks' schemes'') - относятся к классу ''линейных кодов'' деревьев. Пу...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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> вершинами | |||
такое, что каждая внутренняя вершина дерева помечена числом 1, а каждая висячая --- числом 0. Рассматриваются следующие | |||
способы кодирования дерева <math>T</math>: | |||
1) <math>x</math>-''кодом Закса'' дерева <math>T</math> называется | 1) <math>x</math>-''кодом Закса'' дерева <math>T</math> называется последовательность [[пометка|пометок]] его вершин, перечисленных в [[инфиксный порядок обхода дерева|инфиксном порядке]]; | ||
последовательность пометок его вершин, перечисленных в | |||
инфиксном порядке; | |||
2) <math>z</math>-''кодом Закса'' дерева <math>T</math> называется | 2) <math>z</math>-''кодом Закса'' дерева <math>T</math> называется последовательность номеров единиц в <math>x</math>-коде дерева <math>T</math>, перечисленных в порядке их возрастания; | ||
последовательность номеров единиц в <math>x</math>-коде дерева | |||
<math>T</math>, перечисленных в порядке их возрастания; | |||
3) <math>y</math>-''кодом Закса'' дерева <math>T</math> называется | 3) <math>y</math>-''кодом Закса'' дерева <math>T</math> называется последовательность номеров нулей в <math>x</math>-коде дерева <math>T</math>, перечисленных в порядке их возрастания. | ||
последовательность номеров нулей в <math>x</math>-коде дерева | |||
<math>T</math>, перечисленных в порядке их возрастания. | |||
См. также ''Коды Ли, Коды, свободные от повторений, Коды с дублированием номеров вершин, Коды с использованием ограничителей, Линейный код, Уровневые коды корневых деревьев, Ротационный код.'' | [[Файл:Zaks' schemes.png]] | ||
==См. также== | |||
''[[Коды Ли]], [[Коды, свободные от повторений]], [[Коды с дублированием номеров вершин]], [[Коды с использованием ограничителей]], [[Линейный код]], [[Уровневые коды корневых деревьев]], [[Ротационный код]].'' | |||
==Литература== | ==Литература== | ||
[Евстигнеев-Касьянов/94] | [Евстигнеев-Касьянов/94] | ||
Версия от 12:38, 29 октября 2009
Коды Закса (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]