Storing N bits on the smallest possible space in a real computer

Question

Update. Since my original question was misunderstood by many, and lead to a lot of debate about various issues, let me try to pose this modified and rephrased question:

Assume that I have a computer with a giant disk that can store $2^{1000}$ bits. Is it possible for any $N<2^{999}$ to write a code in Python for any $N$-long bit string $x$ that prints $x$, such that the code of the program uses at most $N+O(\log N)$ bits of space?

(I'm aware that such a disk cannot exist in our universe.)

Original version.

Because of Kolmogorov/Levin complexity considerations, most $N$-long bit strings require $N+\log N+o(\log N)$ bits to store, since we also need to specify where the sequence ends; see D.W.'s or Rainer's answer for the details.

I wonder what is the most efficient way something like this can be realized on a real computer. What is the optimal way of storing an $N$-long bit string? Can it be done in $N+o(N)$ space?

Please note that this question is about practical methods that can be implemented as a code, not theory! You can pick your favorite programming language, Python, C++, assembly etc.

Answer 1

I'll take a swing at answering your question about why a physical machine might use more memory than the theoretical optimum. The schemes described by Rainer P. and D.W. can be implemented exactly as then have described; however...

Your assertion that "I don't think it can be done on real hardware" is probably true, but not for theory vs reality reasons (ala a spherical cow in a vacuum) and more because efficiently packing bitstrings is just not the primary goal of actual hardware systems. Real systems care about memory correctness, bandwidth, latency, availability, etc. before they care about storage efficiency.

First, memory is only addressable down to the byte, and since bit twiddling to interact with non-byte-aligned data is probably not worth the performance hit, you'll have to lose some bits to byte alignment.

Next, consider that CPU architectures have a native word size, and so reads/writes and random access perform best when the data is aligned to the word size. Structs generated by C can include multiple bytes of padding even for small structures.

Data in the sense C structs is "records" composed of "fields", and those fields are likely to be fixed length for performance, so if the data in those fields doesn't fill the fields completely, that's wasted space.

Cache is largely invisible to programs, but it's still memory - since the CPU is traditionally orders of magnitude faster than main memory, several layers of cache are used to reduce the latency by "reading ahead", trying to predict what data the CPU might ask for in the near future and saving the eons of time the CPU would otherwise waste blocking for data retrieval - this would probably also count as wasted memory in some sense.

Following from cache into memory itself, consider virtual memory, paging and the Memory Management Unit. When processes interact with main memory, the addresses they use don't have a direct correspondence to where data is stored. Instead they are "virtual addresses" that are mapped by the system into "pages" of physical memory - this is done for several different reasons and worth a read, but my point here is that the virtual memory system has an overhead cost for indexing the pages, similar to a filesystem, with potential additional costs of wasted padding.

Which brings up secondary storage and filesystems. Filesystems are all about tracking blocks of data across a physical drive that comprise files, and about indexing them for structured retrieval (like directory-based filesystems). The files aren't stored as single long blobs of bytes, but as chunks potentially strewn across the physical drive, and each file/chunk requires some indexing overhead. Filesystems often have a native block size that they allocate (e.g. 4096 bytes), so files which are smaller than the block size or not evenly divisible will waste some space.

Next, at a lower layer, physical drives are composed of sectors which use error correcting codes to detect/correct errors and even identify and "disable" bad sectors that no longer store data properly. In both cases, space is wasted to achieve these goals.

Certainly, everything above will waste some space versus the theoretical bitstring packing you asked about, but it's not all doom and gloom: consider that much of the time, data is actually stored MORE efficiently than you propose. Lossy compression for images/video/audio are well established, and generalized lossless compression file archive tools like zip/gzip are fantastic at identifying and exploiting patterns in real world data to achieve remarkable storage efficiency. Video games often achieve pretty insane space efficiency by utilizing procedural generation techniques - consider the 96kb shooter which would have taken 200-300MiB if stored conventionally.

Memory is cheap. Performance is king. I could probably get my hands on a microcontroller or some other simple system that doesn't include many of the bells and whistles above, and I could implement the algorithms mentioned in the other answers (though the bit twiddling to load/store a non-byte-aligned bitstring would be kind of a pain). However from my perspective, the "most efficient way to store data" is actually not to determine and implement the theoretically optimal way to pack bitstrings - it's to wait for hardware engineers invent denser storage.

Answer 2

Represent the string $x$ using the following encoding:

$$0, x_k, \dots, 0, x_2, 0, x_1, 1, x_0$$

where $x_0 = x$, $x_{i+1} = \text{len}(x_i)$ is a binary representation of the length of $x_i$ in bits (namely, $\text{len}(x_i)=\lceil \lg x_i \rceil$, for $i\ge 1$), and $k$ is the smallest $k\ge 1$ such that $x_k \le 3$. In particular, you encode 0 or 1 with a single bit, encode $x_k$ with 2 bits, and encode $x_i$ with $x_{i+1}$ bits.

This requires $N + \lg N + \lg \lg N + \cdots + \log^* N = N + \lg N + o(\lg N)$ bits of space to encode a $N$-bit string $x$.

Answer 3

You can achieve N+2log₂N with a simple algorithm:

1. Write down the binary string.
2. Prefix it with its length.
3. Prefix that with as many zeros as the length is long.

With this encoding, a 20 bit string is encoded as:

00000 10100 XXXXXXXXXXXXXXXXXXXX

Do decode it, count the number of leading zeros (5) and decode as many bits after them (10100 = 20). That's the payload length.