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