LZW

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索

LZWは、辞書式圧縮である Lempel-Ziv法 (LZ78) を、スペリー社のテリー・ウェルチが改良したアルゴリズム。

開発者の Lempel、Ziv、Welch の頭文字を取ってLZWと呼ばれる。

圧縮効率と高速化の両面を追求している為、LZSSハフマン符号化を組み合わせたDeflateアルゴリズム(LZHZIPなどが採用)と比べると30%ほど圧縮効率が悪い。GIFTIFFなどの圧縮で利用されている。UNIX Compressで使える。

実装[編集]

以下、Groovyでの実装。まず、ビット列を扱うストリームを用意する。

class BitStream {
  BitSet bs = new BitSet(); int len = 0, pos = 0;
  void write(int v, int bits) {
    for (int i in 0..<bits) { bs[len++] = ((v >>> i) & 1) != 0 }
  }
  int read(int bits) {
    int v = 0; for (int i in 0..<bits) { if (bs[pos++]) { v |= 1 << i } }
    return v
  }
  String toString() { "length = $len, {" + (0..<len).findAll({ bs[it] }).join(", ") + "}" }
}

圧縮は以下の通り。

BitStream compress(byte[] data) {
  BitStream bs = new BitStream(); List str = []; int maxCode = 255, maxCodeBits = 8;
  Map table = [:]; for (int i in 0..maxCode) { table[[(byte) i]] = i }

  for (byte c in data) {
    str << c
    if (!table.containsKey(str)) {
      bs.write(table[str[0..(str.size() - 2)]], maxCodeBits)
      table[str] = ++maxCode
      if (maxCode == (1 << maxCodeBits)) maxCodeBits++
      str = [c]
    }
  }
  bs.write(table[str], maxCodeBits)
  return bs
}

解凍は以下の通り。

byte[] decompress(BitStream bs) {
  List bytes = []; int maxCode = 255, maxCodeBits = 8, prevCode; byte c;
  List table = []; for (byte v in 0..maxCode) { table << [v] }

  bs.pos = 0
  bytes << (c = prevCode = bs.read(maxCodeBits))
  while (bs.pos < bs.len) {
    if (++maxCode == (1 << maxCodeBits)) maxCodeBits++
    int code = bs.read(maxCodeBits)
    List str = (code == maxCode) ? table[prevCode] + c : table[code]
    bytes.addAll(str)
    table << table[prevCode] + (c = str[0])
    prevCode = code
  }
  return bytes as byte[]
}

Example[編集]

今回圧縮する平文(アルファベットの大文字のみで表される)は

TOKYOTOKKYOKYOKAKYOKU#

である。#は文字列の終端を表す。 この時、使用される文字は27種類(アルファベットおよび#)である。 この例では、1~26の数字をアルファベットに、 0を#に当てはめる。

Encoding[編集]

Current Sequence Next Char Output Extended Dictionary Comments
Code Bits
NULL T
T O 20 10100 27: TO 27 = first available code after 0 through 26
O K 15 01111 28: OK
K Y 22 10110 29: KY
Y O 25 11001 30: YO
O T 15 01111 31: OT
TO K 27 11011 32: TOK 32 requires 6 bits, so for next output use 6 bits
K K 22 010110 33: KK
KY O 29 011101 34: KYO
OK Y 28 011100 35: OKY
YO K 30 011110 36: YOK
K A 22 010110 37: KA
A K 1 000001 38: AK
KYO K 34 100010 39: KYOK
K U 22 010110 40: KU
U # 21 010101 # stops the algorithm; send the cur seq
0 000000 and the stop code

Decoding[編集]

Input Output Sequence New Dictionary Entry Comments
Bits Code Full Conjecture
10100 20 T 27: T?
01111 15 O 27: TO 28: O?
10110 22 K 28: OK 29: K?
11001 25 Y 29: KY 30: Y?
01111 15 O 30: YO 31: O?
11011 27 TO 31: OT 32: TO? created code 31 (last to fit in 5 bits)
010110 22 K 32: TOK 33: K? so start reading input at 6 bits
011101 29 KY 33: KK 34: KY?
011100 28 OK 34: KYO 35: OK? 35 = OK + 1st symbol (Y) of
011110 30 YO 35: OKY 36: YO? next coded sequence received (YO)
010110 22 K 36: YOK 37: K?
000001 1 A 37: KA 38: A?
100010 34 KYO 38: AK 39: KYO?
010110 22 K 39: KYOK 40: K?
010101 21 U 40: KU 41: U?
000000 0 #

また、

TANBANANAS#

などをエンコードしたものを、またデコードする際には、辞書が不完全な状態で使用されることとなるが、その場合も辞書の一文字目を最後の文字として付け足して、使用すればよい。

特許[編集]

LZWは1984年に発表された。当初スペリー社が特許を保有していた。のちスペリー社はバロース社と合併し1986年ユニシス社となり、本アルゴリズムの特許権もユニシス社に引き継がれた。

前述の通りGIF画像の圧縮に用いられており、その特許料に関するユニシス社の姿勢が問題となった。詳細はGIF特許問題を参照。

日本では1984年6月20日に特許が出願され、2004年6月20日に期限切れとなった。以下、日本の特許庁産業財産権情報より:

  • 発明の名称:圧縮装置および圧縮方法
  • 出願日:1984年6月20日
    • 出願番号:特許出願平7-341868
  • 公開日:1996年9月13日
    • 公開番号:特許公開平8-237138