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

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

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

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

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

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

Алгоритм

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

В целом алгоритм состоит из трех фаз: [1]

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

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

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

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

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

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

История

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

Ссылки

  1. ^ abcdefghi Кнут, Дональд Э. (1998), «Алгоритм G (алгоритм Гарсиа–Вакса для оптимальных бинарных деревьев)», Искусство программирования , т. 3: Сортировка и поиск (2-е изд.), Эддисон–Уэсли, стр. 451–453, См. также Историю и библиографию, стр. 453–454.
  2. ^ ab Kingston, Jeffrey H. (1988), «Новое доказательство алгоритма Гарсии–Вакса», Journal of Algorithms , 9 (1): 129–136, doi :10.1016/0196-6774(88)90009-0, MR  0925602
  3. ^ Гарсия, Адриано М.; Вакс , Мишель Л. (1977), «Новый алгоритм для бинарных деревьев минимальной стоимости», SIAM Journal on Computing , 6 (4): 622–642, doi :10.1137/0206045, MR  0520738
  4. ^ Ху, TC ; Такер, AC (1971), «Оптимальные деревья компьютерного поиска и алфавитные коды переменной длины», SIAM Journal on Applied Mathematics , 21 (4): 514–532, doi :10.1137/0121057, MR  0304063
  5. ^ Мельхорн, Курт ; Цагаракис, Маркос (1979), «Об изоморфизме двух алгоритмов: Ху/Такера и Гарсиа/Вакса», Les arbres en algèbre et en programmation (4ème Colloq., Lille, 1979) , Univ. Лилль I, Лилль, стр. 159–172, MR  0554347.
  6. ^ Карпински, Марек ; Лармор, Лоуренс Л .; Риттер, Войцех (1997), «Повторный взгляд на правильность построения оптимальных алфавитных деревьев», Теоретическая информатика , 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
Взято с "https://en.wikipedia.org/w/index.php?title=Алгоритм_Гарсии–Вакса&oldid=1187704784"