レンペル・ジヴ・ウェルチ

Lempel–Ziv–Welch ( LZW ) は、Abraham Lempel、Jacob Ziv、Terry Welchによって考案された汎用的な可逆データ圧縮 アルゴリズムです。1978 年に Lempel と Ziv によって発表されたLZ78アルゴリズムの改良版として、1984 年に Welch によって発表されました。このアルゴリズムは実装が簡単で、ハードウェア実装で非常に高いスループットを実現できます。^{[1]これは、} Unixファイル圧縮ユーティリティのCompress のアルゴリズムであり、 GIF画像形式で使用されています。

^{ウェルチの 1984 年の論文[1]}で説明されているシナリオでは、8 ビット データのシーケンスを固定長 12 ビット コードとしてエンコードします。0 から 255 までのコードは、対応する 8 ビット文字で構成される 1 文字シーケンスを表し、256 から 4095 までのコードは、エンコード時にデータで検出されたシーケンスの辞書に作成されます。圧縮の各段階で、入力バイトは、次の文字が辞書にまだコードがないシーケンスになるまで、シーケンスにまとめられます。シーケンスのコード (その文字なし) は出力に追加され、新しいコード (その文字を含むシーケンス) は辞書に追加されます。

このアイデアはすぐに他の状況にも応用されました。たとえば、カラー テーブルに基づく画像では、自然文字のアルファベットはカラー テーブル インデックスのセットであり、1980 年代には多くの画像に小さなカラー テーブル (16 色程度) がありました。このように縮小されたアルファベットの場合、画像が大きい場合を除き、完全な 12 ビット コードでは圧縮率が低くなるため、可変幅コードというアイデアが導入されました。コードは通常、エンコードされるシンボルより 1 ビット広いところから始まり、コード サイズが使い果たされるごとに、コード幅は 1 ビットずつ増加し、規定の最大値 (通常は 12 ビット) まで増加します。最大コード値に達すると、既存のテーブルを使用してエンコードが続行されますが、テーブルに追加するための新しいコードは生成されません。

さらに改良された点として、コード テーブルをクリアして初期状態に復元する必要があることを示すコード (「クリア コー​​ド」、通常は個々のアルファベット文字の値の直後の最初の値) と、データの終了を示すコード (「ストップ コード」、通常はクリア コー​​ドより 1 つ大きい値) を予約することなどがあります。クリア コー​​ドにより、テーブルがいっぱいになった後にテーブルを再初期化できるため、入力データの変化するパターンにエンコードを適応させることができます。スマート エンコーダーは、圧縮効率を監視し、既存のテーブルが入力に一致しなくなった場合はいつでもテーブルをクリアできます。

コードはデータによって決定される方法で追加されるため、デコーダーは結果のコードを見てテーブルの構築を模倣します。エンコーダーとデコーダーが、アルファベットのサイズ、最大テーブル サイズ (およびコード幅)、可変幅エンコードを使用するかどうか、初期コード サイズ、クリア コー​​ドとストップ コードを使用するかどうか (およびそれらの値) など、使用する LZW の種類について合意することが重要です。LZW を使用するほとんどの形式では、この情報が形式仕様に組み込まれているか、データの圧縮ヘッダーに明示的なフィールドが用意されています。

エンコード アルゴリズムの概要を以下に示します。

1. 長さ 1 のすべての文字列が含まれるように辞書を初期化します。
2. 現在の入力に一致する辞書内の最長の文字列W を検索します。
3. Wの辞書インデックスを出力し、入力からW を削除します。
4. 入力内の次の記号の後にW を辞書に追加します。
5. ステップ2に進みます。

辞書は、すべての可能な入力文字に対応する単一文字の文字列 (使用されている場合はクリア コー​​ドとストップ コード以外のもの) を含むように初期化されます。アルゴリズムは、辞書にない文字列が見つかるまで、入力文字列をスキャンして連続的に長い部分文字列を探します。そのような文字列が見つかると、最後の文字のない文字列 (つまり、辞書にある最長の部分文字列) のインデックスが辞書から取得されて出力に送信され、新しい文字列 (最後の文字を含む) が次の使用可能なコードとともに辞書に追加されます。次に、最後の入力文字が部分文字列をスキャンするための次の開始点として使用されます。

