Binary Representation & Merge Encoding

本文介紹筆者自己定義的名詞 : Merge Encoding ，或許有別的學術名詞 !! 數學概念簡單易懂，用途方便理解集合論，機率論，壓縮紀錄大量的元素等等 :)

在數學上，我們習慣會用  $\{0,1\} = \{ False , True \}$，而且日常生活經驗常構造出高維度子集合

$$s \in  S \subseteq  \{0,1\}^{n}$$
====================================================
例如 : $n = 3$  長相大概像這樣 $$s \equiv (s_1,s_2,s_3) \in S = \{(0,0,1), (1,0,1),.....\} \subseteq \{0,1\}^3$$
====================================================
很明顯 $|S| \leq 2^{n}$，而且 $$\bigwedge_{s \in S}\bigg(\sum_{k=1}^{n} s_k \in [0,n]_{\mathbb{Z}} \bigg)$$

可以把 $n$ 想成物件的集合個數 $|K|$ ，$K$ 為物件集，則 $S$ 相當於選取哪些物件可能的組合，類似背包問題(knapsack problem)的概念。
=====================================================
例如: $(0,1,1)$ 代表選第2個與第3個物件
=====================================================
今想要表達一個物件 $k \in K$ 在集合$S$是可有可無的概念，也就是  $$(s_{k},s_{-k}) , (\bar{s_k},s_{-k})  \in  S$$
其中
$$\bar{s_k} =  \left\{ \begin{array}{ccc} 1 & \text{if }  & s_k = 0 \\  0 & \text{if } & s_k =1 \\  \end{array} \right.  \quad , \quad  s_{-k} \equiv \underbrace{(s_{k'})_{k' \in K-\{k\}}}_{\text{向量}}$$


於是可以使用新的數字 $2$ 來表達此概念 :)   $2 \equiv \{0,1\}$

定義 MergeEncoding ,  $$(s_{k},s_{-k}) \text{ or } (\bar{s_{k}},s_{-k}) \equiv (2,s_{-k})$$
====================================================
例如 :  $S = \{ (0,1,\color{red}{1}), (0,1,\color{red}{0})\} \equiv \{ (0,1,\color{red}{\{0,1\}})\} \equiv \{ (0,1,{\color{red}2}) \}$
====================================================
所以任何 $S \subseteq \{0,1\}^{|K|}$ ，都存在 $S'   \subset  \{0,1,2 \}^{|K|}$
注意:  Merge Encoding 不是函數，$S' \in MergeEncoding(S)$，但是 preimage 是一個函數 !!  $InverseMergeEncoding(S') = S$
白話來說 : 給一個 $S$ 可能有很多種 $S'$ 的表示，給一個 $S'$ 只會有唯一的 $S$ !!
====================================================
例子[*]:
$$S = \{ (1,0,0) , (1,1,0) , (0,1,1) , (1,1,1) \} \equiv \underbrace{\{ (1,0,0) , (1,1,2) , (0,1,1)  \}}_{S'_1} \equiv \underbrace{\{ (1,2,0) ,(2,1,1) \}}_{S'_2}$$
====================================================
有了 Merge Encoding 以後，就可以拿來跟代數意義，集合論/機率論結合

[*] 代數意義:  英文大寫 $= 1$ ，英文小寫 $= 0$
$$Abc  + ABc + aBC + ABC = Abc + AB(C+c) +aBC =  A(B+b)c + (A+a) BC$$

就是分配律啦 ~~ ，項數越少，計算量就越少，如何給定 $S$ 快速找到元素最少的 Merge Encoding  $S^{*} := \underset{S' \in MergeEncoding(S)}{\text{argmin } |S'| }$  是重要的問題 !!

集合論 :
給定一些集合 $\Omega_k$，定義  $$\bigwedge_{k \in K} \bigg( s_k  = 1  \Longleftrightarrow    \omega  \in \Omega_k   \bigg)$$    
於是 $\Omega_{k} \equiv (\overbrace{1}^{s_k},\overbrace{2,...,2}^{s_{-k}})$
==========================================================
例如 :  $|K| = 2$

$\Omega_{1} \cap \Omega_{2}  \equiv (1,1)$
$\Omega_1  \setminus \Omega_2 \equiv \Omega_{1} \cap \bar{\Omega_{2}} \equiv (1,0)$
$\Omega_2 \setminus \Omega_1 \equiv \bar{\Omega_{1}} \cap \Omega_{2} \equiv (0,1)$
$\Omega_{1} \equiv (1,2)$
$\Omega_{2}  \equiv (2,1)$
$\Omega_{1}  \cup \Omega_{2} \equiv \{(1,1),(1,0),(0,1) \}$
全空間 $\equiv \{ (2,2)\}$
==========================================================
機率論:
$P(\Omega_{1} \cap \Omega_{2})  \equiv p_{11}$
$P(\Omega_1  \setminus \Omega_2) \equiv P(\Omega_{1} \cap \bar{\Omega_{2}}) = p_{10}$
$P(\Omega_2 \setminus \Omega_1) \equiv P(\bar{\Omega_{1}} \cap \Omega_{2}) = p_{01}$
$P(\Omega_{1}) = p_{12} = p_{10} + p_{11}$
$P(\Omega_{2}) = p_{21} = p_{01} + p_{11}$
$P(\Omega_{1}  \cup \Omega_{2}) = p_{10} + p_{11} + p_{01} = p_{12} + p_{01} = p_{21} + p_{10} = p_{22} - p_{00}$
$P(全空間) = p_{22} =1$

[檢驗 $S' \equiv S$]
有個必要條件
也就是把 $2$ 全部展開後的元素個數要跟 $|S|$ 相等
  $$S' \in MergeEncoding(S)  \Longrightarrow  \sum_{s' \in S'} 2^{\#} =  |S|$$

其中 : $$\# := \sum_{k \in K}\color{blue}{\underbrace{[s'_k = 2]}_{\text{Iverson Bracket}}} = 2\text{的個數}$$
例如: 例子[*] 分別為 $1+1+1+1 = 1+2+1 = 2+2 = 4$

[小記]
由於筆者對於數字 $2 \equiv \{0,1\}$  比較敏感，有了 Merge Encoding，就更能理解$|K|$維度文氏圖，排容原理(inclusion-exclusion principle)的計算，而非透過集合符號 !! 記得口訣 : 看到 $2$ 就可以展開 $0$ 跟 $1$ !!

[以上純為學術經驗交流知識分享，如有錯誤或建議可留言~~] 

by Plus & Minus 2018.07