再帰インデックス

再帰インデックスは、比較的小さなセットのメンバーを使用して大きな数値を表すために使用されるアルゴリズムです。

再帰インデックスは、数値からアルファベット セットの最大値を抽出した後、数値の連続する差を書き込み、差がセットの範囲内に収まるまで再帰的に続けます。

2 文字のアルファベットを使用した再帰インデックスは、単項コードと呼ばれます。

数値Nをエンコードするには、このセットの最大要素 ( S _max ) をNから減らし続け、そのような差ごとにS max を出力し、数値が半分閉じた半分開いた範囲 [0 – S _max )にあるときに停止します 。

S = [0 1 2 3 4 … 10]を 11要素の集合とし、値N=49を再帰的にインデックス付けする必要があります。

この方法では、49 から 10 を減算し、その差が 0 ～ 10 の範囲になるまで繰り返します。

値は、10 ( N  = 49 – 10 = 39)、10 ( N  = 39 – 10 = 29)、10 ( N  = 29 – 10 = 19)、10 ( N = 19 – 10 = 9)、9 です。 セットSを使用したN = 49 の再帰インデックス付きシーケンスは、10、10、10、10、9 です。

インデックス値の合計を計算します。

上記の例をデコードすると、10 + 10 + 10 + 10 + 9 = 49 になります。

この手法は、アルファベットのサイズが許すよりも長いランをエンコードするために、 ランレングスエンコードシステムで最もよく使用されます。

• Khalid Sayood、『データ圧縮入門』第 3 版、Morgan Kaufmann。