Find repeated patterns in a string via lossy compression

Question

Description

The task is to identify repeated patterns in a string and do lossy compression of the input string using the found patterns. The output is a list containing different ways of encoding the string (information loss VS description length). For simplicity, I'll be using a binary string, though the solution should tolerate at least the English alphabet [a-zA-Z]. The output of the algorithm is "compressed" and "error" columns as shown below. If neither the compression ratio (length) nor the error is improved, the candidate should not be included in the output. In other words, the output should be the Pareto-optimal front: e.g., for each length, I want the encoding of that length that has the fewest errors. The "error" corresponds to the Hamming distance between the original and decoded strings.

This problem is similar to searching repeated substrings in a string indicated in this question: Algorithm to find repeated patterns in a large string. But my approach is (1) lossy and (2) not parametrized by the minimum and maximum chunk lengths (all candidates are to output).

Examples

Let's consider the string 100100100 of length 9. Special symbols [ and ] are also counted (otherwise, how the decoder would know the beginning and the end of a "repeat N times" program?).

compressed	length	errors	description
[100]3	6	0	repeat 100 three times
[0]9	4	3	repeat 0 nine times; it will make three substitutions (errors) of 1 -> 0.
[1]9	4	6	repeat 1 nine times; it has the same length as [0]9 but with more errors and therefore must be excluded from the output

The string 1001001000100 of length 13 can be decomposed into:

compressed	length	errors	description
([100]3)0100	10	0	Don't count (): an elaborate version of the "repeat N times" instruction can perhaps avoid unnecessary brackets
[100]4	6	1	0 is omitted
[0]13	4	4	For simplicity, assume the count 13 as a single byte

What I've tried

I've thought of the Run-length coding but (1) it's lossless by design and (2) the problem lies in identifying the pattern (inside the [] brackets) to repeat. The LZ77 algorithm is somewhat similar but it's not optimal - it starts compressing right from the beginning and goes in online fashion: run the string only once and output the result without returning back and re-iterating. Also, LZ77 has a fixed-size dictionary and the look-ahead buffer.

Probably, suffix trees suit well here but I don't know how to extract the repeated patterns from the edges of a suffix tree. An online resource to play with suffix trees is here: https://visualgo.net/en/suffixtree. And it's also lossless by design.

---

Motivation

This section is for curious readers.

The task is not to compress a string as much as possible but rather make use of compression techniques in AI.

The problem is motivated by an example of an agent moving in a circular Turing Tape only in the right direction and trying to predict the next k symbols (where the agent might expect some reward).

Why lossy?

You haven't probably spotted an extra 0 in the second example above the first time you read the string, have you? This is because the context to the left and to the right - 100 - soaks up an extra zero in the middle 1000. Our ability to simplify (read "to compress lossy") is crucial in inferring in noisy environments. The word "context" implies the use of the neighborhood at each cursor position (like in a convolution operation), and perhaps parsing a string only from left to right won't yield a fruitful solution.

Ideally, the algorithm shall indicate where and what kind of substitution is taken place in each lossy output. For example, the lossy-compressed representation [100]4 of a string 1001001000100 shall indicate that the omission of 0 is taken place at position 10. This is possible if the compression algorithm employs graphs.

---

Answer to comments and updates

1. Do you want the Pareto-optimal front: e.g., for each length, you want the encoding of that length that has the fewest errors? - Yes. Thanks, I didn't know the terminology.

2. Do you want a list of all possible encodings? - Not precisely. The Pareto-optimal front should be in the output. I don't think there will be exponentially many since a candidate that improves neither the length nor the error is not added to the output list, and therefore I expect O(L) candidates in the output, where L is the string length. If I'm wrong and it does grow polynomially or worse, let's constrain the output list to contain at most M=1000 elements. In such a case, these top M candidates are not guaranteed to be the best top M encodings of a string - that's fine.

3. How are you measuring the number of "error"s? Are you using the Hamming distance here? - Yes, the Hamming distance is used, although the edit distance fits the task as well.

Answer 1

You can solve this using dynamic programming. I will describe it in terms of constructing a graph and finding shortest paths in the graph, which is roughly equivalent.

Let $A[1..n]$ be the input string you are trying to encode. Let's construct a graph where each vertex is identified by an integer $i$, with $i \in \{0,1,2,\dots,n\}$. Each edge will have both a length, which represents the length of the encoding so far, and a cost, which represents the number of errors so far. The length of a path is the sum of the lengths of its edges, and same for cost. The intended meaning of a path $0 \leadsto i$ is that it represents an encoding of $A[1..i]$ with a length given by the length of the path, and a number of errors given by the cost of the path. We will add edges to the graph as follows, for each $i$:

• Add an edge $i \to i+1$ of length 1 and cost 0. This represents an encoding where we append $A[i+1]$ to the encoding for $A[1..i]$.

• Add an edge $i \to i+jr$ of length $j+3$, for each $j$ and $r$ such that $i+jr \le n$. This represents an encoding where we append something of the form $[x_1 x_2 \cdots x_j]r$ to the encoding for $A[1..i]$. For a given $j,r$, choose the $x$'s by taking a majority vote among $r$ characters: $$x_k = \text{majority}(A[i+k],A[i+j+k],A[i+2j+k],\dots,A[i+(r-1)j+k]).$$ The cost of this edge is easily computed (it is the number of items that differed from their majority vote, summed across all $k$).

Now the goal is to find the set of all Pareto-optimal paths from $0 \leadsto n$ in this graph. This can be solved using the algorithm at Set of Pareto-optimal paths, in a graph where edges have both length and cost.

If you need to solve this in practice, there are various optimizations that can be applied to reduce the memory consumption of this algorithm. For instance, there is no need to build the entire graph up front; instead, it can be constructed on demand, as whenever you visit a vertex you can identify all edges out of that vertex on demand. There are a number of other fancy optimizations possible, e.g., to extract the encoding (not just its length) in a memory-efficient way. Ask if you need them, but I suggest you start simple to see if this meets your needs, before trying to optimize.