I would like to begin by apologizing. I am not a computer scientist, so my use of terminology will be off. I came across an interesting problem, which I believe to be pretty hard and would love to get references or any other advice to know what to search for in the academic literature on this topic.

Consider a standard LZ77-type compression algorithm. The compressor replaces substring at the current position with the pointer back to the already decompressed text or a literal copy of a single character. Early compressors tended to use greedy algorithms for choosing specific substrings, but better (in fact, optimal for a fixed LZ77 code) results can be obtained by generating a set of several (all) encoding options at each position and then treating the problem as a problem of finding the shortest path on a weighted graph. Each position of the text becomes a vertex, each edge contains the length of the code needed to encode the corresponding substring. The resulting problem is routinely solved by using the Dijkstra algorithm.

In principle, one does not need to store the decompressed text. Instead, one can make references back to the positions in compressed stream and decompress it as needed on the fly. In this case the algorithm becomes recursive - references to previous positions in the compressed stream can require one to follow further references before in the compressed stream. Dealing with overlapping substrings in this case can be a bit tricky, but otherwise, the logic of the algorithm remains mostly the same.

Now, suppose that we have an additional complication. We are using a recursive (buffer-less) version of LZ77 with back references to the compressed stream, but for various reasons we would like to limit the depth of recursion that we are allowed to use during decompression. For example, the maximum recursion depth of 1 would mean that a referred substring can involve further references to previous substrings, but neither of these substrings would be able to have any further back references. The easiest case would be to prohibit recursion completely. Overlapping substrings would not be allowed in this case. All this can be done and in fact I have a working implementation of a greedy algorithm for this problem. Of course, it is much less efficient compared with the classic LZ77. However, this is not a problem.

My real question is: what approach would be necessary to construct an optimal representation of the original text in the case when no recursion is allowed? It is clearly not possible to implement something similar to a Dijkstra algorithm mentioned earlier, because the graph is no longer static: once a particular edge (i.e. a particular substring) gets included into the shortest path, all edges referring to substrings overlapping with the current substring disappear from the graph. The graph is now dynamic and the path-finding algorithm is not "local" in the sense that it can no longer work in a "ripple"-type fashion, because any rush decision early on may disallow much greater savings later on. How would one attack this kind of problem?

  • 1
    $\begingroup$ Afaik, LZ77 is not recursive; can you give a reference to the variant you want to discuss here? Furthermore, it's always possible to convert recursion to iteration (that's a result from computability; WHILE-programs are as powerful as $\mu$-recursive functions). So I'm afraid I don't quite follow. $\endgroup$
    – Raphael
    Oct 9, 2014 at 16:23
  • 1
    $\begingroup$ LZ77 is not recursive, but my third paragraph explains how to reformulate it in a recursive form. Basically, instead of referring back to the window of already decompressed text, you can make references to the positions in the compressed stream and decompress on the fly. This would be hard for a bit-stream, but I implemented a byte-version of the compressor. My reasons to experiment with this formulation come from some coding on extremely weak computing platforms, where this approach turns out both efficient and reasonably inexpensive in terms of memory. $\endgroup$
    – introspec
    Oct 9, 2014 at 18:15
  • $\begingroup$ Ah, and the answer to the second part of your question is: I know how to convert a recursive algorithm into a non-recursive, but I have limited processing power. Limit on recursion is motivated by the need to achieve high performance, not by my inability to implement it. $\endgroup$
    – introspec
    Oct 9, 2014 at 18:21

1 Answer 1


While I do not have a fully satisfactory answer to my own question, I have now found the academic context for what I was trying to do. In their classical paper [1] Storer and Szymanski introduce a classification of "macro encoding schemes", which includes all kinds of LZ compressors as particular cases. The usual LZ77 would be described in their terminology as an OPM (original pointer macro) scheme, and the modification described in my question would be a CPM (compressed pointer macro) scheme. Definition 5 on p.931 specifically introduces macro schemes without recursion in exactly the same sense as described in my question.

They present analysis of different types of macro encoding schemes and, specifically for CPM they state on p.942 that the "optimal encoding for the CPM scheme appears to be intractable". They also give Theorem 9 saying that the problem of finding a constant bound for the optimal CPM compressed size is NP-complete. I cannot see at present if this implies that the problem of finding optimal encoding is NP-complete too, although I would not be particularly surprised if it does.

[1] Storer, J. A., & Szymanski, T. G. (1982). Data compression via textual substitution. Journal of the ACM (JACM), 29(4), 928-951.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.