Recursive indexing
 | This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. (June 2020) |
Recursive indexing is an algorithm used to represent large numeric values using members of a relatively small set.
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.
Encoding
[edit]To encode a number N, keep reducing the maximum element of this set (Smax) from N and output Smax for each such difference, stopping when the number lies in the half closed half open range [0 – Smax).
Example
[edit]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
[edit]Compute the sum of the index values.
Example
[edit]Decoding the above example involves 10 + 10 + 10 + 10 + 9 = 49.
Uses
[edit]This technique is most commonly used in run-length encoding systems to encode longer runs than the alphabet sizes permit.
References
[edit]- Khalid Sayood, Introduction to Data Compression 3rd ed, Morgan Kaufmann.