私はいくつかの背景を見てみましょうスペース

Question

ためtriboolsの配列を最適化：

「tribool」と私は、次のいずれかの値を保持できる変数を理解する：true、falseまたはnull。

Copying array of ints vs pointers to boolsの質問では、OPはできるだけ小さいトリブール（多かれ少なかれ）の配列を持ちたいと思っていました。

最も基本的なbit-fuでは、トリブールごとに2ビットを使用し、OPの64個のトライブアの配列を16バイトに格納することができました。これは問題ありません。

• ブールのAは、 "nullまたはnullでない"
• ブール値Bが "真または偽でない場合はnull" を意味意味：私が使用

  tribool力学は次のように、シンプルでした。

---

しかし、私は思った...「ビット」のalgorithmical定義は次のとおりです。

ビットは、2つの等しく可能性の高いイベントの条を特定する情報の量であります発生する。

明らかに真偽値は1ビット大きくなります。 2つの真偽値は全体として2ビット大きくなります。

私たちの概念的なトリブールはどうですか？

私のポイントは：含まれている情報のサイズに関して、トライブルは1ビットより大きく2ビットより小さいです。

• 正当化1：上記のようにifブール値を実装するものとします。 boolean Aが "null"の場合、boolean Bの値は冗長であり、関連する情報は保持されません。
• 正当化2：これは、1つtriboolに2つの独立したブール値からの情報を格納することは不可能ですので、持っている

（上記のいずれも正式な証拠はありませんが、私は私たちがいることを同意することができると信じています」 1ビットより厳密に大きく、2よりも厳密に小さいtriboolのサイズ」）

---

私の質問は次のとおりです。

プログラム的triboolが少ないを持っているという事実を利用する方法2ビットよりも情報があり、ソフトウェアで実装する（c、C++？）N個のトライブアの配列は、いくつかのN？ビットに対してN/4バイトより小さいメモリフットプリントを持ちます。

はい、私は、このような実装は実際にハードウェアに優しいものではなく、冗長性を備えた一般的なソリューション（OPの質問に示されているもの）よりも遅く実行することを理解しています。効率化ではなく、スペースを最適化してみましょう。

明らかに、この実装では、boolのペア（前述のようにそれ自体は冗長です）とは異なるトリブリプレゼンテーションが必要です。理論によれば、その目標を達成することが可能であり、私は実際の実装を見たいと言います。何か案は？

Answer 1

あなたの直感は正しいです、これは確かに可能です。これは基本的にはarithmetic codingの形式、または少なくとも単純なインスタンスです。

これを考える最も簡単な方法は、「トリブール」の配列をベース3の数字としてエンコードすることです。 0 =偽、1 =真、2 = NULL。そして、次の配列：

{TRUE, FALSE, NULL, NULL, FALSE, FALSE, TRUE} 

は、あなたが通常の方法で進数に変換することができます番号

1022001 

にエンコード：各triboolはLNを占める

(1*3^0)+(0*3^1)+(0*3^2)+(2*3^3)+(2*3^4)+(0*3^5)+(1*3^6) = 946 

（3）/ln（2）ビット（約1.58）なので、この方法を使用すると、32ビットのトライブを32ビットで格納できるため、N=20アレイを4バイト（ここではN/4は5）に格納できます。

Answer 2

このソリューションでは、あなたが持っている "nullでない"値の数を知っておく必要があります（つまり、コンパイル時や空きスペースを作る前に）。

その後、次のようにそれをエンコードすることができます：1または真または偽のために0に続いて、非ヌルのためにヌル 1のため

0。

これは、トリブールごとに最大2ビット、すべてがnullの場合は1ビットになります。

Answer 3

はすることはでき（LaTeXのような表記のかlog_M（N^X））

ln(N^X)/ln M 

M-状態で、理論的にパックX N-状態変数変数。進数で格納し、トライステート変数の場合、上記の式は次のようになります。

ln(3^N)/ln 2 

8ビットのバイトでは、たとえばあなたは5トライステート変数を合うことができます。

これらの値のアンパック/修正は、変数をより密にパックするほど、はるかに難しく、遅くなります。上記の例では、1つのトライステート変数を変更するためにバイト全体を再計算する必要があります。

5つのトライステート変数のバイトは、スペース効率が非常に高いことに注意してください。密度は110バイトではなく、111トライステートの値に収まる22バイトのパックが得られるまで、同じバイトごとに変わりません。

これは、1つのバイトに4つのトライステート値を直接格納する場合と比較して、余計な作業が必要ですか？

Answer 4

@psmearsが正しい場合は、3つの値がすべて同じである可能性があります。 しかし、それらが等しくないか、独立していない場合は、文字列が十分に長い場合は、2ビットまたは他のコーディングを使用してgzipを実行してください。理論上の限界まで圧縮する必要があります。 すべての値が0であった場合と同様に、文字列の長さのログよりもはるかに大きくなるはずです。

ところで、私たちはエントロピーについてここで話しています。この場合の簡単な定義は、-P（0）logP（0）-P（1）logP（1）-P（null）logP（null）です。したがって、例えば、P（0）= P（1）= 1/2、およびP（ヌル）= 0の場合、エントロピーは1ビットである。 P（0）= 1/2、P（1）= 1/4、P（0）= 1/4の場合、エントロピーは1/2 * 1 + 1/4 * 2 + = 1ビット。確率が1022/1024,1/1024,1/1024の場合、エントロピーは（ほぼ1）*（ほぼ0）+ 10/1024 + 10/1024であり、これは20/1024または約2の1/10にほぼ等しいビットの！より明確なものがあれば、それが発生したときの情報が少なくなるため、必要なストレージが少なくなります。

Answer 5

私は@psmearsによって提案された解決策が気に入っていますが、その欠点は直接的なアプローチよりも遅いことです。

3 ** 5 == 243、つまりほぼ256です。つまり、1つのバイトで5つのtribool値を簡単に絞り込むことができます。圧縮率は同じですが、各バイトは独立しているため、LUTを使用して実装できます。

unsigned char get_packed_tribool(unsigned char pk, int num) 
{ // num = (0..4), pk = (0..242) 
    return LUT[num][pk]; // 5*243 bytes of LUTs 
}; 

unsigned char update_packed_tribool(unsigned char old_pk, int num, int new_val) 
{ // new_val = 0..2 
    return old_pk + (new_val - LUT[num][old_pk])*POW3_LUT[num]; 
};