I think almost all compression systems are O(n). All the standard stream compressors are (gz, bz2, 7zip, zstd). I’d have to check png and jpg to make sure they don’t do any non-O(n) global reasoning, but I would be surprised.
I think the author is trying to capture an idea of “simple”, but has misidentified that as O(n). Any algorithm which operates in a single pass on a stream of data and has a fixed upper memory usage is O(n).
You could say his algorithm is 0(n) while others are O(n*m) where m is the size of the window. The window size happens to be a constant in practice, but parameterizing it does seem reasonable from a comparison standpoint. His algorithm works like other algorithms with a window size of 64, but does so more efficiently from an algorithmic point of view. He is using a hash table rather than a linear search after all.
> but does so more efficiently from an algorithmic point of view. He is using a hash table rather than a linear search after all.
Most other compression implementations also use a hash table, at least on the faster settings.
They may switch to something like a hash chain on slower settings, but that doesn't really change asymptotic complexity as it just evaluates more matches.
I don't think any implementation does a straight linear search across the window, as that's just stupidly slow, though maybe a "give me the best compression, I don't care about speed" compressor might.
> Any algorithm which operates in a single pass on a stream of data and has a fixed upper memory usage is O(n).
I think you oversimplified in the other direction? An algorithm can make 1 pass over data (say it's n bits), then flip through all possible states of those n bits, taking exponential time. Or if you consider that to violate having a "fixed" upper bound (not sure this is meaningful in any useful sense, especially given it would probably need at least log(n) bits to know how far it's read its input), consider that it can even loop infinitely if it wants to.
By not reading the input again and just keeping the n-bit counter in unrelated memory, since the actual input is kind of irrelevant for this, only its size. Again, may or may not apply depending on what precisely they meant by a "fixed" additional amount of memory...
Many stream-based compressors don't track how far they have read into their input, they just keep reading bytes, and writing out bytes. Things like zlib can be set up with a fixed sized buffer, and don't go allocating extra memory, so they definately can't start using arbitary extra space.
You are right an algorithm doesn't have to be O(n), as it could enter an infinite loop and never finish.
If it has a fixed upper bound on memory usage then it can’t store all the input to iterate through all the possible bit patterns, at least not for arbitrarily large inputs.
And trying an exponential number of candidate solutions cannot be considered "streaming" through the input: the algorithm doesn't make any real decision until the end is reached.
Compare with algorithms that would like to be omniscient but make decisions at every step in order to produce streaming output and/or to forget old state and old inputs, like Viterbi decoding.
The bzip2 algorithm is, as I recall, quadratic in block size. But that's because of the implementation, ways to do the BWT transform in linear time has been found since. And also, bzip2 doesn't let you choose very big block sizes anyway, it could have supported far larger ones with the memory modern computers have (as opposed to when it was first implemented)
I love the qoi format. I mostly adopted it for the wasm context.
While porting to wasm, using something like stb_image became a little complicated, so I wrote a png-qoi converter, and then use the qoi assets in the game.
Writing a qoi decoder is a fun exercise, though i think most languages have their implementations already.
QOI is confusing simple with primitive. It's worsening compression only due to trauma of using dependencies in C.
I strongly disagree with characterization that JPEG is overcomplicated, especially in a controlled situation where you only need to support files you encode yourself (as is the case with QOI), and not edge cases like Adobe's CMYK extension.
JPEG's design is brilliant for the level of compression it's capable of. libjpeg API is crufty, and C dependencies are a pain, but you can use other implementations and languages.
I'm working at a small company that does computer vision and image processing stuff, doing a lot with embedded systems.
At some point, I was asked to write code to save images on live systems to be downloaded and used for... CV stuff. Also, the images had to be (although weakly) encrypted for IP reasons.
The issue being that those cameras run at 200fps when there's anything of interest and use their compute to do image processing. The flash memory used also isn't made for this kind of write speed.
All that is to say: JPEG is insanely efficient. It takes a moment to compress the image, but only encrypting 10% of the data saves a lot more and the flash memory can keep up way longer than with raw images.
I had to generate some difference images though to convince some CV and management people that we don't need raw images. If our analysis results would depend on a dozen pixels not being off 1-2 gray values, it's broken. There's more noise in every single image than JPEG-induced errors.
JPEG's design is brilliant, that is very true, but it also complicated. It uses a lot of CPU cycles to calculate the FFTs of the signal, and that is where the simplicity of QOK shines, by operating on the signal itself (instead of expensively transforming it to frequency space) it can be order(s) of magnitude faster.
The discussion is not about the quality of the API, but the amount of work an actual machine will have to do to compress/decompress.
DCT is relatively expensive compared to just RLE, but keep in mind that JPEG has been standardized in early 1990s when 33Mhz CPUs were fast. Today a few multiplications are nothing for CPUs. We have fast SIMD implementations. Nowadays Huffman is the bottleneck and could have been improved with tANS coding.
It may help to a limited extent with compression, but the window size is so small it is hardly worth it. I imagine a huge part of the speed of the algorithm is how cache friendly it is. Worse is better sometimes.
1. That an image is expected to be decompressed as a whole, and
2. That an efficient (de)compression is possible with generic compression algorithms.
Both are false. Even PNG does its own filtering, a pretty rudimentary model but much better than just DEFLATE. QOI is much better in this regard because it has a (fixed and also rudimentary) model; it was a clear demonstration that modeling is much important than entropy coding.
Seeing as simple image decoders are still producing CVEs I think it’s worth considering vastly more stupid approaches that get us 80% of the way with 20% of the trouble.
32 comments
[ 3.2 ms ] story [ 65.1 ms ] threadQOI: Lossless Image Compression in O(n) Time (2021-11-24, 293 comments) https://news.ycombinator.com/item?id=29328750
The QOI File Format Specification (2021-12-20, 54 comments) https://news.ycombinator.com/item?id=29625084
QOI – The “Quite OK Image Format” for fast, lossless image compression (2021-12-23, 103 comments) https://news.ycombinator.com/item?id=29661498
QOI – The Quite OK Image Format (2022-04-02, 97 comments) https://news.ycombinator.com/item?id=30885668 [after the official domain has been set up]
I think the author is trying to capture an idea of “simple”, but has misidentified that as O(n). Any algorithm which operates in a single pass on a stream of data and has a fixed upper memory usage is O(n).
Most other compression implementations also use a hash table, at least on the faster settings. They may switch to something like a hash chain on slower settings, but that doesn't really change asymptotic complexity as it just evaluates more matches.
I don't think any implementation does a straight linear search across the window, as that's just stupidly slow, though maybe a "give me the best compression, I don't care about speed" compressor might.
LZW uses a hash table too (traditionally with a prime based capacity)
I think you oversimplified in the other direction? An algorithm can make 1 pass over data (say it's n bits), then flip through all possible states of those n bits, taking exponential time. Or if you consider that to violate having a "fixed" upper bound (not sure this is meaningful in any useful sense, especially given it would probably need at least log(n) bits to know how far it's read its input), consider that it can even loop infinitely if it wants to.
How do you do that in one pass?
You are right an algorithm doesn't have to be O(n), as it could enter an infinite loop and never finish.
Compare with algorithms that would like to be omniscient but make decisions at every step in order to produce streaming output and/or to forget old state and old inputs, like Viterbi decoding.
While porting to wasm, using something like stb_image became a little complicated, so I wrote a png-qoi converter, and then use the qoi assets in the game.
Writing a qoi decoder is a fun exercise, though i think most languages have their implementations already.
I strongly disagree with characterization that JPEG is overcomplicated, especially in a controlled situation where you only need to support files you encode yourself (as is the case with QOI), and not edge cases like Adobe's CMYK extension.
JPEG's design is brilliant for the level of compression it's capable of. libjpeg API is crufty, and C dependencies are a pain, but you can use other implementations and languages.
At some point, I was asked to write code to save images on live systems to be downloaded and used for... CV stuff. Also, the images had to be (although weakly) encrypted for IP reasons. The issue being that those cameras run at 200fps when there's anything of interest and use their compute to do image processing. The flash memory used also isn't made for this kind of write speed.
All that is to say: JPEG is insanely efficient. It takes a moment to compress the image, but only encrypting 10% of the data saves a lot more and the flash memory can keep up way longer than with raw images.
I had to generate some difference images though to convince some CV and management people that we don't need raw images. If our analysis results would depend on a dozen pixels not being off 1-2 gray values, it's broken. There's more noise in every single image than JPEG-induced errors.
TBH that sounds like a job for a video codec.
The discussion is not about the quality of the API, but the amount of work an actual machine will have to do to compress/decompress.
1. That an image is expected to be decompressed as a whole, and
2. That an efficient (de)compression is possible with generic compression algorithms.
Both are false. Even PNG does its own filtering, a pretty rudimentary model but much better than just DEFLATE. QOI is much better in this regard because it has a (fixed and also rudimentary) model; it was a clear demonstration that modeling is much important than entropy coding.
For me, an interesting use-case would be streaming webcam video from my Raspberry Pi.
I have some Raspberry Pi Compute Module 4, and some Raspberry Pi Camera Module 3. Along with some various USB webcams.
I would love to be able to stream video from my RPi CM 4 with the camera 3 modules connected, at the highest possible resolution and frame rate.
Beyond that I would like to stream to many clients at once without too much overhead.
But the initial goal would be to get something with top resolution and frame rate even for just 1 client.
And for that this kind of thing sounds interesting.