このようにして、連続的に長い文字列が辞書に登録され、単一の出力値として後続のエンコードに利用できるようになります。このアルゴリズムは、繰り返しパターンを持つデータに対して最も効果的に機能するため、メッセージの最初の部分はほとんど圧縮されません。ただし、メッセージが長くなるにつれて、圧縮率は漸近的に最大になります (つまり、圧縮係数または圧縮率は直線的ではなく増加曲線で向上し、無限の時間ではなく限られた時間内に理論上の最大値に近づきます)。^[2]

デコード アルゴリズムの概要を以下に示します。

1. 長さ 1 のすべての文字列が含まれるように辞書を初期化します。
2. 次のエンコードされたシンボルを読み取ります。辞書にエンコードされていますか?
   1. はい：
      1. 対応する文字列Wを出力します。
      2. 出力に送られた前の文字列をWの最初のシンボルと連結します。これを辞書に追加します。
   2. いいえ：
      1. 出力に送られた前の文字列をその最初のシンボルと連結します。この文字列をV と呼びます。
      2. V を辞書に追加し、 Vを出力します。
3. 入力文字列の最後まで手順2を繰り返します。

デコード アルゴリズムは、エンコードされた入力から値を読み取り、辞書から対応する文字列を出力することで機能します。ただし、完全な辞書は必要なく、単一文字の文字列を含む初期辞書のみが必要です (これは通常、エンコードされたデータとともに送信されるのではなく、プログラムでハードコードされます)。代わりに、完全な辞書は、デコード プロセス中に次のように再構築されます。値をデコードして文字列を出力した後、デコーダーはそれを次のデコード文字列の最初の文字(または、次の文字列がデコードできない場合は現在の文字列の最初の文字。次の値が不明な場合は、この反復で辞書に追加された値である必要があり、したがってその最初の文字は現在の文字列の最初の文字と同じであるため) と連結し、新しい文字列で辞書を更新します。次に、デコーダーは次の入力 (前の反復で既に読み取られている) に進み、前と同じように処理します。入力ストリームを使い果たすまでこれを繰り返します。

可変幅コードが使用されている場合、エンコーダーとデコーダーは、ストリーム内の個々のコード間の境界で不一致が生じないように、エンコードされたデータ内の同じポイントで幅を変更するように注意する必要があります。標準バージョンでは、テーブルにない シーケンス ω +  sに遭遇した場合 (そのため、コードを追加する必要があります)、テーブル内の次の使用可能なコードは 2 p ( p + 1 ビットを必要とする最初のコード) であり、エンコーダーは幅をp から p + 1 に増やします。エンコーダーは、幅 p^で ω のコードを発行し(このコードはp + 1 ビットを必要としないため)、次に発行される次のコードがp + 1 ビット幅に なるようにコード幅を増やします 。

デコーダーは、テーブルの構築において常にエンコーダーより 1 コード遅れているため、ω のコードを見つけると、コード 2 ^p − 1 のエントリを生成します。これはエンコーダーがコード幅を増やすポイントであるため、デコーダーもここで幅を増やす必要があります ( pビット に収まる最大のコードを生成するポイント) 。

残念ながら、エンコード アルゴリズムの初期の実装では、コード幅を増やしてから、古い幅ではなく新しい幅で ω を出力します。そのため、デコーダーには、幅が 1 コード早く変更されたように見えます。これは「早期変更」と呼ばれます。これは大きな混乱を引き起こしたため、Adobe は現在、PDF ファイルで両方のバージョンを許可していますが、早期変更が使用されているかどうかを示すために、各 LZW 圧縮ストリームのヘッダーに明示的なフラグを含めています。LZW 圧縮をサポートするグラフィック ファイル形式のうち、TIFF は早期変更を使用しますが、GIFおよび他のほとんどの形式では使用しません。

クリア コー​​ドに応答してテーブルがクリアされると、エンコーダーとデコーダーの両方が、クリア コー​​ドの直後のコードから始めて、クリア コー​​ドの後のコード幅を初期コード幅に戻します。

