Алгоритм слияния пакетов — это алгоритм с временем O (nL) для поиска оптимального кода Хаффмана с ограниченной длиной для заданного распределения на заданном алфавите размера n , где ни одно кодовое слово не длиннее L. Это жадный алгоритм и обобщение исходного алгоритма Хаффмана . Алгоритм слияния пакетов работает, сводя задачу построения кода к задаче коллекционера двоичных монет . [1]
Предположим, что у коллекционера монет есть несколько монет разного номинала, каждая из которых имеет нумизматическую ценность, не связанную с ее номиналом. У коллекционера монет закончились деньги, и ему нужно использовать часть своей коллекции монет, чтобы купить что-то стоимостью N . Он хочет выбрать подмножество монет из своей коллекции минимальной нумизматической ценности, общая сумма номиналов которых составляет N .
Двоичная версия этой задачи заключается в том, что все номиналы являются степенями числа 2, то есть 1, 1/2, 1/4 и т. д. доллара.
Предположим, что самый большой номинал — 1 доллар, а N — целое число. (Алгоритм работает, даже если эти предположения не выполняются, с помощью тривиальных модификаций.) Сначала коллекционер монет разделяет свои монеты на списки, по одному для каждого номинала, отсортированные по нумизматической ценности. Затем он упаковывает монеты наименьшего номинала в пары, начиная с пары с наименьшей общей нумизматической ценностью. Если остается одна монета, это будет монета наибольшей нумизматической ценности этого номинала, и она откладывается в сторону и игнорируется в дальнейшем. Затем эти пакеты объединяются в список монет следующего наименьшего номинала, снова в порядке нумизматической ценности. Затем элементы в этом списке упаковываются в пары и объединяются в следующий наименьший список и так далее.
Наконец, есть список предметов, каждый из которых представляет собой монету в 1 доллар или пакет, состоящий из двух или более монет меньшего номинала, общий номинал которых составляет 1 доллар. Они также сортируются в порядке нумизматической ценности. Затем коллекционер монет выбирает наименьшую ценность N из них.
Обратите внимание, что время работы алгоритма линейно зависит от количества монет.
Пусть L будет максимальной длиной, которую разрешено иметь любому кодовому слову. Пусть p 1 , …, p n будут частотами символов алфавита, которые нужно закодировать. Сначала мы сортируем символы так, чтобы p i ≤ p i +1 . Создаем L монет для каждого символа, номиналами 2 −1 , …, 2 − L , каждая из которых имеет нумизматическую ценность p i . Используйте алгоритм слияния пакетов для выбора набора монет минимальной нумизматической ценности, общая сумма номиналов которых составляет n − 1. Пусть h i будет количеством выбранных монет нумизматической ценности p i . Оптимальный код Хаффмана с ограниченной длиной будет кодировать символ i битовой строкой длины h i . Канонический код Хаффмана можно легко построить простым жадным методом снизу вверх, учитывая, что h i известны, и это может стать основой для быстрого сжатия данных . [2]
При таком сокращении алгоритм занимает O(nL) -время и O(nL) -пространство. Однако в оригинальной статье " Быстрый алгоритм для оптимальных кодов Хаффмана с ограниченной длиной " показано, как это можно улучшить до O(nL) -времени и O(n) -пространства. Идея состоит в том, чтобы запустить алгоритм в первый раз, сохранив только достаточно данных, чтобы определить две эквивалентные подзадачи, которые в сумме составляют половину размера исходной задачи. Это делается рекурсивно, в результате чего получается алгоритм, который занимает примерно вдвое больше времени, но требует только линейного пространства. [1]
В алгоритм слияния пакетов было внесено множество других улучшений для уменьшения мультипликативной константы и ускорения его работы в особых случаях, например, в задачах с повторяющимися p i . [3] Подход слияния пакетов также был адаптирован к смежным задачам, таким как алфавитное кодирование . [4]
Было показано, что методы, использующие теорию графов, имеют лучшую асимптотическую пространственную сложность, чем алгоритм слияния пакетов, но они не нашли столь широкого практического применения.