Information Theory For Hash Code

用 Fake coin hypothesis 思考 information theory 如何使用非 constructive method to prove things.

好像 information theory 在此不重要

Major Reference

book.pdf (inference.org.uk) from MacKay 是經典 information theory textbook.

Shannon 的信息論 (Information Theory) 包含兩個部分:

Information Theory	Source Code	Noisy Channel Code	Hash Code
Entropy	Information = Self-entropy H(X)	Channel capacity = Max Mutual Information max I(X;Y)
Application	Compression	Communication	Info Retrival
Shannon Theory	Source coding theorem	Channel code theorem

下圖顯示 block diagram of the information retrival 應用。

完整 database 包含：

$S$ : number of records $\mathbf{x}^{(1)}, \cdots, \mathbf{x}^{(s)}$, e.g. $S \simeq 2^{23} = 8.3M$
$N$ : record length of $\mathbf{x}^{(i)}$, e.g. $N \simeq 200$ bits
假設每一個 record 都是唯一沒有重複

我們的目標是建立一個 hash table 用於 retrieve the database.

Hash function 計算 $\mathbf{h}(\mathbf{x}^{(i)})$ 產生 $M$-bit hash codes, $M \ll N$ , 但 $2^M \gg S$ 組成 hash table.

Hash table 包含：

$M$: hash code length, e.g. $M \simeq 30$ bits
Size of hash table $T = 2^M$, e.g. $2^M \simeq 2^{30} > S$, 例如 10X bigger than $S$

Hash code 可視為每個 record 的指紋 (fingerprint) 或是 key, hash table 比原來的 databse 小很多，同時具有“唯一性”。通過比較小的 hash table, 可以存取 database.

注意此處我們沒有假設 database sequence 是不變的。database record 可能會增加 (appendix), 刪除 (delete), 插入 (insert)。不然可以只用 index number 就可以 access the database.

Information retrival use hash table 對於 cache, hard drive, 區塊鏈都非常有用。

問題是

其實這個問題有點像 data compression 問題。可以視為把完整的 database 壓縮成 hash table 但保存其中的 information.

實務的 Hash function

Security: 有些 hash code 不希望 reverse, 因此會要求相似 records 的 hash code 要差異很大。
Similarity: 這裡剛好和 security 相反。有些 hash code 反而希望保持 neightborhood distance, 類似 isometric. 如果 records 的距離很近，hash code 距離也要很近。

我們看幾個簡單的 hash function

Division method: 就是把 $\mathbf{x}$ 直接除以 $T$ (a prime number bigger than database size) 的餘數。
- 注意如果 x 的 binary values 是 random, 所以餘數也是 random 分佈。