Recursive indexing

When number (generally large number) is represented in a finite alphabet set, and itcannot be represented by just one member of the set, Recursive Indexing is used.

Recursive Indexing itself is a method to write the successive differences of the number after extracting the maximum value of the alphabet set from the number, andcontinuing recursively till the difference falls in the range of the set.

Recursive Indexing with a 2 letter alphabet is called Unary code.

Encoding

To encode a number N, keep reducing the maximum element of this set (Smax) from Nand output Smax for each such difference, stopping when the number lies in the half closed half openrange [0-Smax).

Example

Let set S= [0 1 2 3 4 ... 10] , be a 11 element set, and we have to recursivelyindex the value N=49.

According to this method, we need to keep removing 10 from 49, and keep proceedingtill we reach a number in the 0-10 range.

So the values are 10 (N=49-10 = 39), 10 (N=39-10=29), 10 (N=29-10=19), 10 (N=19-10=9), 9.Hence the recursively indexed sequence for N=49 with set S, is 10,10,10,10,9.

Decoding

Keep adding all the elements of the index, stopping when the index value is between (inclusive of ends)the least & penultimate elements of the set S.

Example

Continuing from above example we have 10+10+10+10+9 = 49.

Uses

This technique is most commonly used in Run Length Encoding systems to encode longer runsthan the alphabet sizes permit.

References

Khalid Sayood, Data Compression 3rd ed, Morgan Kaufman.