Как более эффективно кодировать упорядоченное дерево в битовую последовательность

Question

Предположим, что мы хотим сохранить форму упорядоченного дерева из n узлов, каждый узел имеет максимум 2 дочерних элемента. Если это двоичное дерево, мы должны использовать 2n бит. Поскольку в нашей ситуации у нас нет левого или правого ребенка, они одинаковы, поэтому мы должны иметь несколько избыточных последовательностей. Итак, можем ли мы кодировать это лучше? Кажется, что у каждого узла все еще есть 3 случая, ни одного дочернего, одного дочернего, двух дочерних, но можем ли мы сохранить его менее чем в 2 битах? Или в целом есть лучшая константа, чем 2?

Answer 1

Есть два способа приблизиться к нему:

1. Кодирование многоуровневых поддеревьев. Например: на максимальном уровне два вы можете иметь четыре фигуры: (), (a), (a-> b) и (a <-b-> c). Теперь используйте 0,10,111,111 для каждого из этих случаев. Для простого 2-уровневого полного дерева кодирование: 111 0 0. 3-уровневое полное дерево: 111,10,10. Для 4-го уровня завершенного дерева это становится: 111 111 111 0 0 0 0. Назначения являются произвольными. Вы можете использовать схему кодирования Хоффмана (как уже упоминалось), чтобы найти оптимальное кодирование. Эта схема кодирования хуже для цепочек. Для чистой цепочки необходимо 3n-2 бита для хранения.

2. Выполните 2-битное кодирование, а затем сожмите с помощью любых алгоритмов сжатия.

=== Другой подход ===

В обычном представлении для каждого узла вы можете выбрать один из трех вариантов: 00, 01, 11. Теперь возьмем три узла за раз. Вы можете иметь всего 27 комбинаций. Вы можете хранить каждую из этих комбинаций в 5 битах. Таким образом, средняя необходимая память становится 5/3 вместо 2 бит. Кроме того, вы можете попытаться объединить любое количество узлов, которые вам нравятся. В следующей таблице приведены коэффициенты сжатия:

Как вы можете видеть, если объединить 10 узлов вместе, вы уменьшите пространство хранения в 1,25 раза (то есть пространство уменьшится на 20%)

naive_length compr_length compr_factor
2 2 1.0
4 4 1.0
6 5 1.2
8 7 1.14285714286
10 8 1.25
12 10 1.2
14 12 1.16666666667
16 13 1.23076923077
18 15 1.2
20 16 1.25
22 18 1.22222222222
24 20 1.2
26 21 1.2380952381
28 23 1.21739130435
30 24 1.25
32 26 1.23076923077
34 27 1.25925925926

Answer 2

Возможно, вы сможете сохранить 2n бит, как вы упомянули, а затем использовать кодирование Хаффмана или другой метод сжатия данных без потерь для сжатия этих данных.

Я не думаю, что вы можете достичь лучшей границы наихудшего случая, но в среднем - это должно сэкономить вам немного места.

Answer 3

Если я правильно понимаю, если у узла есть один дочерний элемент, это не левый или правый дочерний элемент, т.е. вы не различаете левый и правый в случае одного дочернего элемента. Тогда я думаю, что это можно сделать в (log 3) n, где log - база 2.

Вы описываете дерево путем обхода предзаказа, для каждого узла вы записываете количество дочерних элементов (0, 1 или 2). Это создает количество оснований 3 длины n (фактически длина n - 1, последний узел всегда будет иметь нулевые дочерние элементы). Таких чисел ровно 3 ^ (n - 1), их можно закодировать в двоичном виде в (log 3) (n - 1) ~ = 1,59 (n - 1).

Можно использовать O (log n) битов, чтобы записать количество бит в начале закодированной строки битов.

Обновление: вот реализация .