Aqui está um arquivo de texto ASCII de 1.2Mb que contém o texto de Moby-Dick, de Herman Melville ; ou, a baleia . Sua tarefa é escrever um programa ou função (ou classe, etc. - veja abaixo) que receberá esse arquivo com um caractere de cada vez e, a cada passo, deve adivinhar o próximo caractere.

Este é um desafio de código . Sua pontuação será

2*L + E

onde Lé o tamanho do seu envio em bytes e Eo número de caracteres que ele adivinha incorretamente. A pontuação mais baixa vence.

Outras informações

Seu envio será um programa ou função (etc.) que será chamado, invocado ou enviado dados várias vezes. (1215235 vezes para ser exato). Quando ele é chamado para o n ^º tempo que será dado o n ^º personagem whale.txtou whale2.txte deve saída de seu palpite para o ( n + 1 ) ^th personagem. O Ecomponente de sua pontuação será o número total de caracteres que ele adivinha incorretamente.

A maioria dos envios precisará armazenar algum estado entre as chamadas, para que eles possam rastrear quantas vezes foram chamados e quais foram as entradas anteriores. Você pode fazer isso gravando em um arquivo externo, usando staticvariáveis ​​globais ou, enviando uma classe em vez de uma função, usando uma mônada de estado ou qualquer outra coisa que funcione no seu idioma. Seu envio deve incluir qualquer código necessário para inicializar seu estado antes da primeira chamada.

Seu programa deve executar deterministicamente, para que ele sempre faça as mesmas suposições com a mesma entrada (e, portanto, sempre obtenha a mesma pontuação).

Sua resposta deve incluir não apenas o envio, mas também o código que você usou para calcular a Eparte da pontuação. Isso não precisa ser escrito no mesmo idioma do seu envio e não será contado na contagem de bytes. Você é incentivado a torná-lo legível.

Com relação à interface entre o envio e o programa de cálculo de pontuação, tudo está bem, desde que o programa sempre dê um byte de saída antes de receber o próximo byte de entrada. (Portanto, por exemplo, você não pode simplesmente passar uma string contendo toda a entrada e obter uma string de volta contendo toda a saída.)

Você deve realmente executar seu programa de teste e calcular / verificar sua pontuação antes de enviar sua inscrição. Se o seu envio for muito lento para você verificar sua pontuação, ele não estará qualificado para competir, mesmo que você saiba qual seria sua pontuação em princípio.

O Lcomponente da sua pontuação será calculado de acordo com as regras usuais para desafios de golfe com código. Se o seu envio contiver vários arquivos, observe as regras de pontuação e estrutura de diretórios nesse caso. Todos os dados que seu código usa devem ser incluídos na sua Lpontuação.

Você pode importar bibliotecas existentes, mas não pode carregar outros arquivos externos, e seu código pode não acessar whale.txtouwhale2.txtarquivo de qualquer maneira que não seja a descrita acima. Você não pode carregar nenhuma rede neural pré-treinada ou outras fontes de dados estatísticos. (Não há problema em usar redes neurais, mas você deve incluir os dados de ponderação em sua submissão e contabilizá-los na contagem de bytes.) Se, por algum motivo, seu idioma ou bibliotecas incluírem um recurso que fornece parte ou todo o texto de Moby Dick , você não pode usar esse recurso. Além disso, você pode usar outros recursos internos ou de biblioteca que desejar, incluindo aqueles relacionados ao processamento, previsão ou compactação de texto, desde que façam parte do seu idioma ou de suas bibliotecas padrão. Para rotinas mais exóticas e especializadas que incluem fontes de dados estatísticos, você teria que implementá-las e incluí-las na sua contagem de bytes.

É provável que alguns envios incluam componentes que são gerados por código. Se for esse o caso, inclua na sua resposta o código que foi usado para produzi-los e explique como ele funciona . (Enquanto esse código não for necessário para executar seu envio, ele não será incluído na sua contagem de bytes.)

Por razões históricas, há duas versões do arquivo e você pode usá-las em uma resposta. Em whale2.txt(vinculado acima), o texto não é quebrado, portanto as novas linhas aparecem apenas no final dos parágrafos. No original, whale.txto texto é dividido em uma largura de 74 caracteres, portanto, você deve prever o final de cada linha e também o texto. Isso torna o desafio mais complicado, por isso whale2.txté recomendado para novas respostas. Ambos os arquivos têm o mesmo tamanho, 1215236 bytes.

Para resumir, todas as respostas devem incluir o seguinte:

• Sua submissão em si. (O código, além de todos os arquivos de dados que ele usa - esses podem ser links se forem grandes.)
• Uma explicação de como seu código funciona. Por favor, explique o método de E / S e também como ele prevê o próximo caractere. A explicação do seu algoritmo é importante, e boas explicações receberão recompensas de mim.
• O código que você usou para avaliar sua pontuação. (Se isso é idêntico a uma resposta anterior, você pode simplesmente vincular a ela.)
• Qualquer código que você usou para gerar seu envio, juntamente com uma explicação desse código. Isso inclui o código usado para otimizar parâmetros, gerar arquivos de dados etc. (isso não conta para a contagem de bytes, mas deve ser incluído na sua resposta.)

