Эффективное сжатие немеченых деревьев

20

Рассмотрим немаркированные, укоренившиеся двоичные деревья. Мы можем сжать такие деревья: всякий раз , когда есть указатели на поддерева и с (интерпретируя как структурное равенство), мы сохраняем (без потери общности) и заменить все указатели на с указателями на . См . Ответ Ули для примера.T T = T = T T TTT'Tзнак равноT'знак равноTT'T

Дайте алгоритм, который принимает дерево в указанном выше смысле в качестве входных данных и вычисляет (минимальное) количество узлов, которые остаются после сжатия. Алгоритм должен выполняться за время (в модели с равномерной стоимостью) с числом узлов на входе.nО(NжурналN)N

Это был экзаменационный вопрос, и мне не удалось найти хорошее решение, и я его не видел.

Рафаэль
источник
И что такое «стоимость», «время», элементарная операция здесь? Количество посещенных узлов? Количество пройденных ребер? И как указан размер ввода?
Uli
Это сжатие дерева является примером хеширования . Не уверен, что это приведет к общему методу подсчета.
Жиль "ТАК - перестань быть злым"
@uli Я уточнил, что такое N . Я думаю, что время достаточно специфично. В непараллельных настройках это эквивалентно подсчету операций, что в терминах Ландау эквивалентно подсчету элементарной операции, которая происходит чаще всего.
Рафаэль
@Raphael Конечно, я могу предположить, какой должна быть намеченная элементарная операция, и, вероятно, выберу такую ​​же, как и все остальные. Но, и я знаю, что я здесь педантичен, всякий раз, когда даются «временные рамки», важно указать, что именно считается. Это свопы, сравнения, дополнения, обращения к памяти, проверенные узлы, пройденные ребра, вы называете это. Это все равно что опустить единицу измерения в физике. Это или 1010Кграмм ? И я полагаю, доступ к памяти - почти всегда самая частая операция. 10мs
Uli
@uli Это такие подробности, которые «единая модель затрат» должна передать. Больно точно определять, какие операции являются элементарными, но в 99,99% случаев (включая этот) нет никакой двусмысленности. Классы сложности в основном не имеют единиц измерения, они не измеряют время, необходимое для выполнения одного экземпляра, но то, как это время изменяется по мере увеличения входных данных.
Жиль "ТАК ... перестать быть злым"

Ответы:

10

Да, вы можете выполнить это сжатие за , но это не легко :) Сначала мы сделаем некоторые наблюдения, а затем представим алгоритм. Мы предполагаем, что дерево изначально не сжато - это на самом деле не нужно, но облегчает анализ.О(NжурналN)

Во-первых, мы характеризуем «структурное равенство» индуктивно. Пусть и T два (под) дерева. Если Т и Т ' являются нулевые деревья (не имеющие вершин на всех), они структурно эквивалентны. Если T и T ′ не являются нулевыми деревьями, то они структурно эквивалентны, если их левые потомки структурно эквивалентны, а их правые потомки структурно эквивалентны. «Структурная эквивалентность» является минимальной фиксированной точкой над этими определениями.TT'TT'TT'

Например, любые два конечных узла являются структурно эквивалентными, так как оба имеют нулевые деревья в качестве своих дочерних элементов, которые являются структурно эквивалентными.

Поскольку довольно неприятно говорить, что «их левые дети структурно эквивалентны, как и их правые дети», мы часто будем говорить, что «их дети структурно эквивалентны» и намерены делать то же самое. Также обратите внимание, что мы иногда говорим «эта вершина», когда имеем в виду «поддерево, корни которого находятся в этой вершине».

Приведенное выше определение немедленно дает нам подсказку, как выполнить сжатие: если мы знаем структурную эквивалентность всех поддеревьев с глубиной не более , то мы можем легко вычислить структурную эквивалентность поддеревьев с глубиной d + 1 . Мы должны сделать это вычисление разумно, чтобы избежать времени выполнения O ( n 2 ) .dd+1О(N2)

Алгоритм будет присваивать идентификаторы каждой вершине во время ее выполнения. Идентификатор - это число в наборе . Идентификаторы уникальны и никогда не меняются: поэтому мы предполагаем, что мы устанавливаем некоторую (глобальную) переменную равной 1 в начале алгоритма, и каждый раз, когда мы присваиваем идентификатор какой-либо вершине, мы присваиваем текущее значение этой переменной вершине и приращению значение этой переменной.{1,2,3,...,N}

Сначала мы преобразуем входное дерево в (не более ) списков, содержащих вершины одинаковой глубины вместе с указателем на их родителя. Это легко сделать за O ( n ) раз.NО(N)

