Сжатие целочисленных последовательностей и множеств: различия между версиями

Предположим, что необходимо представить сообщение M = hs1;s2... sni, состоящее из и = jMj символов, в котором каждый символ si представляет собой целое число в диапазоне 1 < si < U, верхняя граница U которого может быть или не быть известна и может быть или не быть конечной. Сообщения в такой форме часто встречаются на выходе некоторых этапов моделирования в системах сжатия данных. Задача заключается в представлении сообщения на базе бинарного выходного алфавита {0, 1} при помощи минимально возможного количества выходных бит. Специальный случай задачи имеет место, когда элементы сообщения являются строго возрастающими, т.е. si < si+1. В этом случае можно считать, что сообщение M определяет подмножество {1, 2, ..., U}. Примерами такого использования могут быть хранение множеств IP-адресов или кодов товаров, а также регистрация гиперссылок-адресов в графовом представлении сети Интернет.

Основным ограничением в этой задаче может оказаться невозможность предположить, что n > U. Иначе говоря, необходимо предполагать, что сообщение M оказывается слишком коротким (относительно совокупности U), чтобы гарантировать вычисление относящегося к M кода. Тем не менее, в случае строгого возрастания элементов гарантированно выполняется соотношение n < U. Далее в качестве примера будет использоваться сообщение M1 = h1, 3, 1, 1, 1, 10, 8, 2, 1, 1i. Заметим, что любое сообщение M может быть преобразовано в другое сообщение M0 на базе алфавита U0 = Un при помощи префиксных сумм. Это преобразование является обратимым, обратная операция носит название «нахождения разностей».