ハフマンコード：例、アプリケーション

現時点では、圧縮の仕組みについてはほとんど考えていません。 過去と比較して、パーソナルコンピュータを使用する方がはるかに簡単になりました。 実際、ファイルシステムを扱う人はすべてアーカイブを使用します。 しかし、彼らがどのように動作し、どのような原則がファイルの圧縮であるかを考える人はほとんどいません。 このプロセスの最初のバージョンは、ハフマンコードであり、さまざまな人気アーカイバで使用されています。 多くのユーザーはファイルを圧縮するのがどれくらい簡単か、それがどのような仕組みで動作するかは考えていません。 この記事では、圧縮の仕組み、エンコーディングプロセスの高速化と簡素化に役立つニュアンス、コーディングツリーを構築する原則について理解します。

アルゴリズムの歴史

電子情報の効率的なコーディングのための最初のアルゴリズムは、20世紀中ごろ、すなわち1952年にハフマンによって提案されたコードでした。 これは現在、情報を圧縮するために作成されたほとんどのプログラムの主な基本要素です。 現時点では、このコードを使用する最も一般的なソースの1つは、ZIP、ARJ、RARなどのアーカイブです。 このハフマンアルゴリズムは、 JPEG画像および他のグラフィックオブジェクトを圧縮するためにも使用される。 まあ、すべての現代のファックスは、1952年に発明されたコーディングも使用しています。 このコードはあまりにも多くの時間が経過して作成されて以来、今日まで、これは最新のシェルと古いタイプと現代タイプの機器に使用されています。

効率的なコーディングの原則

ハフマンアルゴリズムの基礎は、最も可能性の高い最も一般的に遭遇するシンボルを バイナリ システムの コードで 置き換えることができる方式です。 あまり一般的でないものは、より長いコードに置き換えられます。 長いハフマンコードへの移行は、システムがすべての最小値を使用した後にのみ発生します。 この手法を使用すると、元のメッセージの文字ごとにコード全体の長さを最小限に抑えることができます。 重要な点は、符号化の開始時には、文字の出現の確率が既に分かっているはずであるということです。 これらから、最終的なメッセージが作成されます。 これらのデータに基づいて、ハフマンコードツリーが構築され、それに基づいてアーカイブ内の文字をエンコードするプロセスが実行される。

ハフマンのコード、例

このアルゴリズムを説明するために、コードツリーを構築するためのグラフィカルな変形をしましょう。 このメソッドを使用するには効果的でしたが、このメソッドの概念に必要ないくつかの値の定義を明確にすることは意味があります。 ノードからノードに向けられたアークとノードのセットは、通常、グラフと呼ばれます。 ツリー自体は、特定のプロパティのセットを持つグラフです。

• 各ノードでは、1つのアークだけを入力できます。
• ノードの1つはツリーのルートでなければならず、つまり、そこにアークが存在してはならない。
• ルートからアークに沿って移動を開始する場合、このプロセスはノードのいずれかに完全に到達できるようにする必要があります。

ハフマンコードには、ツリーの葉として含まれる概念もあります。 これは弧が逃げるべきでないノードです。 2つのノードが円弧で接続されている場合、それらのうちの1つは親であり、もう1つの子は、円弧がどのノードから来たのか、どのノードにあるのかによって異なります。 2つのノードが同じ親ノードを持つ場合、通常は兄弟ノードと呼ばれます。 リーフに加えて、ノードに複数のアークがある場合、このツリーはバイナリと呼ばれます。 これはまさにハフマンの木です。 この構造のノードの特異性は、各親の重みが、そのノードのすべての子の重みの合計に等しいことである。

ハフマンに従って木を構築するためのアルゴリズム

ハフマンコードの構成は入力アルファベットの文字から行われます。 将来のコードツリーで空いているノードのリストが作成されます。 このリスト内の各ノードの重みは、このノードに対応するメッセージの文字の出現確率と同じでなければなりません。 この場合、未来のツリーのいくつかのフリー・ノードの中で、最も重みの小さいフリー・ノードが選択されます。 同時に、最小指標がいくつかのノードで観測される場合、任意のペアを自由に選択することが可能です。 その後、親ノードが作成されます。これは、このペアのノードの合計が重くなるほど重くなるはずです。 この後、親はフリー・ノードのリストに送られ、子は削除されます。 同時に、アークは対応するインデックス、1と0を受け取ります。 このプロセスは、ノードを1つだけ残すために必要なだけ正確に繰り返されます。 次に、2進数が上から下に書き込まれます。

圧縮効率の向上

圧縮の効率を上げるためには、コードツリー構築時に、ツリーに添付された特定のファイルに出現する文字の確率に関するすべてのデータを使用し、多数のテキスト文書に散らばっていないようにする必要があります。 このファイルを最初に参照すると、オブジェクトから圧縮される文字の頻度の統計をすぐに計算できます。

圧縮プロセスの高速化

アルゴリズムの作業をスピードアップするためには、文字は、特定の文字の出現確率の指標ではなく、出現の頻度によって決定されなければならない。 これにより、アルゴリズムが簡単になり、処理が大幅に高速化されます。 これにより、浮動小数点や除算に関連する操作も回避されます。 さらに、このモードで作業すると、ダイナミックハフマンコード、またはアルゴリズムそのものが変更されることはありません。 これは主に、確率が周波数に直接比例するためである。 ファイルまたは最終的なルートノードの最終的な重みが、処理されるオブジェクト内の文字数の合計と等しくなるという事実に特に注意する価値があります。

結論

ハフマンのコードは、多くの有名なプログラムや企業で使用されているシンプルで長きに渡って確立されたアルゴリズムです。 そのシンプルさと明快さは、任意のボリュームのファイルの圧縮の効果的な結果を達成し、ストレージディスク上に占有されるスペースを大幅に削減することを可能にする。 換言すれば、ハフマンアルゴリズムは、長く研究され、よく設計されたスキームであり、その関連性は今日まで低下しない。 また、ファイルのサイズを縮小したり、ネットワークやその他の方法でファイルを転送したりすることができれば、より簡単に、より速く、より便利になります。 このアルゴリズムを使用することで、構造や品質を損なうことなく、ファイルの重量を最小限に抑えることができます。 換言すれば、ハフマンコードコーディングは、ファイルサイズ圧縮の最も普及した実際の方法であり続けている。