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

Основным ограничением в этой задаче может оказаться невозможность предположить, что <math>n \gg U \;</math>. Иначе говоря, необходимо предполагать, что сообщение M оказывается слишком коротким (относительно совокупности U), чтобы гарантировать вычисление относящегося к M кода. Тем не менее, в случае строгого возрастания элементов гарантированно выполняется соотношение <math>n \le U \;</math>. Далее в качестве примера будет использоваться сообщение <math>M_1 = \langle 1, 3, 1, 1, 1, 10, 8, 2, 1, 1 \rangle \;</math>. Заметим, что любое сообщение M может быть преобразовано в другое сообщение M' на базе алфавита U' = Un при помощи префиксных сумм. Это преобразование является обратимым, обратная операция носит название «нахождения пробелов».