ビッグデータにおける圧縮：種類と技術

\

はじめに

本記事では、ビッグデータにおける圧縮について、圧縮のタイプと方法を取り上げて説明します。また、各タイプと方法をなぜ、いつ使用すべきかについても解説します。

\

圧縮とは何か?

一般的な英語の定義によると、圧縮とは何かをより小さなスペースに収めるように縮小することを指します。コンピュータサイエンスにおいて、圧縮とはデータをより小さなサイズに縮小するプロセスです。この場合のデータは、テキスト、音声、動画ファイルなどで表現されます。コンピュータのハードドライブに保存するあらゆるもの、つまり異なる形式で表現されたデータと考えてください。より技術的な定義を提供すると、圧縮とはより少ないビット数を使用するようにデータをエンコードするプロセスです。

\ データを圧縮する理由は複数あります。最も一般的で直感的な理由は、ストレージスペースを節約することです。その他の理由は、データが小さくなることによるものです。小さなデータを扱うメリットには以下が含まれます:

1. データ転送時間の短縮:圧縮されたデータはサイズが小さく、送信元から送信先への転送時間が短縮されます。
2. 帯域幅消費の削減:この理由は、データ転送の高速化という利点と強く関連しています。圧縮されたデータはネットワーク帯域幅の使用量が少なく、スループットが向上し、レイテンシが低減されます。
3. データに大きく依存するデジタルシステムのパフォーマンス向上:これは、データ処理に依存するシステムで明らかです。これらのシステムは、処理が必要なデータ量を削減することでシステムのパフォーマンスを向上させるために圧縮を活用します。なお、これはシステム固有のものであり、適切な圧縮技術の使用に依存することに注意してください。圧縮技術については、本記事の後半で説明します。
4. コスト効率:クラウドサービスはデータの保管に対して料金を請求します。より少ないストレージを使用することで、特にビッグデータシステムにおいてコスト削減が実現されます。

\ 圧縮のその他の理由は、異なる圧縮技術と形式に依存します。一部の暗号化アルゴリズムは圧縮の方法として使用できます。そうすることで、前述のデータ圧縮の理由にセキュリティ層が追加されます。さらに、一般的な圧縮形式を使用することで、統合目的で外部システムとの互換性と拡張性の余地がもたらされます。

\ 圧縮の理由は利点のように聞こえることに注意する価値があります。しかし、圧縮にはトレードオフがあります。圧縮の一般的なトレードオフの1つは、解凍の必要性であり、これはリソースが制約されたシステムにとって懸念される可能性があります。その他のトレードオフは、使用される圧縮技術とデータのタイプに依存します。

\

圧縮タイプ

データを圧縮するために使用されるさまざまな技術について説明するために、まず圧縮を2つの主なカテゴリに分類します。次に、各カテゴリに関連する技術について説明します。圧縮は大きく非可逆圧縮と可逆圧縮に分類できます。

\ 名前が既にその意味を示しているように、非可逆圧縮技術は、データの完全な忠実性を保持しない技術です。簡単に言えば、一部のデータは破棄されますが、データが表すものが認識できなくなるほどではありません。したがって、非可逆圧縮は、これから紹介する可逆圧縮と比較して、非常に高いレベルの圧縮を提供できます。

\ 非可逆圧縮の特徴は、それが不可逆的であること、つまり、圧縮されたファイルが提示されたときに、元の忠実性で生データを復元できないことです。特定のファイルとファイル形式は非可逆圧縮に適しています。通常、画像、音声、動画に使用されます。たとえば、JPEG形式の画像は圧縮に適しており、JPEG画像を圧縮することで、作成者または編集者はどの程度の損失を導入するかを選択できます。

\ 一方、可逆圧縮は可逆的であり、圧縮されても、すべてのデータが保持され、解凍時に完全に復元されることを意味します。これは、可逆圧縮がテキストのようなファイルに適しており、データウェアハウスとレイクハウスの世界では、使用する唯一の関連タイプであることを意味します。一部の音声(FLACおよびALAC)および画像ファイル(GIF、PNGなど)形式は、この圧縮タイプでうまく機能します。

