# Compress data with context free grammars

It is possible to compress some kinds of data, such as human text or source code, with straight-line grammars. You basically create a grammar whose language has exactly one word – the uncompressed data. In this task, you have to write a program that implements this method of data compession.

## Input

The input is a string of not more than 65535 bytes length. It is guaranteed, that the input matches the regular expression [!-~]+ (i.e. at least one printable ASCII character excluding whitespace).

An example input is

abcabcbcbcabcacacabcabab

## Output

The output is a set of rules that form a grammar that describes exactly one word (the input). Each nonterminal is denoted by a decimal number greater than 9. The start symbol is symbol number ten. An example output corresponding to the example input is given below; its syntax is described further below:

10=11 11 12 12 11 13 13 11 14 14
11=a 12
12=b c
13=a c
14=a b


Each rule has the form <nonterminal>=<symbol> <symbol> ... with an arbitrary whitespace-separated number of symbols on the right side. Each output that obeys the following restrictions and derives exactly the input string is valid.

# Restrictions

In order to stop people from doing strange things, a number of restrictions are taking place:

• Each nonterminal must appear at least twice on the right side of a rule. For instance, the following grammar for the input abcabc is illegal because rule 12 appears only once:

  10=12
11=a b c
12=11 11

• No sequence of two adjacent symbols may appear more than once in all right-hand sides of all rules, except if they overlap. For instance, the following grammar for the input abcabcbc is illegal since the sequence bc appears twice:

  10=11 11 b c
11=a b c


A valid grammar would be:

  10=11 11 12
11=a 12
12=b c

• Your program must terminate in less than one minute for each valid input that is not longer than 65535 bytes.

• As usual, you may not use any facility of your language or any library function that makes the solution trivial or implements a large part of it.

## Sample input

Generate sample input with the following C program.

#include <stdlib.h>
#include <stdio.h>

int main(int argc, char **argv) {
unsigned int i,j = 0,k;

if (argc != 3
|| 2 != sscanf(argv[1],"%u",&i)
+ sscanf(argv[2],"%u",&k)) {
fprintf(stderr,"Usage: %s seed length\n",argv[0]);
return EXIT_FAILURE;
}

srand(i);

while(j < k) {
i = rand() & 0x7f;
if (i > 34 && i != 127) j++, putchar(i);
}

return EXIT_SUCCESS;
}


The sample input generated by the program above will usually not result in good compression results. Consider using human text or source code as example input.

## Winning criteria

This is code golf; the program with the shortest source code wins. For extra credit, write a program that reconstructs the input from the output.

### GolfScript, 111 108 characters

1/{.}{:^1<{^1$/,2>.{;,)^<.0?)!}*}do-1<.,1>{^1$/[10):10]*0+\+}{;^}if(\}while][0]%.,,]zip{))9+"="+\~" "*+}%n*


This is a quite clumsy approach using GolfScript. The second version performs much better than the initial one. It is much longer than the intended code but my implementation had nested do-loops and this caused issues with the interpreter.

Examples:

> abcba
10=a b c b a

> abcabcbc
10=11 11 12
11=a 12
12=b c

> abcabcbcbcabcacacabcabab
10=11 12 12 13 14 14 c 11 15
11=15 13
12=c b
13=14 b
14=c a
15=a b
`