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

In reply to Re^5: String Compression Optimization (repeated concatenated subsequences) by Beechbone
in thread 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.