壓縮不斷增加的唯一整數序列

Question

我有一個從0到2^16-1 = 65535的雙字節整數序列。 它們被排序，所以序列總是在增加，並且沒有重複。

這個序列通常有大約270〜500個數字。如果它更密集（即> = 32768個元素），我可以保存不在序列中的數字，但那不是這種情況...現在，這是挑戰，我必須使用小於6位的整數進行壓縮（一般）！

我最好的猜測是使用Bloom Filters。以這種方式，爲了解壓縮序列，我必須遍歷從0到65535的所有整數，詢問它們是否處於設置狀態。但我不知道如何處理誤報。我可以將它們存儲起來，但恐怕會佔用太多數據。

Answer 1

平均每個整數不能少於6位。您可以計算從65536組中挑選270或500個事物的方法數量，無需重複，並確定代表挑選所需的位數分別爲9.34位和8.46位。

如果您從65536中挑選2721個或更多，那麼您可以用6位或更少來表示它們。