Рекурсивная индексация

Рекурсивная индексация — это алгоритм, используемый для представления больших числовых значений с использованием членов относительно небольшого набора .

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

Рекурсивная индексация с помощью двухбуквенного алфавита называется унарным кодом .

Кодирование

Чтобы закодировать число N , продолжайте уменьшать максимальный элемент этого набора ( S _max ) от N и выводить S max для каждой такой разницы, останавливаясь, когда число находится в полузакрытом полуоткрытом положении.диапазон [0 – S _макс .).

Пример

Пусть S = [0 1 2 3 4 … 10] — набор из 11 элементов, и нам нужно рекурсивно индексировать значение N=49.

Согласно этому методу, вычитайте 10 из 49 и повторяйте цикл до тех пор, пока разница не станет числом в диапазоне 0–10.

Значения: 10 ( N = 49 – 10 = 39), 10 ( N = 39 – 10 = 29), 10 ( N = 29 – 10 = 19), 10 ( N = 19 – 10 = 9), 9. рекурсивно индексированная последовательность для N = 49 с набором S равна 10, 10, 10, 10, 9.

Декодирование

Вычислите сумму значений индекса.

Пример

Расшифровка приведенного выше примера включает в себя 10 + 10 + 10 + 10 + 9 = 49.

Использование

Этот метод чаще всего используется в системах кодирования длин серий для кодирования более длинных серий, чем позволяют размеры алфавита.

Ссылки

• Халид Саюд, Введение в сжатие данных, 3-е изд., Морган Кауфманн .