壓縮包含與0相同數目1的1和0的字符串

我有一個1和0的字符串，其中1和0的數目是相同的。我想將它壓縮成一個數字，這個數字在存儲它所需的位數方面較小。另外，在壓縮表單和非壓縮表單之間轉換不需要很多工作。壓縮包含與0相同數目1的1和0的字符串

例如，排序所有可能的字符串並將它們編號並讓這個數字成爲壓縮數據將會是太多工作。

一個簡單的解決方案是允許壓縮數據只是字符串長度爲n的字符串的前n-1個字符。壓縮和解壓縮數據之間的轉換將很容易，但是這隻提供很小的壓縮，每個字符串只有一個位。

我想要一個算法，可以壓縮一個字符串與此屬性（相同數量的1和零），可以推廣到一個字符串與任何甚至長度。我還希望它比上面描述的方法壓縮更多。

感謝您的幫助。

2016-05-17 mathew

「例如，排序所有可能的字符串並將它們編號並讓這個數字成爲壓縮數據將是太多工作。」將二進制字符串轉換爲整數是工作太多了？ – Blorgbeard

[Java單線程]（http://stackoverflow.com/questions/17833463/how-do-you-convert-a-binary-number-to-a-biginteger-in-java） – Blorgbeard

不，但要排序所有可能的字符串都是太多的工作。例如，假設字符串的長度爲10，那麼可以將0000011111作爲第一個字符串，以便將其壓縮爲0，第二個可能爲0000101111等等。在這些之間進行轉換將是很多工作。按照您的建議將二進制字符串轉換爲整數將不會壓縮數據，但仍會佔用相同數量的位。 – mathew

這是一個組合問題，一次取N個項目。

在您的評論中，作爲長度10的例子，每次取5，意味着只有252個獨特模式。它可以放入一個8位的值，而不是一個10位的值。請參考：WIKI: Combinations

從0-251擴大索引值，這裏還有例子：

SEE：Algorithm to return all combinations of k elements from n

提取時，您可以使用提取的值設置在重建的位位置值，即每次擴展O（1）次。如果列表不是數以百萬計，則可以預先計算查找表，將索引值轉換爲解碼值會快得多。 IE：建立所有可能的列表，並查找翻譯。

來源

2017-06-21 17:38:08

壓縮包含與0相同數目1的1和0的字符串

回答

相關問題