in reply to Re^4: String Compression Optimization (repeated concatenated subsequences)
in thread String Compression Optimization (repeated concatenated subsequences)

Funny, I was working on the same problem when I read your node. This will compress the 200 line example six times a second: 
use strict;
use warnings;
use Benchmark;

our $a = q{L 0 0 0 0 L 0 L L H 0 0 0 0 0 0 0 0 0 0 1 1;
L 0 1 0 0 L 0 L L H 0 0 0 0 0 0 0 0 0 0 1 1;
L 0 0 0 0 L 0 L L H 0 0 0 0 0 0 0 0 0 0 1 1;
L 0 1 0 0 L 0 L L H 0 0 0 0 0 0 0 0 0 0 1 1;
L 0 0 0 0 L 0 L L H 0 0 0 0 0 0 0 0 0 0 1 1;
L 0 1 0 0 L 0 L L H 0 0 0 0 0 0 0 0 0 0 1 1;
L 0 0 0 0 L 0 L L H 0 0 0 0 0 0 0 0 0 0 1 1;
L 0 1 0 0 L 0 L L H 0 0 0 0 0 0 0 0 0 0 1 1;
L 0 0 0 0 L 0 L L H 0 0 0 0 0 0 0 0 0 0 1 1;
L 0 1 0 0 L 0 L L H 0 0 0 0 0 0 0 0 0 0 1 1;
L 0 0 0 0 L 0 L L H 0 0 0 0 0 0 0 0 0 0 1 1;
L 0 1 0 0 L 0 L L H 0 0 0 0 0 0 0 0 0 0 1 1;
L 0 0 0 0 L 0 L L H 0 0 0 0 0 0 0 0 0 0 1 1;
L 0 1 0 0 L 0 L L H 0 0 0 0 0 0 0 0 0 0 1 1;
L 0 0 0 0 L 0 L L H 0 0 0 0 0 0 0 0 0 0 1 1;
L 0 1 0 0 L 0 L L H 0 0 0 0 0 0 0 0 0 0 1 1;
L 0 0 0 0 L 0 L L H 0 0 0 0 0 0 0 0 0 0 1 1;
L 0 1 0 0 L 0 L L H 0 0 0 0 0 0 0 0 0 0 1 1;
L 0 0 0 0 L 0 L L H 0 0 0 0 0 0 0 0 0 0 1 1;
L 0 1 0 0 L 0 L L H 0 0 0 0 0 0 0 0 0 0 1 1;
L 0 0 0 0 L 0 L L H 0 0 0 0 0 0 0 0 1 0 1 1;
L 0 1 0 0 L 0 L L H 0 0 0 0 0 0 0 0 1 0 1 1;
L 0 0 0 0 L 0 L L H 0 0 0 0 0 0 0 0 1 0 1 1;
L 0 1 0 0 L 0 L L H 0 0 0 0 0 0 0 0 1 0 1 1;
L 0 0 0 0 L 0 L L H 0 0 0 0 0 0 0 0 1 0 1 1;
L 0 1 0 0 L 0 L L H 0 0 0 0 0 0 0 0 1 0 1 1;
L 0 0 0 0 L 0 L L H 0 0 0 0 0 0 0 0 1 0 1 1;
L 0 1 0 0 L 0 L L H 0 0 0 0 0 0 0 0 1 0 1 1;
L 0 0 0 0 L 0 L L H 0 0 0 0 0 0 0 0 1 0 1 1;
L 0 1 0 0 L 0 L L H 0 0 0 0 0 0 0 0 1 0 1 1;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 H 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 1 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 1 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 1 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 1 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 1 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 1 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 1 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 1 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 1 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 1 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 H 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 H 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 H 1 0 1 0;
L 0 0 0 0 L 0 L L H 0 0 0 0 0 0 0 0 1 0 1 1;
L 0 1 0 0 L 0 L L H 0 0 0 0 0 0 0 0 1 1 1 1;
L 0 0 0 0 L 0 L L H 0 0 0 0 0 0 0 0 1 1 1 1;
L 0 1 0 0 L 0 L L H 0 0 0 0 0 0 0 0 1 0 1 1;
L 0 0 0 0 L 0 L L H 0 0 0 0 0 0 0 0 1 0 1 1;
L 0 1 0 0 L 0 L L H 0 0 0 0 0 0 0 0 1 0 1 1;
L 0 0 0 0 L 0 L L H 0 0 0 0 0 0 0 0 1 0 1 1;
L 0 1 0 0 L 0 L L H 0 0 0 0 0 0 0 0 1 0 1 1;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 H 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 H 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 H 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 1 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 1 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 1 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 1 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 H 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 H 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 1 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 1 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 L 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 0 H 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 0 H 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 1 H 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 1 H 1 0 1 0;
L 1 1 0 0 L 0 L L H 0 L 0 L 0 L 1 L 1 0 1 0;
L 1 0 0 0 L 0 L L H 0 L 0 L 0 L 1 L 1 0 1 0;
H 0 0 0 0 L 0 L L H L H L H L H L H 1 0 0 0;};
$a = '<'.join('><',split(/\n/, $a)).'>';

our $x = qr/(?:<(?:[^<>])+>)/;
our $b;

timethese(30, { u => sub { $b = u($a) } } );

print "\n$b\n";

sub u {
    my $a = shift;
    my @bestmatch = (0); # saved chars, before match, match, repetitio
+ns of match, after match
    my $i = 0;
    my $save = 0;
    my $max = @{[$a =~ /$x/g]} - 1;
    while ($i < $max) {
        if ($a =~ /^${x}{$i,$i}($x+?)(\1+)/) { # prefers 'A'x4 'B' 'A'
+x4 'B'
            # we save the length of the ommitted parts minus the lengt
+h of the number minus the overhead ("<>")
            $save = length($2) - length( length($2)/length($1)+1 ) - 2
+;
            if ($save > $bestmatch[0]) {
                @bestmatch = ($save, substr($a, 0, $-[1]), $1, length(
+$2)/length($1)+1, substr($a, $+[0]) );
            }
        }
        if ($a =~ /^${x}{$i,$i}($x+)(\1+)/) { # prefers 'AAAAB'x2
            # we save the length of the ommitted parts minus the lengt
+h of the number minus the overhead ("<>")
            $save = length($2) - length( length($2)/length($1)+1 ) - 2
+;
            if ($save > $bestmatch[0]) {
                @bestmatch = ($save, substr($a, 0, $-[1]), $1, length(
+$2)/length($1)+1, substr($a, $+[0]) );
                last if $save > ($max - $i);
            }
        }
        $i++;
    }
    if ($bestmatch[0]) {
        return $a = u($bestmatch[1]) .'<'. u($bestmatch[2]) . $bestmat
+ch[3] .'>'. u($bestmatch[4]);
    } else {
        return $a;
    }
}

[download]
Search, Ask, Know
  • Comment on Re^5: String Compression Optimization (repeated concatenated subsequences)
  • Download Code

In Section Seekers of Perl Wisdom