Entre os melhores

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>

Recompensas

De tempos em tempos, oferecerei recompensas para incentivar diferentes abordagens.

O primeiro, 50 pontos, foi concedido a A. Rex pela resposta de melhor pontuação da época.

O segundo, 100 pontos, também foi concedido a A. Rex, pela mesma resposta, porque eles adicionaram uma explicação muito boa à resposta existente.

A próxima recompensa, 200 pontos , será concedida a qualquer

• Uma resposta competitiva que utiliza uma nova técnica. (Isso será baseado no meu julgamento subjetivo, já que é meu representante que entra na recompensa, mas você pode confiar que eu seja justo. Observe que sua resposta precisa conter uma explicação suficiente para que eu entenda como funciona!) obter a pontuação máxima, ele precisa se sair razoavelmente bem em comparação com as respostas existentes. Estou particularmente interessado em encontrar soluções baseadas em redes neurais recorrentes, mas concederei a recompensa a qualquer coisa que pareça diferente o suficiente dos modelos de Markov que dominam as principais pontuações atuais.

Ou:

• Qualquer pessoa que supere a pontuação máxima de A. Rex (atualmente 444444), usando qualquer método.

Depois que a recompensa de 200 pontos for reivindicada, provavelmente ofereço uma de 400 pontos, atualizando os requisitos de acordo.

/// , 2 * 1 + 1020874 = 1020876

Imprime um espaço.

Node.js, 2 * 224 + 524279 = 524727

Consulte o log de alterações no final deste post para atualizações de pontuação.

Uma função que recebe e retorna um byte.

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

Consiste em um modelo PPM simples que analisa os últimos 8 caracteres para prever o próximo.

