Twitter文本压缩挑战

Question

规则

你的程序必须有两种模式: 编码和解码。

当编码时:

你的程序必须以一些可读的Latin1文本作为输入，可能是英语。

无论如何忽略标点符号都没有关系。

您只需要担心实际的英语单词，而不是L337。

任何带重音符号的字母都可以转换为简单的ASCII。

您可以选择如何处理数字。

123

• one two three
• one hundred twenty three
• 123
• 1 2 3

one hundred twenty three

• one two three
• one hundred twenty three
• 123
• 1 2 3

您的程序必须输出一个可以用140个代码点表示的消息范围在U+0000–U+10FFFF之间。不包括非字符：

• U+FFFE
• U+FFFF
• U+nFFFE, U+nFFFF其中n是1-10十六进制
• U+FDD0–U+FDEF
• U+D800–U+DFFF（代理代码点）。

它可以以您选择的任何合理编码输出；任何GNU iconv支持的编码都将被视为合理，您的平台本地编码或区域设置编码可能是一个不错的选择。

当解码时:

您的程序应该以编码模式的输出作为输入。

文本输出应该是输入文本的近似值。

越接近原始文本越好。

不需要有任何标点符号。

输出文本应该可供人类阅读，再次假定为英语。

可以是L337或lol。

解码过程可能无法访问编码过程的任何其他输出，除了上面指定的输出；也就是说，您不能上传文本并输出URL，以便解码过程下载，或者像那样愚蠢的事情。

为了保持用户界面的一致性，您的程序必须按以下方式运行：

您的程序必须是一个可以在具有适当解释器的平台上设置为可执行文件的脚本，或者可以编译成可执行文件的程序。

您的程序必须将其第一个参数设置为encode或decode以设置模式。

您的程序必须通过以下至少一种方式接受输入：

从标准输入中获取输入，并在标准输出上产生输出。

• my-program encode <input.txt >output.utf
• my-program decode <output.utf >output.txt

从命名为第二个参数的文件中获取输入，并将输出产生在命名为第三个参数的文件中。

• my-program encode input.txt output.utf
• my-program decode output.utf output.txt

对于您的解决方案，请发布：

您的完整代码和/或托管在其他地方的链接（如果它非常长，或需要许多文件来编译，或其他什么）。

如果代码不是立即显而易见的，或者代码很长，人们会对摘要感兴

规则是Twitter图像编码挑战规则的变体。

- Brad Gilbert

---