Сначала мы сжимаем все листья (мы можем найти эти листья в списке с вершинами глубины 0) в одну вершину. Мы присваиваем этой вершине идентификатор. Сжатие двух вершин выполняется путем перенаправления родителя любой вершины, чтобы указывать на другую вершину.

Мы делаем два наблюдения: во-первых, у любой вершины есть дети строго меньшей глубины, а во-вторых, если мы выполнили сжатие на всех вершинах глубины, меньшей (и дали им идентификаторы), то две вершины глубины d структурно эквивалентны и может быть сжат, если идентификаторы их дочерних элементов совпадают. Последнее наблюдение следует из следующего аргумента: две вершины структурно эквивалентны, если их потомки структурно эквивалентны, и после сжатия это означает, что их указатели указывают на одинаковых потомков, что, в свою очередь, означает, что идентификаторы их потомков равны.dd

Мы перебираем все списки с узлами одинаковой глубины от малой до большой глубины. Для каждого уровня мы создаем список целочисленных пар, где каждая пара соответствует идентификаторам потомков некоторой вершины на этом уровне. Мы имеем, что две вершины на этом уровне структурно эквивалентны, если их соответствующие целочисленные пары равны. Используя лексикографический порядок, мы можем отсортировать их и получить наборы целочисленных пар, которые равны. Мы сжимаем эти множества в отдельные вершины, как указано выше, и присваиваем им идентификаторы.

Приведенные выше наблюдения доказывают, что этот подход работает и приводит к сжатому дереву. Общее время выполнения плюс время, необходимое для сортировки списков, которые мы создаем. Поскольку общее число целочисленных пар, которые мы создаем, равно n , это дает нам общее время работы O ( n log n ) , как требуется. Подсчет количества узлов, которые мы оставили в конце процедуры, тривиален (просто посмотрите, сколько идентификаторов мы раздали).О(N)NО(NжурналN)

Алекс тен Бринк
источник
Я не читал ваш ответ подробно, но я думаю, что вы более или менее переосмыслили хеш-обработку со странным, специфичным для проблемы способом поиска узлов.
Жиль "ТАК - перестань быть злым"
@ Алекс «дети строго меньшей degree» степени должны быть depth? И несмотря на то, что CS-деревья растут вниз, я нахожу «высоту дерева» менее запутанной, чем «глубину дерева».
Uli
Хороший ответ. Я чувствую, что должен быть способ обойти сортировку. Мой второй комментарий к ответу @Gilles действителен и здесь.
Рафаэль
@uli: Да, вы правы, я исправил это (не уверен, почему я перепутал эти два слова). Высота и глубина - это две тонко разные концепции, и мне нужно последнее :). Я думал, что буду придерживаться обычной «глубины», а не путать всех, меняя их местами.
Алекс тен Бринк
4

Сжатие неизменяемой структуры данных таким образом, чтобы она не дублировала какую-либо структурно равную подтерму, называется согласованием хэшей . Это важный метод управления памятью в функциональном программировании. Хеширование - это своего рода систематическое запоминание структур данных.

