Алгоритм слияния пакетов

Алгоритм слияния пакетов представляет собой алгоритм за время O (nL) для поиска оптимального кода Хаффмана с ограниченной длиной для заданного распределения в заданном алфавите размера n где ни одно кодовое слово не длиннее L. , Это жадный алгоритм и обобщение оригинального алгоритма Хаффмана . Слияние пакетов работает путем сведения проблемы построения кода к проблеме сборщика двоичных монет . ^[1]

Проблема коллекционера монет

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

Бинарная версия этой проблемы заключается в том, что все номиналы представляют собой степени двойки, то есть 1, 1/2, 1/4 и т. д. долларов.

Описание алгоритма слияния пакетов

Предположим, что наибольшая купюра равна 1 доллару и что N — целое число. (Алгоритм работает, даже если эти предположения не выполняются, путем тривиальных модификаций.) Коллекционер монет сначала разделяет свои монеты на списки, по одному на каждый номинал, отсортированные по нумизматической ценности. Затем он упаковывает монеты наименьшего номинала попарно, начиная с пары с наименьшей общей нумизматической ценностью. Если останется одна монета, это будет монета наивысшей нумизматической ценности этого номинала, и впредь она откладывается и игнорируется. Затем эти пакеты объединяются в список монет следующего наименьшего номинала, опять же в порядке нумизматической ценности. Затем элементы в этом списке упаковываются попарно и объединяются в следующий наименьший список и так далее.

Наконец, есть список предметов, каждый из которых представляет собой монету номиналом 1 доллар или упаковку, состоящую из двух или более монет меньшего размера, общий номинал которых составляет 1 доллар. Они также отсортированы по нумизматической ценности. Затем сборщик монет выбирает из них наименьшее значение N.

Обратите внимание, что время алгоритма линейно зависит от количества монет.

Сведение ограниченного по длине кодирования Хаффмана к задаче коллекционера монет

Пусть L — максимальная длина, которую разрешено иметь любому кодовому слову.Пусть p ₁ , …, p _n — частотысимволы алфавита, подлежащие кодированию. Сначала мы сортируем символы так, чтобы p _i ≤ p _{i +1} . Создайте L монет для каждого символа номиналом 2. ⁻¹, …, 2 ^{− Л}, каждый нумизматического значения p _i . Используйте алгоритм объединения пакетов, чтобы выбрать набор монет минимальной нумизматической ценности, общий номинал которых равен n - 1. Пусть h _i будет количеством монет нумизматической ценности p _i выбранных . Оптимальный код Хаффмана с ограниченной длиной будет кодировать символ i битовой строкой длины h _i . Канонический код Хаффмана можно легко построить с помощью простого восходящего жадного метода, учитывая, что hi _{известны, и} это может стать основой для быстрого сжатия данных . ^[2]

Улучшения производительности и обобщения

При таком сокращении алгоритм имеет O(nL) -время и O(nL) -пространство. Однако в оригинальной статье « Быстрый алгоритм для оптимальных кодов Хаффмана с ограниченной длиной » показано, как это можно улучшить до O(nL) -времени и O(n) -пространства. Идея состоит в том, чтобы запустить алгоритм в первый раз, сохранив достаточно данных только для того, чтобы можно было определить две эквивалентные подзадачи, сумма которых вдвое меньше исходной задачи. Это делается рекурсивно, в результате чего алгоритм занимает примерно вдвое больше времени, но требует только линейного пространства. ^[1]

В алгоритм слияния пакетов было внесено множество других улучшений, чтобы уменьшить мультипликативную константу и сделать ее быстрее в особых случаях, например, в тех случаях, когда проблемы с повторяющимися числами p _i . ^[3] Подход слияния пакетов также был адаптирован для решения смежных задач, таких как алфавитное кодирование . ^[4]

методы, основанные на теории графов, Было показано, что имеют лучшую асимптотическую сложность пространства, чем алгоритм слияния пакетов, но они не нашли такого большого практического применения.

Ссылки

^ Перейти обратно: ^а ^б Лармор, Лоуренс Л .; Хиршберг, Дэниел С. (1990). «Быстрый алгоритм для оптимальных кодов Хаффмана с ограниченной длиной» . Журнал Ассоциации вычислительной техники . 37 (3): 464–473. дои : 10.1145/79147.79150 . S2CID 11696729 .
^ Моффат, Алистер ; Терпин, Эндрю (октябрь 1997 г.). «О внедрении префиксных кодов минимальной избыточности». Транзакции IEEE в области коммуникаций . 45 (10): 1200–1207. дои : 10.1109/26.634683 .
^ Виттен, Ян Х .; Моффат, Алистер ; Белл, Тимоти Клинтон (1999). Управление гигабайтами: сжатие и индексирование документов и изображений (2-е изд.). Издательство Морган Кауфманн . ISBN 978-1-55860-570-1 . 1558605703.
^ Лармор, Лоуренс Л .; Пшитыцка, Тереза М. (1994). «Быстрый алгоритм построения оптимальных алфавитных двоичных деревьев с ограниченной высотой». SIAM Journal по вычислительной технике . 23 (6): 1283–1312. дои : 10.1137/s0097539792231167 .

Внешние ссылки

Баер, Майкл Б. (2006). «Двадцать (или около того) вопросов: D -арное префиксное кодирование с ограниченной длиной». arXiv : cs.IT/0602085 .
Моффат, Алистер ; Терпин, Эндрю; Катахайнен, Юрки (март 1995 г.). Экономичное построение оптимальных префиксных кодов . Конференция IEEE по сжатию данных. Сноуберд, Юта, США. дои : 10.1109/DCC.1995.515509 .
Реализация алгоритма слияния пакетов " [1] "
Быстрый энтропийный кодер, использующий алгоритм слияния пакетов [2]

[LaHi-1] Перейти обратно: ^а ^б Лармор, Лоуренс Л .; Хиршберг, Дэниел С. (1990). «Быстрый алгоритм для оптимальных кодов Хаффмана с ограниченной длиной» . Журнал Ассоциации вычислительной техники . 37 (3): 464–473. дои : 10.1145/79147.79150 . S2CID 11696729 .

[MoTu-2] Моффат, Алистер ; Терпин, Эндрю (октябрь 1997 г.). «О внедрении префиксных кодов минимальной избыточности». Транзакции IEEE в области коммуникаций . 45 (10): 1200–1207. дои : 10.1109/26.634683 .

[MG-3] Виттен, Ян Х .; Моффат, Алистер ; Белл, Тимоти Клинтон (1999). Управление гигабайтами: сжатие и индексирование документов и изображений (2-е изд.). Издательство Морган Кауфманн . ISBN 978-1-55860-570-1 . 1558605703.

[LaPr-4] Лармор, Лоуренс Л .; Пшитыцка, Тереза М. (1994). «Быстрый алгоритм построения оптимальных алфавитных двоичных деревьев с ограниченной высотой». SIAM Journal по вычислительной технике . 23 (6): 1283–1312. дои : 10.1137/s0097539792231167 .

[1]

[2]

[3]

[4]