Protobufを勉強していたら、良いアルゴリズムを見つけました - ZigZag

[[434311]]

もともと Protobuf の原理を勉強したかったのですが、研究の過程で Protobuf が負の数をエンコードするときに ZigZag アルゴリズムを使用していることがわかったので、この記事を書きました。もちろん、Protobuf を理解していなくても、読むのにまったく影響はありません。

このアルゴリズムについて説明する前に、基本コードと補数コードについて説明しましょう。理解できたら下を指さしてください。

コード:

https://github.com/miaogaolin/gofirst/tree/main/zigzag

ベース

いわゆるベースとは、特定のビットの情報がいっぱいになったときに、それを前方に移動する必要があることを意味します。たとえば、10 進法では、ある位置の数が 10 に達すると繰り上がりが行われ、2 進法では、ある位置の数が 2 に達すると繰り上がりが行われます。

キャリーは相互に変換できます。例:

10進数: 10 → 2進数: 1010 → 16進数: A

以前、「なぜ 10 進法がより一般的に使用されているのですか?」という回答を見たことがあります。

人間には 10 本の指しかなく、正確に 10 個の数字を数えることができるため、10 進法が自然とデフォルトのシステムになります。人間に 11 本の指があるなら、おそらく 11 進数になるでしょう。

その後、コンピュータの登場により、データの有無が最も自然な情報伝達単位となり、0と1からなる2進数が自然にコンピュータの数値体系となりました。これを基に、情報の利用を容易にするために、8進数と16進数が採用されました。

さて、バイナリシステムについて言うべきことは以上です。

3つのこと

次に、10 進数の正の整数を 2 進数で表します。たとえば、10 進数の 10 は 2 進数の 1010 に等しくなります。

バイナリが負の数を表す場合はどうなるでしょうか?降りてきて話しましょう。

コンピュータの世界では、オリジナルコード、リバースコード、補完コードの概念が定義されています。説明を簡単にするために、1 バイト (1 バイト = 8 ビット) を使用して数値を表すと仮定します。

1. オリジナルコード

最初のビットは符号（非負数の場合は 0、負数の場合は 1）を表し、残りのビットは値を表します。例えば：

+8 → オリジナル: 00001000

-8 → オリジナル: 10001000

2. 逆コード

最初のビットは符号を示すために使用され（非負の数の場合は 0、負の数の場合は 1）、残りのビットは非負の数の場合は変更されず、負の数の場合はビットごとに反転されます。例えば：

+8 → オリジナル: 0000 1000 → リバース: 0000 1000

-8 → オリジナル: 1000 1000 → リバース: 1111 0111

整数のバイナリを表現するために元のコードまたは補数コードを使用する場合、何か問題がありますか?表面的には問題ないように見えます。しかし、よく考えてみると、2 つの問題があることがわかります。

まず、0 は実際には +0 と -0 の 2 つのコードで表すことができます。

オリジナル: 0000 0000 → 1000 0000

逆順: 0000 0000 → 1111 1111

第二に、コンピュータは符号ビットの存在を認識しないため、計算後に奇妙な現象が発生します。

オリジナルコード

1 + (-1)

→ 0000 0001 + 1000 0001

→ 1000 0010

→ -2

これは明らかに間違っています!

逆コード

1 + (-1)

→ 0000 0001 + 1111 111

→ 1111 1111

→ -0

これも変な感じですね。

そこで、これらの問題を解決するために、コンピュータシステムに補完コードを導入しました。

3. 補完

最初の桁は符号を示すために使用し（非負の数の場合は 0、負の数の場合は 1）、非負の数の残りの桁は変更されず、負の数の場合はビットごとに反転され、最後の桁に 1 が追加されます。

+8 → オリジナル: 0000 1000 → 追加: 0000 1000

-8 → オリジナル: 1000 1000 → 追加: 1111 1000

次に、計算に記号を導入すると何が起こるかを見てみましょう。

1 + (-1)

→ 0000 0001 + 1111 1111

→ 0000 0000

→ 0

明らかに、この方法では、コンピュータが計算を実行するときに、符号の問題を心配する必要がなく、すべての計算は、2 がいっぱいになると 1 を追加するという規則に従って処理されます。

さて、これで基数と補数に関する知識はすべて終わりです。それでは本題に入りましょう。

ジグザグ

ほとんどの場合、使用する整数は小さい傾向があります。

システム通信中の送信を容易にするために、基本的な送信タイプとして整数 (int32、int64) が必要になることがよくあります。

したがって、ほとんどのシステムでは、4 バイトと 8 バイトで表されます。このように、整数 1 を送信するには、「00000000 00000000 00000000 00000001」の 32 ビットを送信する必要がありますが、貴重なデータは 1 ビットだけであり、残りは無駄になります。