Confiamos em um padrão de comprimento L quando o encontramos pelo menos T [L] vezes, em que T é uma matriz de limites arbitrários: [1,1,2,1,2,3,5,2] . Além disso, sempre confiamos em um padrão cujo primeiro caractere corresponde [A-Z '"(].

Selecionamos o padrão confiável mais longo e retornamos a previsão com a pontuação mais alta associada a esse padrão no momento da chamada.

Notas

• Obviamente, isso não é otimizado para velocidade, mas é executado em cerca de 15 segundos no meu laptop.

• Se pudéssemos repetir o processo várias vezes seguidas sem redefinir o modelo, o número de erros convergiria para ~ 268000 após 5 iterações.

• A taxa de sucesso atual da função de previsão é de ~ 56,8%. Conforme observado por @immibis nos comentários, se palpites ruins e corretos são misturados, o resultado nem é quase legível.

  Por exemplo, este trecho próximo ao final do livro:

  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.
  

  torna-se:

  "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,
  

  Ao substituir palpites ruins por sublinhados, temos uma idéia melhor do que a função deu certo:

  _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_
  

  _{Nota : O exemplo acima foi criado com uma versão anterior do código, trabalhando na primeira versão do arquivo de entrada.}

Código de teste

/**
  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)

Log de alterações

• 524727 - economizou 19644 pontos ao mudar para whale2.txt (atualização do desafio)
• 544371 - economizou 327 pontos forçando padrões começando com letra maiúscula, aspas, aspas duplas ou parêntese de abertura a serem também sempre confiáveis
• 544698 - economizou 2119 pontos forçando padrões começando com um espaço para sempre ser confiável
• 546817 - economizou 47 pontos ajustando os limites e jogando golfe na função de previsão
• 546864 - salvou 1496 pontos, estendendo o comprimento máximo do padrão para 8 caracteres
• 548360 - economizou 6239 pontos ao introduzir a noção de padrões confiáveis, com limites dependendo do comprimento
• 554599 - economizou 1030 pontos melhorando a previsão de avanço de linha
• 555629 - economizou 22 pontos jogando a função de previsão
• 555651 - economizou 40 pontos jogando a função de previsão
• 555691 - pontuação inicial

Perl, 2 · 70525 + 326508 = 467558

Preditor

$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}

Para executar este programa, você precisa deste arquivo aqui , que deve ser nomeado B. (Você pode alterar esse nome de arquivo na segunda instância do caractere Bacima.) Veja abaixo como gerar esse arquivo.

O programa usa uma combinação de modelos de Markov essencialmente como nesta resposta do usuário 2699 , mas com algumas pequenas modificações. Isso produz uma distribuição para o próximo caractere. Usamos a teoria da informação para decidir se devemos aceitar um erro ou gastar bits de armazenamento em Bdicas de codificação (e, se sim, como). Utilizamos a codificação aritmética para otimizar os bits fracionários do modelo.

O programa tem 582 bytes (incluindo uma nova linha final desnecessária) e o arquivo binário Btem 69942 bytes; portanto, de acordo com as regras de pontuação de vários arquivos , obtemos L582 + 69942 + 1 = 70525.

O programa quase certamente requer uma arquitetura de 64 bits (little-endian?). Demora aproximadamente 2,5 minutos para executar em uma m5.largeinstância no Amazon EC2.

Código de teste

# 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

O equipamento de teste assume que o envio está no arquivo submission.pl, mas isso pode ser facilmente alterado na segunda linha.

Comparação de texto

"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

Este exemplo (escolhido em outra resposta ) ocorre bastante tarde no texto, portanto o modelo é bastante desenvolvido nesse ponto. Lembre-se de que o modelo é aumentado por 70 kilobytes de "dicas" que ajudam diretamente a adivinhar os personagens; não é direcionado simplesmente pelo pequeno trecho de código acima.

Gerando dicas

O programa a seguir aceita o código exato de envio acima (na entrada padrão) e gera o Barquivo exato acima (na saída padrão):

@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],'}}'

Demora aproximadamente o tempo necessário para executar o envio, pois ele executa cálculos semelhantes.

Explicação

Nesta seção, tentaremos descrever o que essa solução faz com detalhes suficientes para que você possa "experimentá-la em casa". A principal técnica que diferencia essa resposta das outras é algumas seções abaixo, como o mecanismo de "rebobinar", mas antes de chegarmos lá, precisamos configurar o básico.

Modelo

O ingrediente básico da solução é um modelo de linguagem. Para nossos propósitos, um modelo é algo que pega uma certa quantidade de texto em inglês e retorna uma distribuição de probabilidade no próximo caractere. Quando usamos o modelo, o texto em inglês será um prefixo (correto) de Moby Dick. Observe que a saída desejada é uma distribuição e não apenas um palpite para o caracter mais provável.

No nosso caso, usamos essencialmente o modelo nesta resposta do usuário2699 . Não usamos o modelo da resposta de maior pontuação (exceto a nossa) de Anders Kaseorg justamente porque não conseguimos extrair uma distribuição em vez de apenas um palpite. Em teoria, essa resposta calcula uma média geométrica ponderada, mas obtivemos resultados um pouco ruins quando a interpretamos literalmente. "Roubamos" um modelo de outra resposta, porque nosso "molho secreto" não é o modelo, mas a abordagem geral. Se alguém tiver um modelo "melhor", deverá conseguir melhores resultados usando o restante de nossas técnicas.

Como observação, a maioria dos métodos de compactação, como o Lempel-Ziv, pode ser vista como um "modelo de linguagem" dessa maneira, embora seja necessário apertar os olhos um pouco. (É particularmente complicado para algo que transforma uma Burrows-Wheeler!) Além disso, observe que o modelo por user2699 é uma modificação de um modelo de Markov; essencialmente, nada mais é competitivo para esse desafio ou talvez até modelar texto em geral.

Arquitetura geral

Para fins de entendimento, é bom dividir a arquitetura geral em várias partes. Da perspectiva de mais alto nível, é necessário haver um pouco de código de gerenciamento de estado. Isso não é particularmente interessante, mas, para ser completo, queremos enfatizar que, em todo momento, o programa é solicitado a adivinhar o seguinte, ele tem disponível um prefixo correto de Moby Dick. Nós não usamos nossas suposições incorretas do passado de forma alguma. Por uma questão de eficiência, o modelo de linguagem provavelmente pode reutilizar seu estado dos primeiros N caracteres para calcular seu estado para os primeiros (N + 1) caracteres, mas, em princípio, ele pode recompilar as coisas do zero toda vez que é invocado.

Vamos deixar esse "driver" básico de lado e espiar dentro da parte que adivinha o próximo caractere. Conceitualmente, ajuda a separar três partes: o modelo de linguagem (discutido acima), um arquivo de "dicas" e um "intérprete". A cada passo, o intérprete solicitará ao modelo de linguagem uma distribuição para o próximo caractere e possivelmente lerá algumas informações do arquivo de dicas. Em seguida, combinará essas partes em um palpite. Precisamente, quais informações estão no arquivo de dicas e como são usadas serão explicadas mais tarde, mas, por enquanto, ajuda a manter essas partes separadas mentalmente. Observe que, em termos de implementação, o arquivo de dicas é literalmente um arquivo (binário) separado, mas poderia ter sido uma string ou algo armazenado dentro do programa. Como uma aproximação,

Se alguém estiver usando um método de compactação padrão, como bzip2, como nesta resposta , o arquivo "dicas" corresponderá ao arquivo compactado. O "intérprete" corresponde ao descompressor, enquanto o "modelo de linguagem" é um pouco implícito (como mencionado acima).

Por que usar um arquivo de dica?

Vamos escolher um exemplo simples para analisar melhor. Suponha que o texto tenha Ncaracteres longos e bem aproximados por um modelo em que cada caractere seja (independentemente) a letra Ecom probabilidade ligeiramente menor que a metade, Tsimilarmente com probabilidade ligeiramente menor que a metade e Acom probabilidade 1/1000 = 0,1%. Vamos supor que nenhum outro personagem seja possível; de qualquer forma, Aé bem parecido com o de um personagem anteriormente invisível do nada.

Se operamos no regime L0 (como a maioria, mas não todas, das outras respostas a essa pergunta), não há melhor estratégia para o intérprete do que escolher uma das opções Ee T. Em média, ele receberá cerca da metade dos caracteres corretos. Então E ≈ N / 2 e a pontuação ≈ N / 2 também. No entanto, se usarmos uma estratégia de compactação, podemos compactar para um pouco mais de um bit por caractere. Como L é contado em bytes, obtemos L ≈ N / 8 e, portanto, obtemos ≈ N / 4, duas vezes melhor que a estratégia anterior.

Atingir essa taxa de pouco mais de um bit por caractere para este modelo não é trivial, mas um método é a codificação aritmética.

Codificação aritmética

Como é comumente conhecido, uma codificação é uma maneira de representar alguns dados usando bits / bytes. Por exemplo, ASCII é uma codificação de 7 bits / caracteres do texto em inglês e caracteres relacionados, e é a codificação do arquivo Moby Dick original em consideração. Se algumas letras são mais comuns que outras, uma codificação de largura fixa como ASCII não é ideal. Em tal situação, muitas pessoas buscam a codificação de Huffman . Isso é ideal se você deseja um código fixo (sem prefixo) com um número inteiro de bits por caractere.

No entanto, a codificação aritmética é ainda melhor. Grosso modo, é capaz de usar bits "fracionários" para codificar informações. Existem muitos guias para codificação aritmética disponíveis online. Iremos pular os detalhes aqui (especialmente a implementação prática, que pode ser um pouco complicada do ponto de vista da programação) por causa dos outros recursos disponíveis online, mas se alguém reclamar, talvez esta seção possa ser mais aprofundada.

Se houver texto realmente gerado por um modelo de linguagem conhecido, a codificação aritmética fornecerá uma codificação essencialmente ótima do texto desse modelo. Em certo sentido, isso "resolve" o problema de compactação desse modelo. (Portanto, na prática, a questão principal é que o modelo não é conhecido e alguns são melhores que outros na modelagem de texto humano.) Se não foi permitido cometer erros neste concurso, então no idioma da seção anterior , uma maneira de produzir uma solução para esse desafio seria usar um codificador aritmético para gerar um arquivo "dicas" a partir do modelo de linguagem e, em seguida, usar um decodificador aritmético como "intérprete".

Nesta codificação essencialmente ideal, acabamos gastando -log_2 (p) bits para um caractere com probabilidade p, e a taxa de bits geral da codificação é a entropia de Shannon . Isso significa que um caractere com probabilidade próxima a 1/2 leva cerca de um bit para codificar, enquanto um caractere com probabilidade 1/1000 leva cerca de 10 bits (porque 2 ^ 10 é aproximadamente 1000).

Mas a métrica de pontuação para esse desafio foi bem escolhida para evitar a compactação como a estratégia ideal. Teremos que descobrir uma maneira de cometer alguns erros como compensação por obter um arquivo de dicas mais curto. Por exemplo, uma estratégia que se pode tentar é uma estratégia simples de ramificação: geralmente tentamos usar a codificação aritmética quando possível, mas se a distribuição de probabilidade do modelo é "ruim", de alguma forma, apenas adivinhamos o personagem mais provável e não ' tente codificá-lo.

Por que cometer erros?

Vamos analisar o exemplo anterior para motivar por que podemos querer cometer erros "intencionalmente". Se usarmos a codificação aritmética para codificar o caractere correto, gastaremos aproximadamente um bit no caso de um Eou T, mas cerca de dez bits no caso de um A.

No geral, essa é uma codificação muito boa, gastando um pouco mais de um pouco por caractere, embora haja três possibilidades; basicamente, Aé bastante improvável e não acabamos gastando seus dez bits correspondentes com muita frequência. No entanto, não seria bom se pudéssemos cometer um erro no caso de um A? Afinal, a métrica para o problema considera 1 byte = 8 bits de comprimento como equivalente a 2 erros; portanto, parece que se deve preferir um erro ao invés de gastar mais de 8/2 = 4 bits em um caractere. Gastar mais de um byte para salvar um erro definitivamente parece subótimo!

O mecanismo de "rebobinar"

Esta seção descreve o principal aspecto inteligente desta solução, que é uma maneira de lidar com suposições incorretas sem nenhum custo.

Para o exemplo simples que analisamos, o mecanismo de rebobinagem é particularmente direto. O intérprete lê um bit do arquivo de dicas. Se é um 0, adivinha E. Se for um 1, adivinha T. Na próxima vez que for chamado, ele verá qual é o caractere correto. Se o arquivo de dica estiver bem configurado, podemos garantir que, no caso de um Eou T, o intérprete adivinhe corretamente. Mas que tal A? A ideia do mecanismo de retrocesso é simplesmente não codificar Aem tudo . Mais precisamente, se o intérprete mais tarde descobrir que o caractere correto era um A, metaforicamente " rebobina a fita": retorna o bit lido anteriormente. A parte que ele lê pretende codificar EouT, mas agora não; será usado mais tarde. Neste exemplo simples, isso basicamente significa que continua adivinhando o mesmo caractere ( Eou T) até acertar; depois lê outro pedaço e continua.

A codificação para esse arquivo de dicas é muito simples: transforme todos os Es em 0 bits Tes em 1 bits, ignorando-os Acompletamente. Pela análise no final da seção anterior, esse esquema comete alguns erros, mas reduz a pontuação geral ao não codificar nenhum dos As. Como efeito menor, ele também economiza o tamanho do arquivo de dicas, porque acabamos usando exatamente um bit para cada um Ee T, em vez de um pouco mais do que um pouco.

Um pouco de teorema

Como decidimos quando cometer um erro? Suponha que nosso modelo nos dê uma distribuição de probabilidade P para o próximo caractere. Separaremos os caracteres possíveis em duas classes: codificado e não codificado . Se o caractere correto não estiver codificado, usaremos o mecanismo "rebobinar" para aceitar um erro sem nenhum custo. Se o caractere correto for codificado, usaremos outra distribuição Q para codificá-lo usando codificação aritmética.

Mas qual distribuição Q devemos escolher? Não é difícil ver que todos os caracteres codificados devem ter maior probabilidade (em P) do que os caracteres não codificados. Além disso, a distribuição Q deve incluir apenas os caracteres codificados; afinal, não estamos codificando os outros, por isso não devemos "gastar" entropia neles. É um pouco mais complicado ver que a distribuição de probabilidade Q deve ser proporcional a P nos caracteres codificados. Reunir essas observações significa que devemos codificar os caracteres mais prováveis, mas possivelmente não os menos prováveis, e que Q é simplesmente P redimensionado nos caracteres codificados.

Além disso, verifica-se que existe um teorema interessante sobre qual "corte" deve-se escolher para os caracteres de codificação: você deve codificar um caractere contanto que seja pelo menos 1 / 5.393 tão provável quanto os outros caracteres codificados combinados. Isso "explica" a aparência da constante aparentemente aleatória 5.393mais próxima do final do programa acima. O número 1 / 5.393 ≈ 0,18542 é a solução para a equação -p log (16) - p log p + (1 + p) log (1 + p) = 0 .

Talvez seja uma idéia razoável escrever esse procedimento no código. Este fragmento está em 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;
}

Juntando tudo

Infelizmente, a seção anterior é um pouco técnica, mas se juntarmos todas as outras peças, a estrutura será a seguinte. Sempre que o programa é solicitado a prever o próximo caractere após um determinado caractere correto:

1. Adicione o caractere correto ao prefixo correto conhecido de Moby Dick.
2. Atualize o modelo (Markov) do texto.
3. O segredo : se o palpite anterior estiver incorreto, rebobine o estado do decodificador aritmético para o estado anterior ao palpite anterior!
4. Peça ao modelo de Markov para prever uma distribuição de probabilidade P para o próximo caractere.
5. Transforme P em Q usando a sub-rotina da seção anterior.
6. Peça ao decodificador aritmético que decodifique um caractere do restante do arquivo de dicas, de acordo com a distribuição Q.
7. Adivinha o personagem resultante.

A codificação do arquivo de dicas funciona da mesma forma. Nesse caso, o programa sabe qual é o próximo caractere correto. Se é um caractere que deve ser codificado, é claro que se deve usar o codificador aritmético; mas se for um caractere não codificado, ele simplesmente não atualizará o estado do codificador aritmético.

Se você entende o contexto teórico da informação como distribuições de probabilidade, entropia, compressão e codificação aritmética, mas tentou e não conseguiu entender este post (exceto por que o teorema é verdadeiro), informe-nos e podemos tentar esclarecer as coisas. Obrigado pela leitura!

Python 3, 2 · 267 + 510193 = 510727

Preditor

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]

Utiliza uma combinação bayesiana ponderada dos modelos Markov da ordem 0,…, 16, com pesos [1, 6, 12, 30, 65, 99, 87, 117, 118, 89, 95, 118, 96, 184, 126, 219, 126].

O resultado não é muito sensível à seleção desses pesos, mas eu os otimizei porque pude, usando o mesmo algoritmo de escalada de aceitação tardia que usei na minha resposta para “Reunir a maioria do Senado” , onde cada mutação candidata é apenas um incremento de ± 1 para um único peso.

Código de teste

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

Experimente online!

Uma função usando variáveis ​​globais. Aprende à medida que constrói um modelo no nível da palavra: dado o que é visto até agora nesta palavra , qual é o próximo personagem mais comum? À medida que mais informações entram, ele aprende muito bem as palavras comuns do texto e também aprende o caractere mais comum para iniciar a próxima palavra.

Por exemplo:

• Se o que é visto até agora é 'Captai', ele prevê um "n"
• Se for "Capitão", ele prevê um espaço
• Se for o início de uma palavra e a última palavra for "Capitão", ele prevê um 'A'
• Se a palavra até agora é 'A', ela prediz um 'h' (e depois 'a' e 'b'; da mesma forma para 'C').

Não se sai muito bem no início, mas no final existem grandes partes de palavras reais saindo. A opção de fallback é um espaço e, após um único espaço, é um "a", a menos que a letra anterior seja de "nedtfo", um dígito ou um hífen ou apóstrofo. Ele também prevê agressivamente quebras de linha após 71 caracteres ou se um espaço era esperado após 66. Ambos foram sintonizados com os dados ("t" é muito mais comum após um espaço, mas já foi previsto com mais frequência, portanto " um "é um palpite melhor fora desses seis casos especiais).

Aprender quais pares de palavras foram combinados e prever o mapeamento acabou não valendo a pena.

Termina com um texto como este:

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!

que corresponde a esta parte da entrada:

ao seu redor.

"Eu o vi quase no mesmo instante, senhor, que o capitão Ahab viu, e eu gritei", disse Tashtego.

"Não é o mesmo instante; não é o mesmo - não, o dobrão é meu, o destino reservou o dobrão para mim. Eu só; nenhum de vocês poderia ter criado a baleia branca primeiro. Lá ela sopra! - aí ela sopra! - -tá ela sopra!

Você pode ver onde os nomes próprios em particular saem muito bem, mas o final das palavras também está correto. Quando é visto "dou", espera "dúvida", mas quando o "l" aparece, ele fica "dobrado".

Se você executá-lo pela segunda vez com o mesmo modelo que ele acabou de criar, obtém imediatamente outros 92k de correção (51,7% -> 59,3%), mas sempre fica abaixo de 60% a partir da segunda iteração.

O código de medição está no link TIO, ou aqui está uma versão um pouco melhor:

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 tem a saída estimada no final.

C ++, pontuação: 2 * 132 + 865821 = 866085

Obrigado a @Quentin por salvar 217 bytes!

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;}

Uma solução muito simples que, dada um caractere, apenas gera o caractere que aparece com mais frequência após o caractere de entrada.

Verifique a pontuação com:

#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;
}

Editar: Usar whale2.txtfornece uma pontuação melhor.

Python, 2 * 516 + 521122 = 522154

Algoritmo:

Ainda outra submissão em python, esse algoritmo calcula a próxima letra mais provável, observando seqüências de comprimento 1, ..., l. A soma das probabilidades é usada e existem alguns truques para obter melhores resultados.

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')]

Resultados:

Principalmente sem sentido, embora você possa ver que ele pega uma frase ocasional, como "Pai Mapple".

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

Código do teste:

Muito simples, gera alguns exemplos do texto em diferentes pontos. Usa whale2.txt, pois isso evita uma lógica extra para calcular novas linhas.

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

C (gcc) , 679787 652892

84 76 bytes, 679619 652740 suposições incorretas

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];}

Experimente online!

Atualização: ~ 27000 pontos com o arquivo atualizado, 16 pontos (8 bytes) com uma função com melhor desempenho.

Explicação

A maneira como isso funciona é que, à medida que o código percorre o texto, ele memoriza o último caractere que encerrou qualquer sequência de 4 caracteres e retorna esse valor. Um pouco semelhante à abordagem de Arnauld acima, mas se baseia na probabilidade inerente de duas seqüências de 4 caracteres que terminam da mesma maneira.

De-golfe:

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

seguido pelo bzip2-compressed whale2.txt com o primeiro byte ausente

Ignora sua entrada; gera a resposta correta. Isso fornece uma linha de base em uma extremidade; daniero fornece uma linha de base na outra extremidade.

Script do construtor:

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

Arnês de teste de E / S (tcc; corte da primeira linha para gcc). Esse equipamento de teste pode ser usado por qualquer pessoa em uma plataforma adequada que envie um programa completo que espere E / S de leitura / gravação. Ele usa E / S de byte por vez para evitar trapaças. O programa filho deve liberar a saída após cada byte para evitar o bloqueio.

#!/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])

Experimente online!

... A ///resposta que imprime um espaço recebe 10 votos positivos, enquanto meu código só pode receber 3 ...

Explicação:

Para cada personagem, o programa:

• aumentar frequency[prev][char]
• Encontre o personagem que aparece mais vezes em frequency[char]
• e produzi-lo.

• Código ungolfed no link TIO, comentou.
• O código é 131 bytes.
• O código executado nos meus relatórios de máquina:

879504 / 1215235
Time: 62.01348257784468

que têm a pontuação total

2*131 + 879504 = 879766

Como não há como fazer upload de um arquivo grande para o TIO (exceto pedir a Dennis), o exemplo executado no link TIO executa o programa apenas para uma pequena parte do texto.

Em comparação com a resposta mais antiga, essa possui 362 caracteres mais incorretos, mas o código é mais curto em 255 bytes. O multiplicador faz com que minha inscrição tenha uma pontuação menor.

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:' ';}}

Essa abordagem usa uma tabela de consulta para aprender o caractere mais comum que segue uma determinada sequência. As teclas da tabela de pesquisa têm no máximo 4 caracteres; portanto, a função atualiza primeiro a tabela de pesquisa com o caractere atual e depois apenas verifica qual caractere é o mais provável de ocorrer após os 4 anteriores, incluindo o atual . Se esses 4 caracteres não forem encontrados na tabela de pesquisa, ele imprimirá um espaço.

Esta versão usa o whale2.txtarquivo, pois melhora bastante o número de suposições bem-sucedidas.

A seguir está o código usado para testar a classe:

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();
    }
}

O código é executado em apenas 2 segundos. Apenas para constar, é isso que recebo quando modifico o tamanho das chaves da tabela de consulta (inclui os resultados de uma segunda execução sem redefinir o modelo):

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

Seria interessante saber por que um tamanho de chave de 4 caracteres é a melhor escolha nesse algoritmo.

Comparação de texto

Original:

"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!"

Recriado:

"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 

Palpites:

"_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__

Log de alterações

• 569279 - alterado para whale2.txte, portanto, removido a otimização.
• 577366 - otimizado com código que tentou adivinhar quando retornar um avanço de linha.
• 590354 - versão original.

Java 7, caracteres de 1995, (1995 * 2 + 525158) 529148

Java é péssimo para pequenos tamanhos de programa. Enfim, tentei várias abordagens extremamente complexas e complicadas que produziram resultados surpreendentemente ruins. Posteriormente, voltei e fiz uma abordagem simples, que resultou em um tamanho menor de programa e melhores resultados.

Essa abordagem é realmente extremamente simples. Alimenta cegamente os x caracteres anteriores (além de todas as substrings desses caracteres) em uma hashtable, mapeada para o caractere atual. Em seguida, ele acompanha quais padrões preveem com mais precisão o caractere atual. Se padrões que precedem certos caracteres forem encontrados várias vezes, eles conseguirão prever o personagem. Dá precedência a seqüências mais longas e dá precedência a qualquer caractere que mais frequentemente segue uma determinada sequência. Esse algoritmo não sabe nada sobre o tipo de documento ou o idioma inglês.

Decidi usar 9 caracteres e tentar combinar palavras inteiras nos 9 caracteres anteriores, quando possível. Quando você não tenta fazer a correspondência de palavras nas cadeias, o tamanho ideal é de 6 caracteres, produzindo milhares de outras previsões erradas.

Uma observação interessante foi que o uso de 20 caracteres resultou em previsões ruins na primeira vez, mas com precisão de 99,9% nas passagens subsequentes. O algoritmo foi basicamente capaz de memorizar o livro em pedaços de 20 bytes sobrepostos, e isso foi distinto o suficiente para permitir que ele lembrasse o livro inteiro de um caractere por vez.

• (1950 * 2 + 532919) 536819
• (2406 * 2 + 526233) 531045 verificando pontuação para fazer melhores suposições
• (1995 * 2 + 525158) 529148 mais ajustes, jogou fora alguns palavrões

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

Tentei isso de forma independente, mas acabei com o que é efetivamente uma versão inferior da resposta de Michael Homer. Espero que isso não torne minha resposta completamente obsoleta.

Isso cria ao longo do tempo um dicionário de palavras (definido de forma grosseira como cadeias terminadas por ou \n, diferenciando maiúsculas de minúsculas e incluindo pontuação). Em seguida, ele pesquisa neste dicionário por palavras que começam com o que até agora conhece a palavra atual, classifica a lista resultante por frequência de ocorrência (lentamente) e supõe que o próximo caractere seja o próximo na palavra correspondente mais comum. Se já tivermos a palavra correspondente mais comum ou se não existir mais, ela retornará .

Ele também cria um dicionário repugnantemente ineficiente de pares de palavras. Ao atingir um limite de palavra, ele adivinha que o próximo caractere é a primeira letra da segunda palavra no par de palavras correspondente mais comum ou tse não há correspondência. Não é muito inteligente, no entanto. A seguir Moby, o programa adivinha corretamente que o próximo personagem é D, mas depois esquece tudo sobre o contexto e geralmente acaba chamando a baleia de "Moby Duck" (porque a palavra "holandês" parece ser mais frequente na primeira metade do texto ) Seria fácil corrigir isso priorizando pares de palavras em detrimento de palavras individuais, mas espero que o ganho seja marginal (já que geralmente é correto a partir do terceiro caractere, e os pares de palavras não são tão úteis em primeiro lugar).

Eu poderia ajustar isso para corresponder melhor ao texto fornecido, mas não acho que o ajuste manual do algoritmo com base no conhecimento prévio da entrada esteja realmente no espírito do jogo, exceto por escolher t como o caractere de fallback após um espaço ( e eu provavelmente não deveria ter feito isso também), evitei isso. Eu ignorei o comprimento da linha conhecida do arquivo de entrada e, em vez disso, inseri-lo \napós cada 13 espaços - é quase certamente uma correspondência muito ruim, a principal intenção era manter o comprimento da linha razoável, em vez de corresponder à entrada.

O código não é exatamente rápido (~ 2 horas na minha máquina), mas no geral obtém cerca da metade dos caracteres corretos (49%). Espero que a pontuação seja marginalmente melhor se for executada whale2.txt, mas ainda não o fiz.

O início da saída é assim:

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

mas no final, parece um pouco mais com ... alguma coisa. Minha passagem favorita do final do livro,

e como nenhum deles pode ser meu, deixe-me então me despedaçar, enquanto ainda te persegue, ainda que amarrado a ti, maldita baleia! ASSIM, desisto da lança! "

sai como

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 "

Isso teria tornado A Ira de Khan muito mais confusa. E "solitário" → "formigamento" é uma substituição particularmente satisfatória.

Editar: salvou um byte excluindo um espaço estranho

Pontuação

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

Isso executa o programa para o texto de Moby Dick e gera o texto "previsto" para stdout e abusa do stderr para escrever a pontuação. Eu recomendo redirecionar a saída para um arquivo.

C ++, 2 · 62829 + 318786 = 444444

Para executar este programa, você precisa deste arquivo aqui , que deve ser nomeado C.

O programa usa a mesma combinação de modelos de Markov que em nossa resposta anterior . Como antes, essa combinação é essencialmente o modelo desta resposta do usuário2699 , mas com algumas pequenas modificações.

Visto que essa resposta usa exatamente o mesmo modelo de antes, a melhoria é um mecanismo teórico da informação melhor do que o mecanismo de "rebobinar" descrito anteriormente. Isso permite cometer menos erros e também ter um comprimento combinado menor. O programa em si não é muito jogado, porque não é o principal colaborador da pontuação.

O programa tem 2167 bytes de comprimento (incluindo todas as guias para indentação e muitos outros caracteres desnecessários, mas antes do código de teste) e o arquivo binário Ctem 60661 bytes, portanto, de acordo com as regras de pontuação de vários arquivos , obtemos L2167 + 60661 + 1 = 62829.

O programa leva aproximadamente 8 minutos para ser executado em uma m5.4xlargeinstância no Amazon EC2 e usa um pouco mais de 16 GB de memória. (Esse uso excessivo de memória não é necessário - nós também não otimizamos isso.)

#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 bytes, erros 526092 (usando whale2.txt). Definitivamente, isso é capaz de melhorar ainda mais, mas chegou ao estágio "bom o suficiente para publicar".

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

A idéia é armazenar as frequências de todas as execuções de 2, 3, 4, ..., 10 caracteres. Para cada um desses comprimentos L, verificamos se os caracteres L-1 mais recentes correspondem a um padrão armazenado; Nesse caso, nosso palpite g _L é o próximo caractere mais frequente após esse padrão. Coletamos até nove palpites dessa maneira. Para decidir qual palpite usar, ponderamos a frequência de cada padrão pelo seu comprimento até a 8ª potência. O palpite com a maior soma de frequências ponderadas é escolhido. Se não houver padrões que correspondam, adivinhamos espaço.

(O comprimento máximo do padrão e o expoente de ponderação foram escolhidos por tentativa e erro para fornecer o menor número possível de suposições incorretas.)

Aqui está minha versão de trabalho em andamento não destruída:

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

E o chicote de teste:

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

Aqui está um exemplo de saída do início do texto. Já começamos a ver a capacidade de terminar palavras depois de ver sua primeira carta ( in, to, and, by, também, aparentemente, 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 

Perto do final, ainda existem muitos erros, mas também muitas seqüências muito boas ( shmage seashawkspor exemplo).

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

É interessante observar alguns dos erros e adivinhar qual palavra o algoritmo "esperava". Por exemplo, depois sail, o programa ambas as vezes prediz o--para sailor, presumo. Ou então, depois que , aele espera - npossivelmente por causa da ocorrência comum de , and.

Changelog:

• 274 * 2 + 526092 = 526640 Jogou o algoritmo, com o custo de alguns erros extras
• 306 * 2 + 526089 = 526701 Versão original

Python 2, pontuação: 2 * (407 + 56574) + 562262 = 676224

Procura por palavras que correspondam aos caracteres anteriores em uma lista de  todas as  palavras mais usadas no texto, classificadas pelo número de ocorrências.

Código:

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"

Dados: https://www.dropbox.com/s/etmzi6i26lso8xj/d?dl=0

Suíte de teste:

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

Editar: Usar whale2.txtfornece uma pontuação melhor.

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

Mais um envio de prefixo-frequência. Corra whale2.txte obtenha pontuação semelhante (um pouco pior) do que outras.

#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]];}

Este avidamente encontra a corda mais longa que começa com um sufixo da história e, se houver vários candidatos, faça o tiebreak com cordas mais curtas.

Por exemplo: Se os últimos 7 personagens são abcdefgh, ea cadeia abcdefghie abcdefghjaparece com a maior frequência em todas as cordas da forma abcdefgh*, a saída será tanto iou j, tiebreak com sufixos mais curtos ( bcdefgh, cdefgh...).

Por razões desconhecidas, nada mais que 7 e meu computador não tem RAM suficiente para executá-lo. Mesmo com 7, preciso fechar todos os navegadores da web para executá-lo.

Código de teste:

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]];
}