UMEHOSHI ITA TOP PAGE COMPUTER SHIEN LAB
（構想時の初期情報はここを参照）
[UMEHOSHI ITA]での録音データをUSBのHOSTに送信する際、 115200bpsのCDC(Communication Device Class)を介して行うので、転送能力が足りません。
この転送能力を補うための圧縮として開発しましたが、連続データであれば他の用途でも利用できます。
さて音のように連続的なデータの場合、前に変換した値に対して次のタイミングのデータの変化量に注目すると、情報量が少ないケースが多いと予測できます。
このアルゴリズムは、直前のデータとの変化量を、必要なサイズのビット長で記憶させる方式です。
よって、変化が少ないほどに圧縮率が上がります。逆に直前のデータとの変化量が大きすぎる場合は圧縮しません。
当然ですが、連続するデータの変化量に応じて記憶に必要なビット長が変化する箇所に、ビット長切り替えのデリミタが必要になります。
このビット長の変化時ごとにビット長を切り替えると、切り替えを知らせるデリミタの埋め込みが多くなり、圧縮効果が得られません。
効率よく圧縮するために、ちょうど良いまとまりで適切なビット長に切り替えるデリミタを埋め込む必要があります。
このアルゴリズムはそのビット長の切り替えタイミングと埋め込み手法を解決するための方策を示したものです。
上述は直前のデータとの差分を短いビット数で記憶する考え方ですが、他に重複して多く出現するデータを参照する添え字を埋め込む技法も併用しています。
圧縮データ対象は、符号なし整数の連続データで固定ビット長のリストに記憶されているものとして解説します。
この要素の固定ビット長を、ここでは[ベースビット長]と呼びます。
後述の試作ソースでは、「ベースビット長」を16ビットとしています。
圧縮データは、ヘッド部とボディ部に分けることができます。
ボディ部には圧縮対象の順番であるまとまりのデータが並びます。
このデータのまとまりを種類で分類して各ブロックを命名して、そのサイズと意味を次の通りとします。
| ブロック名 | 記号 | 説明 |
|---|---|---|
| 「基準データブロック」 | BAB | 元データと同じ[ベースビット長]の「最大分解能のデータブロック」です。
最初のブロックはこの「基準データブロック」に決まっており、続く「切り替えブロック」で続くブロックの数が
分かるようになっています。 （この「基準データブロック」のデータサイズは圧縮対象のデータと同じものとなり、圧縮されていないデータとなります） |
| 「データ差分ブロック」 | DAB |
直前のデータの変化量を記憶させます。つまり符号ありの差分情報で、[ベースビット長]より小さいビット長で記憶します。
「切り替えブロック」が出現するまで、同じサイズのビット長の「データ差分ブロック」が続きます。 より小さいビット長で、より多くの「データ差分ブロック」が連続して続くことで、効率よい圧縮が可能となります。 |
| 「切り替えブロック」 | CHB |
「データ差分ブロック」や「基準データブロック」に切り替える場合と、別途に記憶する辞書データの添え字指定にも使われます。 「切り替えブロック」で次のブロックが連続する個数が分かるようになっており、この仕組みで次の「切り替えブロック」を読み取れます。 |
以下で、前述のブロックが並ぶボディ部の圧縮データ例を、ブロックの記号を使って示します。
BAB CHB DAB DAB DABにCHB DAB DAB DAB DAB CHB BAB BAB
CHB DAB CHB
最初のBABの取り出して、最初の値を復元します。
次でCHBで、後述のDABのビット長と、そのサイズのビット長が連続に並ぶ個数が分かるようになっています。
つまり、CHBの出現後は次のCHBが出現するまで同じビット長のブロックが並ぶことになります。
このように、CHBの出現数が多いのでCHBのビットサイズを小さくしなければ効率良い圧縮ができません。
以上より、このCHBの仕様を下記のように３つの種類に分けて決めています。
|
[CHB]先頭部が0b001〜0b110である場合、その値はこの後に続くブロックのビットサイズです。
そしてこの3bit直後に5ビットの固定領域があります。(合計8bit固定のCHBです。) 3bitが意味する値は1から6ですが、これを添え字のように使ってビット長のテーブル内の実際のビット長を指定します。 続く固定5ビット領域の値は、後に続く[DAB]または[BAB]の個数で(0〜31)の値です。 この個数の[DAB]または[BAB]の並びの直後に、次の[CHB]が存在しなければなりません。 固定5ビット領域の個数が0でデータの終了を意味します。 （最後のブロックは、この個数ゼロの[CHB]です。） CHBの後に[DAB]と[BAB]のどちらが並ぶかは、3bitが0b110であれば[BAB]、そうでなければ[DAB]が並びます。 （先頭部3bitが0b110のビット長の時は、続くデータブロックが「ベースビット長のBAB」となります） |
|
[CHB]の先頭部が0b111である場合、
直後に辞書テーブルの添え字を指定する5ビットの固定領域と、
後に続く[DAB]または[BAB]の個数を指定する5ビットの固定領域があります。(合計3＋5＋5=13bitの固定長のCHBです。) この指定個数が0であれば最後のブロックを意味します。 この指定個数が0であれば、直後がCHBとなります。 辞書テーブル指定用ビットは5bitなので、辞書テーブルへの登録は最大32個しか登録できません。 なお、辞書テーブルへ登録する一つのデータは、[ベースビット長]の倍数の可変長サイズとします。 |
|
[CHB]が0b000である場合、現在のビット長を維持したまま、
この直後に32個の[BAB]または[DAB]が並ぶことを意味します。 つまり、この特別な3bitの[CHB]だけで、同じビットサイズが32個並ぶ延長指定ができるということです。 |
ヘッド部の仕様を次のように決めました。 （[CHB]やアルゴリズムの補足説明も示します）
[Ver] [BB] [B5] [B4] [B3] [B2] [B1] [B0] [DT_NUM] 「 [DTD0] [DTD1] ・・ [DTD31] 」
上記の[B5] [B4] [B3] [B2] [B1] [B0]の部分が「ビット長のテーブル」で、
それぞれが[BB]で示すビット長です。
[Ver]のデータは1ビット長で0に決まっています。
ビット長を記憶する[BB]の記憶域は4ビット固定です。
そして[B5] が「ベースビット長」に決まっており、
以降の[B0]まで順次に小さいビット長の数になっています。
このビット長を指定するのが、0b001〜0b110の添え字で始まる[CHB]です。
0b110が[B5]の内容のビット長を意味します。
そして、0b101が[B4]、0b100が[B3]
、0b011が[B2]、0b010が[B1]、
0b001が[B0]の記憶内容のビット長を意味します。
5bit固定長の[DT_NUM]が辞書テーブルの登録数で、
「[DTD0] [DTD1] ・・ [DTD31]」の部分が辞書テーブルのデータです。
([DTD0]〜[DTD31]のいずれかを先頭部が0b111である[CHB]の直後の5bit添え字で参照します。)
辞書テーブルのデータは『[ベースビット長]に対する倍数値』を表現する情報を先頭とするデータです。
『[ベースビット長]に対する倍数値』は、要素先頭が0の1ビットから始まる倍数値は１、
要素先頭が10の２ビットから始まる場合は倍数値が2、要素先頭が110の３ビットから始まる場合は倍数値が3、
要素先頭が1110の４ビットから始まる場合は倍数値が4、・・・・と要素先頭ビットで倍数値を指定します。
UME連続可逆圧縮 の動作を、簡単なデータの具体例で示します。
[40000, 34000, 29000, 30000, 36000, 35000, 30000, 31000 ]
の16ビットの連続データの場合です。
短すぎるので圧縮にはなっていませんが、次のように変換されます。（ がヘッダー部です。）
ヘッダー以外は縦に並べて説明
[Ver=0:1bit] [BB=5:4bit] [B5=16:5bit] [B4=15:5bit] [B3=13:5bit] [B2=11:5bit] [B1=9:5bit] [B0=7:5bit]
[DT_NUM=1:] [0b0, DTD0=30000:1+5=6bit]
[BAB=40000:16bit] ：先頭データの生データ
[CHB=0b100:3bit,2:5bit] ：ヘッダーのB4で15ビット長に変更で、後続に２個並ぶ
[BAB=-6000:15bit] ：前の40000の値に対して、-6000なので、34000のデータを意味する
[BAB=-5000:15bit] ：前の34000の値に対して、-5000なので、29000のデータを意味する
[CHB=0b111:3bit,0:5bit,2:5bit] ：8bit固定の辞書CHBで、0の添え字で30000の値で、後続に２個並ぶ
[BAB=6000:15bit] ：前の30000の値に対して、6000なので、36000のデータを意味する
[BAB=-1000:15bit] ：前の36000の値に対して、-1000なので、35000のデータを意味する
[CHB=0b111:3bit,0:5bit,0:5bit] ：8bit固定の辞書CHBで、0の添え字で30000の値で、後続に0個並ぶ
[CHB=0b011:3bit,1:5bit] ：ヘッダーのB3で13ビット長に変更で、後続に１個並ぶ
[BAB=1000:15bit] ：前の30000の値に対して、1000なので、31000のデータを意味する
[CHB=0b011:3bit,0:5bit] ：ヘッダーのB3で13ビット長に変更指示であるが、後続が0個なのでデータの終了を意味する
UME連続可逆圧縮 の開発の補足説明
上記例から分かるように、CHBの埋め込みが多いと圧縮できません。
ビットサイズを変化しないで連続的に記憶できる個数をパラメタ（Block.SBC_NUMB）で指定して、
この個数だけ記憶可能な小さいビットサイズが求められる場合だけ、
ビットサイズを変更するCHBを使います。
辞書テーブルを参照する先頭部が0b111のCHBのサイズは、3＋5＋5＝13bit固定になっています。
よって、小さいビット長区間でこれを使うと、サイズが逆に大きくなってしまいます。
(置き換え対象となるビットサイズは、ある程度大きくないと効果がないので、そのサイズをDuplicateCount.DC_BSIZEで決めています)
また辞書参照CHBへの置き換えるブロックは、サイズ変更が存在しない所にだけを対象とします。
過去の検討初期では、辞書参照[CHB]の直後に固定数の同じビット長データブロックを並べる仕様になっていました。
その場合、[CHB]が8bit固定長の小さいサイズで参照できるからです。
ですがそのの場合、辞書参照可能なデータが限られ、別途にビット長指定の[CHB]が必要になるため、効率よい圧縮ができませんでした。
よって最終的に、辞書参照[CHB]に直後に並ぶデータ個数を5ビットで指定する仕様に変更しています。
そして、参照する辞書テーブルを１ワードでなく、Nワードを参照できるように変更しました。
これにより、辞書テーブルの操作が複雑になりますが、大きな重複範囲が見つけられれば、効率よく圧縮できます。
ですが、辞書テーブルを作るために2パスになって、リアルタイム圧縮の実装が難しいと考えられます。
そこで、辞書を参照しない1パスの処理も可能なように作るのが良いと考えます。
このアルゴリズムのpythonモジュールのソースをそこに示します。