3 ms·

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

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

sgtnoodle 4y ago
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.
- RaisingSpear 4y ago
  > 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.
- xxs 4y ago
  >He is using a hash table rather than a linear search after all. LZW uses a hash table too (traditionally with a prime based capacity)
dataflow 4y ago
> 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.
- selcuka 4y ago
  > flip through all possible states of those n bits How do you do that in one pass?
  - dataflow 4y ago
    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...
  - fdupress 4y ago
    Hash the input (O(n)), search for a second preimage (very much not O(n) if you use a cryptographic hash).
- CJefferson 4y ago
  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.
- aardvark179 4y ago
  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.
  - HelloNurse 4y ago
    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.
vintermann 4y ago
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)
- AbrahamParangi 4y ago
  Sure but n^2 in block size is still linear in data length.

sgtnoodle 4y ago

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.

RaisingSpear 4y ago
> 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.
xxs 4y ago
>He is using a hash table rather than a linear search after all. LZW uses a hash table too (traditionally with a prime based capacity)

dataflow 4y ago

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

selcuka 4y ago
> flip through all possible states of those n bits How do you do that in one pass?
- dataflow 4y ago
  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...
- fdupress 4y ago
  Hash the input (O(n)), search for a second preimage (very much not O(n) if you use a cryptographic hash).
CJefferson 4y ago
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.
aardvark179 4y ago
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.
- HelloNurse 4y ago
  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.

vintermann 4y ago

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)

AbrahamParangi 4y ago
Sure but n^2 in block size is still linear in data length.