2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks for the edits and the responses. Rather than appending some questions and answers to the end of your existing post, we'd prefer if you would revise your post to read well for someone who encounters it for the first time, and so it has all information needed, in a logical order. When authors write a book, they don't leave in confusing parts and then add a Q&A at the end of the chapter to clear up the confusion; they edit it to make that information clear at the point where the information is needed. $\endgroup$
    – D.W.
    Dec 28, 2021 at 8:38
  • $\begingroup$ Sorry for the confusion. By "all possible answers" I meant "all possible Pareto-optimal front answers", not just the "best" encoding (because the "best" is undefined here and subject to a use-case). $\endgroup$
    – dizcza
    Dec 28, 2021 at 10:34

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ How to modify the second step for the Levenshtein distance? $\endgroup$
    – dizcza
    Dec 29, 2021 at 12:43
  • $\begingroup$ @dizcza, I don't know, but you can try to see if you can construct a dynamic programming algorithm using the structured approach listed here: cs.stackexchange.com/tags/dynamic-programming/info (build a set of subproblems that lets you construct an exponential-time recursive algorithm, then memoize). $\endgroup$
    – D.W.
    Dec 29, 2021 at 19:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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