4

I have come up with the term loop rolling myself with the hope that it does not overlap with an existing term. Basically I'm trying to come up with an algorithm to find loops in a printed text.

Some examples from simple to complicated

Example1

Given:

a a a a a b c d

I want to say:

5x(a) b c d

or algorithmically:

for 1 .. 5
    print a
end
print b
print c
print d

Example2

Given:

a b a b a b a b c d

I want to say:

4x(a b) c d

or algorithmically:

for 1 .. 4
    print a
    print b
end
print c
print d

Example3

Given:

a b c d b c d b c d b c e

I want to say:

a 3x(b c d) b c e

or algorithmically:

print a
for 1 .. 3
    print b
    print c
    print d
end
print b
print c
print d

It didn't remind me of any algorithm that I know of. I feel like some of the problems can be ambiguous but finding one of the solutions is enough to me for now. Efficiency is always welcome but not mandatory. How can I do this?

EDIT

First of all, thanks for all the discussion. I have adapted an LZW algorithm from rosetta and ran it on my input:

abcdbcdbcdbcdef

which gave me:

a
b
c
d
8  => bc
10 => db
9  => cd
11 => bcd
e
f

where I have a dictionary of:

a a
c c
b b
e e
d d
f f
8 bc
9 cd
10 db
11 bcd
12 dbc
13 cdb
14 bcde
15 ef
7 ab

It looks good for compression but it's not quite what I wanted. What I need is more like compression in the algorithmic representation from my examples which would have:

  • subsequent sequences (if a sequence is repeating, there would be no other sequence in between)
  • no dictionary but only loops
  • irreducable
  • with maximum sequence sizes (which would minimize the algorithmic representation)
  • and let's say nested loops are allowed (contrary to what I said before in the comment)
none
  • 11,793
  • 9
  • 51
  • 87
  • 5
    This is very similar to [Lempel–Ziv–Welch algorithm](http://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Welch). – Evgeny Kluev Nov 01 '12 at 17:37
  • I think you need some additional constraints, what constitutes a "loop"? 1 or more repetitions? Is `a b a b a b a b c` equivalent to `4x(a b) c` or is it `2x(a b a b) c` or do you want all possible combinations? – NominSim Nov 01 '12 at 17:38
  • There's always the trivial solution of "no loops found". You can even find it in constant time! – Kevin Nov 01 '12 at 17:40
  • @Kevin linear, if you need to copy the input to output – John Dvorak Nov 01 '12 at 17:42
  • @NominSim - I think OP is looking for an irreducible scheme. `2x(a b a b)` can be shortened, so it is not irreducible. – Ted Hopp Nov 01 '12 at 17:42
  • @TedHopp even then the solution may not be unique. `3x(a) a` is irreducible but not shortest. – John Dvorak Nov 01 '12 at 17:43
  • @NominSim smaller is better therefore I would go with the `4x(a b) c` – none Nov 01 '12 at 17:43
  • @JanDvorak - Well, irreducible and maximal, then. The interesting cases are things like `a a b a a b`. Is it `2x(a a b)` or is it `2x(a) b 2x(a) b` (or even `2x(2x(a) b)`)? – Ted Hopp Nov 01 '12 at 17:43
  • @TedHopp minimal, you mean? The trivial solution is maximal ;-) – John Dvorak Nov 01 '12 at 17:44
  • I'll take a guess and say the problem "given a string, is it possible to compress it to a given length" is NP-complete – John Dvorak Nov 01 '12 at 17:45
  • @JanDvorak - I meant maximal in the sense of greedy. If a pattern can consume the following input, it should. – Ted Hopp Nov 01 '12 at 17:45
  • @TedHopp That makes sense, the question doesn't specify though so wanted to make sure. Was just pointing out that the OP may want to be more specific in what he is looking for. i.e. (Finding the shortest compression of a string by grouping repetitions). – NominSim Nov 01 '12 at 17:48
  • 1
    gokcehan - are nested loops allowed? – Ted Hopp Nov 01 '12 at 18:04
  • @TedHopp I will probably have only one loop and it will probably be non ambiguous so I would say no. – none Nov 01 '12 at 18:08
  • 1
    Essentially, this is about compression and borders on Kolmogorov-complexity. – phant0m Nov 01 '12 at 18:17
  • What you ask for is called RLE, see here for similar problem: http://stackoverflow.com/questions/7705086/c-and-rle-for-sequences-of-symbols – SomeWittyUsername Nov 01 '12 at 19:54
  • 4
    @TedHopp: I would think the interesting cases are the ones which fail greedy composition, like `a b a b a b a b c d e a b c d e`, where you really want `3(a b) 2(a b c d e)` rather than `4(a b) c d e a b c d e`. – rici Nov 01 '12 at 21:06
  • 1
    @icepack - That other problem is missing the core difficulty of the present question: how to identify the groups. (The groups are already determined in the question you link to.) – Ted Hopp Nov 01 '12 at 21:39
  • @TedHopps that's pretty simple: just run the same algorithm on sequences of 2,3,4 etc. – SomeWittyUsername Nov 01 '12 at 21:51
  • It is a folding, not "unrolling". – SK-logic Nov 02 '12 at 09:59
  • @SK-logic I did say "rolling" not "unrolling". "unrolling" is the one that compilers do for optimization which was also my inspiration because it looks like the opposite of "unrolling". "folding" seems appropriate as well though.. – none Nov 02 '12 at 11:46
  • @gokcehan, sorry, my bad; Spent too much time coding compiler optimisations. – SK-logic Nov 02 '12 at 11:52
  • Maximum sequence sizes would not always minimize the algorithmic representation: `aab a ab cd ab cd d cdd`. To get maximum sequence sizes (4), we have to combine `ab` with `cd`, but with shorter sequences `aab` and `cdd` algorithmic representation is better. – Evgeny Kluev Nov 02 '12 at 19:51

