確率 p(a) のイベント a に関連付けられた情報内容は -log(p(a)) であるというシャノンの情報理論を読者が認識していることを願っています。簡単に言うと、0 ~ 7 の範囲の数値を表す必要がある場合は、少なくとも -log(1/8)=log(8) (基数は 2)、つまり 3 ビットが必要です。
0 から 255 の範囲の整数の配列があるとします。配列を 8 ビットの数値として格納する代わりに、最初に配列を昇順で並べ替えます (もちろんバックアップを保持します)。すべての配列要素を 8 ビット整数としてエンコードする代わりに、ソートされた配列内の位置を出力します。問題は、このソートされた配列をデコーダーまたはレシーバーに知らせることです。最初の (最小の) 整数値を 8 ビットの数値として出力し、次にこの数値に加算されるインクリメントを出力します。最初にソートされたすべての配列が続き、その後に要素の順序、つまり位置の値が続きます。
例: 元の配列 -> 231 、 3 、 45 、 0 、 23 、 32 、 78
ソートされた配列 -> 0,3,23,32,45,78,231
エンコードされた情報は 0 (8 ビット num としてソートされた配列の最初の要素)、次に 3 (これは 0 を超える増分)、次に 20、次に 9、次に 13、次に 33、次に 153 です。
最初の数値と連続するデルタを送信した後、注文を送信します。つまり、ここには 7 つの整数があるため、注文には 3 ビットの数値が必要です。3 (元の配列の 0 の位置)、次に 1 (3 の位置)、次に 4 (23 の位置)次に 5(32 の位置)、次に 2(45 の位置)、次に 6(78 の位置)、次に 0(231 の位置)。
つまり、現在の位置の値は 3 、 1 、 4 、 5 、 2 、 6 、 0 です。
このスキームが圧縮されるかどうかを確認するための分析:
最初の数値 -> 8 ビット (最小であるため、実際には必要なビット数が少なくなる場合があります)
次の 6 つの数字 -> 5 ビット (問題は、0、3、20、9、13 を 5 ビットでエンコードできますが、31 (最大 5 ビット) としてエンコードする必要がある 33 と 153 はエンコードできないことです)
それぞれ 3 ビットの 7 つの位置 -> 21 ビット
合計 -> 8+6*5+21=59. これは、それぞれ 8 ビットの 7 つの数値をエンコードするのに必要な 56 ビットを超えており、圧縮よりも拡張を達成しており、いくつかの大きな数値を適切に表現できなかったため、スキームは損失を伴います。
このスキームに複雑さを加えてみましょう。
最初の 0 を 8 ビットの数値としてエンコードし、その直後に最後の数値 231 のコードを送信します。次に、3 のコードを 0 の次のインクリメントとして送信し、次に 153 のコードを送信し、231 のデクリメントを送信し、次に 20、次に 33、9、13 をコードします。
つまり、別の順序で送信しました-> 0,3,20,9,13,33,153 の代わりに、3,153,20,33,9,13 として送信します
これによって得られるのは、ダイナミックレンジの連続的な減少です。0、231、3、153 を送信したことがわかります。この時点で値の範囲が減少します。次の 3 への増分は 20 になり、最後から 2 番目の増分よりも大きくすることはできません。数、つまり 78 であり、数 20 は 75 を超えることはできません (超えた場合、3 番目の数 (3+76(たとえば)) は 78 よりも大きくなり、ソートの仮定に明らかに違反します。
これまでのアイデアを理解していれば、バイナリ検索のアイデアを使用してダイナミックレンジをさらに減らし、この手法を強化するためのさらに改善されたスキームがあります。ここにソートされた配列があります
0 、 3 、 23 、 32 、 45 、 78 、 231
並べ替えられた配列には 7 つの数字があり、中央の数字は 32 であることがわかります。したがって、この 32 を 8 ビットでエンコードし、デルタをプリオーダーで送信します。つまり、32 の次の数値は 3 で、29 (つまり 32-3) としてエンコードされ、次の数値は 78 で 46(78-32) としてエンコードされ、次に 0 が 3(3-0) としてエンコードされ、次に 23 が 20 としてエンコードされます。 (23-3) 次に 45 が 33(78-45) としてエンコードされ、最後の 231 が 153(231-78) としてエンコードされます。
ここで、ケースバイケースで各数値に使用するビット数を決定できます。
ソートされた配列を 32 (範囲 0 ~ 255 の場合 8 ビット)、29 (範囲 0 ~ 32 の場合 6 ビット)、46 (範囲 32 ~ 255 の場合 8 ビット)、3 (範囲 0 ~ 3 の場合 2 ビット) として送信します。 ) ,20(範囲 3-32 で 5 ビット),33(範囲 32-78 で 6 ビット),153(範囲 78-255 で 8 ビット)
したがって、合計で 8+6+8+2+5+6+8=43 となり、これは非損失であり、当初の見積もりである 38 (8 ビット + 5*6 ビット) よりも大きいため、それぞれ 3 ビットの 7 つの位置値が追加されます。全体で 43+21=64 は 56 以上です。私たちのスキームはまだ拡大中です。
21 ビットの位置番号をどのように改善できるでしょうか。位置情報を送信するたびに、送信する位置が 7 つある場合、位置の数は 1 つ減るので、ビット数は log(7)+log(6)+log(5) になります。これは log(fact (7)) すべての対数が 2 を底とするビット。
式 log(a)+log(b)=log(ab) を使用していることに注意してください
これは 12.299 に等しく、これに 43 を加えると 55.299 になり、56 よりも少し低くなります。しかし、これは実用的ではありません。少なくとも 3(範囲 7)+3(範囲 6)+3(範囲 5)+2(範囲 4)+2(範囲 3)+1(範囲 2)+0(範囲 1)=14 が必要です。 with 43 は展開である 57 を与えます。
この取り組みの目標は、データ サイズを少なくとも 1 ビット削減することです。データについて何も仮定せずに 56 ビットを 55 ビットに圧縮すると、55 ビットの出力を取得して、それを再び 54 ビットに圧縮することができます。これは不可能に見え、アイデアは永久機械に似ています。ここでのタスクは、圧縮をさらに進めるのを妨げているものを確認することです。
並べ替えられた配列の 43 ビットが 43 未満になる可能性があるかどうかを確認するために、より大きな配列の例を取り上げて分析する必要があります。また、配列を多くの部分に分割し、各部分を個別にエンコードする利点は何ですか。また、ソートされた配列を表すために必要なビット数を計算する式を見つけることも目標です。つまり、配列サイズと配列要素の範囲が与えられた場合、43 のような数値を見つける方法です。
この 3,1,4,5,2,6,0 を再びソートされていない配列として取り、このシーケンスが 0 から 6 までの 7 つの数値の 5040 個の順列の 1 つであることを観察します。これを 13 ビット数値 (12.299理論が示唆するように)。
この配列をさらに圧縮できるかどうかを知る必要があります。