出力されるコードは通常バイト境界に収まらないため、エンコーダとデコーダはコードをバイトにパックする方法について合意する必要があります。一般的な 2 つの方法は、LSB ファースト("最下位ビットが先") とMSB ファースト("最上位ビットが先") です。LSB ファーストのパックでは、最初のコードは、コードの最下位ビットが最初のストリーム バイトの最下位ビットに収まるように配置されます。コードが 8 ビットを超える場合は、残った上位ビットが次のバイトの最下位ビットに収まるように配置されます。それ以降のコードは、LSB が現在のストリーム バイトでまだ使用されていない最下位ビットに入るようにパックされ、必要に応じて次のバイトに進みます。MSB ファーストのパックでは、最初のコードの最上位ビットが最初のストリーム バイトの MSB に収まるように配置され、オーバーフローが次のバイトの MSB に収まるように配置されます。それ以降のコードは、MSB が現在のストリーム バイトでまだ使用されていない最上位ビットに入るように書き込まれます。

GIF ファイルは LSB ファーストのパッキング順序を使用します。TIFF ファイルと PDF ファイルは MSB ファーストのパッキング順序を使用します。

次の例は、LZW アルゴリズムの動作を示しており、データのエンコードとデコードの両方で、各段階での出力と辞書の状態を示しています。この例は、非常に短いメッセージを適切に圧縮するように作成されています。実際のテキスト データでは、繰り返しは一般的にそれほど顕著ではないため、圧縮の効率を高めるには、通常、より長い入力ストリームが必要になります。

エンコードされる平文（大文字のみを使用したアルファベットから）は次のとおりです。

いけない、いけない、いけない、いけない#

プレーンテキスト アルファベットには 26 個のシンボルがあります (大文字のAからZまで)。 # はストップ コードを表すために使用されます。ストップ コードとは、プレーンテキスト アルファベットの外側にあるコードで、特別な処理をトリガーします。文字には 1 から 26 までの値を、ストップ コード '#' には 0 を任意に割り当てます。(LZW のほとんどのバージョンでは、ストップ コードはデータ アルファベットの後に配置されますが、基本アルゴリズムではその必要はありません。エンコーダとデコーダは、その値が何であるかを一致させるだけで済みます。)

コンピュータは、これらをビットの文字列としてレンダリングします。この 27 個の値のセットを網羅するのに十分な組み合わせを提供するには、5 ビットのコードが必要です。辞書は、これらの 27 個の値で初期化されます。辞書が大きくなるにつれて、コードの幅を広げて、追加のエントリを収容する必要があります。5 ビットのコードでは、2 ⁵ = 32 個のビットの組み合わせが可能になるため、33 番目の辞書単語が作成されると、アルゴリズムはその時点で 5 ビットの文字列から 6 ビットの文字列に切り替える必要があります (すべてのコード値、以前に 5 ビットのみで出力されたものも含む)。すべてゼロのコード 00000 が使用され、ラベルが「0」になっているため、33 番目の辞書エントリは32​​ というラベルが付けられていることに注意してください。(以前に生成された出力は、コード幅の変更の影響を受けませんが、辞書で 6 ビットの値が生成されると、それが次に出力されるコードになる可能性があるため、後続の出力の幅は、それに対応するために 6 ビットにシフトします。)

初期辞書は次のエントリで構成されます。

ω + 次の文字が辞書になくなるまで、シーケンス ω の入力文字をバッファリングします。ω のコードを出力し、ω + 次の文字を辞書に追加します。次の文字で再度バッファリングを開始します。(エンコードされる文字列は "TOBEORNOTTOBEORTOBEORNOT#" です。)

エンコードされていない長さ = 25 シンボル × 5 ビット/シンボル = 125 ビット

エンコードされた長さ = (6 コード × 5 ビット/コード) + (11 コード × 6 ビット/コード) = 96 ビット。

LZW を使用すると、125 ビットのうち 29 ビットが節約され、メッセージが 23% 以上削減されます。メッセージが長くなると、辞書の単語はますます長いテキスト セクションを表すようになり、繰り返される単語が非常にコンパクトに送信されます。

LZW 圧縮アーカイブをデコードするには、使用される初期辞書を事前に知っておく必要がありますが、追加のエントリは常に以前のエントリの単純な連結であるため、再構築できます。

