Kompresi Teks Lossy

9

Latar Belakang

Dari 256 karakter yang mungkin dimiliki oleh byte, hanya beberapa di antaranya yang digunakan dalam sebagian besar keadaan. Tidak bisakah kita mengambil keuntungan dari ini, dan membuat file teks kita lebih kecil dengan menghilangkan kebutuhan akan huruf yang jarang digunakan?

Banyak huruf tidak menambah nilai dalam kebanyakan situasi, dan dapat diganti dengan huruf yang lebih umum. Misalnya, huruf kecil "L", huruf kapital "I", dan angka "1" terlihat hampir identik di sebagian besar situasi, sehingga dapat dikonsolidasikan.

Hanya ada sedikit kebutuhan untuk huruf kapital, sehingga mereka dapat ditiadakan. Program dekompresi / tampilan bahkan dapat secara otomatis memanfaatkan huruf pertama dari setiap kalimat, nama umum, dll.

Aturan

Entri akan dinilai pada:

  • rasio kompresi
  • keterbacaan setelah de-kompresi

Entri akan diuji terhadap versi teks biasa dari artikel ini: http://en.wikipedia.org/wiki/Babbage dan artikel BBC News yang dipilih secara acak .

Nilai ekstra akan diberikan untuk; menjaga mark-up, mempercantik setelah de-kompresi (yaitu huruf kapitalisasi dll).

Bahasa

  • Apa pun yang Anda suka, tetapi harus dengan mudah mengkompilasi (atau ditafsirkan) pada kotak * nix dasar.
rjstelling
sumber
Jadi PowerShell sudah keluar? Kekecewaan.
Joey
1
Haskell:main = interact (\x -> take 90 x ++ " yada yada yada")
Joey Adams
1
Perhatikan juga bahwa "keterbacaan setelah dekompresi" adalah kriteria yang cukup subjektif.
Joey
Terutama pada Unix-Box, kita perlu perbedaan huruf besar, huruf kecil. :) Dan menemukan awal pengiriman. Bukankah sepele, jika Anda. Gunakan singkatan! :)
pengguna tidak diketahui
Apakah kita ingin mengompres alfabet atau teks? :) L = l = 1 memampatkan karakter yang diperlukan untuk mewakili pemikiran kita. Tetapi "satu apel" = "1 apl" mengompres teks.
Pembalasan dendam

Jawaban:

11

Perl

Sangat tidak efisien dan memiliki angka buruk. Membutuhkan /usr/share/dict/words.

Kompresor

#!/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;

Dekompresor

#!/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;
Ming-Tang
sumber
3

Perl, 0 karakter

Rasio kompresi infinity, meskipun tidak dapat dibaca setelah dekompresi sehingga akan kehilangan beberapa tanda.

Ry-
sumber
2

Bash, 5 karakter

Entri malas saya yang mungkin saja menang:

bzip2

Lossless, sehingga menjaga keterbacaan dengan sempurna dan mendapatkan semua nilai ekstra! Rasio kompresi pada html Babbage adalah 4,79x (153804 hingga 32084 bytes).

Keith Randall
sumber
Entah bagaimana aku tahu itu akan datang dengan tantangan itu ;-)
Joey
Itu akan sulit dikalahkan.
Lowjacker
Hah! Saya mengalahkannya dalam perbandingan panjang dan kompresi;)
Ry-
2
xz, rasio yang lebih pendek dan lebih baik :)
OneOfOne