This comes from a real-world, icky problem I'm facing, but I'm simplifying it to avoid the mucky details.

If I had the string: 

# 10 quoted chars
my $string = 'ABABCABCAC';

[download]
I could save some space by noting that 'ABCABC' could be changed to 'ABC'x2: 1,2 
# 7 quoted chars
my $string = 'AB'.'ABC'x2.'AC';

[download]
Note that if I had just taken the first repeated string, 'ABAB', I would have this: 
# 8 quoted chars
my $string = ('AB'x2).'CABCAC'x2;

[download]
which is not optimal.

Additionally, there is a limit to the number of x$N elements allowed, $Max_Repeats. So the final solution would have to weigh the number of repeats used against the character savings.

The approach I'm considering first walks through the string, building a table of substrings seen. Each entry would be a substring, along with each starting position where it was found. 3 Then walk the table, making a 2nd table of all repeated, concatenated subsequences, which would have the base sequence, and a substructure for each base sequence indicating starting position(s), repeat count(s), and characters saved. Then sorting by characters saved, I should be able to minimize the number of characters without exceeding the repeat code limit. 4

But I can't seem to get past "build a table of substrings seen". If the real problem were small enough that this wouldn't run out of memory, then I could probably do it with paper and pencil anyway.

Update: One point I didn't make is that "chars" in the example above translate to statements in a simple language in the real problem. These statements are easily matched with a regex, but they are somewhat complicated. Trying to use BrowserUK's approach directly forces the regex engine to backtrack mercilessly through all of the subexpressions in a single statement match (and not spend much time on the repeat search.]

One obvious reduction is to translate the real input to a fundamental form that doesn't need a fancy regex to match each element. Perhaps something like a comma-separated list of a hash function in hex format.

1 I don't really have "just a string", and there is a magic way to indicate repeated concatenated items that doesn't take up "item space", but does takes up "repeat space".

2 I can't use the coding table approach of ordinary compression algorithms to, for instance, substitute a code for each occurrence of 'AB'. All reductions must consist of a repeated, concatenated sequence.

3 Obviously I have a complexity flaw. I've played with a regex on toy input, but it was just real enough that it wouldn't have finished before the next blackout.

4 Flaws 2 and 3 -- overlapping sequences; and the bin packing problem.

-QM
--
Quantum Mechanics: The dreams stuff is made of

In reply to String Compression Optimization (repeated concatenated subsequences) by QM

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.