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

Предположим, что необходимо представить сообщение <math>M = \langle s_1, s_2, ..., s_n \rangle</math>, состоящее из n = |M| символов, в котором каждый символ <math>s_i \;</math> представляет собой целое число в диапазоне <math>1 \le s_i \le U \;</math>, верхняя граница U которого может быть или не быть известна и может быть или не быть конечной. Сообщения в такой форме часто встречаются на выходе некоторых этапов моделирования в системах сжатия данных. Задача заключается в представлении сообщения на базе бинарного выходного алфавита {0, 1} при помощи минимально возможного количества выходных бит. Специальный случай задачи имеет место, когда элементы сообщения являются строго возрастающими, т. е. <math>s_i < s_{i+1} \;</math>. В этом случае можно считать, что сообщение M определяет подмножество {1, 2, ..., U}. Примерами такого использования могут быть хранение множеств IP-адресов или кодов товаров, а также регистрация гиперссылок-адресов в графовом представлении сети Интернет.

Важный аспект интерполяционного кода заключается в том, что могут возникнуть ситуации, в которых длина кодового слова равна 0, что становится понятным из равенства lo' = hi'. В этом случае нет необходимости в выдаче битов, поскольку в обозначенный диапазон попадает только одно значение, и декодер может вычислить его. Четыре символа из последовательности <math>M_2 \;</math> могут успешно воспользоваться этой возможностью. Благодаря этому свойству интерполяционное кодирование особенно эффективно в случаях, когда подмножества содержат кластеры последовательных элементов, либо локализованные области подмножеств имеют высокую плотность. В предельном случае, если подмножество содержит все элементы интервала, для его кодировки вообще не требуется ни одного бита при известном значении U. В более общем случае плотные множества могут быть представлены с использованием мене чем одного бита на символ.