Мы собираемся хешировать дерево и считать узлы после хэширования. Хеширование структуры данных размера всегда можно сделать в O ( nN операции; Подсчет количества узлов в конце линейный по количеству узлов.О(NLграмм(N))

Я буду рассматривать деревья как имеющие следующую структуру (написанную здесь в синтаксисе Haskell):

data Tree = Leaf
          | Node Tree Tree

Для каждого конструктора нам нужно поддерживать соответствие его возможных аргументов результату применения конструктора к этим аргументам. Листья тривиальны. Для узлов мы сохраняем конечное частичное отображение где T - набор идентификаторов деревьев, а N - набор идентификаторов узлов; T = N { } где - единственный листовой идентификатор. (В конкретных терминах идентификатор - это указатель на блок памяти.)Nоdеs:T×TNTNTзнак равноN{}

Мы можем использовать структуру данных логарифмического времени nodes, например сбалансированное двоичное дерево поиска. Ниже я вызову lookup nodesоперацию, которая ищет ключ в nodesструктуре данных, и insert nodesоперацию, которая добавляет значение в новый ключ и возвращает этот ключ.

Теперь мы пересекаем дерево и добавляем узлы по мере продвижения. Хотя я пишу в псевдокоде, похожем на Haskell, я буду воспринимать его nodesкак глобальную переменную; мы только добавим к нему, но вставки должны быть пронизаны. addФункция рекурсивно на дереве, добавив его поддеревьев к nodesкарте, и возвращает идентификатор корня.

insert (p1,p2) =
add Leaf = $\ell$
add (Node t1 t2) =
    let p1 = add t1
    let p2 = add t2
    case lookup nodes (p1,p2) of
      Nothing -> insert nodes (p1,p2)
      Just p -> p

Количество insertвызовов, которое также является окончательным размером nodesструктуры данных, представляет собой количество узлов после максимального сжатия. (Добавьте один для пустого дерева, если необходимо.)

Жиль "ТАК - перестань быть злым"
источник
Можете ли вы дать ссылку на «Хеш, содержащий структуру данных размера всегда можно сделать в O ( n l g»).Nоперациях ( n ) ) »? Обратите внимание, что вам понадобятся сбалансированные деревья длятого, чтобы достичь желаемого времени выполнения. O(nlg(n))nodes
Рафаэль
Я рассматривал только структурирование хеширования подструктур для чисел, чтобы независимое вычисление хеша для одного и того же дерева всегда давало один и тот же результат. Ваше решение тоже подойдет, если у нас в руках изменяемые структуры данных. Я думаю, что это можно почистить немного, хотя; чередование insertи addдолжно быть сделано явным, и должна быть дана функция, которая фактически решает проблему, imho.
Рафаэль
1
@Raphael Hash consing опирается на конечную структуру карты по кортежам указателей / идентификаторов, вы можете реализовать это с логарифмическим временем поиска и добавления (например, с помощью сбалансированного бинарного дерева поиска). Мое решение не требует изменчивости; nodesДля удобства я делаю изменяемую переменную, но вы можете использовать ее во всех случаях. Я не собираюсь давать полный код, это не так.
Жиль "ТАК - перестань быть злым"
1
@Raphael HASHING структура, в отличии от присвоения им произвольных чисел, немного изворотливый. В модели с равномерной стоимостью вы можете закодировать что угодно в большое целое число и выполнять с ним операции постоянного времени, что нереально. В реальном мире вы можете использовать криптографические хеши, чтобы иметь фактическое сопоставление «один к одному» из бесконечных множеств в конечный диапазон целых чисел, но они медленные. Если вы используете в качестве хэша контрольную сумму без шифрования, вам нужно подумать о коллизиях.
Жиль "ТАК - перестань быть злым"
3

Вот еще одна идея, которая направлена ​​на (инъективное) кодирование структуры деревьев в числа, а не на их произвольную маркировку. Для этого мы используем, что первичная факторизация любого числа уникальна.

Для наших целей пусть обозначает пустую позицию в дереве, а N ( l , r ) узел с левым поддеревом l и правым поддеревом r .ЕN(L,р)Lр будет листом. Теперь пустьN(Е,Е)

е(Е)знак равно0е(N(L,р))знак равно2е(L)3е(р)

е

Это последнее предположение является натяжкой для реальных машин; в этом случае вместо возведения в степень предпочли бы использовать нечто похожее на функцию спаривания Кантора .

О(NжурналN)О(NжурналN)

Рафаэль
источник
1

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

введите описание изображения здесь

вверху слева: дерево ввода

вверху справа: поддеревья с корнями в узлах 5 и 7 тоже изоморфны.

внизу слева и справа: сжатые деревья не определены однозначно.

7+5|T|6+|T|

улы
источник
Это действительно пример желаемой операции, спасибо. Обратите внимание, что ваши последние примеры идентичны, если вы не различаете оригинальные и добавленные ссылки.
Рафаэль
-1

Изменить: я прочитал вопрос, как T и T ′ были детьми одного и того же родителя. Я взял определение сжатия также рекурсивным, то есть вы можете сжать два ранее сжатых поддерева. Если это не фактический вопрос, то мой ответ может не сработать.

О(NжурналN)T(N)знак равно2T(N/2)+сN

def Comp(T):
   if T == null:
     return 0
   leftCount = Comp(T.left)
   rightCount = Comp(T.right)
   if leftCount == rightCount:
     if hasSameStructure(T.left, T.right):
       T.right = T.left
       return leftCount + 1
     else
       return leftCount + rightCount + 1    

где hasSameStructure() функция, которая сравнивает два уже сжатых поддерева за линейное время, чтобы увидеть, имеют ли они точно такую ​​же структуру. Написание рекурсивной функции с линейным временем, которая обходит каждую и проверяет, есть ли у одного поддерева левый дочерний элемент каждый раз, когда у другого есть и т. Д., Не должно быть трудным.

Пусть NNр

T(N)знак равноT(N1)+T(N2)+О(1) если NNр
2T(N/2)+О(N) в противном случае
Джо
источник
Что делать, если поддеревья не являются братьями и сестрами? Забота о ((T1, T1), (T2, T1)) T1 может быть сохранена дважды с помощью указателя два в третий раз.
Uli
TT'
На вопросы Мерли утверждается, что два подстресса определены как изоморфные. Ничего не сказано о том, что у них один и тот же родитель. Если поддерево T1 появляется три раза в дереве, как в моем предыдущем примере ((T1, T1), (T1, T2)), два экземпляра могут быть сжаты, указывая на третий orccurence.
Uli