Вот текстовый файл ASCII объемом 1,2 Мб, содержащий текст « Моби-Дика» Германа Мелвилла ; или Кит . Ваша задача состоит в том, чтобы написать программу или функцию (или класс и т. Д. - см. Ниже), которым будет присваиваться этот файл по одному символу за раз, и на каждом шаге должен угадываться следующий символ.

Это вызов кода . Ваша оценка будет

2*L + E

где L- размер вашего представления в байтах, и Eэто количество символов, которое он угадывает неправильно. Самый низкий балл побеждает.

Дальнейшие подробности

Ваша заявка будет программой или функцией (и т. Д.), Которая будет вызываться или вызываться или отправлять данные несколько раз. (1215235 раз, чтобы быть точным.) Когда он вызывается в n- ^й раз, ему присваивается n- ^й символ whale.txtили, whale2.txtи он должен вывести свое предположение для ( n + 1 ) ^-го символа. EКомпонент его счет будет общее количество символов , которые он не угадает.

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

Ваша программа должна выполняться детерминистически, так что она всегда делает одни и те же предположения при одинаковых входных данных (и, следовательно, всегда получает один и тот же результат).

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

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

Вы должны запустить свою тестовую программу и рассчитать / проверить свой счет перед отправкой заявки. Если ваша заявка идет слишком медленно, чтобы вы могли проверить ее оценку, тогда она не может участвовать в соревнованиях, даже если вы знаете, какой будет ее оценка в принципе.

LКомпонент вашего счета будет рассчитываться в соответствии с обычными правилами для вызовов кода для гольфа. Если ваша заявка будет содержать несколько файлов, обратите внимание на правила оценки и структуру каталогов в этом случае. Любые данные, которые использует ваш код, должны быть включены в ваш Lсчет.

Вы можете импортировать существующие библиотеки, но не можете загружать любые другие внешние файлы, и ваш код может не получить доступ к whale.txtилиwhale2.txtФайл любым способом, кроме описанного выше. Вы не можете загружать предварительно обученные нейронные сети или другие источники статистических данных. (Можно использовать нейронные сети, но вы должны включить данные о весе в свое представление и сосчитать их в счетчике байтов.) Если по какой-то причине в вашем языке или библиотеках есть функция, предоставляющая весь или весь текст Moby Dick Вы не можете использовать эту функцию. Кроме того, вы можете использовать любые другие встроенные или библиотечные функции, которые вам нравятся, в том числе связанные с обработкой текста, предсказанием или сжатием, если они являются частью вашего языка или его стандартных библиотек. Для более экзотических, специализированных подпрограмм, которые включают источники статистических данных, вы должны будете реализовать их самостоятельно и включить в свой счетчик байтов.

Вполне вероятно, что некоторые материалы будут включать компоненты, которые сами генерируются кодом. Если это так, пожалуйста, включите в свой ответ код, который использовался для их создания, и объясните, как это работает . (Пока этот код не нужен для запуска вашего представления, он не будет включен в ваш счетчик байтов.)

По историческим причинам существует две версии файла, и вы можете использовать любую из них в ответе. В whale2.txt(ссылка выше) текст не переносится, поэтому новые строки появляются только в конце абзацев. В оригинале whale.txtтекст оборачивается на ширину в 74 символа, поэтому вы должны прогнозировать конец каждой строки, а также прогнозировать текст. Это делает задачу более трудной, поэтому whale2.txtрекомендуется для новых ответов. Оба файла имеют одинаковый размер, 1215236 байт.

Подводя итог, все ответы должны включать в себя следующее:

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

Leaderboard

var QUESTION_ID=152856,OVERRIDE_USER=21034;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;

body{text-align:left!important}#answer-list,#language-list{padding:10px;width:380px;float:left}table thead{font-weight:700}table td{padding:5px}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Score</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

щедроты

Время от времени я буду предлагать награды, чтобы поощрять различные подходы.

Первый, 50 баллов, был присужден А. Рексу за лучший результат на тот момент.

Второе, 100 баллов, было также присуждено А. Рексу за тот же ответ, потому что они добавили очень хорошее объяснение к своему существующему ответу.

Следующая награда, 200 баллов , будет присуждена

• Конкурентный ответ, который использует новую технику. (Это будет основано на моем субъективном суждении, поскольку в награду входит мой представитель, но вы можете доверять мне, чтобы быть справедливым. Обратите внимание, что ваш ответ должен содержать достаточно объяснений, чтобы я мог понять, как это работает!) Такой ответ не нужен Не берите наивысший балл, это просто необходимо сделать достаточно хорошо по сравнению с существующими ответами. Я особенно заинтересован в том, чтобы увидеть решения, основанные на рекуррентных нейронных сетях, но я буду награждать награду всем, что кажется достаточно отличным от марковских моделей, которые доминируют в текущих высших оценках.

Или же:

• Любой, кто бьет лучший результат А. Рекса (в настоящее время 444444), используя любой метод.

После получения награды в 200 баллов я, скорее всего, предложу 400 баллов, соответственно обновив требования.

/// , 2 * 1 + 1020874 = 1020876

Печатает пробел.

Node.js, 2 * 224 + 524279 = 524727

Пожалуйста, обратитесь к журналу изменений в конце этого поста для обновления результатов.

Функция, принимающая и возвращающая байт.

