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).
Let's consider the string
100100100 of length 9. Special symbols
] are also counted (otherwise, how the decoder would know the beginning and the end of a "repeat N times" program?).
|3||6||0||repeat 100 three times|
|9||4||3||repeat 0 nine times; it will make three substitutions (errors) of
|9||4||6||repeat 1 nine times; it has the same length as
1001001000100 of length 13 can be decomposed into:
|13||4||4||For simplicity, assume the count
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.
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).
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
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
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.
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.
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.