Recursive indexing

<h2 id="encoding">Encoding</h2>
<p>To encode a number <i>N</i>, keep reducing the maximum element of this set (<i>S</i>max) from <i>N</i> and output <i>S</i>max for each such difference, stopping when the number lies in the half closed half open
range [0 – <i>S</i>max).
</p>
<h3>Example</h3>
<p>Let <i>S</i> = [0 1 2 3 4 … 10], be an 11-element set, and we have to recursively index the value N=49.
</p><p>According to this method, subtract 10 from 49 and iterate until the difference is a number in the 0–10 range.
</p><p>The values are 10 (<i>N</i> = 49 – 10 = 39), 10 (<i>N</i> = 39 – 10 = 29), 10 (<i>N</i> = 29 – 10 = 19), 10 (<i>N</i> = 19 – 10 = 9), 9. The recursively indexed sequence for <i>N</i> = 49 with set <i>S</i>, is 10, 10, 10, 10, 9.
</p>
<h2 id="decoding">Decoding</h2>
<p>Compute the sum of the index values.
</p>
<h3>Example</h3>
<p>Decoding the above example involves  10 + 10 + 10 + 10 + 9 = 49.
</p>
<h2 id="uses">Uses</h2>
<p>This technique is most commonly used in <a href="/facts/Run-length_encoding/3k6x9afM">run-length encoding</a> systems to encode longer runs than the alphabet sizes permit.
</p>

<ul><li>Khalid Sayood, Introduction to Data Compression 3rd ed, <a href="/facts/Morgan_Kaufmann/HfefrWju">Morgan Kaufmann</a>.</li></ul>

Recursive indexing open-in-new

Recursive indexing