Кодирование деревьев с помощью линейных рекуррентных последовательностей

Abstract

Предлагается унифицированное кодирование упорядоченных бинарных деревьев с числовыми метками в вершинах с помощью линейных форм соседних членов линейных рекуррентных последовательностей вида Pn+2=αn+2Pn+1+Pn, где P1=P2=1; α3, α4, ... — натуральные числа. Процедуры кодирования/декодирования просты в реализации и используют рекурсивную технику прямого обхода дерева способом перебора в глубину. Дан краткий обзор возможных применений такого кодирования для задач обработки деревьев и криптографических преобразований.

Запропоновано уніфіковане кодування упорядкованих бінарних дерев з числовими позначками у вершинах за допомогою лінійних форм сусідніх членів лінійних рекурентних послідовностей вигляду Pn+2=αn+2Pn+1+Pn, де P1=P2=1; α3, α4, ... — натуральні числа. Процедури кодування/декодування прості у реалізації і використовують рекурсивну техніку прямого обходу дерева способом перебору в глибину. Надано короткий огляд можливих застосувань такого кодування для задач обробки дерев і криптографічних перетворень .

A unified integer encoding of ordinal binary trees with integer labels in vertices is given. The encoding is based on the use of linear forms depending on two neighboring members of linear recurrences Pn+2=αn+2Pn+1+Pn, where P1=P2=1; α3, α4, ... are natural numbers. Encoding and decoding procedures are simple in implementation and use recursive pre-order tree traversal. A brief review of possible applications for subtree processing and cryptographic symmetric encoding is presented .