方法の選択

一般的に最良の圧縮方法はありません。ケースバイケースで、どの方法が適しているかを選択するには、さまざまな要因が関係します。これを例で補強すると、保存されている表形式データを扱う金融業界のデータエンジニアは、正確なレポート作成においてデータの欠落による影響があるため、可逆圧縮を使用する傾向があります。あるいは、画像を圧縮してウェブサイトを軽くすることで読み込み項目を削減し、多くの画像があるウェブページを最適化する場合、非可逆圧縮が適しているかもしれません。したがって、ビジネス要件に沿った最も適切な圧縮方法を決定するために評価を実施することが重要です。

圧縮技術

このセクションでは、非可逆圧縮と可逆圧縮の両方の一般的な圧縮技術のみを取り上げます。これは決して網羅的なものではないことに注意してください。さらに、説明される技術には、さまざまな研究に裏付けられた、パフォーマンスを向上させるための若干のバリエーションがある場合があります。

可逆圧縮技術

3つの一般的な可逆技術は、ランレングス符号化(RLE)、ハフマン符号化、およびLempel-Ziv-Welch技術です。

\ ランレングス符号化:RLEは、繰り返されるデータのシーケンスを単一のデータとそのデータのカウントで置き換えるようにデータをエンコードすることに基づいています。繰り返されるデータの長い実行に効果的です。また、低レベルから高レベルのカーディナリティにソートされたディメンション(フィールド)を持つデータセットは、RLEの恩恵を受けます。

\ たとえば、AAAAABBCDDDのような単純な文字列を取ります。RLEはデータをA(5)B(2)C(1)D(3)に圧縮します。より実用的にするために、以下の画像のテーブルを見てください。

\ 図1 - RLE前。フィールドのカーディナリティレベルが左から右に増加していることを観察することが重要です

図2 - RLE後

RLEは繰り返されるフィールドの実行に依存し、2番目の例では、データのカーディナリティとソート順に依存するため、item列のMouseレコードは、前の列がすべての値をIT, MouseとHR, Mouseに分割するため、単にMouse (3)に圧縮することはできません。TIFF、BMPなどのビットマップファイル形式など、特定のファイル形式はRLEと互換性があります。ParquetファイルもRLEをサポートしており、S3やGCSなどのオブジェクトストレージを使用する最新のデータレイクハウスで非常に便利です。

\ ハフマン符号化:これは、生データで発生する頻度に基づいて、生データの値に可変長コードを割り当てる統計モデリングに基づいています。このモデリングの表現は、ハフマン木と呼ばれ、二分木に似ています。次に、この木を使用して、生データの各値のハフマンコードを作成します。アルゴリズムは、最も頻繁に出現する値を可能な限り少ないビット数でエンコードすることを優先します。

\ RLEの例で使用したのと同じデータAAAAABBCDDDを取りましょう。対応するハフマン木は次のようになります。

\ ハフマン木

木から、文字Aが0で表されていることがわかります。同様にDは10で表されます。文字B: 111およびC:110と比較すると、AとDがより少ないビットで表されていることがわかります。これは、それらの頻度が高いためであり、したがって、ハフマンアルゴリズムは設計上、それらをより少ないビットで表します。結果として得られる圧縮データは00000111111110101010になります。

\ ハフマン符号化はプレフィックスルールを使用します。これは、文字を表すコードが他のコードのプレフィックスに存在してはならないことを述べています。たとえば、有効なハフマンコードは、Cの表現がDのプレフィックスであるため、C: 00およびD: 000を使用して文字cとdを表すことはできません。

\ これを実際に見るために、Computer Science Field Guideには、試すことができるハフマン木ジェネレーターがあります。

