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