5

確率 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理論が示唆するように)。

この配列をさらに圧縮できるかどうかを知る必要があります。

4

2 に答える 2

2

データについて何も仮定せずに56ビットを55に圧縮すると、55ビットの出力を取得し、すぐに再び54ビットに圧縮できます。これは不可能に見え、アイデアは永久機関に似ています。ここでのタスクは、何が私たちがそれ以上圧縮するのを妨げるのかを確認することです。

可能なすべてのデータ値のサイズを縮小することが保証されているデータについての仮定がなければ、ロスレス圧縮アルゴリズムを使用することはできません。鳩の巣原理だけで次のことがわかります。nビットを使用すると、2^n個の値を表すことができます。n-1ビットを使用すると、2 ^(n-1)個の値のみを表すことができます。したがって、元の値の半分をエンコードする場合、次の値は、すでにエンコードされている値の1つと同じビットを使用してエンコードする必要があるため、情報が失われます。もちろん、元のデータで使用する値が2 ^(n-1)未満の場合は、そのデータのサイズを少し(またはそれ以上)小さくすることができますが、これはすでにデータについての仮定を行っています。さらに、そのアプローチを使用して、データのサイズを損失なく再帰的に縮小することはできません。

したがって、配列をビット単位で圧縮する方法を見つけることができますが、これは、現在の圧縮方法で可能なビットパターンの最大半分を使用している場合に限られます。ただし、これは配列を圧縮するためのあいまいな方法である可能性があり、確かにいくつかのkビットのビットパターンの半分以上を使用します。このkがしきい値になり、サイズをこれ以上小さくすることはできなくなります。

また、配列を多くの部分に分割し、各部分を個別にエンコードすることの利点は何ですか。

配列を小さな部分に分割すると、局所的な差異が少なくなるため、数値間の差異を表すために使用するビット数が少なくなる可能性があります。したがって、[1、2、3、4、2 ^ 30、2 ^ 30 + 1、2 ^ 30 + 2、2 ^ 30 + 3]のような配列では、スペースを節約できます。ただし、新しい絶対値を表すには、より多くのビットを使用する必要があります。これらも、スペースを節約するために、任意の絶対値までの距離として表すことができます。しかし、場合によっては1ビット節約するために、あなたが概説したすべての努力が本当に価値があるかどうかはわかりません。

要約すると。[2 ^ 30、2 ^ 30 + 1、2 ^ 30 + 2、2 ^ 30 + 3]のような配列がある場合は、数値の差をとることで明らかにスペースを節約できますが、すでに述べたようにあなたの答え、場合によってはデータのサイズが大きくなります。したがって、nビット未満を使用して数値の配列を(仮定せずに)格納する圧縮アルゴリズムを使用することはできません。ここで、nは配列内の数値の対数の上限の合計です。

于 2012-04-07T10:22:28.670 に答える
2

この取り組みの目標は、データ サイズを少なくとも 1 ビット削減することです。

これは、すべての入力に対して可能ではありません。さまざまな表現でビットを適切に数えたり、間違いを犯したり、修正したりするために多大な労力を浪費する可能性があります。実際に行う必要があるのは、ケースの数を数えることだけです。

2^k の可能な入力があります。ここで、k は入力のビット数です。すべての単一入力の k-1 ビット表現があると信じているとしましょう。次に、2^(k-1) の可能な表現があります。次に、これらの 2^(k-1) 表現のすべてをデコンプレッサにフィードすると、明らかに 2^(k-1) の結果しか得られません。他の 2^(k-1) の可能な入力が実際にはありません。表現からこれらの欠落した入力を生成する方法はありません。つまり、実際には表現が可能な 2^k 入力のすべてをカバーすることはできません。それらの少なくとも半分はカバーされていません。

于 2012-04-07T20:26:33.177 に答える