Алгоритм Гарсиа-Вакса - Garsia–Wachs algorithm - Wikipedia

В Алгоритм Гарсиа-Вакса это эффективный метод для компьютеров, чтобы построить оптимальные бинарные деревья поиска и буквенные коды Хаффмана, в линейный время. Он назван в честь Адриано Гарсия и Мишель Л. Вакс.

Описание проблемы

Вход в задачу для целого числа ${\displaystyle n}$, состоит из последовательности ${\displaystyle n+1}$ неотрицательные веса ${\displaystyle w_{0},w_{1},\dots ,w_{n}}$. Результатом является корневой двоичное дерево с ${\displaystyle n}$ внутренние узлы, каждый из которых имеет ровно два дочерних элемента. Такое дерево имеет ровно ${\displaystyle n+1}$ листовые узлы, которые можно идентифицировать (в порядке, заданном двоичным деревом) с помощью ${\displaystyle n+1}$ входные веса. Цель задачи - найти дерево среди всех возможных деревьев с ${\displaystyle n}$ внутренние узлы, что минимизирует взвешенную сумму длина внешнего пути. Эти длины пути представляют собой количество шагов от корня до каждого листа. Они умножаются на вес листа, а затем суммируются, чтобы получить качество всего дерева.^[1]

Эту проблему можно интерпретировать как задачу построения двоичное дерево поиска за ${\displaystyle n}$ упорядоченные ключи, предполагая, что дерево будет использоваться только для поиска значений, которых еще нет в дереве. В этом случае ${\displaystyle n}$ ключи разделяют пространство значений поиска на ${\displaystyle n+1}$ интервалов, а вес одного из этих интервалов можно принять как вероятность поиска значения, попадающего в этот интервал. Взвешенная сумма длин внешних путей управляет ожидаемое время для поиска по дереву.^[1]

В качестве альтернативы, вывод задачи можно использовать как Код Хаффмана, метод кодирования ${\displaystyle n+1}$ заданных значений однозначно с помощью последовательностей переменной длины двоичные значения. В этой интерпретации код для значения задается последовательностью шагов влево и вправо от родителя к дочернему на пути от корня к листу в дереве (например, с 0 для левого и 1 для правого). В отличие от стандартных кодов Хаффмана, построенные таким образом алфавитный, что означает, что отсортированный порядок этих двоичных кодов такой же, как входной порядок значений. Если вес значения - это его частота в кодируемом сообщении, тогда выходом алгоритма Гарсиа-Вакса является алфавитный код Хаффмана, который компрессы сообщение максимально короткой длины.^[1]

Алгоритм

Двоичное дерево, построенное на первом этапе алгоритма путем поиска и слияния неупорядоченных троек во входной последовательности (слева) и на выходе алгоритма, правильно упорядоченное двоичное дерево, листья которого находятся на тех же уровнях, что и другое дерево

В целом алгоритм состоит из трех этапов:^[1]

1. Постройте двоичное дерево со значениями в виде листьев, но, возможно, в неправильном порядке.
2. Вычислите расстояние каждого листа от корня в получившемся дереве.
3. Постройте еще одно двоичное дерево с листьями на том же расстоянии, но в правильном порядке.

Первую фазу алгоритма легче описать, если к входу добавить два дозорные ценности, ${\displaystyle \infty }$ (или любое достаточно большое конечное значение) в начале и в конце последовательности.^[2]

На первом этапе поддерживается лес деревьев, первоначально дерево с одним узлом для каждого входного веса, не являющегося дозорным, которое в конечном итоге станет бинарным деревом, которое оно построит. Каждое дерево связано со значением, сумма весов его листьев образует узел дерева для каждого входного веса, не являющегося дозорным. Алгоритм поддерживает последовательность этих значений с двумя контрольными значениями на каждом конце. Первоначальная последовательность - это просто порядок, в котором веса листьев были заданы в качестве входных данных. Затем она повторно выполняет следующие шаги, каждый из которых уменьшает длину входной последовательности, пока не останется только одно дерево, содержащее все листья:^[1]

• Найдите первые три последовательных веса ${\displaystyle x}$, ${\displaystyle y}$, и ${\displaystyle z}$ в последовательности, для которой ${\displaystyle x\leq z}$. Такая тройка существует всегда, потому что конечное контрольное значение больше любых двух предыдущих конечных значений.
• Удалять ${\displaystyle x}$ и ${\displaystyle y}$ из последовательности и сделайте новый узел дерева родительским для узлов для ${\displaystyle x}$ и ${\displaystyle y}$. Его ценность ${\displaystyle x+y}$.
• Повторно вставьте новый узел сразу после самой правой более ранней позиции, значение которой больше или равно ${\displaystyle x+y}$. Такая позиция всегда существует из-за левого дозорного значения.

