2009-09-06

今日のInterpolative codingの話が面白かったのと復号の部分のコードが必ずしも自明ではないかと思ったのでメモ。

Interpolative codingは長さと出てくる値の最小値、最大値が分かっている狭義単調増加な自然数のリストを圧縮する方法である。
ここで最大値とはリストの最大値ではなく、たとえば転置リストであれば最大の文書IDなど圧縮を行う際に出てきうる値の最大値である。

Interpolative codingの基本的な考え方としてはたとえば1から20までの数が表れるとわかっておりかつリストの長さが20であるということが分かっていれば、なにもデータがなくてもリストが[1..20]であるとわかるということに基づいている。

ここでは例で説明する。長さ7のリスト<7;3,8,9,11,12,13,17>を圧縮することを考える。またここで出てくる数の最大値は20であることが分かっているとする。

いま3を圧縮する際に次の値が8と分かっていれば出てくる値が1..7までの範囲であることがわかり3bitで表現できる。次に3番目のポインタ9を圧縮するときに2番目のポインタが8、4番目のポインタが11とわかっていれば出てくる値は9..10であることがわかり1bitで表現できる。また2番目のポインタ8は4番目のポインタが11とわかれば2..9の範囲にあることが分かる(ここでリストが狭義単調増加のため、3番目のポインタの値が10以下であるということを利用している)、このとき3bitで圧縮できる。以下同様にして圧縮を行っていくと全体を17bitで圧縮できることが分かる。これはb=2のときのGolomb codeの18bitより1bit短くなっている。

この例だけでは正直わかりづらいと思うので以下に示すコードの流れを紙か何かに書いてシミュレーションをすることをお勧めする。

符号化のコードは以下のようになる。符号化したビット列はencodeResultの中に入れられる。

  static private int lg(int x){
    return 32 - Integer.numberOfLeadingZeros(x - 1);
  }

  static private void binary_encode(int x , int low , int high , List<Boolean> encodeResult){
    int range = high - low + 1;
    int bnum = lg(range);
    int enc = x - low;
    for(int i = bnum - 1 ; i >= 0 ; i--){
      if((enc & (1 << i)) == 0){
        encodeResult.add(false);
      }else{
        encodeResult.add(true);        
      }
    }
  }
  //encode L[left..right) and assert lo <= L[i] <= hi forall i where left <= i < right
  public static void interpolativeEncode(
      int L[], int f, 
      int lo, int hi,
      int left , int right,
      List<Boolean> encodeResult) {
    if(f == 0){
      return ;
    }else if(f == 1){
      binary_encode(L[left], lo, hi, encodeResult);
      return ;
    }
    int h = f / 2;
    int m = L[left + h];
    int f1 = h;
    int f2 = f - h - 1;
    binary_encode(m, lo + f1, hi - f2, encodeResult);
    interpolativeEncode(L, f1, lo, m - 1, left , left + h ,encodeResult);
    interpolativeEncode(L, f2, m + 1, hi, left + h + 1 , right , encodeResult);
  }

次に復号化であるが基本的にはencodeのときと同じコードを書いて、binary_encodeでencodeしている値をdecodeで取ってくるという操作を行えばよい。

  static private int binary_decode(int low , int high , Iterator<Boolean> inputIterator){
    int range = high - low + 1;
    int bnum = lg(range);
    int dec = 0;
    for(int i = 0 ; i < bnum ; i++){
      boolean b = inputIterator.next();
      dec = dec * 2 + (b ? 1 : 0);
    }
    return low + dec;
  }

  public static void interpolativeDecode(
      int[] L, int f,
      int lo , int hi,
      int left , int right,
      Iterator<Boolean> inputStream
  ){
    if(f == 0){
      return ;
    }else if(f == 1){
      int dec = binary_decode(lo, hi, inputStream);
      L[left] = dec;
      return ;
    }
    int h = f / 2;
    int f1 = h;
    int f2 = f - h - 1;
    int m = binary_decode(lo + f1, hi - f2, inputStream);
    L[left + h] = m;
    interpolativeDecode(L, f1, lo, m - 1, left , left + h, inputStream);
    interpolativeDecode(L, f2, m + 1, hi, left + h + 1, right, inputStream);
  }

実行例

  public static void main(String[] args) {
    int L[] = {3 , 8 , 9 , 11 , 12 , 13 , 17};
    List<Boolean> eres = new ArrayList<Boolean>();
    interpolativeEncode(L , L.length , 1, 20, 0 , L.length, eres);
    System.err.println(Arrays.toString(L));
    System.err.println(eres.size());
    int Ldec[] = new int[L.length];
    interpolativeDecode(Ldec, L.length, 1, 20, 0, L.length, eres.iterator());
    System.err.println(Arrays.toString(Ldec));
  }
/* 出力
[3, 8, 9, 11, 12, 13, 17]
17
[3, 8, 9, 11, 12, 13, 17]
*/