{{no footnotes, date=June 2020 Recursive indexing is an

algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...

used to represent large numberic values using members of a relatively small

set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...

. Recursive indexing writes the successive differences of the number after extracting the maximum value of the alphabet set from the number, and continuing recursively till the difference falls in the range of the set. Recursive indexing with a 2-letter alphabet is called

unary code Unary may refer to: *Unary numeral system, the simplest numeral system to represent natural numbers *Unary function, a function that takes one argument; in computer science, a unary operator is a subset of unary function *Unary operation, a kind of ...

Encoding

To encode a number ''N'', keep reducing the maximum element of this set (''S''_max) from ''N'' and output ''S''max for each such difference, stopping when the number lies in the half closed half open range – ''S''_max).

Example

Let ''S'' = [0 1 2 3 4 … 10 be an 11-element set, and we have to recursively index the value N=49. According to this method, subtract 10 from 49 and iterate until the difference is a number in the 0–10 range. The values are 10 (''N'' = 49 – 10 = 39), 10 (''N'' = 39 – 10 = 29), 10 (''N'' = 29 – 10 = 19), 10 (''N'' = 19 – 10 = 9), 9. The recursively indexed sequence for ''N'' = 49 with set ''S'', is 10, 10, 10, 10, 9.

Decoding

Compute the sum of the index values.

Example

Decoding the above example involves 10 + 10 + 10 + 10 + 9 = 49.

Uses

This technique is most commonly used in run-length encoding systems to encode longer runs than the alphabet sizes permit.

References

* Khalid Sayood, Introduction to Data Compression 3rd ed, Morgan Kaufmann. Coding theory Data compression Lossless compression algorithms