Lossy Text Compression

Question

Background

Of the 256 possible characters that a byte can represent, only a few of these are used under most circumstances. Couldn't we somehow take advantage of this, and make our text files smaller by eliminating the need for the rarely used letters?

Many letters don't add any value in most situations, and can be replaced by more common letters. For example, a lower-case "L", capital "I", and the number "1" look nearly identical in most situations, so they can be consolidated.

There is little need for capital letters, so they can be dispensed with. The decompression/display program could even automatically capitalize the first letter of every sentence, common names, etc.

Rules

Entries will be judged on:

• compression ratio
• readability after de-compression

Entries will be tested against the plain text version of this article: http://en.wikipedia.org/wiki/Babbage and a randomly selected BBC News article.

Extra marks will be awarded for; preserving any mark-up, beautifying after de-compression (i.e. Capitalising sentences etc).

Languages

• Any you like, but must easily compile (or be interpreted) on a basic *nix box.

Answer 1

Perl

Very inefficient and has bad rates. Requires /usr/share/dict/words.

Compressor

#!/usr/bin/perl

$M = 2;
$N = 1;
$Min = 3;
$Max = 8;

while (<>) {
  for (split /\s+/) {
    s/[^a-z]//i;
    ($p) = m/([^a-z]*)$/;
    $_ = lc $_;
    $l = (length $_) - (length $p);
    s/^and$/A/;
    s/^he$/H/;
    s/^in$/I/;
    s/^of$/O/;
    s/^you$/U/;
    s/^the$/Z/;
    if (length $_ >= $Min) {
      if (length $_ <= $Max) {
        s/ed/D/g;
        s/ing\b/N/g;
        s/er/R/g;
        s/'s/S/g;
        s/th/T/g;
        s/[aeo]{1,2}//g;
        $_ .= $l;
      } else {
        s/^(.{$M})(.+)(\w{$N})$/$1.(length$2).$3/e;
      }
    }
    $a .= $_ . $p . ' ';
  }
}
print $a;

Decompressor

#!/usr/bin/perl

$M = 2;
$N = 1;

open D, '/usr/share/dict/words';
chomp, push @W, $_ while <D>;
close D;

while (<>) {
  for (split /\s+/) {
    ($_, $p) = m/^(.+)([^a-z]*)$/;
    s/^A$/and/;
    s/^H$/he/;
    s/^I$/in/;
    s/^O$/of/;
    s/^U$/you/;
    s/^Z$/the/;
    if ($_ =~ m/^(\w{$M})(\d+)(\w{$N})$/) {
      $r = '^' . quotemeta($1) . ('\w' x $2) . quotemeta($3) . '$';
      ($_) = (grep /$r/, @W);
      $_ .= $4;
    } else {
      ($_, $l) = m/^(.+)(\d+)$/;
      s/D/ed/g;
      s/N/ing/g;
      s/R/er/g;
      s/S/'s/g;
      s/T/th/g;
      $r = '[aeo]{0,2}';
      for $y(split //) { $r .= (quotemeta $y) . '[aiueo]{0,2}' }
      ($_) = (grep /^(?=[a-z]{$l})$r$/, @W);
    }
    $a .= $_ . $p . ' ';
  }
}
print $a;

Answer 2

Perl, 0 chars

Compression ratio of infinity, though not that readable after decompression so it will lose some marks.

Answer 3

Bash, 5 chars

My lazy entry that just might win:

bzip2

Lossless, so it preserves readability perfectly and gets all the extra marks! Compression ratio on the Babbage html is 4.79x (153804 to 32084 bytes).