LZ77

LZ77 という圧縮アルゴリズムがあります。Lempel と Ziv という人が１９７７年に発表したアルゴリズムなのでこのように呼ばれています。辞書式圧縮とも呼ばれます。

圧縮対象のデータを先頭から順番に見ていき、手前に存在する部分データと一致する部分のポインタと次の不一致文字として符号化することで圧縮を行うアルゴリズムです。一致する部分へのポインタは一致しているデータの長さと現在の位置からの距離として表現します。

比較的簡単で、割と圧縮率の良いアルゴリズムです。

実装例

package sample.compress;

import java.io.ByteArrayOutputStream;

public class LZ77 {

  private final static int LENGTH_SIZE = 8;
  private final static int DISTANCE_SIZE = 12;

  private final static int LOOKAHEAD_SIZE = (1 << LENGTH_SIZE) - 1;
  private final static int DICTIONARY_SIZE = 1 << DISTANCE_SIZE;

  public static String encode(byte[] input) {
    StringBuilder result = new StringBuilder();
    int slidePosition = 0;
    while (slidePosition < input.length) {
      int length = 0, distance = 0;
      for (int i = 0; i < Math.min(slidePosition, DICTIONARY_SIZE); i++) {
        int matchLength = matchLength(input, slidePosition, i);
        if (length < matchLength) {
          length = matchLength;
          distance = i;
        }
      }
      slidePosition += length;

      result.append(toBits(length, LENGTH_SIZE));
      result.append(toBits(distance, DISTANCE_SIZE));

      if (slidePosition < input.length) {
        byte nextOctet = input[slidePosition++];
        result.append(toBits(nextOctet, Byte.SIZE));
      }
    }
    return result.toString();
  }

  private static int matchLength(byte[] input, int slidePosition,
                                                 int distance) {
    int laSize = Math.min(input.length - slidePosition,
                                       LOOKAHEAD_SIZE);
    int length;
    for (length = 0; length < Math.min(laSize, distance + 1);
                                                  length++) {
      if (input[slidePosition - distance + length - 1] 
         != input[slidePosition+ length]) {
        return length;
      }
    }
    return length;
  }

  private static String toBits(int val, int width) {
    return width == 0 ? "" : toBits(val >>> 1, width - 1) + (val & 1);
  }

  public static byte[] decode(String input) {
    ByteArrayOutputStream result = new ByteArrayOutputStream();
    byte[] slide = new byte[DICTIONARY_SIZE + LOOKAHEAD_SIZE + 1];
    int slidePosition = 0;
    while (true) {
      if (LENGTH_SIZE + DISTANCE_SIZE <= input.length()) {
        String lengthBits = input.substring(0, LENGTH_SIZE);
        int length = Integer.parseInt(lengthBits, 2);
        String distanceBits = input.substring(LENGTH_SIZE, LENGTH_SIZE
            + DISTANCE_SIZE);
        int distance = Integer.parseInt(distanceBits, 2);
        input = input.substring(LENGTH_SIZE + DISTANCE_SIZE);
        if (length > 0) {
          System.arraycopy(slide, slidePosition - distance - 1,
                  slide, slidePosition, length);

        }
        slidePosition += length;
      } else {
        break;
      }
      if (Byte.SIZE <= input.length()) {
        String nextOctetBits = input.substring(0, Byte.SIZE);
        byte nextOctet = (byte) Integer.parseInt(nextOctetBits, 2);
        input = input.substring(Byte.SIZE);
        slide[slidePosition++] = nextOctet;
      } else {
        break;
      }
      if (slidePosition > DICTIONARY_SIZE) {
        result.write(slide, 0, slidePosition - DICTIONARY_SIZE);
        System.arraycopy(slide, slidePosition - DICTIONARY_SIZE, slide,
            0, DICTIONARY_SIZE);
        slidePosition = DICTIONARY_SIZE;
      }
    }
    result.write(slide, 0, slidePosition);
    return result.toByteArray();
  }
}

2010年10月26日 | カテゴリー：アルゴリズム