1 Answers1

2

I start with an algorithm, which gives maximum sequence sizes. Though it would not always minimize the algorithmic representation, it may be used as an approximation algorithm. Or it may be extended to optimal algorithm.

  1. Start with constructing Suffix array for your text along with LCP array.
  2. Sort an array of indexes of LCP array, indexes of larger elements of LCP array come first. This groups together repeating sequences of the same length and allows to process sequences in greedy manner, starting from maximum sequence sizes.
  3. Extract suffix array entries, grouped by LCP value (by group I mean all the entries with selected LCP value as well as all entries with larger LCP values), and sort them by position in the text.
  4. Filter out entries with positional difference not equal to LCP. For remaining entries, get prefixes of length, equal to LCP. This gives all possible sequences in the text.
  5. Add sequences, sorted by starting position, to ordered collection (for example, binary search tree). Sequences are added in order of appearance in sorted LCP, so longer sequences are added first. Sequences are added only if they are independent or if one of them is completely nested inside the other one. Intersecting intervals are ignored. For example, in caba caba bab sequence ab intersects with caba and so it is ignored. But in cababa cababa babab one instance of ab is dropped, 2 instances are completely inside larger sequence, and 2 instances are completely outside of it.
  6. At the end, this ordered collection contains all the information, needed to produce the algorithmic representation.

Example:

Text          ababcabab

Suffix array  ab abab ababcabab abcabab b bab babcabab bcabab cabab
LCP array       2    4         2       0 1   3        1      0

Sorted LCP            4 3 2 2 1 1 0 0
Positional difference 5 5 2 2 2 2 - -
Filtered LCP          - - 2 2 - - - -
Filtered prefixes   (ab ab) (ab ab)

Sketch of an algorithm, producing the minimal algorithmic representation.

Start with the first 4 steps of previous algorithm. Fifth step should be modified. Now it is not possible to ignore intersecting intervals, so every sequence is added to the collection. Since the collection now contains intersecting intervals, it is better to implement it as some advanced data structure, for example, Interval tree.

Then recursively determine the length of algorithmic representation for all sequences, that contain any nested sequences, starting from the smallest ones. When every sequence is evaluated, compute optimal algorithmic representation for whole text. Algorithm for processing either a sequence or whole text uses dynamic programming: allocate a matrix with number of columns, equal to text/sequence length and number of rows, equal to the length of algorithmic representation; doing in-order traversal of interval tree, update this matrix with all sequences, possible for each text position; when more than one value for some cell is possible, either choose any of them, or give preference to longer or shorter sub-sequences.

Evgeny Kluev
  • 24,287
  • 7
  • 55
  • 98
  • This looks about right but I have ended up using regular expressions for now as the input is small. I will give this a try in case we need more performance, thanks.. – none Nov 07 '12 at 13:36