Lempel–Ziv–Welch

Lempel–Ziv–Welchは、1984年に辞書式圧縮である Lempel-Ziv法 (LZ78) を、スペリー社のテリー・ウェルチが改良したアルゴリズムで、開発者のLempel、Ziv、Welchの頭文字を取って命名された。略称はLZW。

圧縮効率と高速化の両面を追求している為、LZSSとハフマン符号化を組み合わせたDeflateアルゴリズム（LZHやZIP、PNGなどが採用）と比べると30%ほど圧縮効率が悪い。GIFで利用されている他、TIFFやPDFの圧縮でLZWを選択可能。UNIX Compressで使える。

アルゴリズム

LZ78と違い、最初に入力可能なすべての文字を辞書に追加して初期化しておくため、部分文字列は辞書に必ず存在し、出力はコードだけの配列となる。「コード」とは辞書に登録されている文字列に対応するインデックスのことである。Welchの1984年の論文^[1]では8ビットが並んだデータを12ビット固定長のコード列としてエンコードしていた。0から255のコードは対応する1つの8ビット文字を表し、256から4095のコードは辞書にない文字列がデータに出現し、辞書にその文字列を追加するときに順次割り振られる。

このアルゴリズムは同じパターンが繰り返されるデータに最適に働く。辞書に追加しながらエンコードするため文字列の最初の部分は低圧縮率となるが、文字列が増えるに連れ圧縮率はしだいに最大へと近づく。^[2]

「文字列」と表現しているが入力は文字列でなくともよいため、他のデータの圧縮にもすぐに用いられた。例えば、カラーテーブルを使った画像では1文字はカラーテーブルのインデックスに対応する。しかし、1980年代には多くの画像が16色程度の小さなカラ―テーブルしか持っていなかったため、画像が大きくない限り12ビット幅のコードでは小さな圧縮率しか得られなかった。このため可変幅コードのアイディアが導入された。コードはエンコードしているシンボルより一般的には1ビット広い幅から始め、各コードサイズが使い切られるにつれて、コード幅は1ビットずつ広げられ、予め決められた最大値(一般的には12ビット)まで広げられる。最大コード値まで達した時は、エンコーディングは既存の辞書を使用して続けられるが、新たなコードが作られたり、辞書に追加されることはない。

その他の改善には、辞書をクリアーして初期状態に復元することを示すコード(クリアーコード、一般的には個別のアルファベット文字の値のすぐ後の最初の値)や、データの終わり(ストップコード、一般的にはクリアーコードより1大きい)を示すコードを辞書に確保することが含まれる。クリアーコードはテーブルが満杯になった後に再初期化し、エンコーディングが入力データのパターンの変化に対応することを可能にする。賢いエンコーダーは圧縮効率を監視し、既存のテーブルが入力に合っていないときはいつでも辞書をクリアーすることができる。

デコーダーは出力されたコード列だけでエンコーダに使われたのと同じ辞書をデコードしながら再び作ることができるため、完全な辞書をエンコードされたデータと一緒に送る必要はない。このためエンコーダーとデコーダーがどの種類のLZWが使われているかー―1文字のサイズ、最大辞書サイズ(とコード幅)、可変幅のエンコーディングが使われているかどうか、初期コード幅、クリアーコード・ストップコードが使われているかどうか(そしてコード値はなにか)ーーについて合意していることが重要である。LZWを採用している多くのフォーマットではこの情報はフォーマット仕様に盛り込まれているか、圧縮データのヘッダーにこれらの情報のための明確なフィールドが確保されている。

エンコーディング

エンコーディングアルゴリズムは以下の通り。

すべての入力可能な文字(使用される場合はクリアーコード・ストップコードも)で辞書を初期化する
現在の入力文字列と最も長く一致する文字列Wを辞書から探す
出力にWの辞書のインデックス(コード)を送出し、Wを入力文字列から削除する
入力で後ろに続く1文字sを付け足したW + sを辞書に追加する
2に戻る

デコーディング

デコーディングアルゴリズムは以下の通り。

辞書を初期化する(エンコーディングの1と同じ)
入力からコードを1つ読み込み、入力から削除する
そのコードに対応する文字列Wを辞書から得る
出力にWを送出する
入力から次のコードを読み込む
次のコードに対応する文字列の最初の文字sをWに付け足したW + sを辞書に追加する
2に戻る

可変幅コード

もし可変幅コードが使われている場合、エンコーダーとデコーダーはエンコードされたデータの同じ位置でコード幅の変更が行われなくてはならない。一般的なバージョンではエンコーダーは文字列W + sが辞書になかったが、次に辞書で利用可能なコードが2^pであったときに幅をpからp + 1へ増やす(コードを辞書に追加しなければならないため)。エンコーダーはWのコードを幅pで出力に送出する。そして次のコードからp + 1ビット幅で送出できるようにコード幅を増やす。

デコーダーはいつも辞書の作成でエンコーダーより1コード分遅れており、Wのコードを見るとき、それは2^p − 1のコードを生成する。エンコーダーがコード幅を増やすポイントであるから、デコーダーもpビットで最大のコードを生成するポイントであるここで同じように幅を増やさなければならない。

