前回はLZ77という圧縮アルゴリズムを実装してみました。今回はLZ77を改良したLZSSというアルゴリズムを実装してみます。

LZ77ではすでに処理された文字列の中に一致する部分があれば、そこを指すポインタ(長さと位置)を生成し、次にその後の一文字を出力する、ということを繰り返す形式でした。 この形式だと、すでに処理された文字列の中に一致する部分がなくても、ポインタを置かなければなりませんでした。 LZSSでは最初の1bitでその後に続くビット列がポインタであるか、文字であるかを表すように改良しています。また、すでに処理された文字列の中に一致する部分があっても、それをポインタで出力するよりも、文字データ出力するほうが効率が良い場合には文字として出力するようにすることでさらに効率が良くなっています。

sample/compress/LZSS.java

package sample.compress;

import java.io.ByteArrayOutputStream;
import java.nio.ByteBuffer;

public class LZSS {

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

  private static final int LOOKAHEAD_SIZE_MAX = (1 << LENGTH_SIZE) - 1;
  private static final int DICTIONARY_SIZE_MAX = 1 << DISTANCE_SIZE;

  public static String encode(byte[] data) {
    ByteBuffer buf = ByteBuffer.wrap(data).asReadOnlyBuffer();
    StringBuilder sb = new StringBuilder();
    while (buf.hasRemaining()) {
      int length = 0, distance = 0;
      int dictSize = Math.min(buf.position(), DICTIONARY_SIZE_MAX);
      for (int i = 0; i < dictSize; i++) {
        int j;
        int lkahSize = Math.min(buf.remaining(), LOOKAHEAD_SIZE_MAX);
        for (j = 0; j < i + 1 && j < lkahSize; j++) {
          int dictDatum = buf.get(buf.position() - i + j - 1);
          int lkahDatum = buf.get(buf.position() + j);
          if (dictDatum != lkahDatum) {
            break;
          }
        }
        if (length < j) {
          length = j;
          distance = i;
        }
      }
      if (length * (1 + Byte.SIZE) < 1 + LENGTH_SIZE + DISTANCE_SIZE) {
        sb.append("0").append(toBits(Byte.SIZE, buf.get()));
      } else {
        sb.append("1").append(toBits(LENGTH_SIZE, length)).append(
            toBits(DISTANCE_SIZE, distance));
        buf.position(buf.position() + length);
      }
    }
    return sb.toString();
  }

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

  public static byte[] decode(String code) {
    ByteArrayOutputStream baos = new ByteArrayOutputStream();
    byte[] slide = new byte[DICTIONARY_SIZE_MAX + LOOKAHEAD_SIZE_MAX];
    int off = 0;
    while (!code.isEmpty()) {
      if (code.startsWith("0")) {
        slide[off++] = (byte) Integer.parseInt(code.substring(1,
            1 + Byte.SIZE), 2);
        code = code.substring(1 + Byte.SIZE);
      } else {
        int length = Integer.parseInt(code
            .substring(1, 1 + LENGTH_SIZE), 2);
        int distance = Integer.parseInt(code.substring(1 + LENGTH_SIZE,
            1 + LENGTH_SIZE + DISTANCE_SIZE), 2);
        try {
          System.arraycopy(slide, off - distance - 1, slide, off,
              length);
        } catch (Exception e) {
          e.printStackTrace();
        }
        off += length;
        code = code.substring(1 + LENGTH_SIZE + DISTANCE_SIZE);
      }
      if (off > DICTIONARY_SIZE_MAX) {
        baos.write(slide, 0, off - DICTIONARY_SIZE_MAX);
        System.arraycopy(slide, off - DICTIONARY_SIZE_MAX, slide, 0,
            DICTIONARY_SIZE_MAX);
        off = DICTIONARY_SIZE_MAX;
      }
    }
    baos.write(slide, 0, off);
    return baos.toByteArray();
  }
}