\ Lempel–Ziv–Welch符号化:これは1984年にAbraham Lempel、Jacob Ziv、Terry Welchによって作成され、明らかに創設者にちなんで名付けられています😅。RLEおよびハフマン符号化と同様に、LZWは繰り返されるデータを多く含むデータでうまく機能します。LZWアルゴリズムは辞書ベースであり、生データでよく見られるパターンのキーと値のペアを含む辞書を作成します。このような辞書は、コードテーブルとも呼ばれます。この技術がどのように機能するかを説明するために図を使用して、生データをABBABABABAで表すとしましょう。A-Zを可能な値とする構成を使用してアルゴリズムを通過すると、結果のコードテーブルは次のようになります:

\ LZWコードテーブル

上記のコードテーブルから、すべての文字A-Zのキーと値のペア、およびAB、BB、BA、ABAなどのパターンのキーと値のペアがあります。これらのパターンのより短い表現を持つことで、LZWアルゴリズムは生データをより少ないビットにエンコードすることで圧縮できます。したがって、その入力から生成されたコードテーブルを使用すると、圧縮されたバージョンは0 1 1 26 29 28です。圧縮データのスペースに注意することが重要です。それらを文字の終わりと考えることができるため、デコーダは1,0を10として解釈しません。それらは異なる意味を持つためです。

\ LZWは通常汎用であり、今日広く使用されています。多くのUnix/Linuxベースのオペレーティングシステムのcompressシェルコマンドの背後に統合されています。また、LZWと互換性のある一般的なファイル形式は、GIF、TIFF、およびPDFです。LZW圧縮の他のアプリケーションは、NLPにおけるトークン化に関するこの論文で説明されているように、自然言語処理の分野で見ることができます。

\ RLE、ハフマン符号化、およびLZW符号化は、一般的な例にすぎません。可逆圧縮技術は、上記で説明した3つ(3)を超えています。その他の技術には、ハフマンとLZW - 具体的にはLZ77 - 符号化の組み合わせを使用するDEFLATEが含まれます。

非可逆圧縮技術

このセクションでは、2種類の非可逆圧縮を見ていきます。非可逆圧縮は元のデータに損失をもたらし、すべてのデータが保持されるわけではないことを思い出してください。

\ 離散コサイン変換(DCT):この圧縮方法は主に音声、画像、動画ファイルで使用され、ブロック圧縮とも呼ばれます。名前が示すように、数学関数 - コサイン関数 - を使用して、元のデータのブロックを周波数に変換します。データのブロックは通常、8x8、4x4などの行列であり、その順序の大きさです。

\ 圧縮は、数学関数を使用して生データが周波数ドメインに変換された後、データで発生する高周波を処理するときに行われます。圧縮にDCTを使用する全体的なプロセスは次のとおりです:

• 生データをチャンクに分割します。たとえば、画像圧縮では、これは8x8ピクセルになる可能性があります。
• 数学関数を適用して、データのチャンクを周波数に変換します。これにより、いくつかの高周波と低周波が生成されます。
• 次に、導入したい許容可能な損失の程度に応じて、高周波が削減または除去されます。ここで本当に非可逆圧縮になります。
• 表現可能なデータに戻すために、残りのすべての周波数は逆離散コサイン変換 - IDCT - を通過して、周波数からデータを復元します。

\ DCTは今日、圧縮だけでなく信号処理にもさまざまな分野で広く使用されています。DCTと互換性のある一般的なファイル形式は、JPEG(画像)、MP3(音声)、およびMPEG(動画)です。さらに、DCTは高い圧縮率を達成できるため、インターネット上のウェブページのように多くの画像を持つデジタルシステムに適しています。

\ フラクタル圧縮:フラクタルは、異なるスケールで繰り返される自己反復的な無限パターンです。スケール上の任意の点から見たとき、パターンは似ているように見えます。パターンは任意のスケールで類似しているため、フラクタル圧縮は「大きな」フラクタルのスケールを縮小して、データのサイズを縮小します。

\ フラクタルの例