a=[...l='14210100'],m={},s={},b={}
f=c=>a.some((t,n)=>x=s[y=l.slice(n)]>t|/^[A-Z '"(]/.test(y)&&b[y],l+=String.fromCharCode(c),a.map((_,n)=>(m[x=l.slice(n)]=-~m[x])<s[y=l.slice(n,8)]||(s[y]=m[x],b[y]=c)),l=l.slice(1))&&x||32

Он состоит из простой модели PPM, которая просматривает последние 8 символов, чтобы предсказать следующий.

Мы доверяем шаблону длины L, когда встречаемся с ним по крайней мере T [L] раз, где T - массив произвольных порогов: [1,1,2,1,2,3,5,2] . Кроме того, мы всегда доверяем шаблону, чей первый символ совпадает [A-Z '"(].

Мы выбираем самый длинный доверенный шаблон и возвращаем прогноз с наивысшей оценкой, связанной с этим шаблоном во время вызова.

Примечания

• Это, очевидно, не оптимизировано для скорости, но на моем ноутбуке оно работает примерно за 15 секунд.

• Если бы нам было позволено повторить процесс несколько раз подряд без сброса модели, число ошибок сравнялось бы с ~ 268000 после 5 итераций.

• Текущий показатель успеха функции прогнозирования составляет ~ 56,8%. Как заметил @immibis в комментариях, если плохие и правильные догадки смешиваются вместе, результат даже едва читаем.

  Например, этот фрагмент в конце книги:

  Here be it said, that this pertinacious pursuit of one particular whale,[LF]
  continued through day into night, and through night into day, is a thing[LF]
  by no means unprecedented in the South sea fishery.
  

  будет выглядеть так:

  "e e be it said, that thes woacangtyous sarsuet of tie oort cular thale[LF][LF]
   orsinued toeough tir on e togh   and sheough toght an o ters af t shin[LF][LF]
  be to means insrocedented tn hhe sputh Sevsaonh ry,
  

  Заменив неверные догадки на подчеркивания, мы лучше понимаем, что получилось с этой функцией:

  _e_e be it said, that th_s _____n___ous __rsu_t of __e __rt_cular _hale_[LF]
  _o__inued t__ough ___ _n__ __gh__ and _h_ough __ght _n_o ____ __ _ _hin_[LF]
  b_ _o means _n_r_cedented _n _he __uth _e_____h_ry_
  

  _{Примечание : приведенный выше пример был создан с предыдущей версией кода, работающей с первой версией входного файла.}

Тестовый код

/**
  The prediction function f() and its variables.
*/
a=[...l='14210100'],m={},s={},b={}
f=c=>a.some((t,n)=>x=s[y=l.slice(n)]>t|/^[A-Z '"(]/.test(y)&&b[y],l+=String.fromCharCode(c),a.map((_,n)=>(m[x=l.slice(n)]=-~m[x])<s[y=l.slice(n,8)]||(s[y]=m[x],b[y]=c)),l=l.slice(1))&&x||32

/**
  A closure containing the test code and computing E.
  It takes f as input.
  (f can't see any of the variables defined in this scope.)
*/
;
(f => {
  const fs = require('fs');

  let data = fs.readFileSync('whale2.txt'),
      len = data.length,
      err = 0;

  console.time('ElapsedTime');

  data.forEach((c, i) => {
    i % 100000 || console.log((i * 100 / len).toFixed(1) + '%');

    if(i < len - 1 && f(c) != data[i + 1]) {
      err++;
    }
  })

  console.log('E = ' + err);
  console.timeEnd('ElapsedTime');
})(f)

Журнал изменений

• 524727 - сэкономил 19644 балла, переключившись на whale2.txt (обновление задачи)
• 544371 - сэкономил 327 баллов, заставив шаблоны, начинающиеся с заглавной буквы, кавычки, двойной кавычки или открывающей скобки, также всегда доверять
• 544698 - сэкономил 2119 баллов, заставив шаблоны, начинающиеся с пробела, всегда доверять
• 546817 - сэкономил 47 баллов, настроив пороги и используя функцию прогнозирования
• 546864 - сохранено 1496 баллов за счет увеличения максимальной длины шаблона до 8 символов
• 548360 - сэкономил 6239 баллов, введя понятие доверенных шаблонов с пороговыми значениями в зависимости от их длины
• 554599 - сэкономлено 1030 баллов за счет улучшения прогноза перевода строки
• 555629 - сэкономил 22 балла, сыграв в гольф функцию прогнозирования
• 555651 - сэкономил 40 очков благодаря функции прогнозирования
• 555691 - начальная оценка

Perl, 2 · 70525 + 326508 = 467558

предсказатель

$m=($u=1<<32)-1;open B,B;@e=unpack"C*",join"",<B>;$e=2903392593;sub u{int($_[0]+($_[1]-$_[0])*pop)}sub o{$m&(pop()<<8)+pop}sub g{($h,%m,@b,$s,$E)=@_;if($d eq$h){($l,$u)=(u($l,$u,$L),u($l,$u,$U));$u=o(256,$u-1),$l=o($l),$e=o(shift@e,$e)until($l^($u-1))>>24}$M{"@c"}{$h}++-++$C{"@c"}-pop@c for@p=($h,@c=@p);@p=@p[0..19]if@p>20;@c=@p;for(@p,$L=0){$c="@c";last if" "ne pop@c and@c<2 and$E>99;$m{$_}+=$M{$c}{$_}/$C{$c}for sort keys%{$M{$c}};$E+=$C{$c}}$s>5.393*$m{$_}or($s+=$m{$_},push@b,$_)for sort{$m{$b}<=>$m{$a}}sort keys%m;$e>=u($l,$u,$U=$L+$m{$_}/$s)?$L=$U:return$d=$_ for sort@b}

Чтобы запустить эту программу, вам нужен этот файл , который должен быть назван B. (Вы можете изменить это имя файла во втором экземпляре символа Bвыше.) Ниже описано, как создать этот файл.

Программа использует комбинацию моделей Маркова в основном как в этом ответе пользователя 2699 , но с несколькими небольшими модификациями. Это создает распределение для следующего символа. Мы используем теорию информации, чтобы решить, принимать ли ошибку или тратить биты памяти на Bподсказки кодирования (и если да, то как). Мы используем арифметическое кодирование для оптимального хранения дробных битов из модели.

Длина программы составляет 582 байта (включая ненужный заключительный Bсимвол новой строки), а длина двоичного файла составляет 69942 байта, поэтому по правилам оценки нескольких файлов мы получаем L582 + 69942 + 1 = 70525.

Программа почти наверняка требует 64-битной (little-endian?) Архитектуры. Для запуска m5.largeэкземпляра на Amazon EC2 требуется примерно 2,5 минуты .

Тестовый код

# Golfed submission
require "submission.pl";

use strict; use warnings; use autodie;

# Scoring length of multiple files adds 1 penalty
my $length = (-s "submission.pl") + (-s "B") + 1;

# Read input
open my $IN, "<", "whale2.txt";
my $input = do { local $/; <$IN> };

# Run test harness
my $errors = 0;
for my $i ( 0 .. length($input)-2 ) {
    my $current = substr $input, $i, 1;
    my $decoded = g( $current );

    my $correct = substr $input, $i+1, 1;
    my $error_here = 0 + ($correct ne $decoded);
    $errors += $error_here;
}

# Output score
my $score = 2 * $length + $errors;
print <<EOF;
length $length
errors $errors
score  $score
EOF

Тестовый жгут предполагает, что отправка находится в файле submission.pl, но это можно легко изменить во второй строке.

Сравнение текста

"And did none of ye see it before?" cried Ahab, hailing the perched men all around him.\\"I saw him almost that same instant, sir, that Captain 
"And wid note of te fee bt seaore   cried Ahab, aasling the turshed aen inl atound him. \"' daw him wsoost thot some instant, wer, that Saptain 
"And _id no_e of _e _ee _t _e_ore__ cried Ahab, _a_ling the __r_hed _en __l a_ound him._\"_ _aw him ___ost th_t s_me instant, __r, that _aptain 

Ahab did, and I cried out," said Tashtego.\\"Not the same instant; not the same--no, the doubloon is mine, Fate reserved the doubloon for me. I 
Ahab aid  ind I woued tut,  said tashtego, \"No, the same instant, tot the same -tow nhe woubloon ws mane. alte ieserved the seubloon ior te, I 
Ahab _id_ _nd I ___ed _ut,_ said _ashtego__\"No_ the same instant_ _ot the same_-_o_ _he _oubloon _s m_ne_ __te _eserved the __ubloon _or _e_ I 

only; none of ye could have raised the White Whale first. There she blows!--there she blows!--there she blows! There again!--there again!" he cr
gnly  towe of ye sould have tersed the shite Whale aisst  Ihere ihe blows! -there she blows! -there she blows! Ahere arains -mhere again!  ce cr
_nly_ _o_e of ye _ould have ___sed the _hite Whale _i_st_ _here _he blows!_-there she blows!_-there she blows! _here a_ain__-_here again!_ _e cr

Этот образец (выбранный в другом ответе ) встречается довольно поздно в тексте, поэтому модель достаточно развита к этому моменту. Помните, что модель дополнена 70 килобайтами «подсказок», которые напрямую помогают ей угадывать символы; он не управляется просто коротким фрагментом кода выше.

Генерация подсказок

Следующая программа принимает точный код отправки выше (при стандартном вводе) и генерирует точный Bфайл выше (при стандартном выводе):

@S=split"",join"",<>;eval join"",@S[0..15,64..122],'open W,"whale2.txt";($n,@W)=split"",join"",<W>;for$X(0..@W){($h,$n,%m,@b,$s,$E)=($n,$W[$X]);',@S[256..338],'U=0)',@S[343..522],'for(sort@b){$U=($L=$U)+$m{$_}/$s;if($_ eq$n)',@S[160..195],'X<128||print(pack C,$l>>24),',@S[195..217,235..255],'}}'

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

объяснение

В этом разделе мы попытаемся описать, что делает это решение достаточно подробно, чтобы вы могли «попробовать его дома» самостоятельно. Основной метод, который отличает этот ответ от других, - это несколько разделов, называемых механизмом «перемотки», но прежде чем мы доберемся до этого, нам нужно настроить основы.

модель

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

В нашем случае мы по существу используем модель в этом ответе пользователя 2699 . Мы не использовали модель из ответа с наивысшим баллом (кроме нашего) Андерса Касеорга именно потому, что нам не удалось извлечь распределение, а не единственное лучшее предположение. Теоретически, этот ответ вычисляет средневзвешенное геометрическое значение, но мы получили несколько плохие результаты, когда интерпретировали это слишком буквально. Мы «украли» модель из другого ответа, потому что наш «секретный соус» - не модель, а общий подход. Если у кого-то есть «лучшая» модель, тогда он сможет добиться лучших результатов, используя остальные наши методы.

Как примечание, большинство методов сжатия, таких как Lempel-Ziv, можно рассматривать как «модель языка», хотя, возможно, придется немного щуриться. (Это особенно сложно для того, что выполняет преобразование Берроуза-Уилера!) Также обратите внимание, что модель user2699 является модификацией модели Маркова; по сути, ничто иное не является конкурентоспособным для этой задачи или, возможно, даже для моделирования текста в целом.

Общая архитектура

В целях понимания полезно разбить общую архитектуру на несколько частей. С точки зрения самого высокого уровня, должен быть небольшой код управления состоянием. Это не особенно интересно, но для полноты картины мы хотим подчеркнуть, что в каждой точке программы запрашивается следующая догадка, в ней есть правильный префикс Moby Dick. Мы никоим образом не используем наши прошлые неверные догадки. Ради эффективности, языковая модель, вероятно, может повторно использовать свое состояние из первых N символов для вычисления своего состояния для первых (N + 1) символов, но в принципе она может пересчитывать вещи с нуля каждый раз, когда она вызывается.

Давайте отложим этот основной «драйвер» программы и заглянем внутрь части, которая угадывает следующий символ. Концептуально это помогает разделить три части: языковую модель (обсуждаемую выше), файл «подсказок» и «интерпретатор». На каждом шаге переводчик будет запрашивать у языковой модели распределение следующего символа и, возможно, считывать некоторую информацию из файла подсказок. Тогда он объединит эти части в догадку. Точно какая информация содержится в файле подсказок, а также как она используется, будет объяснено позже, но пока она помогает мысленно разделить эти части. Обратите внимание, что в плане реализации файл подсказок является буквально отдельным (двоичным) файлом, но он мог быть строкой или чем-то другим, хранящимся внутри программы. В качестве приближения

Если используется стандартный метод сжатия, такой как bzip2, как в этом ответе , файл «подсказок» соответствует сжатому файлу. «Интерпретатор» соответствует декомпрессору, в то время как «языковая модель» немного неявна (как упомянуто выше).

Зачем использовать файл подсказки?

Давайте выберем простой пример для дальнейшего анализа. Предположим, что текст состоит из Nдлинных символов и хорошо аппроксимируется моделью, в которой каждый символ (независимо) представляет собой букву Eс вероятностью чуть меньше половины, Tаналогично с вероятностью чуть меньше половины и Aс вероятностью 1/1000 = 0,1%. Давайте предположим, что другие символы невозможны; в любом случае, Aэто очень похоже на случай ранее невидимого символа на ровном месте.

Если мы работаем в режиме L 0 (как большинство, но не все другие ответы на этот вопрос), нет лучшей стратегии для переводчика, чем выбрать один из Eи T. В среднем примерно половина символов будет правильной. Так что E ≈ N / 2 и оценка ≈ N / 2 тоже. Однако, если мы используем стратегию сжатия, мы можем сжать до чуть более одного бита на символ. Поскольку L считается в байтах, мы получаем L ≈ N / 8 и, таким образом, получаем значение ≈ N / 4, что вдвое больше, чем в предыдущей стратегии.

Достижение этой скорости чуть более одного бита на символ для этой модели немного нетривиально, но одним из методов является арифметическое кодирование.

Арифметическое кодирование

Как известно, кодирование - это способ представления некоторых данных с использованием битов / байтов. Например, ASCII - это 7-битная / символьная кодировка английского текста и связанных с ним символов, и это кодировка исходного файла Moby Dick, который мы рассматриваем. Если некоторые буквы встречаются чаще, чем другие, то кодирование с фиксированной шириной, например ASCII, не является оптимальным. В такой ситуации многие люди тянутся к кодированию Хаффмана . Это оптимально, если вам нужен фиксированный (без префикса) код с целым числом битов на символ.

Однако арифметическое кодирование еще лучше. Грубо говоря, он может использовать «дробные» биты для кодирования информации. В Интернете доступно множество руководств по арифметическому кодированию. Здесь мы пропустим детали (особенно практической реализации, которая может быть немного хитрой с точки зрения программирования) из-за других ресурсов, доступных онлайн, но если кто-то пожалуется, возможно, этот раздел может быть расширен более подробно.

Если у вас есть текст, фактически сгенерированный известной языковой моделью, то арифметическое кодирование обеспечивает по существу оптимальное кодирование текста из этой модели. В некотором смысле это «решает» проблему сжатия для этой модели. (Таким образом, на практике основная проблема заключается в том, что модель неизвестна, и некоторые модели лучше, чем другие, моделируют человеческий текст.) Если в этом конкурсе не было допущено ошибок, то на языке предыдущего раздела Одним из способов решения этой проблемы было бы использование арифметического кодера для генерации файла «подсказок» из языковой модели, а затем использование арифметического декодера в качестве «интерпретатора».

В этом по существу оптимальном кодировании мы в конечном итоге тратим -log_2 (p) битов на символ с вероятностью p, а общая скорость кодирования - энтропия Шеннона . Это означает, что для символа с вероятностью, близкой к 1/2, требуется около одного бита для кодирования, а для символа с вероятностью 1/1000 - около 10 битов (поскольку 2 ^ 10 составляет примерно 1000).

Но показатель выигрыша для этой задачи был выбран правильно, чтобы избежать сжатия в качестве оптимальной стратегии. Мы должны найти способ сделать несколько ошибок в качестве компромисса для получения более короткого файла подсказок. Например, одна стратегия, которую можно попробовать, - это простая стратегия ветвления: мы обычно пытаемся использовать арифметическое кодирование, когда можем, но если распределение вероятностей из модели «плохое», мы просто угадываем наиболее вероятный символ и не не пытайтесь его кодировать.

Зачем делать ошибки?

Давайте проанализируем предыдущий пример, чтобы мотивировать, почему мы можем захотеть делать ошибки «намеренно». Если мы используем арифметическое кодирование для кодирования правильного символа, мы потратим примерно один бит в случае с Eили T, но около десяти бит в случае с A.

В целом, это довольно хорошая кодировка, тратящая чуть больше на символ, хотя есть три возможности; в принципе, Aэто маловероятно, и мы не заканчиваем тратить соответствующие десять бит слишком часто. Однако разве не было бы неплохо, если бы мы могли просто сделать ошибку вместо случая A? В конце концов, метрика для проблемы считает, что 1 байт = 8 бит длины эквивалентен 2 ошибкам; таким образом, кажется, что следует предпочесть ошибку, а не тратить более 8/2 = 4 бита на символ. Тратить больше байта на сохранение одной ошибки определенно звучит неоптимально!

Механизм «перемотки»

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

Для простого примера, который мы анализировали, механизм перемотки особенно прост. Интерпретатор читает один бит из файла подсказок. Если это 0, он угадывает E. Если это 1, он угадает T. В следующий раз, когда он вызывается, он видит правильный символ. Если файл подсказки настроен правильно, мы можем убедиться, что в случае Eили Tинтерпретатор правильно угадывает. Но как насчет A? Идея механизма перемотки заключается в том, чтобы просто не кодировать Aвообще . Точнее, если интерпретатор позже узнает, что правильный символ был A, он метафорически « перематывает ленту»: он возвращает бит, который он прочитал ранее. Бит, который он читает, намеревается закодировать EилиT, но не сейчас; это будет использовано позже. В этом простом примере это в основном означает, что он продолжает угадывать один и тот же символ ( Eили T) до тех пор, пока не получит его правильно; затем он читает еще один бит и продолжает идти.

Кодировка для этого файла подсказок очень проста: превратить все Es в 0 бит и Ts в 1 бит, полностью игнорируя As. В результате анализа в конце предыдущего раздела эта схема допускает некоторые ошибки, но снижает общий балл, не кодируя ни одну из As. В меньшем эффекте, он на самом деле экономит на длину намеков файла , а также, потому что мы в конечном итоге , используя ровно один бит для каждого Eи T, вместо того , чтобы немного больше , чем немного.

Маленькая теорема

Как мы решаем, когда сделать ошибку? Предположим, что наша модель дает нам распределение вероятности P для следующего символа. Мы разделим возможные символы на два класса: кодированные и не кодированные . Если правильный символ не закодирован, то мы в конечном итоге будем использовать механизм «перемотки», чтобы принять ошибку бесплатно. Если правильный символ закодирован, то мы будем использовать какой-то другой дистрибутив Q для его кодирования с использованием арифметического кодирования.

Но какое распределение Q мы должны выбрать? Нетрудно понять, что все кодированные символы должны иметь более высокую вероятность (в P), чем не кодированные символы. Также в дистрибутив Q должны входить только кодированные символы; в конце концов, мы не кодируем другие, поэтому мы не должны «тратить» на них энтропию. Немного сложнее увидеть, что распределение вероятностей Q должно быть пропорционально P на кодированных символах. Объединение этих наблюдений означает, что мы должны кодировать наиболее вероятные символы, но, возможно, не менее вероятные символы, и что Q - это просто P, масштабируемый на кодированных символах.

Более того, оказывается, что есть классная теорема о том, какой «обрез» нужно выбрать для кодирующих символов: вы должны кодировать символ, если он по меньшей мере равен 1 / 5,393 с той же вероятностью, что и другие кодированные символы вместе взятые. Это «объясняет» появление, казалось бы, случайной константы 5.393ближе к концу указанной выше программы. Число 1 / 5,393 ≈ 0,18542 является решением уравнения -p log (16) - p log p + (1 + p) log (1 + p) = 0 .

Возможно, разумно написать эту процедуру в коде. Этот фрагмент находится в C ++:

// Assume the model is computed elsewhere.
unordered_map<char, double> model;

// Transform p to q
unordered_map<char, double> code;
priority_queue<pair<double,char>> pq;
for( char c : CHARS )
    pq.push( make_pair(model[c], c) );
double s = 0, p;
while( 1 ) {
    char c = pq.top().second;
    pq.pop();
    p = model[c];
    if( s > 5.393*p )
        break;
    code[c] = p;
    s += p;
}
for( auto& kv : code ) {
    char c = kv.first;
    code[c] /= s;
}

Собираем все вместе

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

1. Добавьте правильный символ к известному правильному префиксу Моби Дика.
2. Обновите (марковскую) модель текста.
3. Секретный соус : Если предыдущее предположение было неверным, перемотать состояние арифметического декодера его состояние перед предыдущей догадкой!
4. Попросите модель Маркова предсказать распределение вероятности P для следующего символа.
5. Преобразуйте P в Q, используя подпрограмму из предыдущего раздела.
6. Попросите арифметический декодер декодировать символ из оставшейся части файла подсказок в соответствии с распределением Q.
7. Угадай получившегося персонажа.

Кодировка файла подсказок работает аналогично. В этом случае программа знает, какой правильный следующий символ. Если это символ, который должен быть закодирован, тогда, конечно, следует использовать арифметический кодер на нем; но если это не кодированный символ, он просто не обновляет состояние арифметического кодировщика.

Если вы понимаете теоретико-информационный фон, такой как распределение вероятностей, энтропия, сжатие и арифметическое кодирование, но пытались и не смогли понять этот пост (за исключением того, почему теорема верна), дайте нам знать, и мы можем попытаться прояснить ситуацию. Спасибо за чтение!

Python 3, 2 · 267 + 510193 = 510727

предсказатель

def p():
 d={};s=b''
 while 1:
  p={0:1};r=range(len(s)+1)
  for i in r:
   for c,n in d.setdefault(s[:i],{}).items():p[c]=p.get(c,1)*n**b'\1\6\f\36AcWuvY_v`\270~\333~'[i]
  c=yield max(sorted(p),key=p.get)
  for i in r:e=d[s[:i]];e[c]=e.get(c,1)+1
  s=b'%c'%c+s[:15]

При этом используется взвешенная байесовская комбинация моделей Маркова порядка 0,…, 16 с весами [1, 6, 12, 30, 65, 99, 87, 117, 118, 89, 95, 118, 96, 184, 126, 219, 126].

Результат не очень чувствителен к выбору этих весов, но я оптимизировал их, потому что я мог, используя тот же алгоритм подъема на поздние этапы приема, который я использовал в своем ответе на вопрос «Собрать большинство в Сенате» , где каждая кандидатская мутация только увеличение ± 1 до одного веса.

Тестовый код

with open('whale2.txt', 'rb') as f:
    g = p()
    wrong = 0
    a = next(g)
    for b in f.read():
        wrong += a != b
        a = g.send(b)
    print(wrong)

Python 3 , 2 * 279 + 592920 = 593478 2 * 250 + 592467 = 592967 2 * 271 + 592084 = 592626 2 * 278 + 592059 = 592615 2 * 285 + 586660 = 587230 2 * 320 + 585161 = 585801 2 * 339 + 585050 = 585728

d=m={}
s=1
w,v='',0
def f(c):
 global w,m,v,s,d
 if w not in m:m[w]={}
 u=m[w];u[c]=c in u and 1+u[c]or 1;v+=1;q=n=' ';w=w*s+c;s=c!=n
 if w in m:_,n=max((m[w][k],k)for k in m[w])
 elif s-1:n=d in'nedtfo'and't'or'a'
 elif'-'==c:n=c
 elif"'"==c:n='s'
 elif'/'<c<':':n='.'
 if v>4*(n!=q)+66:n='\n'
 if s:d=c
 if c<q:w=w[:-1]+q;v=s=0
 return n

Попробуйте онлайн!

Функция, использующая глобальные переменные. Изучая, как это происходит, выстраивая модель на уровне слова: учитывая то, что он видел в этом слове , какой персонаж чаще всего встречается? По мере того, как вводится больше информации, он довольно хорошо изучает обычные слова из текста, а также изучает наиболее распространенный символ для начала следующего слова.

Например:

• Если то, что он видел до сих пор, это «Captai», он предсказывает «n»
• Если это «Капитан», он предсказывает пробел
• Если это начало слова, а последним словом было «Капитан», оно предсказывает «А»
• Если до сих пор слово «A», оно предсказывает «h» (а затем «a» и «b»; аналогично для «C»).

В начале это не очень хорошо, но к концу появляются большие части реальных слов. Резервный вариант - это пробел, а после единственного пробела это «а», если предыдущей буквой не было «nedtfo», цифры, дефиса или апострофа. Он также агрессивно предсказывает разрывы строк после 71 символа, или если после 66 ожидался пробел. Оба из них были только настроены на данные («t» гораздо чаще встречается после пробела, но чаще уже предсказывалось, поэтому » «это лучшее предположение за пределами этих шести особых случаев).

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

В итоге получается такой текст:

nl tneund his    I woi tis tnlost ahet toie tn tant  wod, ihet taptain Ahab ses
 snd t
oeed Sft   aoid thshtego    Io, fhe soie tn tant  tot the soie      ahe sewbtoon
swn tagd  aoths eatmved fhe sewbtoon wor ta  I sfey  aote of totsonld nive betse
d ahe
hate Whale iorst  Ihe e ioi beaos! -there soi beaos! -there soi beaos!

что соответствует этой части ввода:

все вокруг него.

«Я видел его почти в то же мгновение, сэр, как и капитан Ахав, и я закричал», - сказал Таштего.

«Не в одно мгновение; не в то же самое - нет, дублон мой, судьба зарезервировала для меня дублон. Только я; никто из вас не мог поднять Белого кита первым. Там она дует! - там она дует! - - вот она и дует!

Вы можете видеть, где, в частности, правильные существительные получаются довольно хорошо, но концы слов в основном правильные. Когда он видит «доу», он ожидает «сомнения», но как только появляется «я», он получает «дублон».

Если вы запускаете его второй раз с той же моделью, которую он только что построил, он сразу же получает правильные 92 КБ (51,7% -> 59,3%), но это всегда чуть меньше 60% от второй итерации.

Код измерения находится в ссылке TIO, или вот немного лучшая версия:

total = 0
right = 0
with open('whale.txt') as fp:
    with open('guess.txt', 'w') as dest:
        for l in fp.readlines():
            for c in l:
                last = c
                if p == c: right += 1
                n = f(c)
                p = n
                total += 1
                dest.write(n)
                if total % 10000 == 0:
                    print('{} / {} E={}\r'.format(right, total, total-right), end='')
print('{} / {}: E={}'.format(right, total, total - right))

guess.txt имеет угаданный вывод в конце.

C ++, оценка: 2 * 132 + 865821 = 866085

Спасибо @Quentin за сохранение 217 байтов!

int f(int c){return c-10?"t \n 2  sS \n  -  08........       huaoRooe oioaoheu thpih eEA \n   neo    enueee neue hteht e"[c-32]:10;}

Очень простое решение, которое, учитывая символ, просто выводит символ, который чаще всего появляется после вводимого символа.

Проверьте счет с:

#include <iostream>
#include <fstream>

int f(int c);

int main()
{
    std::ifstream file;
    file.open("whale2.txt");

    if (!file.is_open())
        return 1;

    char p_ch, ch;
    file >> std::noskipws >> p_ch;
    int incorrect = 0;
    while (file >> std::noskipws >> ch)
    {
        if (f(p_ch) != ch)
            ++incorrect;
        p_ch = ch;
    }

    file.close();

    std::cout << incorrect;
}

Изменить: Использование whale2.txtдает лучший результат.

Python, 2 * 516 + 521122 = 522154

Алгоритм:

В еще одном представлении Python этот алгоритм вычисляет наиболее вероятную следующую букву, просматривая последовательности длиной 1, ..., l. Используется сумма вероятностей, и есть несколько приемов, чтобы получить лучшие результаты.

from collections import Counter as C, defaultdict as D
R,l=range,10
s,n='',[D(C) for _ in R(l+1)]
def A(c):
 global s;s+=c;
 if len(s)<=l:return ' '
 P=D(lambda:0)
 for L in R(1,l+1):
  w=''.join(s[-L-1:-1]);n[L][w].update([c]);w=''.join(s[-L:])
  try:
   q,z=n[L][w].most_common(1)[0];x=sum(list(n[L][w].values()))
  except IndexError:continue
  p=z/x
  if x<3:p*=1/(3-x)
  P[q]+=p
 if not P:return ' '
 return max(P.items(),key=lambda i:i[1])[0]
import this, codecs as d
[A(c) for c in d.decode(this.s, 'rot-13')]

Результаты:

В основном тарабарщина, хотя вы можете заметить, что она появляется на случайной фразе, такой как «Отец Мэппл».

errors: 521122
TRAINING:
result:  tetlsnowleof the won -opes  aIther Mapple,woneltnsinkeap hsd   lnd the  thth a shoey,aeidorsbine ao
actual: ntal knobs of the man-ropes, Father Mapple cast a look upwards, and then with a truly sailor-like bu
FINAL:
result: mnd wnd round  ahe   ind tveryaonsracting th ards the sol ens-ike aeock tolblescn the sgis of thet t
actual: und and round, then, and ever contracting towards the button-like black bubble at the axis of that s

Тестовый код:

Довольно просто, выводит несколько примеров текста в разных точках. Использует whale2.txt, так как это позволяет избежать дополнительной логики для вычисления новых строк.

from minified import A

def score(predict, text):
    errors = 0
    newtext = []
    for i, (actual, current) in  enumerate(zip(text[1:], text[:-1])):
        next = predict(current)
        errors += (actual != next)
        newtext.append(next)
        if (i % (len(text) // 100) == 0):
            print ('.', end='', flush=True)
    return errors, ''.join(newtext)

t = open('whale2.txt')
text = t.read()
err2, text2 = score(A, text)
print('errors:', err2)
print("TRAINING:")
print(text2[100000:100100].replace('\n', '\\n'))
print(text1[100001:100101].replace('\n', '\\n'))
print("FINAL:")
print(text2[121400:1215500].replace('\n', '\\n'))
print(text[121401:1215501].replace('\n', '\\n'))

С (gcc) , 679787 652892

84 76 байт, 679619 652740 неверных догадок

p[128][128][128][128];a,b,c,d;g(h){p[a][b][c][d]=h;h=p[a=b][b=c][c=d][d=h];}

Попробуйте онлайн!

Обновление: ~ 27000 очков с обновленным файлом, 16 очков (8 байт) с улучшенной функцией игры в гольф.

объяснение

Это работает так: когда код проходит по тексту, он запоминает последний символ, завершивший любую заданную 4-символьную последовательность, и возвращает это значение. В некоторой степени аналогично подходу Арно, описанному выше, но полагается на присущую ему вероятность двух заданных последовательностей из 4 символов, заканчивающихся одинаково.

Де-golfed:

p[128][128][128][128];
a,b,c,d;
g(h){
    p[a][b][c][d]=h; // Memorize the last character.
    h=p[a=b][b=c][c=d][d=h]; // Read the guess. We save several
                             // bytes with the assignments inside indices.
}

sh + bzip2, 2 * 364106 = 728212

2 * 381249 + 0 = 762498

dd if=$0 bs=1 skip=49|bunzip2&exec cat>/dev/null

сопровождаемый сжатым bzip2 whale2.txt с пропущенным первым байтом

Игнорирует его ввод; выводит правильный ответ. Это обеспечивает базовую линию на одном конце; Даниеро обеспечивает базовую линию на другом конце.

Скрипт строителя:

#!/bin/sh
if [ $# -ne 3 ]
then
    echo "Usage $0 gen.sh datafile output.sh"
    exit 1
fi

cat $1 > $3
dd ibs=1 if=$2 skip=1 | bzip2 -9 >> $3
chmod +x $3

Испытательный жгут I / O (tcc; отрезать первую строку для gcc). Этот тестовый комплект может быть использован любым пользователем на подходящей платформе, которая представляет полную программу, которая ожидает ввода / вывода для чтения / записи. Он использует байтовый ввод-вывод, чтобы избежать мошенничества. Дочерняя программа должна сбрасывать вывод после каждого байта, чтобы избежать блокировки.

#!/usr/bin/tcc -run
#include <stdio.h>
#include <stdlib.h>
#include <fcntl.h>
#include <unistd.h>
#include <errno.h>

int main(int argc, char **argv)
{
    volatile int result;
    int readfd[2];
    int writefd[2];
    int cppid;
    int bytecount;
    char c1, c2, c3;
    if (argc != 2) {
        printf("write X approximately -- service host\n");
        printf("Usage: %s serviceprocessbinary < source.txt\n", argv[0]);
        return 1;
    }
    /* Start service process */
    if (pipe(readfd)) {
        perror("pipe()");
        return 3;
    }
    if (pipe(writefd)) {
        perror("pipe()");
        return 3;
    }
    result = 0;
    if (!(cppid = vfork())) {
        char *argtable[3];
        argtable[0] = argv[1];
        argtable[1] = NULL;
        dup2(readfd[0], 0);
        dup2(writefd[1], 1);
        close(readfd[1]);
        close(writefd[0]);
        close(readfd[0]);
        close(writefd[1]);
        execvp(argv[1], argtable);
        if (errno == ENOEXEC) {
            argtable[0] = "/bin/sh";
            argtable[1] = argv[1];
            argtable[2] = NULL;
            /* old standard -- what isn't an executable
             * can be exec'd as a /bin/sh script */
            execvp("/bin/sh", argtable);
            result = ENOEXEC;
        } else {
            result = errno;
        }
        _exit(3);
    } else if (cppid < 0) {
        perror("vfork()");
        return 3;
    }
    if (result) {
        errno = result;
        perror("execvp()");
        return 3;
    }
    close(readfd[0]);
    close(writefd[1]);
    /* check results */
    read(0, &c2, 1);
    bytecount = 1;
    errno = 0;
    while (read(0, &c1, 1) > 0) {
        write(readfd[1], &c2, 1);
        if (read(writefd[0], &c3, 1) <= 0) {
            printf("%d errors (%d bytes)\n", result, bytecount);
            if (errno == 0)
                fprintf(stderr, "pipe: unexpected EOF\n");
            else
                perror("pipe");
            return 3;
        }
        if (c3 != c1)
            ++result;
        c2 = c1;
        ++bytecount;
    }
    printf("%d errors (%d bytes)\n", result, bytecount);
    return 0;
}

Python 3 , 879766

F=[[0]*123for _ in range(123)]
P=32
def f(C):global P;C=ord(C);F[P][C]+=1;P=C;return chr(max(enumerate(F[C]),key=lambda x:x[1])[0])

Попробуйте онлайн!

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

Объяснение:

Для каждого персонажа программа:

• увеличение frequency[prev][char]
• Найдите персонажа, который появляется чаще всего в frequency[char]
• и вывести его.

• Разгруженный код в ссылке TIO, закомментирован.
• Код составляет 131 байт.
• Код, запущенный на моей машине, сообщает:

879504 / 1215235
Time: 62.01348257784468

которые имеют общий балл

2*131 + 879504 = 879766

Поскольку нет никакого способа загрузить большой файл в TIO (кроме как спросить Денниса), пример запуска по ссылке TIO запускает программу только для небольшой части текста.

По сравнению со старым ответом, на этот раз на 362 больше неправильных символов, но код короче на 255 байт. Множитель заставляет мое представление иметь более низкий балл.

C #, 378 * 2 + 569279 = 570035

using System.Collections.Generic;using System.Linq;class P{Dictionary<string,Dictionary<char,int>>m=new
Dictionary<string,Dictionary<char,int>>();string b="";public char N(char
c){if(!m.ContainsKey(b))m[b]=new Dictionary<char,int>();if(!m[b].ContainsKey(c))m[b][c]=0;m[b][c]++;b+=c;if(b.Length>4)b=b.Remove(0,1);return
m.ContainsKey(b)?m[b].OrderBy(k=>k.Value).Last().Key:' ';}}

Этот подход использует справочную таблицу, чтобы узнать наиболее распространенный символ, который следует за данной строкой. Клавиши справочной таблицы имеют максимум 4 символа, поэтому функция сначала обновляет справочную таблицу текущим символом, а затем просто проверяет, какой символ наиболее вероятен после 4 предыдущих, включая текущий. , Если эти 4 символа не найдены в справочной таблице, она печатает пробел.

Эта версия использует whale2.txtфайл, так как это значительно улучшает количество удачных догадок.

Ниже приведен код, используемый для проверки класса:

using System;
using System.IO;
using System.Text;

public class Program
{
    public static void Main(string[] args)
    {
        var contents = File.OpenText("whale2.txt").ReadToEnd();
        var predictor = new P();

        var errors = 0;
        var generated = new StringBuilder();
        var guessed = new StringBuilder();
        for (var i = 0; i < contents.Length - 1; i++)
        {
            var predicted = predictor.N(contents[i]);
            generated.Append(predicted);
            if (contents[i + 1] == predicted)
                guessed.Append(predicted);
            else
            {
                guessed.Append('_');
                errors++;
            }
        }

        Console.WriteLine("Errors/total: {0}/{1}", errors, contents.Length);
        File.WriteAllText("predicted-whale.txt", generated.ToString());
        File.WriteAllText("guessed-whale.txt", guessed.ToString());

        Console.ReadKey();
    }
}

Код выполняется всего за 2 секунды. Для справки: вот что я получаю, когда меняю размер ключей таблицы соответствия (включая результаты второго запуска без сброса модели):

Size   Errors   Errors(2)
-------------------------
1      866162   865850
2      734762   731533
3      621019   604613
4      569279   515744
5      579446   454052
6      629829   396855
7      696912   335034
8      765346   271275
9      826821   210552
10     876471   158263

Было бы интересно узнать, почему размер ключа в 4 символа является лучшим выбором в этом алгоритме.

Сравнение текста

Оригинал:

"And did none of ye see it before?" cried Ahab, hailing the perched men all around him.

"I saw him almost that same instant, sir, that Captain Ahab did, and I cried out," said Tashtego.

"Not the same instant; not the same--no, the doubloon is mine, Fate reserved the doubloon for me. I only; none of ye could have raised the White Whale first. There she blows!--there she blows!--there she blows! There again!--there again!"

Воссоздал:

"Tnd tes note of to seamtn we ore  
sried thab  wedleng the srriead te  a l tneund tes  
"T day tim t lost shet toie tn tand  aor, ahet taptain thab sid  tnd t waued tnt   said teshtego  
"To, ahe shme tn tand  aot the shme whot nhe sewbteodsan tagd  althsteatnved the sewbteodsaor te, I hncy  aote of to sanld bave beised the shate Whale iorst  Bhe e ati boaos  -the   ati boaos  -the   ati boaos  the e anains -ahe   anains 

Догадки:

"_nd ___ no_e of __ se____ _e_ore____ried _hab_ ___l_ng the __r___d _e_ a_l ___und _____
"_ _a_ _im ___ost _h_t ___e _n_tan__ __r, _h_t _aptain _hab _id_ _nd _ ___ed __t__ said __shtego__
"_o_ _he s_me _n_tan__ _ot the s_me___o_ _he ___b__o____ _____ __t___e___ved the ___b__o___or _e_ I _n_y_ _o_e of __ ___ld _ave __ised the _h_te Whale __rst_ _he_e ___ b___s__-the__ ___ b___s__-the__ ___ b___s_ _he_e a_ain__-_he__ a_ain__

Журнал изменений

• 569279 - изменен whale2.txtи, следовательно, удален оптимизация.
• 577366 - оптимизирован с помощью кода, который пытался угадать, когда возвращать перевод строки.
• 590354 - оригинальная версия.

Java 7, 1995 символов, (1995 * 2 + 525158) 529148

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

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

Я остановился на использовании 9 символов и попытался сопоставить целые слова в этих предыдущих 9 символах, когда это возможно. Если вы не пытаетесь сопоставлять слова в строках, оптимальная длина составляет 6 символов, что приводит к еще нескольким тысячам неправильных предсказаний.

Одним интересным наблюдением было то, что использование 20 символов в первый раз приводило к ошибочным прогнозам, но при последующих проходах точность составляла 99,9%. Алгоритм был в основном способен запоминать книгу в перекрывающихся 20-байтовых кусках, и это было достаточно отчетливо, чтобы позволить ему вспомнить всю книгу за символ за раз.

• (1950 * 2 + 532919) 536819
• (2406 * 2 + 526233) 531045 проверка на пунктуацию, чтобы лучше угадать
• (1995 * 2 + 525158) 529148 больше настроек, игра в гольф немного словоблудия

package mobydick; import java.util.HashMap; public class BlindRankedPatternMatcher { String previousChars = ""; int FRAGLENGTH = 9; HashMap > patternPredictor = new HashMap<>(); void addWordInfo(String key, String prediction) { HashMap predictions = patternPredictor.get(key); if (predictions == null) { predictions = new HashMap(); patternPredictor.put(key, predictions); } WordInfo info = predictions.get(prediction); if (info == null) { info = new WordInfo(prediction); predictions.put(prediction, info); } info.freq++; } String getTopGuess (String pattern) { if (patternPredictor.get(pattern) != null) { java.util.List predictions = new java.util.ArrayList<>(); predictions.addAll(patternPredictor.get(pattern).values()); java.util.Collections.sort(predictions); return predictions.get(0).word; } return null; 
} String mainGuess() { 
if (trimGuess(",") != null) return trimGuess(","); if (trimGuess(";") != null) return trimGuess(";"); 
if (trimGuess(":") != null) return trimGuess(":"); 
if (trimGuess(".") != null) return trimGuess("."); if (trimGuess("!") != null) return trimGuess("!"); if (trimGuess("?") != null) return trimGuess("?"); if (trimGuess(" ") != null) return trimGuess(" "); for (int x = 0;x< previousChars.length();x++) { String tg = getTopGuess(previousChars.substring(x)); if (tg != null) { return tg; } } return "\n"; } String trimGuess(String c) { if (previousChars.contains(c)) { 
String test = previousChars.substring(previousChars.indexOf(c)); return getTopGuess(test); } return null; } public String predictNext(String newChar) { if (previousChars.length() < FRAGLENGTH) { previousChars+= newChar; } else { for (int x = 0; x addWordInfo(previousChars.substring(x), newChar); } previousChars = previousChars.substring(1) + newChar; } return mainGuess(); 
} class WordInfo implements Comparable { public WordInfo (String text) { this.word = text; } 
String word; int freq = 0; @Override public int compareTo(WordInfo arg0) { return Integer.compare(arg0.freq, this.freq); }

Python 3, 2 × 497 + 619608 = 620602 2 × 496 + 619608 = 620600

import operator as o
l=''
w=''
d={}
p={}
s=0
def z(x,y):
 return sorted([(k,v) for k,v in x.items() if k.startswith(y)],key=o.itemgetter(1))
def f(c):
 global l,w,d,p,s
 r=' '
 if c in' \n':
  s+=1
  if w in d:d[w]+=1
  else:d[w]=1
  if w:
   if l:
    t=l+' '+w
    if t in p:p[t]+=1
    else:p[t]=1
   n=z(p,w+' ')
   if n:g=n[-1];l=w;w='';r=g[0][len(l)+1]
   else:l=w;w='';r='t'
 else:
  w=w+c;m=z(p,w)
  if m:
   g=m[-1]
   if g[0]==w:
    if s>12:s=0;r='\n'
   else:r=g[0][len(w)]
 return r

Я попытался сделать это самостоятельно, но в итоге получился худший вариант ответа Майкла Гомера. Я надеюсь, что это не сделает мой ответ полностью устаревшим.

Со временем создается словарь слов (грубо определяется как строки, оканчивающиеся на или \nс учетом регистра и включая знаки препинания). Затем он ищет в этом словаре слова, начинающиеся с того, что ему до сих пор известно о текущем слове, сортирует результирующий список по частоте встречаемости (медленно) и догадывается, что следующий символ - следующий символ в наиболее распространенном совпадающем слове. Если у нас уже есть наиболее распространенное совпадающее слово или более не совпадающее слово существует, оно возвращается .

Это также создает отвратительно неэффективный словарь пар слов. При достижении границы слова он предполагает, что следующим символом является первая буква второго слова в наиболее часто встречающейся паре слов или tесли совпадения нет. Это не очень умно, хотя. После Mobyэтого программа правильно угадывает, что следующий символ - это следующий D, но затем она забывает все о контексте и обычно заканчивает тем, что называет кита «Moby Duck» (потому что слово «голландский», кажется, встречается чаще в первой половине текста ). Это было бы легко исправить, расставив приоритеты между парами слов над отдельными словами, но я ожидаю, что выигрыш будет незначительным (поскольку обычно он корректен с третьего символа, а пары слов не очень полезны в первую очередь).

Я мог бы настроить это, чтобы лучше соответствовать предоставленному тексту, но я не думаю, что ручная настройка алгоритма, основанная на предварительных знаниях ввода, действительно соответствует духу игры, за исключением выбора t в качестве запасного символа после пробела ( и я, вероятно, не должен был этого делать), я избежал этого. Я проигнорировал известную длину строки входного файла и вместо этого вставил \nпосле каждых 13 пробелов - это почти наверняка очень плохое совпадение, главное намерение было сохранить разумную длину строки, а не совпадать с вводом.

Код не очень быстрый (~ 2 часа на моем компьютере), но в целом получается примерно половина правильных символов (49%). Я ожидаю, что счет будет немного лучше, если продолжать whale2.txt, но я этого не сделал.

Начало вывода выглядит так:

T t t t t t t t t L t t t tsher t t t ty t to t t te t t t t t tem t t t d b ta tnL te t tv tath a to tr t tl t l toe g to tf ahe gi te we th austitam ofd laammars, tn te to t tis nf tim oic t t th tn cindkth ae tf t d bh ao toe tr ai tat tnLiat tn to ay to tn hf to tex tfr toe tn toe kex te tia t l t l ti toe ke tf hhe kirl tou tu the tiach an taw th t t Wh tc t d t te the tnd tn tate tl te tf teu tl tn oan. HeAL. tn nn tf r t-H ta t WhALE.... S tn nort ts tlom rhe ka tnd Dr t t tALL th teuli th tis t-H taCTIONARY " t r t o t a t A t . t eALT t I t HLW t I t e t w t AO t t t AOLE, I T t t t ALE t w t t R t EK t T t R tSupplied by wnLw t t iit ty cce thet whe to tal ty tnd

но в конце это выглядит немного больше как ... что-то. Мой любимый отрывок из ближе к концу книги,

и поскольку ни один из них не может быть моим, позвольте мне тогда буксировать на куски, все еще преследуя тебя, хотя и привязан к тебе, ты, проклятый кит! ТАК, я оставляю копье!

выходит как

I dhrnery oyay ooom the woc Ihal iiw chshtego -tit my ti ddohe bidmer Hh, ho sheee opdeprendera toetis of tygd ahesgapdo tnep tnd tf y arosl tinl ahesgaorsltoak, and tidlhty ai p, cnd telas taep toip syst ho she tachlhe tnd tith ut ay Rnet hor bf toom the wist tord oaeve of ty nsst toip recked,hontain th, tingly toadh af tingly tike 'h, tot a hoet ty oh ost sreat ess iik in ty oh ost sremf Hew hiw"aoom tnl tou oolthert tyand . taoneoo sot an ao syad tytlows of ty oii e oor hoi tike and th ohes if oaped uoueid tf ty ooadh Ih ards the t houle lhesganl p tyt tpdomsuera tiile ah the wist t hrenelidtith the Ioom ti p s di dd o hoinbtn the Ior tid toie o hoetefy oist tyoakh on the Opr tnl toufin and tnl ti dd .mh tf ooueon gaor tnd todce tovther lon by tygd ait my the th aih tapce ciice toill moaneng she thesgh thmd th the thesgaoy d jiile YhE t hrve tpothe woerk "

Это сделало бы Гнев Хана намного более запутанным. И «одинокий» → «покалывание» является особенно удовлетворительной заменой.

Изменить: один байт сохранен путем удаления постороннего пространства

счет

#! /usr/bin/env python3
import sys
import os
import mobydick as moby


def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)

total = 0
right = 0
real_char = ''
guess_char = 'T'
print('T',end='')
with open("whale.txt") as whale:
    while True:
        if real_char == guess_char:
            right += 1
        real_char = whale.read(1)
        if not real_char:
            eprint(str(right) + " / " + str(total) + " (" +
                str(right/total*100) + "%)")
            size = os.path.getsize("mobydick.py")
            eprint("Source size: " + str(size) + "B")
            eprint("Score: " + str(2*size + total - right))
            sys.exit(0)
        guess_char = moby.f(real_char)
        print(guess_char,end='')
        total += 1

Это запускает программу для текста Moby Dick и выводит «прогнозируемый» текст на стандартный вывод, а также злоупотребляет stderr для записи счета. Я бы порекомендовал перенаправить вывод в файл.

С ++, 2 · 62829 + 318786 = 444444

Чтобы запустить эту программу, вам нужен этот файл , который должен быть назван C.

В программе используется та же комбинация марковских моделей, что и в нашем предыдущем ответе . Как и прежде, эта комбинация по сути является моделью из этого ответа пользователя 2699 , но с небольшими изменениями.

Видя, как в этом ответе используется та же самая модель, что и раньше, улучшение является лучшим теоретико-информационным механизмом, чем механизм «перемотки», описанный ранее. Это позволяет делать меньше ошибок, а также иметь меньшую общую длину. Сама программа не очень удачна, потому что она не является основным источником оценки.

Длина программы составляет 2167 байт (включая все вкладки для отступа и множество других ненужных символов, но перед тестовым кодом), а Cдлина двоичного файла составляет 60661 байт, поэтому по правилам оценки нескольких файлов мы Lоцениваем как 2167 + 60661 + 1 = 62829.

Программа занимает приблизительно 8 минут для запуска на m5.4xlargeэкземпляре в Amazon EC2 и использует чуть более 16 ГБ памяти. (Это чрезмерное использование памяти не является необходимым - мы просто не оптимизировали это либо.)

#include <map>
#include <queue>
#include <vector>
using namespace std;

FILE *in;
unsigned int a, b = -1, c, d;
string s, t;
double l, h = 1, x[128][129], y[129], m[128];
map<string, int> N;
map<string, double[128]> M;
int G, S;

int f(int C)
{
    int i, j;
    for (i = 0; i <= 20 && i <= S; i++) {
        t = s.substr(S - i);
        N[t]++;
        M[t][C]++;
    }
    s += C;
    S++;

    for (i = 0; i < 128; i++)
        m[i] = 0;

    int E = 0;
    for (i = 20; i >= 0; i--) {
        if (i > S)
            continue;
        t = s.substr(S - i);
        if (i <= 2 && E >= 100 && (i == 0 || t[0] != ' '))
            break;
        if (M.find(t) == M.end())
            continue;
        for (j = 0; j < 128; j++) {
            m[j] += M[t][j] / N[t];
        }
        E += N[t];
    }

    double r = 0;
    for (i = 0; i < 128; i++)
        r += m[i];
    for (i = 0; i < 128; i++)
        m[i] = m[i] / r;

    if (!in) {
        in = fopen("C", "r");
        for (i = 0; i < 4; i++)
            c = c << 8 | getc(in);
    } else {
        l = x[C][G]
            + (l - y[G]) * (x[C][G + 1] - x[C][G]) / (y[G + 1] - y[G]);
        h = x[C][G]
            + (h - y[G]) * (x[C][G + 1] - x[C][G]) / (y[G + 1] - y[G]);
    }

    priority_queue<pair<double, int>> q;
    for (i = 0; i < 128; i++) {
        q.push(make_pair(m[i], i));
    }

    int n = 0;
    double s = 0;
    while (q.size()) {
        i = q.top().second;
        q.pop();
        if (m[i] < s / (n + 15))
            break;
        s += m[i];
        n++;
    }

    r = 0;
    for (i = 0; i < 128; i++) {
        y[i + 1] = m[i] - s / (n + 15);
        if (y[i + 1] < 0)
            y[i + 1] = 0;
        r += y[i + 1];
    }
    for (i = 0; i < 128; i++)
        y[i + 1] /= r;

    for (i = 0; i < 128; i++) {
        r = 0;
        for (j = 0; j < 128; j++) {
            x[i][j + 1] = y[j + 1];
            if (i == j)
                x[i][j + 1] *= 16;
            r += x[i][j + 1];
        }
        for (j = 0; j < 128; j++)
            x[i][j + 1] /= r;
        x[i][0] = 0;
        for (j = 0; j < 128; j++)
            x[i][j + 1] += x[i][j];
    }

    y[0] = 0;
    for (i = 0; i < 128; i++)
        y[i + 1] += y[i];

    for (G = 0; G < 128; G++) {
        if (y[G + 1] <= l)
            continue;
        if (y[G + 1] < h) {
            d = a + (b - a) * ((h - y[G + 1]) / (h - l));
            if (c <= d) {
                b = d;
                l = y[G + 1];
            } else {
                a = d + 1;
                h = y[G + 1];
            }
            while ((a ^ b) < (1 << 24)) {
                a = a << 8;
                b = b << 8 | 255;
                c = c << 8 | getc(in);
            }
        }
        if (h <= y[G + 1])
            return G;
    }
}
// End submission here.  Test code follows.
int main()
{
    FILE *moby = fopen("whale2.txt", "r");

    int E = 0;
    int c = getc(moby);
    while (c != EOF) {
        int guess = f(c);
        c = getc(moby);
        if (c != guess)
            E++;
    }

    printf("E=\t%d\n", E);

    return 0;
}

Python 3, 526640

274 байта, 526092 ошибки (при использовании whale2.txt). Это определенно способно к дальнейшему совершенствованию, но оно достигло стадии «достаточно хорошо, чтобы опубликовать».

from collections import*
D=defaultdict
M=[D(lambda:D(int))for i in range(10)]
X=""
def f(c):
 global X;G=D(int)
 for L in range(10):
  M[L][X[:L]][c]+=1;N=M[L][(c+X)[:L]]
  if N:g=max(N,key=lambda k:(N[k],k));G[g]+=N[g]*L**8
 X=(c+X)[:10]
 return max(G,key=lambda k:(G[k],k))

Идея состоит в том, чтобы хранить частоты всех серий 2, 3, 4, ..., 10 символов. Для каждой из этих длин L мы проверяем, соответствуют ли последние символы L-1 сохраненному шаблону; если это так, наше предположение g _L является наиболее частым следующим символом, следующим за этим шаблоном. Таким образом, мы собираем до девяти догадок. Чтобы решить, какое предположение использовать, мы взвешиваем частоту каждого паттерна по длине до 8-й степени. Выбирается предположение с наибольшей суммой взвешенных частот. Если нет подходящих шаблонов, мы предполагаем пространство.

(Максимальная длина шаблона и весовой показатель были выбраны методом проб и ошибок, чтобы дать наименьшее количество неверных догадок.)

Вот моя неутешительная версия в процессе разработки:

from collections import defaultdict

PATTERN_MAX_LEN = 10
prev_chars = ""
patterns = [defaultdict(lambda:defaultdict(int))
            for i in range(PATTERN_MAX_LEN)]
# A pattern dictionary has entries like {" wh": {"i": 5, "a": 9}}

def next_char(c):
    global prev_chars
    guesses = defaultdict(int)
    for pattern_len in range(PATTERN_MAX_LEN):
        # Update patterns dictionary based on pattern and c
        pattern = prev_chars[:pattern_len]
        patterns[pattern_len][pattern][c] += 1
        # Make a guess at the next letter based on pattern (including c)
        pattern = (c + prev_chars)[:pattern_len]
        if pattern in patterns[pattern_len]:
            potential_next_chars = patterns[pattern_len][pattern]
            guess = max(potential_next_chars,
                        key=lambda k:(potential_next_chars[k], k))
            frequency = potential_next_chars[guess]
            # Exact formula TBD--long patterns need to be heavily
            # advantaged, but not too heavily
            weight = frequency * pattern_len ** 8
            guesses[guess] += weight
    # Update prev_chars with the current character
    prev_chars = (c + prev_chars)[:PATTERN_MAX_LEN]
    # Return the highest-weighted guess
    return max(guesses, key=lambda k:(guesses[k], k))

И испытательный жгут:

from textPredictorGolfed import f as next_char
# OR:
# from textPredictor import next_char

total = 0
correct = 0
incorrect = 0

with open("whale2.txt") as file:
    character = file.read(1)
    while character != "":
        guess = next_char(character)
        character = file.read(1)
        if guess == character:
            correct += 1
        else:
            incorrect += 1
        total += 1

print("Errors:", incorrect, "({:.2f}%)".format(100 * incorrect / total))

Вот пример выходных данных в начале текста. Уже сейчас мы начинаем видеть возможность закончить общие слова после просмотра их первого письма ( in, to, and, by, а также, по- видимому, school).

 you take in hand to school others, and to teach them by what name a whale-fish
xU wshhlnrwn cindkgo dooool)tfhe -; wnd bo so rhoaoe ioy aienisotmhwnqiatl t n 

Ближе к концу, все еще есть много ошибок, но также есть много очень хороших последовательностей ( shmage seashawksнапример).

savage sea-hawks sailed with sheathed beaks. On the second day, a sail drew near
shmage seashawks wtidod oith tua dh   tyfr.  Tn the shaond tay, wnltiloloaa niar

Интересно взглянуть на некоторые ошибки и угадать, какое слово «ожидал» алгоритм. Например, после того sail, как программа оба раза предсказывает o- для sailor, я полагаю. Или, опять же, после , aтого , как он ожидает - nвозможно, из-за обычного возникновения , and.

Changelog:

• 274 * 2 + 526092 = 526640 Гольф алгоритм, за счет нескольких дополнительных ошибок
• 306 * 2 + 526089 = 526701 Оригинальная версия

Python 2, оценка: 2 * (407 + 56574) + 562262 = 676224

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

Код:

import zlib
f=open("d","rb")
l=zlib.decompress(f.read()).split()
w=""
def f(c):
 global w
 if c.isalpha():
  w+=c
  try:n=next(x for x in l if x.startswith(w))
  except StopIteration:return" "
  if len(n)>len(w):
   return list(n)[len(w)]
  return" "
 w="";
 n=ord(c)
 if n>31:
  return list("t \n 2  sS \n  -  08........       huaoRooe oioaoheu thpih eEA \n   neo    enueee neue hteht e")[n-32]
 return"\n"

Данные: https://www.dropbox.com/s/etmzi6i26lso8xj/d?dl=0

Тестирование:

incorrect = 0

with open("whale2.txt") as file:
    p_ch = ch = file.read(1)
    while True:
        ch = file.read(1)
        if not ch:
            break
        f_ch = f(p_ch)
        if f_ch != ch:
            incorrect += 1
        p_ch = ch

print incorrect

Изменить: Использование whale2.txtдает лучший результат.

С ++ (GCC), 725 × 2 + 527076 = 528526

Еще одна префиксная частота представления. Беги дальше whale2.txtи получай схожий (чуть хуже) счет, чем другие.

#import<bits/stdc++.h>
char*T="\n !\"$&'()*,-.0123456789:;?ABCDEFGHIJKLMNOPQRSTUVWXYZ[]_abcdefghijklmnopqrstuvwxyz";
int I[124];std::string P(7,0);struct D{int V=0;std::array<int,81>X{{0}};};std::vector<D>L(1);D
init(){for(int i=81;i--;)I[T[i]]=i;}int
f(int c){P=P.substr(1)+(char)I[c];for(int i=7;i--;){int D=0;for(char
c:P.substr(i)){if(!L[D].X[c]){L[D].X[c]=L.size();L.push_back({});}D=L[D].X[c];}++L[D].V;}std::vector<int>C(81);for(int
i=81;i--;)C[i]=i;for(int
i=0;i<7;++i){int D=0;for(char c:P.substr(i)){D=L[D].X[c];if(!D)break;}if(!D)continue;int M=0;for(int
x:C)M=std::max(M,L[L[D].X[x]].V);C.erase(std::remove_if(C.begin(),C.end(),[&](int
x){return L[L[D].X[x]].V!=M;}),C.end());if(C.size()<2)break;}return T[C[0]];}

Эта жадно находит самую длинную строку, которая начинается с суффикса истории, и, если есть несколько кандидатов, разрыв связи с более короткими строками.

Например: Если последние 7 символы abcdefgh, а строка abcdefghiи abcdefghjпоявляется с наибольшей частотой во всех строках формы abcdefgh*, на выходе будет либо iили j, тай - брейке с более короткими суффиксами ( bcdefgh, cdefgh, ...).

По неизвестным причинам, больше чем 7, и мой компьютер не имеет достаточно оперативной памяти для его запуска. Даже с 7 мне нужно закрыть все веб-браузеры, чтобы запустить его.

Тестовый код:

int main() {
    init(); 

    std::cout << "Start ---\n";
    std::time_t start = std::clock();

    std::ifstream file {"whale2.txt"};
    // std::ofstream file_guess {"whale_guess.txt"};
    std::ofstream file_diff {"whale_diff.txt"};
    if (!file.is_open()) {
        std::cout << "File doesn't exist\n";
        return 0;
    }

    char p_ch, ch;
    file >> std::noskipws >> p_ch;
    int incorrect = 0, total = 0;
    // file_diff << p_ch;

    int constexpr line_len = 80;
    std::string correct, guess_diff;
    correct += p_ch;
    guess_diff += '~';

    while (file >> ch) {
        char guess = f(p_ch);

        // file_guess << guess;
/*        if (guess != ch) {
            if (ch == '\n') {
                file_diff << "$";
            } else if (ch == ' ') {
                file_diff << '_';
            } else {
                file_diff << '~';
            }
        } else {
            file_diff << ch;
        }*/
        incorrect += (guess != ch);
        total += 1;
        p_ch = ch;

        if (guess == '\n') guess = '/';
        if (ch == '\n') ch = '/';
        correct += ch; guess_diff += (ch == guess ? ch == ' ' ? ' ' : '~' : guess);
        if (correct.length() == line_len) {
            file_diff << guess_diff << '\n' << correct << "\n\n";
            guess_diff.clear();
            correct.clear();
        }
    }

    file_diff << guess_diff << '\n' << correct << "\n\n";

    file.close();
    file_diff.close();

    std::cout << (std::clock() - start) 
    / double(CLOCKS_PER_SEC) << " seconds, "
    "score = " << incorrect << " / " << total << '\n';
}

Ungolfed:

size_t constexpr N = 7;

int constexpr NCHAR = 81;

std::array<int, NCHAR> const charset = {{
'\n', ' ', '!', '"', '$', '&', '\'', '(', ')', '*', ',', '-', '.', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', ':', ';', '?', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z', '[', ']', '_', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'
}}; // this actually contains a lot of information, may want to golf it
// (may take the idea of using AndersKaseorg's algorithm, late acceptance hill climbing)

std::array<int, 'z' + 1> const char_index = [](){
    std::array<int, 'z' + 1> char_index;
    for (size_t i = NCHAR; i --> 0;) 
        char_index[charset[i]] = i;
    return char_index;
}(); // IIFE ?

std::string past (N, 0); 
// modifying this may improve the score by a few units

struct node {
    int value = 0;
    std::array<size_t, NCHAR> child_index {{0}};
};
std::vector<node> node_pool (1); // root

int f(int c) {
    past = past.substr(1) + (char) char_index[c];

    for (size_t i = 0; i < N; ++i) {
        // add past.substr(i) to the string
        size_t node = 0;
        for (char c : past.substr(i)) {
            if (node_pool[node].child_index[c] == 0) {
                node_pool[node].child_index[c] = node_pool.size();
                node_pool.emplace_back();
            }
            node = node_pool[node].child_index[c];
        }
        assert(node != 0); // the substring is non-empty
        ++node_pool[node].value;
    }

    std::vector<size_t> candidates (NCHAR);
    std::iota(candidates.begin(), candidates.end(), 0);
    for (size_t i = 0; i < N; ++i) {
        size_t node = 0;
        for (char c : past.substr(i)) {
            node = node_pool[node].child_index[c];
            if (node == 0) break;
        }
        if (node == 0) continue;

        assert(node_pool[0].value == 0);
        int max_value = 0;
        for (size_t x : candidates)
            max_value = std::max(max_value, node_pool[node_pool[node].child_index[x]].value);

        candidates.erase(
            std::remove_if(candidates.begin(), candidates.end(), [&](size_t x){
                return node_pool[node_pool[node].child_index[x]].value != max_value;
            }), candidates.end()
        );

        if (candidates.size() == 1) 
            break;
    }

    return charset[candidates[0]];
}