Алгоритм Гарсии – Вакса

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

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

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

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

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

Алгоритм

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

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

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

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

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

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

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

История

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

Ссылки

^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я Кнут, Дональд Э. (1998), «Алгоритм G (алгоритм Гарсиа-Вакса для оптимальных двоичных деревьев)», Искусство компьютерного программирования , Vol. 3: Сортировка и поиск (2-е изд.), Аддисон – Уэсли, стр. 451–453 . См. также «История и библиография», стр. 453–454.
^ Jump up to: ^а ^б Кингстон, Джеффри Х. (1988), «Новое доказательство алгоритма Гарсиа-Вакса», Journal of Algorithms , 9 (1): 129–136, doi : 10.1016/0196-6774(88)90009-0 , MR 0925602
^ Гарсия, Адриано М .; Вакс, Мишель Л. (1977), «Новый алгоритм для бинарных деревьев с минимальной стоимостью», SIAM Journal on Computing , 6 (4): 622–642, doi : 10.1137/0206045 , MR 0520738
^ Ху, ТК ; Такер, AC (1971), «Оптимальные компьютерные деревья поиска и алфавитные коды переменной длины», SIAM Journal on Applied Mathematics , 21 (4): 514–532, doi : 10.1137/0121057 , MR 0304063
^ Мельхорн, Курт ; Цагаракис, Маркос (1979), «Об изоморфизме двух алгоритмов: Ху/Такера и Гарсиа/Вакса», Деревья в алгебре и программировании (4-й семинар, Лилль, 1979) , Univ. Лилль I, Лилль, стр. 159–172, МР 0554347
^ Карпински, Марек ; Лармор, Лоуренс Л .; Риттер, Войцех (1997), «Возврат к правильности построения оптимальных алфавитных деревьев», Theoretical Computer Science , 180 (1–2): 309–324, doi : 10.1016/S0304-3975(96)00296-4 , MR 1453872

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

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

[k-1] Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я Кнут, Дональд Э. (1998), «Алгоритм G (алгоритм Гарсиа-Вакса для оптимальных двоичных деревьев)», Искусство компьютерного программирования , Vol. 3: Сортировка и поиск (2-е изд.), Аддисон – Уэсли, стр. 451–453 . См. также «История и библиография», стр. 453–454.

[kingston-2] Jump up to: ^а ^б Кингстон, Джеффри Х. (1988), «Новое доказательство алгоритма Гарсиа-Вакса», Journal of Algorithms , 9 (1): 129–136, doi : 10.1016/0196-6774(88)90009-0 , MR 0925602

[gw-3] Гарсия, Адриано М .; Вакс, Мишель Л. (1977), «Новый алгоритм для бинарных деревьев с минимальной стоимостью», SIAM Journal on Computing , 6 (4): 622–642, doi : 10.1137/0206045 , MR 0520738

[ht-4] Ху, ТК ; Такер, AC (1971), «Оптимальные компьютерные деревья поиска и алфавитные коды переменной длины», SIAM Journal on Applied Mathematics , 21 (4): 514–532, doi : 10.1137/0121057 , MR 0304063

[mt-5] Мельхорн, Курт ; Цагаракис, Маркос (1979), «Об изоморфизме двух алгоритмов: Ху/Такера и Гарсиа/Вакса», Деревья в алгебре и программировании (4-й семинар, Лилль, 1979) , Univ. Лилль I, Лилль, стр. 159–172, МР 0554347

[klr-6] Карпински, Марек ; Лармор, Лоуренс Л .; Риттер, Войцех (1997), «Возврат к правильности построения оптимальных алфавитных деревьев», Theoretical Computer Science , 180 (1–2): 309–324, doi : 10.1016/S0304-3975(96)00296-4 , MR 1453872

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]