フラクタル圧縮は1980年代にMichael Barnsleyによって導入されました。画像を使用した一般的なアイデアは、画像に似ている部分がいくつか含まれている場合、なぜそれらを2回保存するのかということです。これを行うために、フラクタル圧縮は次のことを行います:

• 画像をレンジブロックとして知られる重複しないブロックに分割します。これは、8x8、16x16ピクセルなどのレンジブロックになる可能性があります。
• 自己反復パターン(フラクタルパターン)の画像をスキャンします。レンジブロックを使用して、アルゴリズムはこれらのレンジブロックに類似した画像のより大きなセクションを見つけます。これらのより大きなセクションは、ドメインブロックと呼ばれます。
• 次に、変換関数がドメインブロックに適用されて、レンジブロックが近似されます。これらの変換関数は、スケーリング、平行移動、回転などの数学関数です。それらは変換とも呼ばれます。これらの変換は、フラクタル圧縮に関してフラクタルコードと呼ばれます。
• 次に、データはこれらの変換関数にエンコードされます。ピクセルごとのデータを保存する代わりに、変換が保存されます。これらの変換は、ドメインブロックから画像を再構築する方法を記述するルールです。

\ フラクタルコードを使用して、画像は反復プロセスを使用して再構築されます。このプロセスは計算コストが高い場合がありますが、フラクタル圧縮は他の圧縮技術と比較して高い圧縮率を達成できます。自己反復パターンへの依存により、そのような自己反復パターンを持つデータでより良いパフォーマンスを発揮します。例としては、風景写真(自然の画像)やDNA画像があります。

\ 離散ウェーブレット変換、量子化など、他の非可逆圧縮技術があります。これらの技術は通常、画像、音声、動画ファイルで使用され、各ファイルタイプの特定のタイプまたはファイル形式 - JPEG、MP3 - に適しています。

\ 非可逆圧縮は一般的に可逆圧縮よりも高い圧縮率を持ち、ユーザーが事前に導入する損失の量を知っていることを期待する場合があります。圧縮方法と技術の選択はいくつかの要因に依存することを強調することが適切です。これらの要因の中核にあるのは、データ形式と望ましい結果です。

TL;DR

全体として、この投稿はデータの世界における圧縮について説明しています。それは、コンピュータサイエンスと情報理論における既存の知識体系に強く依存しています。圧縮するということは、エンティティが占める容量を減らすことを意味し、データの分野では、容量はストレージスペースを指します。デジタルシステムにおける圧縮は、適切に行われた場合、多くの利点があります。明らかなのは、スペースを削減し、より多くのデータを保存する余地を与えることです。その他の利点には、より速い送信、より少ない帯域幅の使用、および上記のシステムの効率の一般的な改善が含まれます。これは適切に行われた場合であることを忘れないでください。

\ 圧縮の利点を活用するには、どのタイプを使用するかを知ることが重要です。圧縮は非可逆または可逆のいずれかです。非可逆圧縮は、通常不可逆的である元のデータに損失をもたらしますが、可逆圧縮はデータを圧縮し、元のデータに含まれるすべての情報を保持します。さらに、ハイブリッド圧縮タイプに関する議論がありますが、非可逆と可逆の組み合わせは単に非可逆だと思います。コメントであなたの考えを教えてください。

\ 最後に、非可逆圧縮と可逆圧縮の両方のためにさまざまな技術が導入されました。技術のリストとこれらの技術の説明は、網羅的でも包括的でもありません。各技術がどのように機能するかについてのアイデアを提供する上で、それらは良いスタートにすぎないと考えています。まとめると、ビッグデータにおける圧縮についてさらに調査し、より深く読むのに役立つ追加のリソースを追加しました。

追加リソース

動画:Data Lake fundamentals - RLE encoding with Parquet in practice

論文:A review of data compression techniques

論文:lossless compression techniques

A concise introduction to Data Compression by David Salomon

論文:A Study of Various Data Compression Techniques

ブログ投稿:Compression in open file formats

記事:Open file formats

記事:Compression in databases

Lossy Compression for Genomic data (RNA)

\