[ create a new paste ] login | about

Link: http://codepad.org/uYeOAlRD    [ raw code | output | fork ]

Perl, pasted on Dec 2:
$a = 'ABCDEF1GHIJKL2ABCDEFGHIJKL3X4DEFGHI';

# Indexing the matches

$l = length($a);
for( $i=0; $i<$l; $i++ ) {
  $c = substr($a,$i,1);

  $oldprice = 1E9;
  @match = (0,0,0);
  for( $j=$i-1; $j>=0; $j-- ) {
    $flag=0;
    for( $k=$l; $k>=$i+2; $k-- ) {
      next if $f_match[$j+$k-$i];
      if( substr($a,$i,$k-$i) eq substr($a,$j,$k-$i) ) {
        $flag = 1; last;
      }
    }
    if( $flag ) {
      $price = (log(1+$i-$j)+log($k-$i)) / ($k-$i);
      if( $price<$oldprice ) {
        $oldprice = $price;
        @match = ($j,$i,$k-$i);
      }
    }
  }

  if( $match[2] ) {
    $j = $match[0]+$match[2];
    $target[$j] = $match[1];
    $length[$j] = $match[2];
    $source[$match[1]] = $match[2];

    for( $x=0; $x<$match[2]; $x++ ) { $f_match[$match[1]+$x]=1; }

    $i += $match[2]-1;
  }
}

$cs = ""; # compressed string

# Compressing the string, $a -> $cs

for( $i=0; $i<$l; $i++ ) {
  if( $source[$i] ) {
    $i += $source[$i]-1;
  } else {
    $c = substr($a,$i,1);
    if( $target[$i] ) {
      $cs .= sprintf( "<%s;%s>", $target[$i]-$i, $length[$i] );
    }
    $cs .= $c;
  }
}

print $a, "\n";
print $cs,"\n";

$us = ""; # uncompressed string

# Decompressing $cs -> $us

undef @target;
undef @length;
for( $j=0; $j<length($cs); $j++ ) {
  while(1) {
    $i = length($us);
    last unless $length[$i];
    $us .= substr( $us, $target[$i]-$length[$i], $length[$i] );
  }
  $s = substr($cs,$j);
  $c = substr($cs,$j,1);
  if( $s=~/^<(\d+);(\d+)>/ ) {
    $k = $1+$i; # + $1 + $2;
    $target[$k] = $i;
    $length[$k] = $2;
    $j += length($&)-1;
  } else {
    $us .= $c;
  }
}

print $us,"\n";


Output:
1
2
3
ABCDEF1GHIJKL2ABCDEFGHIJKL3X4DEFGHI
ABCDEF<23;3>1GHI<22;3>JKL<7;6>23X4
ABCDEF1GHIJKL23X4


Create a new paste based on this one


Comments: