私はバイトエンコーディングの世界に非常に慣れていないので、単純な概念を間違った方法で使用/表現している場合は、すみません (そして、ぜひ訂正してください)。
可変バイトエンコーディングを理解しようとしています。ウィキペディアの記事 ( http://en.wikipedia.org/wiki/Variable-width_encoding ) と、情報検索の教科書の本の章を読みました。10 進整数をエンコードする方法を理解していると思います。たとえば、整数 60 に可変バイト エンコーディングを提供したい場合、次の結果が得られます。
1 0 1 1 1 1 0 0
（上記が間違っている場合はお知らせください）。スキームを理解したとしても、情報がどのように圧縮されているかは完全にはわかりません。通常、整数を表すために 32 ビットを使用するため、60 を表すと1 1 1 1 0 026 個のゼロが前に付いてしまい、代わりに 8 ビットだけで表すのではなく、そのスペースを無駄にするのでしょうか?
明確にしていただきありがとうございます。
それを行う方法は、ビットの 1 つを予約して、「私はその値で終わっていない」ことを意味することです。通常、これが最上位ビットです。
バイトを読み取るときは、下位 7 ビットを処理します。最上位ビットが 1 の場合、読み取るバイトがもう 1 バイトあることがわかり、現在の 7 ビットに次の 7 ビットを追加してプロセスを繰り返します。
MIDI 形式は、その正確なエンコードを使用して、次の方法で MIDI イベントの長さを表します。
たとえば、値 0x80 はバイト 0x81 0x00 を使用して表されます。この 2 バイトでアルゴリズムを実行してみると、正しい値が得られることがわかります。
UTF-8 も同様に機能しますが、予想されるバイト数を通知するために、もう少し複雑なスキームを使用します。これにより、取得しているバイトが要求された長さと一致するかどうかを簡単に判断できるため、エラー修正が可能になります。ウィキペディアはそれらの構造を非常によく説明しています。
あなたは頭に釘を打ちました。
エリアス コーディングの特殊なケースであるガンマやデルタなど、多くのエンコード スキームがあります。これらは、使用したバイト レベルのコードとは対照的に、ビット レベルのコードであり、小さい数値に対して強い偏りがある場合に役立ちます (これは、絶対値ではなくデルタをエンコードすることで実現できます)。
最新のほとんどの CPU には「最上位ビット」命令と「最下位ビット」命令がありますが、ビットレベルのエンコード方式はバイトレベルの方式よりも実装がはるかに難しく、追加の CPU 負担が、読み取るデータが少ないことによって節約される時間を上回る可能性があります。ビットレベルのコーデックのパフォーマンスを劇的に向上させます。CPU の速度が RAM の速度を追い越し続けるにつれて、バイトレベルのコーデックの単純さも大きな要因ですが、ビットレベルのスキームがより魅力的になるでしょう。
はい、その通りです。4 バイトではなく 1 バイトを使用してエンコードすることでスペースを節約できます。通常、エンコードする値が元の固定幅エンコードに収まる最大値よりもはるかに小さい場合、メモリを節約できます。