Recursive indexing: Difference between revisions

Revision as of 20:46, 11 January 2007

Latest revision as of 15:40, 16 October 2023

(17 intermediate revisions by 17 users not shown)

Line 1:

{{no footnotes|date=June 2020}}

{{Orphan|November 2006}}

When number (generally large number) is represented in a finite alphabet set, and it

cannot be represented by just one member of the set, Recursive Indexing is used.

'''Recursive indexing''' is an [[algorithm]] used to represent large numeric values using members of a relatively small [[Set (mathematics)|set]].

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 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]].

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

==Encoding==

To encode a number ''N'', keep reducing the maximum element of this set (Smax''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 – ''S''_max).

and output Smax for each such difference, stopping when the number lies in the half closed half open

range [0-Smax).

=== 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.

index the value N=49.

According to this method, we need to keep removingsubtract 10 from 49, and keepiterate until the difference is a number in the 0–10 proceedingrange.

till we reach a number in the 0-10 range.

So theThe 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.

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

==Decoding==

Compute the sum of the index values.

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 ===

ContinuingDecoding fromthe above example we haveinvolves  10 + 10 + 10 + 10 + 9  =  49.

==Uses==

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

than the alphabet sizes permit.

==References==

* Khalid Sayood, Introduction to Data Compression 3rd ed, [[Morgan KaufmanKaufmann]].

==See also==

[[Category:Coding theory]]