LZ77

LZ77は、PDF文書で使用される多くの圧縮方式の基礎となる可逆データ圧縮アルゴリズムです。 ( Citation: N.A., 2020 (N.A.). (2020). Document management — Portable document format — Part 2: PDF 2.0 .  International Organization for Standardization Retrieved from https://www.iso.org/standard/75839.html ) で規定されているように、FlateDecode（ZLIB/DEFLATEアルゴリズムを使用）などのLZ77ベースの圧縮方式は、PDFのコンテンツストリーム、画像データ、その他のオブジェクトに広く適用され、データの完全性を保ちながらファイルサイズを削減します。この圧縮技術は、PDFのパフォーマンスを最適化し、ストレージ要件を最小限に抑えるために特に重要です。

LZ77は、1977年にAbraham LempelとJacob Zivによって開発された辞書ベースの圧縮アルゴリズムで、スライディングウィンドウ内の以前の出現箇所への参照でデータの繰り返し出現を置き換えることによって機能します。文字の頻度を分析する統計的圧縮方式とは異なり、LZ77は重複するバイトシーケンスを検出し、以前のデータを指す（距離、長さ）のペアとして符号化する原理で動作します。

PDFの文脈において、LZ77は ( Citation: N.A., 2020 (N.A.). (2020). Document management — Portable document format — Part 2: PDF 2.0 .  International Organization for Standardization Retrieved from https://www.iso.org/standard/75839.html ) で定義されているFlateDecodeフィルターを通じて実装されるDEFLATE圧縮方式の基盤となるアルゴリズムです。PDFのコンテンツストリームや画像がFlateDecodeを使用して圧縮される場合、LZ77アルゴリズムはデータ内の繰り返しパターンを識別し、それらをコンパクトな後方参照に置き換え、その後ハフマン符号化によってさらに圧縮します。

LZ77は、連続する同一バイトのみを圧縮するランレングス符号化（RLE）のような他の圧縮手法とは異なり、任意の長さの繰り返しパターンを識別して圧縮できます。また、別のコードテーブルを構築するLZW（Lempel-Ziv-Welch）のような辞書ベース方式とも異なり、LZ77は以前に処理されたデータ自体を辞書として使用します。

PDFファイルを扱う開発者にとって、LZ77圧縮を理解することは、いくつかの実用的な理由から非常に重要です。

ファイルサイズの最適化: LZ77ベースの圧縮は、フォーム、構造化データ、繰り返しのグラフィック要素など、反復的なコンテンツを含む文書において、PDFファイルサイズを大幅に削減できます。これは、ダウンロード時間、ストレージコスト、アプリケーションのパフォーマンスに直接影響します。

ストリーム処理: PDFのコンテンツストリームをプログラムで読み書きする際、開発者はFlateDecode圧縮されたデータを扱う必要があり、これには基盤となるLZ77圧縮の理解が必要です。PDFコンテンツを操作するライブラリやツールは、処理前にストリームを解凍し、必要に応じて後で再圧縮する必要があります。

パフォーマンスの考慮事項: LZ77圧縮は圧縮率と処理速度の間で良好なバランスを提供し、リアルタイムのPDF生成と操作に適しています。開発者は、パフォーマンス要件に基づいて、圧縮を適用するタイミングとコンテンツを非圧縮のままにするタイミングについて、情報に基づいた判断を下すことができます。

互換性と標準準拠: FlateDecodeはPDF仕様で最も広くサポートされている圧縮方式の1つであるため、そのLZ77基盤を理解することで、開発者は、コンテンツを解凍して分析やテキスト抽出を行う必要がある、さまざまなビューア、プロセッサ、アクセシビリティツール全体で確実に動作するPDFを作成できます。

LZ77圧縮は、入力データをスキャンして繰り返しシーケンスを探すスライディングウィンドウメカニズムを通じて動作します。

スライディングウィンドウ構造: このアルゴリズムは2つのバッファーを維持します。最近処理されたデータを含むサーチバッファーと、符号化される今後のデータを含む先読みバッファーです。圧縮が進むにつれて、両方のウィンドウが入力ストリームを前方にスライドします。

パターンマッチング: 入力の各位置について、LZ77はサーチバッファー内で先読みバッファーのデータと最も長く一致するものを検索します。一致が見つかると、エンコーダーはリテラルバイトを出力する代わりに、トリプル（一致までの後方距離、一致の長さ、次のリテラル文字）を出力します。

符号化プロセス: 圧縮された出力は、これらの後方参照タプルと一致しないリテラルバイトが混在したもので構成されます。例えば、「the document」というフレーズがデータ内で500バイト後に再び現れる場合、LZ77は12文字すべてを再び格納する代わりに、(500, 12)のような参照と後続の一致しない文字を格納します。

PDFでの実装: PDFのFlateDecodeフィルターでは、LZ77圧縮はDEFLATEアルゴリズムでハフマン符号化と組み合わされます。LZ77フェーズは長さ-距離ペアとリテラルバイトを生成し、それらがハフマン木を使用してさらに圧縮のために符号化されます。結果として得られるビットストリームが、stream/endstreamキーワード間のPDFファイルに格納されます。

解凍: 解凍は単純で高速です。デコーダーは各タプルを読み取り、すでにデコードされた出力内の指定された距離から指定されたバイト数をコピーし、リテラル文字を追加します。このシンプルさにより、LZ77解凍はPDFリーダーにとって特に効率的です。

• FlateDecode – LZ77とハフマン符号化を組み合わせたDEFLATE圧縮を実装するPDFフィルター
• Content stream（コンテンツストリーム） – LZ77ベースの方式で圧縮される可能性のあるページ記述命令を含むPDFストリームオブジェクト
• Filter（フィルター） – FlateDecodeなどの圧縮アルゴリズムを含む、ストリームデータのエンコードまたはデコードのためのPDFメカニズム
• Stream object（ストリームオブジェクト） – 辞書とそれに続くバイナリデータで構成され、さまざまなフィルターを使用して圧縮できるPDFオブジェクト
• Lossless compression（可逆圧縮） – 一部の画像フォーマットで使用される非可逆圧縮とは対照的に、元のデータの完全な再構築を可能にする圧縮方式