ではどうすればいいでしょうか？ ZigZagアプリケーションが誕生しました。では、このアルゴリズムの具体的なアイデアは何でしょうか?

正の整数の場合、データを送信するときに、冗長な 0 を削除するか、意味のない 0 を可能な限り削減します。それで、データを圧縮できますか?ではどうやって圧縮するのでしょうか?

答えも非常に簡単です。たとえば、数字は 00000000 00000000 00000000 00000001 です。 1 ビットまたは 1 バイト 00000001 のみを送信すると、無駄なデータが大幅に削減されますか?

もちろん、世界に正の整数しか存在しないのであれば、これは簡単に実行できます。残念ながら、彼は実際にはマイナスの数を持っています!負の数をどのように表すのでしょうか?

たとえば、-1 の 10 進補数表現は 11111111 11111111 11111111 1111111 です。

ご覧のとおり、最初の部分はすべて 1 です。どうすればよいと思いますか?

ZigZag は非常に巧妙な方法を提供します。前に述べたように、補数コードの最初のビットは符号ビットであり、先頭の 0 を圧縮することができません。そのため、この符号ビットを補数コードの最後に配置し、他のビットを 1 ビット前方に移動します。

補足: ** 1 **1111111 11111111 11111111 11111111

→ 符号シフト: 11111111 11111111 11111111 111111** 1 **

しかし、それでも圧縮するのは難しいです。したがって、このアルゴリズムは、負の数のすべてのデータビットをビットごとに反転し、符号ビットは変更せずに、次のように整数を取得します。

小数点: -1

→ 補足: ** 1 **1111111 11111111 11111111 11111111

→ 符号シフト: 11111111 11111111 11111111 1111111** 1 **

→ ジグザグ: 00000000 00000000 00000000 0000000** 1 **

負でない整数の場合、符号ビットは末尾に移動され、他のビットは 1 つ前方に移動されますが、データは次のように変更されません。

小数点: 1

→ 補数: ** 0 **0000000 00000000 00000000 00000001

→ 符号シフト: 00000000 00000000 00000000 0000001** 0 **

→ ジグザグ: 00000000 00000000 00000000 0000001** 0 **

このように、正の数、0、負の数はすべて同じように表現できます。小さな整数を圧縮することはできますか?

したがって、次のコードを記述できます。

関数 int32ToZigZag(n int32) int32 { 
 
 (n << 1 ) ^ (n >> 31 )を返す
 
 }

n << 1 は値全体を 1 つ左にシフトし、値の最後の桁は正数、0、負数のいずれであっても 0 になります。説明は次のとおりです。

小数点: 1

→ 補数: ** 0 **0000000 00000000 00000000 00000001

→ 1ビット左にシフト: 00000000 00000000 00000000 00000010

小数点: -1

→ 補足: ** 1 **1111111 11111111 11111111 11111111

→ 1つ左にシフト: 11111111 11111111 11111111 11111110

n >> 31 は符号ビットを最後に配置します。負でない数値の場合はすべて 0 になり、負の数値の場合はすべて 1 になります。説明は次のとおりです。

小数点: 1

→ 補数: ** 0 **0000000 00000000 00000000 00000001

→ 31ビット右シフト: 00000000 00000000 00000000 0000000** 0 **

小数点: -1

→ 補足: ** 1 **1111111 11111111 11111111 11111111

→ 31ビット右シフト: 11111111 11111111 11111111 1111111** 1 **

最後のステップは巧妙なもので、2 つの値に対してビット単位の XOR 演算を実行します。

小数点: 1

→ n << 1 ：00000000 00000000 00000000 00000010 ^

n >> 31 : 00000000 00000000 00000000 0000000** 0 **

→ 00000000 00000000 00000000 0000001** 0 **

最終結果を確認できます。データビットは変更されず、符号ビットも変更されませんが、符号ビットは最後のビットに移動します。

小数点: -1

→ n << 1 ：11111111 11111111 11111111 11111110 ^

ｎ >> 31 ：11111111 11111111 11111111 1111111** 1 **

→ 00000000 00000000 00000000 0000000** 1 **

ご覧のとおり、データビットはすべて反転されますが、符号ビットは変更されずに最後のビットに移動します。このステップは本当に巧みに書かれています!

ZigZag 復元コードは次のとおりです。

 toInt32関数(zz int32) int32 { 
 
 int32(uint32(zz)>> 1 )^-(zz & 1 )を返す
 
 }

同様に、復元されたコードを逆に記述することもできます。ただし、ここで注意すべき点は、右にシフトする場合は符号なしシフトを使用する必要があることです。そうしないと、最初の桁が 1 の場合、シフト時に 1 が追加されます。したがって、符号なしシフト演算 uint32(zz)>>1 が使用されます。

