Recursive indexing: Difference between revisions

Revision as of 21:29, 28 March 2014

Revision as of 00:41, 15 May 2014

Line 8:

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, and continuing recursively till the difference falls in the range of the set.

Recursive indexing with a 2 -letter alphabet is called [[Unaryunary code]].

==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 [0–0 – ''S''_max).

===Example===

Let set ''S'' = [0 1 2 3 4 … 10], be aan 11 -element set, and we have to recursively index the value N=49.

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

So the values are 10 (''N'' =49–10 49 – 10 =  39), 10 (''N'' =39–10 39 – 10 = 29), 10 (''N'' =29–10 29 – 10 = 19), 10 (''N'' =19–10 19 – 10 = 9), 9.

Hence the recursively indexed sequence for ''N'' = 49 with set ''S'', is  10, 10, 10, 10, 9.

==Decoding==

Line 26:

===Example===

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

==Uses==

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

==References==