2
$\begingroup$

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.

$\endgroup$
21
  • 2
    $\begingroup$ What is the definition of "optimal"? What is wrong with storing the N-bit string as a N-bit string? $\endgroup$
    – D.W.
    Nov 30, 2022 at 18:17
  • 3
    $\begingroup$ That's because your question has nothing to do with complexity (since you already know that). You're asking how to implement it. That fits more in StackOverflow. You can also ask algorithmic questions there. $\endgroup$
    – justhalf
    Dec 1, 2022 at 7:31
  • 1
    $\begingroup$ Also, in real computer, an N-bit string doesn't exist in isolation. If it's stored in a disk/memory, then we need to be given the address of the starting bit somehow, and this shouldn't be considered part of the N-bit string, nor should it be considered a disadvantage of the computer. The given encoding utilizes this fact, and asymptotically reach the optimal bound when N goes larger. If you want to go lower level than the filesystem, then it's even more specific, since only very few people care about that, probably in embedded systems. $\endgroup$
    – justhalf
    Dec 1, 2022 at 7:32
  • 2
    $\begingroup$ Wouldn't any HTTP parser/encoder be an answer to this question? For example, a request might contain the text "Content-Length: 17" followed by 2 newlines followed by 17 bytes of data. So you have log(N)+constant overhead to store N bytes in a self-delimiting way. (I'm yet another programmer that's kinda confused by this question) $\endgroup$
    – Navin
    Dec 1, 2022 at 7:36
  • 2
    $\begingroup$ A "real" computer is going to lose space to OS/filesystem page size, plus any journaling done by the filesystem, any duplication due to RAID etc, and maybe any block issues in disk firmware. If that's too real, you can write your own OS and use the algorithm you already specified... $\endgroup$
    – BurnsBA
    Dec 1, 2022 at 13:59

3 Answers 3

1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ @domotorp I know this answer isn't actually code, but I hope it addresses your underlying intuition that computers use more memory than necessary to simply store the data they contain. If this is an unacceptable form for an answer and you still want some code (though technically any program running on a modern computer/os is going to be subject to most of these forms of wasted memory), I can take it down $\endgroup$
    – Blackhawk
    Dec 9, 2022 at 23:42
  • $\begingroup$ If you argue about a lower bound, then of course I don't want a code, in fact, this is exactly the kind of thing I was curious about (though many parts of your answer I find irrelevant). $\endgroup$
    – domotorp
    Dec 10, 2022 at 6:55
  • $\begingroup$ @domotorp which parts interest you specifically? Perhaps I could prune the irrelevant bits and link better resources for the relevant ones $\endgroup$
    – Blackhawk
    Dec 14, 2022 at 15:33
  • $\begingroup$ It's all right, don't worry about it, as I'm not interested in the details so much. $\endgroup$
    – domotorp
    Dec 14, 2022 at 15:35
  • $\begingroup$ I might amend this slightly to make the point that cost is a large factor. The layers of cache I mentioned are separate pieces of hardware from main memory RAM, and they are vastly more performant than RAM which is why they are used to do the "readahead" caching for the CPU: the coversation between CPU and L1,2,3 cache is much faster than between CPU and RAM. The natural question is, "Why not use L1 cache technology for RAM if it's so much faster?" and the answer is 1. prohibitive cost and 2. insufficient bus speed. $\endgroup$
    – Blackhawk
    Dec 14, 2022 at 15:40
8
$\begingroup$

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$.

$\endgroup$
18
  • 1
    $\begingroup$ This sounds familiar from what I learned in college, as far as being asymptotically optimal, but there is a small improvement you can make, to improve the concrete amount of space it uses very slightly. Instead of encoding the actual x_k in bits, you should offset it so you don't have any redundant encodings. For example, if 100 through 111 represent 0-3 (I assume), then it's redundant for 010100 though 010111 to also be 0-3. (And what does 000 represent? That prefix can never appear, and that encoding space is wasted.) $\endgroup$ Dec 1, 2022 at 4:58
  • 1
    $\begingroup$ @domotorp, I don't understand. If I have misunderstood your question, please edit your question to clarify what you are asking. Of course the encoding in my answer can be used in real computers. I'm not sure what distinction you are trying to draw between real computers vs theoretical models. If you already know of some answer, it would help to state of approaches you've already considered and why you rejected them, in the question, so that people don't waste time repeating something you already know. $\endgroup$
    – D.W.
    Dec 1, 2022 at 5:58
  • 8
    $\begingroup$ @domotorp which part of the encoding is still too theoretical for you? From this answer I can easily write a code to encode and decode numbers using this encoding. That's real enough for me. The numbers can be placed next to each other in the memory as well (that's the whole purpose of the encoding), so the theoretical limit is achieved. This encoding stores the length of the data, so once it has read that amount of bits, the next bit starts a new number. $\endgroup$
    – justhalf
    Dec 1, 2022 at 6:25
  • 4
    $\begingroup$ @domotorp I am a professional software engineer. This answer describes a representation format specification in sufficient detail and precision that, based solely on this answer and my general programming knowledge, I would easily be able to implement it in any programming language I am proficient in. What more do you want? $\endgroup$
    – Douglas
    Dec 1, 2022 at 6:36
  • 3
    $\begingroup$ @domotorp This isn't done in practice (that I know of) because it doesn't really serve a practical purpose that isn't better served with existing methods for storing data. And you're on the wrong site if you're looking for someone to write code for you. $\endgroup$
    – NotThatGuy
    Dec 1, 2022 at 12:15
4
$\begingroup$

You can achieve N+2log2N 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.