# Understanding compression/encoding in linear time

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)$?

• You should ask a more specific question. Reiterating a paper in different words seems to broad for this site. Where in the paper do the authors lose you? Aug 12 '16 at 15:43
• @adrianN I've written a little more on what specifically I'm confused about.
– Eff
Aug 12 '16 at 16:02
• The paper made assumption that it will use hash table and counted it as $\mathcal O(n)$, which in this case might be wlog replaced by suffix tree to be $\mathcal O(n)$. I just skimmed the text, your question is still very demanding, but I do not really see why you would spend $\mathcal O(n^2)$ just for one item.
– Evil
Aug 12 '16 at 16:59
• @Evil So you are saying that one could construct a suffix tree of $S$ in $\Theta (n)$ time (BTW, I still quite don't understand when it is possible to construct a suffix tree in linear time and when it takes $\mathcal O (n\log n)$). Then we find the most frequent substring in the suffix tree in $\Theta (n)$ time. Correct?
– Eff
Aug 12 '16 at 17:25
• Me? No. But Ukkonen said a few words about it. $\mathcal O(n)$ for constant size alphabet and $\mathcal O(n\log n)$ in general. Then we can sort by frequencies in $\mathcal O(n\log n)$ or even exploit small natural numbers for counting sort. I am not sure if something 1~n is $\Theta(n)$, sorry no answer for that part.
– Evil
Aug 12 '16 at 17:32

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