各段階で、デコーダーはコード X を受け取ります。デコーダーはテーブルで X を検索し、コード化したシーケンス χ を出力し、エンコーダーが追加したエントリとして χ + ? を推測します。これは、エンコーダーが χ に対して X を出力したのは、まさに χ + ? がテーブルになかったためであり、エンコーダーは先に進んでそれを追加するからです。しかし、不足している文字は何でしょうか? それは、デコーダーが受け取る次のコード Z によってコード化されたシーケンスの最初の文字です。そのため、デコーダーは Z を検索し、シーケンス ω にデコードし、最初の文字 z を取得して、次の辞書エントリとして χ の末尾に追加します。

これは、受信したコードがデコーダの辞書内にある限り機能し、シーケンスにデコードできます。デコーダが、まだ辞書内にないコード Z を受信した場合はどうなりますか? デコーダは常にエンコーダより 1 コードだけ遅れているため、エンコーダが χ の前のコード X を発行したときに Z を生成した場合にのみ、Z がエンコーダの辞書内に存在する可能性があります。したがって、Z は χ + ? である何らかの ω をコード化し、デコーダは次のようにして未知の文字を判別できます。

1. デコーダーは X を見てから Z を見ます。ここで、X はシーケンス χ をコード化し、Z は未知のシーケンス ω をコード化します。
2. デコーダーは、エンコーダーが χ + 未知の文字cのコードとして Z を追加しただけなので、 ω = χ + cであることを認識しています。
3. c は入力ストリーム内で χ の後の最初の文字であり、ω は χ の直後に現れる文字列であるため、c はシーケンス ω の最初の文字である必要があります。
4. χ は ω の最初の部分文字列なので、cも χ の最初の文字でなければなりません。
5. したがって、Z コードがテーブルにない場合でも、デコーダーは未知のシーケンスを推測し、χ + (χ の最初の文字) を Z の値としてテーブルに追加できます。

この状況は、エンコーダーがcScSc という形式の入力に遭遇するたびに発生します。ここで、cは 1 つの文字、Sは文字列、cS は既に辞書に存在しますが、cSc は存在しません。エンコーダーはcSのコードを発行し、 cScの新しいコードを辞書に追加します。次に、入力でcSc を確認し ( cScScの2 番目のcから開始)、挿入したばかりの新しいコードを発行します。上記の議論は、デコーダーが辞書にないコードを受け取るたびに、状況は次のようになる必要があることを示しています。

cScSc形式の入力はありそうにないと思われるかもしれませんが、入力ストリームが大幅な繰り返しを特徴とする場合、このパターンはかなり一般的です。特に、単一文字の長い文字列 (LZW がエンコードによく使用される種類の画像では一般的) は、この種のパターンを繰り返し生成します。

上記の単純な方式は、LZW アルゴリズム自体に焦点を当てています。多くのアプリケーションでは、出力シンボルのシーケンスにさらにエンコードを適用します。一部のアプリケーションでは、何らかの形式のバイナリからテキストへのエンコードを使用して、コード化されたストリームを印刷可能な文字としてパッケージ化します。これにより、エンコードされた長さが増加し、圧縮率が低下します。逆に、適応型エントロピー エンコーダーを使用すると、圧縮率を高めることができます。このようなコーダーは、これまでに観測された値の頻度に基づいて、次のシンボルの値の確率分布を推定します。ハフマン コーディングや算術コーディングなどの標準的なエントロピー エンコードでは、確率の高い値には短いコードを使用します。

LZW 圧縮は、コンピューターで広く使用される最初の汎用データ圧縮方法となりました。通常、大きな英語のテキスト ファイルは、LZW によって元のサイズの約半分に圧縮できます。

LZW はパブリック ドメイン プログラムであるCompressで使用されていました。このプログラムは 1986 年頃にUnixシステムでほぼ標準のユーティリティになりました。LZW の特許を侵害していたことと、 LZ77 ベースのDEFLATEアルゴリズムを使用してgzip の方が圧縮率が高かったことから、このプログラムは多くのディストリビューションから姿を消しましたが、2008 年現在、少なくとも FreeBSD には、ディストリビューションの一部として、 compressとuncompressの両方が含まれています。他のいくつかの一般的な圧縮ユーティリティも、LZW または密接に関連する方法を使用していました。