SMAZ (http://github.com/antirez/smaz/tree/master) + BASE64 - 我赢了什么？ - Tamas Czinege

投票重新开放的假设是Brad Gilbert将使该社区为维基。 - Randolpho

也许应该有一种投票方式，可以将一个问题变成社区维基，就像你可以投票关闭一个问题一样。 - Brad Gilbert

@Brad Gilbert: "encoding"部分的第三点是什么意思呢？ - Kuroki Kaze

如果您愿意，可以使用问题文本，或者更好的方法是，您可以发布一条评论，其中包含一些文本或链接，以便查看（未）压缩的内容。 - Brad Gilbert

Answer 1

我不确定是否有时间和精力编写实际代码，但这是我的想法：

• 任何长度在一定限制内的拉丁1字符串可简单编码（甚至不压缩），并无损转换为140个字符。朴素估计是280个字符，尽管由于竞赛规则中的代码点限制，它可能比那略短。
• 比以上长度略长的字符串（让我们估计在280到500个字符之间）可以最可能通过标准压缩技术缩小成足够短的字符串，以允许进行上述编码。

超过这个长度，我们开始失去文本中的信息。因此，执行以下步骤的最小次数可将字符串缩短至可使用上述方法进行压缩/编码的长度。此外，在子串上执行这些替换而不是在整个字符串上执行，如果这样做将使其变得足够短的话（我可能会从字符串的末尾开始遍历它）。

1. 用非重音字母或可能是一个通用符号替换所有高于127的拉丁1字符（主要是带重音的字母和奇怪的符号）。
2. 将所有大写字母替换为其相应的小写形式。
3. 将所有非字母数字（任何剩余的符号或标点符号）替换为空格。
4. 将所有数字替换为0。

现在，我们已经消除了尽可能多的多余字符。现在我们要进行一些更加戏剧性的缩减：

5. 将所有双字母（balloon）替换为单个字母（balon）。虽然看起来有点奇怪，但读者应该仍然能够理解它们。
6. 使用较短的等效项替换其他常见的字母组合（例如：CK用K替换、WR用R替换等）。

这是我们能够简化并使文本可读的最大限度。如果我们无法从中获得明显的信息，那么让我们看看是否可以找到一种方法，使文本虽然最终无法被理解，但仍类似于原始文本（同样地，从字符串的末尾逐个字符执行此操作，当长度足够短时停止）：

7. 将所有元音字母（aeiouy）替换为a。
8. 将所有“高”的字母（bdfhklt）替换为l。
9. 将所有“短”的字母（cmnrsvwxz）替换为n。
10. 将所有“悬挂”的字母（gjpq）替换为p。

这应该使我们得到一个字符串，由恰好5个可能的值（a、l、n、p和空格）组成，这些值应该允许我们编码相当长的字符串。

除此之外，我们只能简单截断。

我能想到的另一种技术是基于词典的编码，对于常见单词或字母组可能会对正确的语句有些好处，但对于任意字符串可能没有太大帮助。

- BradC

Answer 2

这是我对实际英语的变体。

每个代码点都有大约1100000种可能的状态。嗯，那是很多空间。

因此，我们提取所有原始文本并从中获取Wordnet同义词集。数字被转换为英文名称（“fourty two”）。1.1M个状态将允许我们保存同义词集ID（可以在0到82114之间），同义词集内的位置（大约10个变体，我想）和同义词集类型（其中四个 - 名词，动词，形容词，副词）。我们甚至可能有足够的空间来存储单词的原始形式（例如动词时态ID）。

解码器只需将同义词集提供给Wordnet并检索相应的单词即可。

源文本：

A white dwarf is a small star composed mostly of electron-degenerate matter. Because a
white dwarf's mass is comparable to that of the Sun and its volume is comparable to that 
of the Earth, it is very dense.

变成：

A white dwarf be small star composed mostly electron degenerate matter because white
dwarf mass be comparable sun IT volume be comparable earth IT be very dense

（使用 在線詞彙網 測試）。這段“代碼”應該占用27個代碼點。 當然，所有像'lol'和'L33T'這樣的“胡言亂語”都將永遠丟失。

- Kuroki Kaze

Answer 3

这里有一个简单的例子，它接受一个输入文件并删除任何非单词字符。

#! perl
use strict;
use warnings;
use 5.010;


use Getopt::Long;
use Pod::Usage;
use autodie;

my %opts = (
  infile  => '-',
  outfile => '-',
);
GetOptions (
  'encode|e'    => \$opts{encode},
  'decode|d'    => \$opts{decode},
  'infile|i=s'  => \$opts{infile},
  'outfile|o=s' => \$opts{outfile},
  'help|h'      => \&help,
  'man|m'       => \&man,
);

unless(
  # exactly one of these should be set
  $opts{encode} xor $opts{decode}
){
  help();
}


{
  my $infile;
  if( $opts{infile} ~~ ['-', '&0'] ){
    $infile = *STDIN{IO};
  }else{
    open $infile, '<', $opts{infile};
  }

  my $outfile;
  if( $opts{outfile} ~~ ['-', '&1'] ){
    $outfile = *STDOUT{IO};
  }elsif( $opts{outfile} ~~ '&2' ){
    $outfile = *STDERR{IO};
  }else{
    open $outfile, '>', $opts{outfile};
  }

  if( $opts{decode} ){
    while( my $line = <$infile> ){
      chomp $line;

      say {$outfile} $line;
    }
  }elsif( $opts{encode} ){
    while( my $line = <$infile> ){
      chomp $line;

      $line =~ s/[\W_]+/ /g;

      say {$outfile} $line;
    }
  }else{
    die 'How did I get here?';
  }
}

sub help{
  pod2usage();
}
sub man{
  pod2usage(1);
}
__END__

=head1 NAME

sample.pl - Using GetOpt::Long and Pod::Usage

=head1 SYNOPSIS

sample.pl [options] [file ...]

 Options:
   --help     -h      brief help message
   --man      -m      full documentation
   --encode   -e      encode text
   --decode   -d      decode text
   --infile   -i      input  filename
   --outfile  -o      output filename

=head1 OPTIONS

=over 8

=item B<--help>

Print a brief help message and exits.

=item B<--man>

Prints the manual page and exits.

=item B<--encode>

Removes any character other than /\w/.

=item B<--decode>

Just reads from one file, and writes to the other.

=item B<--infile>

Input filename. If this is '-' or '&0', then read from STDIN instead.
If you use '&0', you must pass it in with quotes.

=item B<--outfile>

Output filename. If this is '-' or '&1', then write to STDOUT instead.
If this is '&2', then write to STDERR instead.
If you use '&1' or '&2', you must pass it in with quotes.

=back

=head1 DESCRIPTION

B<This program> will read the given input file(s) and do something
useful with the contents thereof.

=cut

echo Hello, this is, some text | perl sample.pl -e
输出：Hello this is some text

- Brad Gilbert

---

如何无损地反转编码？ - ephemient

这个例子没有无损压缩，实际上我想鼓励一些有损压缩方案的例子。 - Brad Gilbert

Answer 4

PAQ8O10T << FTW

- Camilo Martin