Для эффективной реализации этого этапа алгоритм может поддерживать текущую последовательность значений в любом самобалансирующееся двоичное дерево поиска структура. Такая структура позволяет удалять ${\displaystyle x}$ и ${\displaystyle y}$, и повторная вставка их нового родителя в логарифмическом времени. На каждом этапе веса до ${\displaystyle y}$ в четных позициях массива образуют убывающую последовательность, а веса в нечетных позициях образуют другую убывающую последовательность. Таким образом, позиция для повторной вставки ${\displaystyle x+y}$ можно найти в логарифмическом времени, используя сбалансированное дерево для выполнения двух бинарный поиск, по одному для каждой из этих двух убывающих последовательностей. Поиск первой позиции, по которой ${\displaystyle x\leq z}$ может быть выполнено за линейное общее время с помощью последовательный поиск что начинается в ${\displaystyle z}$ из предыдущей тройки.^[1]

Нетривиально доказать, что на третьем этапе алгоритма существует другое дерево с такими же расстояниями и что это дерево обеспечивает оптимальное решение проблемы. Но если предположить, что это правда, вторую и третью фазы алгоритма просто реализовать за линейное время. Таким образом, общее время работы алгоритма на входе длины ${\displaystyle n}$, является ${\displaystyle O(n\log n)}$.

История

Алгоритм Гарсиа – Вакса назван в честь Адриано Гарсия и Мишель Л. Вакс, опубликовавший его в 1977 году.^[1][3] Их алгоритм упростил более ранний метод Т. К. Ху и Алан Такер,^[1][4] и (хотя он отличается во внутренних деталях) он в конечном итоге выполняет те же сравнения в том же порядке, что и алгоритм Ху – Такера.^[5] Первоначальное доказательство правильности алгоритма Гарсиа – Вакса было сложным, а позже было упрощено Кингстон (1988)^[1][2]и Карпинский, Лармор и Риттер (1997).^[6]

Рекомендации

1. Кнут, Дональд Э. (1998), «Алгоритм G (алгоритм Гарсиа – Вакса для оптимальных двоичных деревьев)», Искусство программирования, Vol. 3. Сортировка и поиск (2-е изд.), Addison – Wesley, стр. 451–453. См. Также «История и библиография», стр. 453–454.
2. Кингстон, Джеффри Х. (1988), "Новое доказательство алгоритма Гарсиа-Вакса", Журнал алгоритмов, 9 (1): 129–136, Дои:10.1016/0196-6774(88)90009-0, МИСТЕР  0925602
3. Гарсия, Адриано М.; Вакс, Мишель Л. (1977), «Новый алгоритм для бинарных деревьев с минимальной стоимостью», SIAM Журнал по вычислениям, 6 (4): 622–642, Дои:10.1137/0206045, МИСТЕР  0520738
4. Hu, T. C .; Такер, А.С. (1971), «Оптимальные деревья компьютерного поиска и алфавитные коды переменной длины», Журнал SIAM по прикладной математике, 21: 514–532, Дои:10.1137/0121057, МИСТЕР  0304063
5. Мельхорн, Курт; Цагаракис, Маркос (1979), "Об изоморфизме двух алгоритмов: Ху / Такера и Гарсиа / Вахса", Les arbres en algèbre et en Programming (4ème Colloq., Лилль, 1979), Univ. Лилль I, Лилль, стр. 159–172, МИСТЕР  0554347
6. Карпинский, Марек; Лармор, Лоуренс Л.; Риттер, Войцех (1997), "Повторное рассмотрение правильности построения оптимальных алфавитных деревьев", Теоретическая информатика, 180 (1–2): 309–324, Дои:10.1016 / S0304-3975 (96) 00296-4, МИСТЕР  1453872

дальнейшее чтение

• Филлиатр, Жан-Кристоф (2008), «Функциональная реализация алгоритма Гарсиа-Вакса (функциональная жемчужина)», Материалы семинара ACM SIGPLAN по машинному обучению 2008 г. (ML '08), Нью-Йорк, Нью-Йорк, США: Ассоциация вычислительной техники, стр. 91–96, Дои:10.1145/1411304.1411317, ISBN  978-1-60558-062-3