LZW は、1987 年にGIF画像形式の一部になって以来、広く使用されるようになりました。また、 TIFFファイルやPDFファイルでも (オプションで) 使用できます。(LZW はAdob​​e Acrobatソフトウェアで使用できますが、Acrobat はデフォルトで、PDF ファイル内のほとんどのテキストおよびカラー テーブル ベースの画像データに DEFLATE を使用します。)

LZW および類似のアルゴリズムについては、米国およびその他の国でさまざまな特許が発行されています。LZ78 は、Lempel、Ziv、Cohn、Eastman による米国特許 4,464,650で保護されており、1981 年 8 月 10 日にSperry Corporation (後のUnisys Corporation) に譲渡されました。LZW アルゴリズムについては、Victor S. MillerおよびMark N. Wegmanによる米国特許 4,814,746 ( IBMに譲渡、1983 年 6 月 1 日に最初に出願) とWelch による米国特許 4,558,302 (Sperry Corporation (後の Unisys Corporation) に譲渡、1983 年 6 月 20 日に出願) の 2 つの米国特許が発行されています。

上記の特許に加えて、ウェルチの1983年の特許には、NECの金津純による1980年の日本特許2件（JP9343880AおよびJP17790880A）、ジョン・S・ホーニングによる米国特許4,021,782 （1974年）、クラウス・E・ホルツによる米国特許4,366,551（1977年）、およびカール・エックハルト・ハインツによる1981年のドイツ特許（DE19813118676）など、それに影響を与えた他のいくつかの特許への引用も含まれています。^[3]

1993年から1994年、そして1999年に、Unisys CorporationはGIF画像のLZWにライセンス料を課そうとしたため、広く非難を浴びた。1993年から1994年にかけてのUnisysとCompuServeの論争（CompuServeはGIF形式の作成者）は、Usenetのcomp.graphicsでの議論「GIFに代わるファイル形式に関する考察」を誘発し、それが電子メールのやり取りに発展し、最終的には1995年に特許に縛られないPortable Network Graphics（PNG）ファイル形式の作成に至った。

ユニシスのLZWアルゴリズムに関する米国特許は、出願から20年後の2003年6月20日に失効した^[4]。英国、フランス、ドイツ、イタリア、日本、カナダで出願された特許も、同様に出願から20年後の 2004年に失効した^{[4] 。}

• LZMW (1985、V. Miller、M. Wegman 著) ^[5] – 入力文字列から辞書にすでに存在する最長の文字列 (「現在の」一致) を検索し、前回の一致と現在の一致を連結したものを辞書に追加します。(辞書のエントリはこのようにして急速に増加しますが、この方式の実装ははるかに複雑です。) Miller と Wegman は、辞書がいっぱいになったときに、頻度の低いエントリを辞書から削除することも提案しています。
• LZAP (1988、James Storer 作) ^[6] – LZMW の修正: 前回の一致と現在の一致の連結を辞書に追加するだけでなく、前回の一致の連結と現在の一致の各先頭部分文字列を追加します (「AP」は「すべてのプレフィックス」の略)。たとえば、前回の一致が「wiki」で、現在の一致が「pedia」の場合、LZAP エンコーダーは 5 つの新しいシーケンスを辞書に追加します: 「wikip」、「wikipe」、「wikiped」、「wikipedi」、「wikipedia」。LZMW エンコーダーは 1 つのシーケンス「wikipedia」のみを追加します。これにより、LZMW の複雑さがいくらか軽減されますが、辞書エントリが追加されるという代償があります。
• LZWL はLZW の音節ベースの変形です。

• LZ77とLZ78
• ルズマ
• レンペル＝ジヴ＝ストーラー＝シマンスキー
• 翻訳
• コンテキストツリーの重み付け
• 離散コサイン変換（DCT）は、JPEGおよびMPEGコーディング標準で使用される非可逆圧縮アルゴリズムです。

• Rosettacode wiki、さまざまな言語でのアルゴリズム
• 米国特許 4,558,302、テリー A. ウェルチ、高速データ圧縮および解凍装置および方法
• SharpLZW – C# オープンソース実装
• MIT OpenCourseWare: LZW アルゴリズムを含む講義
• マーク・ネルソン、LZW データ圧縮、ドクター・ドブス・ジャーナル (1989 年 10 月 1 日)
• 縮小、縮小、および崩壊: 従来の Zip 圧縮方式では、LZW とそれがPKZIPでどのように使用されていたかについて説明します。