Сжатие текста в Твиттере

Question

Правила

1. Ваша программа должна иметь два режима: кодировка и декодирование .

2. Когда кодировка :

   1. Ваша программа должна принимать в качестве входных данных некоторый читаемый человеком текст Latin1, предположительно на английском языке.
      • Неважно, если вы игнорируете знаки препинания.
      • Вам нужно беспокоиться только о реальных английских словах, а не L337.
      • Любые буквы с акцентом могут быть преобразованы в простые ASCII.
      • Вы можете выбрать способ работы с числами.
      • 123
        • один два три
        • сто двадцать три
        • 123
        • 1 2 3
      • сто двадцать три
        • один два три
        • сто двадцать три
        • 123
        • 1 2 3

   2. Ваша программа должна вывести сообщение, которое может быть представлено в

      • 140 кодовых точек в диапазоне U+0000 - U+10FFFF

        Исключая не-символы:

        • U+FFFE
        • U+FFFF
        • U+nFFFE, U+nFFFF, где n равно 1 - 10 шестнадцатеричный
        • U+FDD0U+FDEF
        • U+D800 - U+DFFF (суррогатные кодовые точки).

   Может выводиться в любой разумной кодировке по вашему выбору; любая кодировка, поддерживаемая GNU iconv, будет считаться разумной, и нативная кодировка вашей платформы или кодировка локали, вероятно, будут хорошим выбором.

3. При декодировании :

   1. Ваша программа должна принимать в качестве входных данных ваш режим кодирования .
   2. Вывод текста должен быть приближенным к вводимому тексту.
      • Чем ближе вы к оригинальному тексту, тем лучше.
      • Не нуждается в пунктуации.

   3. Выводимый текст должен быть доступен для чтения человеку, опять же предположительно на английском языке.

      • Может быть L337 или LOL.
   4. Процесс декодирования может не иметь доступа к каким-либо другим выходным данным процесса кодирования кроме выхода, указанного выше; то есть вы не можете загрузить текст куда-нибудь и вывести URL для процесса декодирования, чтобы загрузить, или что-нибудь глупое, как это.
4. Для согласованности в пользовательском интерфейсе ваша программа должна вести себя следующим образом:
   1. Ваша программа должна быть скриптом, который можно установить на исполняемый файл на платформе с соответствующим интерпретатором, или программа, которая может быть скомпилирована в исполняемый файл.
   2. Ваша программа должна принять в качестве первого аргумента либо encode, либо decode, чтобы установить режим.
   3. Ваша программа должна принимать данные как минимум одним из следующих способов:
      • Возьмите ввод со стандартного входа и произведите вывод на стандартный выход.
        • 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
5. Для вашего решения, пожалуйста, напишите:
   1. Ваш код полностью и / или ссылка на него, размещенная в другом месте (если он очень длинный или требует много файлов для компиляции, или что-то в этом роде).
   2. Объяснение того, как это работает, если это не сразу видно из кода или если код длинный и люди будут заинтересованы в резюме.
   3. Пример текста с исходным текстом, текстом, сжимаемым до него, и декодированным текстом.
   4. Если вы основываетесь на идее, которая была у кого-то другого, пожалуйста, приписывайте их. Можно попытаться усовершенствовать чужую идею, но вы должны приписать их.

Правила представляют собой вариацию правил для Задача кодирования изображений Twitter .

Answer 1

Не уверен, если у меня будет время / энергия, чтобы дополнить это реальным кодом, но вот моя идея:

• Любая произвольная строка LATIN 1 определенной длины может быть просто закодирована (даже не сжатая ) без потерь в 140 символов. Наивная оценка составляет 280 символов, хотя с учетом ограничений по коду в правилах конкурса она, вероятно, немного короче.
• Строки, немного превышающие указанную выше длину (можно предположить, что между 280 и 500 символами), скорее всего, могут быть сжаты с использованием стандартных методов сжатия до достаточно короткой строки, чтобы разрешить вышеуказанное кодирование.

Что-нибудь длиннее, и мы начинаем терять информацию в тексте. Поэтому выполните минимальное количество следующих шагов, чтобы уменьшить строку до длины, которая затем может быть сжата / кодирована с использованием вышеуказанных методов. Кроме того, не выполняйте эти замены для всей строки , если только выполнение их для подстроки сделает ее достаточно короткой (я, вероятно, прошел бы по строке назад).

1. Заменить все символы LATIN 1 выше 127 (в основном, ударные буквы и символы в стиле фанк) их ближайшим эквивалентом в неакцентированных буквенных символах или, возможно, заменой универсального символа, например "#"
2. Заменить все заглавные буквы на их эквивалентную строчную форму
3. Заменить все не алфавитно-цифровые символы (любые оставшиеся символы или знаки пунктуации) пробелом
4. Заменить все числа на 0

Хорошо, теперь мы удалили столько лишних символов, сколько мы можем разумно избавить. Теперь мы собираемся сделать несколько более существенных сокращений:

5. Заменить все двойные буквы (шарик) одной буквой (шарик). Будет выглядеть странно, но все же, надеюсь, расшифрован читателем.
6. Заменить другие общие буквенные комбинации более короткими эквивалентами (CK с K, WR с R и т. Д.)

Хорошо, это все, что мы можем сделать, чтобы текст был читабельным . Помимо этого, давайте посмотрим, сможем ли мы придумать метод, так что текст будет напоминать оригинал, даже если он в конечном итоге не будет дешифруемым (снова выполните этот символ в время от конца строки и остановка, когда она достаточно коротка):

7. Заменить все гласные (aeiouy) на
8. Заменить все "высокие" буквы (bdfhklt) на l
9. Заменить все "короткие" буквы (cmnrsvwxz) на n
10. Заменить все "висячие" буквы (gjpq) на p

Это должно оставить нам строку, состоящую ровно из 5 возможных значений (a, l, n, p и пробел), что должно позволить нам кодировать довольно длинные строки.

Кроме того, нам просто нужно было бы усечь.

Единственная другая техника, о которой я могу подумать, - это кодирование на основе словаря для общих слов или групп букв. Это может дать нам некоторую выгоду для правильных предложений, но, вероятно, не для произвольных строк.

Answer 2

Вот мой вариант для реального английского языка.

Каждая кодовая точка имеет примерно 1100000 возможных состояний. Ну, это много места.

Итак, мы остановим весь оригинальный текст и получим из него синтаксис Wordnet. Числа отлиты в английские имена («сорок два»). 1,1M состояния позволят нам хранить идентификатор набора (который может быть между 0 и 82114), положение внутри набора (около 10 вариантов, я полагаю) и тип набора (одно из четырех - существительное, глагол, прилагательное, наречие) , У нас даже может быть достаточно места для хранения оригинальной формы слова (например, идентификатора времени глагола).

Декодер просто передает наборы в 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

(протестировано с Интернет Wordnet ). Этот «код» должен занимать 27 кодов. Конечно, все "бред", такие как "LOL" и "L33T", будут потеряны навсегда.

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

Answer 4

PAQ8O10T << FTW </p>