不幸なことに、初期に実装されたいくつかのエンコーディングアルゴリズムはコード幅を増やした後、古い幅ではなく新しい幅でWを送出する。デコーダーには1コード分早く変化したと見えるため、これは"Early Change"と呼ばれる。この違いは大きな混乱を招くため、アドビはPDFファイルではどちらのバージョンも許容しているが、それぞれのLZW圧縮ストリームのヘッダーにEarly Changeが使われているかどうかを示す明示的なフラグを含めている。LZW圧縮が使用可能な画像ファイルフォーマットのうち、TIFFはEarly Changeを使うが、GIFとその他多くの画像ファイルフォーマットでは使っていない。

クリアーコードによって辞書がクリアーされた時、エンコーダーとデコーダーの両方はコード幅をクリアーコードのあと初期のコード幅に戻し、クリアーコードの後すぐにそのコードから開始する。

パッキング順序

コードの送出は一般的にはバイト境界に一致しないため、エンコーダーとデコーダーはどのようにコードをバイトに詰め込むかを合意しておかなければならない。一般的な2つの方法はLSB-First("Least Significant Bit First")とMSB-First("Most Significant Bit First")である。

GIFはパッキング順序にLSB-Firstを使い、TIFFとPDFはMSB-Firstを使う。

実装

以下、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[]
}

例

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

TOKYOTOKKYOKYOKAKYOKU#

である。#は文字列の終端を表す。この時、使用される文字は27種類（アルファベットおよび#）である。この例では、1～26の数字をアルファベットに、 0を#に当てはめる(ストップコードが0)。27種類を表すために必要な最小のビット幅は5なので、5ビットから始める。

エンコーディング

現在の文字	次の文字	出力		辞書への追加		コメント
現在の文字	次の文字	コード	ビット	辞書への追加		コメント
なし	T
T	O	20	10100	27:	TO	27は0から26の後で最初に使えるコード
O	K	15	01111	28:	OK
K	Y	11	01011	29:	KY
Y	O	25	11001	30:	YO
O	T	15	01111	31:	OT
TO	K	27	11011	32:	TOK	32は6ビット必要なため次の出力から6ビットになる
K	K	11	001011	33:	KK
KY	O	29	011101	34:	KYO
OK	Y	28	011100	35:	OKY
YO	K	30	011110	36:	YOK
K	A	11	001011	37:	KA
A	K	1	000001	38:	AK
KYO	K	34	100010	39:	KYOK
K	U	11	001011	40:	KU
U	#	21	010101			次の文字が#なので辞書への追加はない
#		0	000000			ストップコードを出力する

デコーディング

デコーダーはアルファベット大文字しか使わず、初期コード幅が5ビットで可変幅エンコーディングであり、ストップコードが0であるという前提を知っていなければならない。

入力		出力する文字	辞書への追加				コメント
ビット	コード	出力する文字	完全		推測		コメント
10100	20	T			27:	T?
01111	15	O	27:	TO	28:	O?
01011	11	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?	コード31を追加する(5ビットで読み取る最後の入力)
001011	11	K	32:	TOK	33:	K?	6ビットで読み込む
011101	29	KY	33:	KK	34:	KY?
011100	28	OK	34:	KYO	35:	OK?
011110	30	YO	35:	OKY	36:	YO?
001011	11	K	36:	YOK	37:	K?
000001	1	A	37:	KA	38:	A?
100010	34	KYO	38:	AK	39:	KYO?
001011	11	K	39:	KYOK	40:	K?
010101	21	U	40:	KU	41:	U?
000000	0	#

まず入力ビット列から5ビット読み込み、コード20に対応した文字Tを辞書から得る。次の5ビットを読み込み、同様に文字Oを得る。ここで一回前に得られた文字Tと今回得られた文字Oの先頭の文字Oを連結したTOを辞書に追加する。以下同様にやっていき、復号する。

また、

TANBANANAS#

をエンコードしたものを、デコードする際には、

エンコーディング				デコーディング
現在の文字	出力するコード	辞書への追加		入力コード	出力する文字	辞書への追加
T	20	27:	TA	20	T
A	1	28:	AN	1	A	27:	TA
N	14	29:	NB	14	N	28:	AN
B	2	30:	BA	2	B	29:	NB
AN	28	31:	ANA	28	AN	30:	BA
ANA	31	32:	ANAS	31	?
S	19			19
#	0			0

入力コード31が出てくるが辞書にはない。これはエンコーディングで辞書に追加したばかりのコードを直後に使っているが、デコーディングでは辞書への追加は1コード分遅れておりまだ追加されていないために起こる。しかし、コード31に対応する文字列がANAであることは原理上明らかである。なぜなら、コード31に対応する文字列は1つ前にデコーディングした文字列ANになんらかの1文字を連結したものである。その1文字はコード31に対応する文字列の先頭の文字である。よってその1文字はANの先頭の文字のAであり、31に対応するのはANにAを連結したANAである。

cは文字で、Sは文字列とし、cSはすでに出現しているが、cScは出現していない状況でcScScと並んだ時に起きる。

特許

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

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

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

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

出典

この項目は、コンピュータに関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（PJ:コンピュータ/P:コンピュータ）。

[WelchIEEE-1] Welch, Terry (1984). “A Technique for High-Performance Data Compression”. Computer 17 (6): 8–19. doi:10.1109/MC.1984.1659158.

[2] Ziv, J.; Lempel, A. (1978). “Compression of individual sequences via variable-rate coding”. IEEE Transactions on Information Theory 24 (5): 530. doi:10.1109/TIT.1978.1055934.

[1]

[2]