Revaz BukhradzeおよびKirill Perminovとの共同執筆
1.はじめに
オフラインメッセージングは現在、最も人気のあるコミュニケーション方法の1つです（ 1、2、3 ）-視聴者のコミュニケーション方法とその成長のダイナミクスによって判断します。
同時に、メッセージ交換の重要な要件は常に、送信されたメッセージと受信されたメッセージの完全な対応です。つまり、データ転送によってデータ自体が不可逆的に歪められることはありません。 自然な欲求-お金を節約する-は、データの自然な冗長性を削除し、保存および送信されるファイルの量を最小限に抑えるデータ圧縮アルゴリズムの作成につながりました。
明白なデータ回復を保証する最大の達成可能な圧縮ボリュームは、情報理論に関するC.シャノンの仕事によって決定され、一般に、冗長なだけでなく意味情報も削除すると元のメッセージを一意に復元することができないため、乗り越えられません。 場合によっては正確な回復を拒否することは重要ではなく、重要ではない要素の損失が正当化されるグラフィック 、 ビデオ 、および音楽データを効果的に圧縮するために使用されますが、一般的な場合、データの整合性はそのサイズよりもはるかに重要です。
したがって、興味深い質問は、情報理論の規定に違反することなく、最良のデータ圧縮で達成できる最小量よりも少ない量のメッセージを送信できるかどうかです。
2.例
したがって、情報転送の機能を調べることができる例を分析してみましょう。 また、情報交換参加者の「英語」の伝統でアリスとボブを呼び出すのが慣例ですが、新年の前夜には、より親しみのあるメッセージング愛好家、それぞれマトロスキンとシャリックを使用します。
メッセージmとして、「 , , !
「。 単一文字エンコーディングの長さ-len（m） -34バイト。
メッセージの長さが、その中の情報の量よりも著しく大きいことに気付くかもしれません。 これは、最初に10文字ごとにメッセージから削除し、（元のメッセージから）9回ごとに削除することで確認できます。その後、4回ごとに削除します。結果は次のようになり , !
「-26バイト。 したがって、「ミステリー」の程度は徐々に増加しますが、それが何であるかを推測するために、それは非常に簡単になります。 さらに、Yandexはこの魅力を認識しています。
母音とスペースの一部を破棄することにより、意味を維持しながらメッセージの長さをさらに大幅に短縮できます。「 ,, !
-21バイト、検索エンジンはそのようなスペルに対応していませんが、フレーズを復元することは難しくないことは注目に値します。
情報エントロピーの概念により厳密に定義されたこのメッセージの情報量I（m）を見ると、このメッセージで送信される情報量は約34 * 4.42 / 8 = 18.795バイトであることがわかります。 ここで：4.42ビット/文字はロシア語の1バイト（ 4、5 ）の平均情報量であり、8はビットからバイトへの変換です。 これは、データ圧縮の最良の方法を使用して、MatroskinからSharikへのメッセージの送信に少なくとも19バイトを費やす必要があることを示しています。
さらに、19バイト未満で損失なしに必要なメッセージを送信することは不可能であるという逆も事実です（K. Shannon、情報理論とサイバネティックスの研究、外国文学、モスクワ、1963年）。 .458。
3.さらなる考慮事項
ただし、続けましょう... MatroskinとSharikに追加情報kといくつかの関数を持たせ、そのうちの1つはm '= E（k、m）で、追加情報kと元のメッセージmの共通部分を計算します 
2番目のD（k、m '）= mはEの逆です。 さらに、シャノンが決定した情報量は次の条件を満たす。 
。 したがって、次の2つの条件が満たされるように、上で定義した関数E（k、m）と* D（k、m '）のペアを作成できた場合：
、 
これは、受信者間で情報を転送するために、元のメッセージに含まれる情報よりも少ない情報が必要になる場合があることを意味します。
この場合、これらの関数の定義により、情報理論の記述の違反はないという事実に注意を払う価値があります。
ハッシュで伝えられた情報の置き換えを提供する同様のアルゴリズムはネットワーク交通最適化システムで活発に使用されます 。 ただし、この場合、前述のアルゴリズムとは対照的に、このタイプの最適化を効果的に使用するには、少なくとも1回のデータ送信が必要です。
自然言語のメッセージには情報量よりも大きなデータ量が含まれているため、 算術コーディングなどの冗長性を効果的に排除するアルゴリズムのいずれかを使用して元のメッセージを事前圧縮するとします。
圧縮操作m '= Ar（m）の適用を示します。 
。 事前に圧縮されたメッセージに対して上記で定義された関数Eを使用すると、受信者間で送信されるデータ量と送信される情報量の両方が、元のメッセージのデータ量と情報量よりも少ない場合があります。
つまり、一般化：可逆変換D（k、E（k、m））= mがあるという仮定の下で、 
冗長性除去操作を使用すると、元のメッセージの対応するパラメーター（長さlen（m）および情報量I（m） ）を超えないボリューム内の情報量および量を転送できます。
一般に、機能を選択するだけです... ..