Understanding compression/encoding in linear time

Question

I'm reading the paper N. J. Larsson, A. Moffat: Offline Dictionary-Based Compression, which describes a compression algorithm that, if I understand it correctly, is quite similar to Byte pair encoding.

Given a string $S$ of length $n$, I'm trying to understand how one can compress it in linear, $\mathcal O (n)$, time with this compression method. How exactly is this done? I've read the paper, but I still don't understand how they achieve linear time, so maybe I would understand it explained in a different way.

My first confusion arises in the first step in the algorithm, where we find the most common pair, e.g. in abcababcabc the most common pair ab would be replaced by a new symbol, say XcXXcXc. I don't understand how we can find the most common pair quickly enough. My naive approach would be to look first at the first pair ab and then count the number of occurrences, then look at the next pair bc and count the number of occurrences, etc. However this would already give $\mathcal O (n^2)$ just for finding the most common pair once.

Next, even if I understood how to find the most common pair in $\mathcal O(n)$ time. My next problem is that, don't we have to find the most common pair up to $\mathcal O(n)$ times? And hence this would give a total time of $\mathcal O(n^2)$?

Answer 1

I have checked the code, reread the paper and it seems that algorithm is not performing in $\mathcal O(n)$ in the way you have described.
The recursive calls of finding pairs works in $\mathcal O(n \log n)$ divided by constant if you wish to pack it to the end. In fact the structure underneath keeps pointers to the first occurence of pair, splits the queue of pairs by occurences to make it efficient, but still loglinear. On the other hand by analysing the code written by Ph.D. student of the author I have discovered several tricks - the length of pairs (the original name) is given as parameter (default is 2) and the recurrence is limited by parameter, which can discard further calls (default is about 5 levels), with ability to make only one pass or push to the end. The default code runs in $\mathcal O(n)$, but will not yield optimal compression. There is also switch to prefer memory, time or be neutral.

The paper and the code shows usage of hash-table, which runs only in expected constant time, but the function given works very well with characters. Also the code limits the input length by constant hardcoded.

Changing hashtable to suffix tree and rewritting the part of recurrence into bookkeepping partial pairs might yield better results - I am not sure if this is possible to make it $\mathcal O(n)$, this would be probably a different question.

There is also trick used to keep empty space from traversing - the start of empty block points to the first non-empty character, but this only speeds up traversing, still with loglinear time. The part responsible for this behaviour is replacing pairs by the new character every iteration - keeping only rewrite rules and operating on them would be faster, but still the access to check if new pairs were introduced would require to check rewrite rules against the new ones - in the case we build full binary tree with pairs at the leaves in such way that after replacing pair with new character and concating with the parent we got new pairs at the leaves up to the root - there are $n$ chatacters then $\frac{n}{2}$ pairs, then $\frac{n}{4}$, $\frac{n}{8}$, $\frac{n}{16}$... You see the pattern, there are $2n$ pairs, but according to algorithm description this yelds $\mathcal O(n\log n + n)$ time taking only input traversals.