9
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ So PowerShell is out? Bummer. \$\endgroup\$ – Joey Apr 13 '11 at 16:44
  • 1
    \$\begingroup\$ Haskell: main = interact (\x -> take 90 x ++ " yada yada yada") \$\endgroup\$ – Joey Adams Apr 13 '11 at 19:26
  • 1
    \$\begingroup\$ Note also that "readability after decompression" is a fairly subjective criterion. \$\endgroup\$ – Joey Apr 13 '11 at 20:02
  • \$\begingroup\$ Especially on a Unix-Box, we need the distinction upper case, lower case. :) And finding the beginning of a sent. Isn't trivial, if the u. Uses abbrev.! :) \$\endgroup\$ – user unknown Apr 21 '11 at 3:34
  • \$\begingroup\$ Do we want to compress the alphabet or the text? :) L = l = 1 compresses the characters needed to represent our thoughts. But "one apple" = "1 apl" compresses the text. \$\endgroup\$ – anemgyenge Apr 22 '11 at 17:00
11
\$\begingroup\$

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;
\$\endgroup\$
3
\$\begingroup\$

Perl, 0 chars

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

\$\endgroup\$
2
\$\begingroup\$

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).

\$\endgroup\$
  • \$\begingroup\$ Somehow I knew that was coming with that challenge ;-) \$\endgroup\$ – Joey Apr 14 '11 at 11:07
  • \$\begingroup\$ That's going to be hard to beat. \$\endgroup\$ – Lowjacker Apr 18 '11 at 15:57
  • \$\begingroup\$ Hah! I beat it in both length and compression ratio ;) \$\endgroup\$ – Ry- Apr 21 '11 at 1:03
  • 1
    \$\begingroup\$ xz, even shorter and better ratio :) \$\endgroup\$ – OneOfOne Apr 24 '11 at 8:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.