さて、このアルゴリズムを使用すると、先頭に 0 が付いた整数を取得できます。ただし、データは依然として 4 バイトを使用して保存されます。次に、バイト数をできるだけ減らして復元する方法を検討する必要があります。

たとえば、上記のアルゴリズムに従って 1 を変換すると、次のようになります: 00000000 000000000 00000000 00000010。

先頭の 0 をすべて省略して、2 ビット (10) または 8 ビット (00000010) のみを送信すればよい場合が最適です。データ転送はバイト単位で行われるため、単位は 8 ビットのままにしておくのが最適です。したがって、2 つのアプローチがあります。

次の有効なバイトの長さを示すために、追加のバイトを追加できます。例: 00000001 00000010。最初の 8 ビットは、次に送信するバイトが 1 つあることを示し、次の 8 ビットは実際のデータを示します。この方法では望ましい効果が得られますが、不可解なことに余分なバイトの無駄が追加されます。無駄を避ける方法はあるでしょうか？

バイト自己表現方式。 ZigZag は、バイトがそれ自体を表現する方法を導入します。具体的にはどうすればいいのでしょうか？コードを見てみましょう。

関数compress(zz int32) []バイト{ 
 
 var res []バイト  
 
サイズ := バイナリ.Size(zz) 
 
 i := 0の場合; i < サイズ; i++ { 
 
 (zz & ^ 0x7F ) != 0 の場合{ 
 
 res = append(res,バイト( 0x80 |(zz& 0x7F ))) 
 
 zz = int32(uint32(zz) >> 7 ) 
 
 }それ以外{ 
 
 res = append(res,バイト(zz& 0x7F )) 
 
壊す  
 
 } 
 
 } 
 
戻り値
 
 }

まず、コード内の ^0x7F を見てみましょう。これは一体何でしょうか?

^0x7F: 11111111 11111111 11111111 10000000

下から 8 番目から始まる数字で、上位の数字はすべて 1 です。その機能は、最後の 7 桁を削除した後に情報があるかどうかを判断することです。

この関数に ZigZag 値を渡すと、この関数は値を下位から上位まで 7 ビットのグループに分割します。上位ビットに有効な情報がある場合は、7 ビットに 1 ビット (0x80) が追加されます。このプロセスは、先頭の 0 がすべて揃うまで繰り返され、その後アルゴリズムは終了します。

例えば：

小数点: -1000

→ 補数: ** 1 **1111111 11111111 11111100 00011000

→ ジグザグ: 00000000 00000000 00000111 1100111** 1 **

まず、上記の数字を 7 桁のグループに分けます: 0000 0000000 0000000 0001111 1001111。

詳細な手順は次のとおりです。

^0x7F との AND 演算の結果にはまだ上位ビットの情報が含まれているため、下位 7 ビットを取り出して、最後から 8 番目のビットに 1 (0x80) を追加します: 11001111。

この数値を 7 ビット右にシフトすると、0000 0000000 0000000 0000000 0001111 になります。

次に、最後の 7 ビットを取り出し、^0x7F との AND 演算を実行します。上位ビット (すべて 0) には情報がないことがわかります。次に、最後の 8 ビット (00001111) を完全に取り出し、ループから抜け出してアルゴリズムを終了します。

最終的に、2バイトのデータ[11001111, 00001111]が取得されます。

上記の手順により、4 バイトの ZigZag 変換された数値が 2 バイトのデータに変換されました。ネットワーク経由で送信する場合は、これらの 2 バイトを他のプロセスに直接送信します。他のプロセスがデータを受信した後、データを組み立てて復元できます。具体的な復旧作業は以下のとおりです。

関数 decompress(zzByte [] byte ) int32 { 
 
 var res int32 
 
 i , offset := 0 , 0 ; i < len(zzByte); i, offset = i+ 1 , offset+ 7 { 
 
 b := zzByte[i] 
 
 (b & 0x80 ) == 0x80の場合{ 
 
 res |= int32(b& 0x7F ) << オフセット
 
 }それ以外{ 
 
 res |= int32(b) << オフセット
 
壊す  
 
 } 
 
 } 
 
戻り値
 
 }

全体のプロセスは圧縮の逆です。各バイトについて、まず最上位ビットが 1 (0x80) かどうかを確認します。ある場合は、それが最後のデータバイトパケットではないことを意味するため、このバイトの最後の 7 ビットをアセンブリに使用します。それ以外の場合は、最後のバイトに到達したことを意味します。その後、アセンブリ後にループが終了し、アルゴリズムが終了します。最終結果は 4 バイトの整数になります。