4 ms·

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 paramet

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)