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

В алгоритм слияния пакетов является О (нЛ)-временной алгоритм поиска оптимального ограниченный по длине код Хаффмана для данного распределения по заданному алфавиту размера п, где нет кодовое слово длиннее, чем L. Это жадный алгоритм, и обобщение Оригинальный алгоритм Хаффмана. Слияние пакетов сводит проблему построения кода к двоичному проблема коллекционера монет.[1]

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

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

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

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

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

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

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

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

Позволять L - максимальная длина, разрешенная для любого кодового слова. п1, …, пп быть частотами символов алфавита, которые нужно кодировать. Сначала сортируем символы так, чтобы пя ≤ пя+1. Создавать L монеты за каждый символ достоинством 2−1, …, 2−L, каждое из нумизматических ценностей пя. Используйте алгоритм объединения пакетов, чтобы выбрать набор монет с минимальной нумизматической ценностью, общий номинал которых п - 1. Пусть чася быть количеством монет нумизматической ценности пя выбрано. Оптимальный код Хаффмана с ограниченной длиной будет кодировать символ я с битовой строкой длины чася. В канонический код Хаффмана легко построить простым жадным методом снизу вверх, учитывая, что чася известны, и это может быть основанием для быстрого Сжатие данных.[2]

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

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

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

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

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

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

внешняя ссылка

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