Aquí hay un archivo de texto ASCII de 1.2Mb que contiene el texto de Moby-Dick de Herman Melville ; o la ballena . Su tarea es escribir un programa o función (o clase, etc. - ver más abajo) que se le dará a este archivo un carácter a la vez, y en cada paso debe adivinar el siguiente carácter.

Este es un desafío de código . Tu puntaje será

2*L + E

donde Les el tamaño de su envío en bytes y Ees el número de caracteres que adivina incorrectamente. El puntaje más bajo gana.

Otros detalles

Su envío será un programa o función (etc.) que será invocado o invocado o enviado datos varias veces. (1215235 veces para ser exactos). Cuando se llama a la n ^º tiempo que se le dará el n ^º carácter de whale.txto whale2.txty debe adivinar su salida para el ( n + 1 ) ^ésimo carácter. El Ecomponente de su puntuación será el número total de caracteres que adivina incorrectamente.

La mayoría de las presentaciones necesitarán almacenar algún estado entre invocaciones, para que puedan rastrear cuántas veces se han llamado y cuáles fueron las entradas anteriores. Puede hacerlo escribiendo en un archivo externo, utilizando staticvariables globales o, enviando una clase en lugar de una función, utilizando una mónada de estado o cualquier otra cosa que funcione para su idioma. Su envío debe incluir cualquier código requerido para inicializar su estado antes de la primera invocación.

Su programa debe ejecutarse de manera determinista, de modo que siempre haga las mismas conjeturas con la misma entrada (y, por lo tanto, siempre obtenga la misma puntuación).

Su respuesta debe incluir no solo su envío, sino también el código que utilizó para calcular la Eparte de su puntaje. No es necesario que esté escrito en el mismo idioma que su envío y no se contará para su recuento de bytes. Se le recomienda que sea legible.

Con respecto a la interfaz entre su envío y este programa de cálculo de puntaje, todo está bien, siempre que su programa siempre dé un byte de salida antes de recibir su próximo byte de entrada. (Entonces, por ejemplo, no puede simplemente pasarle una cadena que contenga toda la entrada y recuperar una cadena que contenga toda la salida).

En realidad, debe ejecutar su programa de prueba y calcular / verificar su puntaje antes de enviar su entrada. Si su envío es demasiado lento para que pueda verificar su puntaje, entonces no está calificado para competir, incluso si sabe cuál sería su puntaje en principio.

El Lcomponente de su puntaje se calculará de acuerdo con las reglas habituales para los desafíos de golf de código. Si su envío contendrá varios archivos, tome nota de las reglas sobre puntuación y estructura de directorios en ese caso. Cualquier información que use su código debe incluirse en su Lpuntaje.

Puede importar bibliotecas existentes, pero no puede cargar ningún otro archivo externo, y su código puede no acceder a la whale.txtowhale2.txtarchivo de cualquier otra manera que no sea la descrita anteriormente. No puede cargar ninguna red neuronal previamente entrenada u otras fuentes de datos estadísticos. (Está bien usar redes neuronales, pero debe incluir los datos de peso en su envío y contarlos para su recuento de bytes). Si por alguna razón su idioma o bibliotecas incluyen una función que proporciona parte o la totalidad del texto de Moby Dick , no puede usar esa función. Además de eso, puede usar cualquier otra función incorporada o de biblioteca que desee, incluidas las relacionadas con el procesamiento de texto, la predicción o la compresión, siempre que formen parte de su idioma o de sus bibliotecas estándar. Para rutinas más exóticas y especializadas que incluyen fuentes de datos estadísticos, deberá implementarlas usted mismo e incluirlas en su recuento de bytes.

Es probable que algunas presentaciones incluyan componentes que son generados por el código. Si este es el caso, incluya en su respuesta el código que se utilizó para producirlos y explique cómo funciona . (Mientras este código no sea necesario para ejecutar su envío, no se incluirá en su recuento de bytes).

Por razones históricas, hay dos versiones del archivo, y puede usar cualquiera de ellas en una respuesta. En whale2.txt(vinculado anteriormente) el texto no está ajustado, por lo que las nuevas líneas aparecen solo al final de los párrafos. En el original, whale.txtel texto se ajusta a un ancho de 74 caracteres, por lo que debe predecir el final de cada línea y el texto. Esto hace que el desafío sea más complicado, por lo que whale2.txtse recomienda para nuevas respuestas. Ambos archivos son del mismo tamaño, 1215236 bytes.

Para resumir, todas las respuestas deben incluir lo siguiente:

• Su presentación en sí. (El código, más cualquier archivo de datos que use; estos pueden ser enlaces si son grandes).
• Una explicación de cómo funciona su código. Explique el método de E / S y cómo predice el siguiente carácter. La explicación de su algoritmo es importante, y las buenas explicaciones me darán recompensas.
• El código que usó para evaluar su puntaje. (Si esto es idéntico a una respuesta anterior, simplemente puede vincularla).
• Cualquier código que utilizó para generar su envío, junto con una explicación de ese código. Esto incluye el código que utilizó para optimizar los parámetros, generar archivos de datos, etc. (Esto no cuenta para el recuento de bytes, pero debe incluirse en su respuesta).

Tabla de clasificación

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 vez en cuando ofreceré recompensas para alentar diferentes enfoques.

El primero, 50 puntos, fue otorgado a A. Rex por la respuesta con mejor puntuación en ese momento.

El segundo, 100 puntos, también fue otorgado a A. Rex, por la misma respuesta, porque agregaron una muy buena explicación a su respuesta existente.

La próxima recompensa, 200 puntos , se otorgará a cualquiera

• Una respuesta competitiva que utiliza una nueva técnica. (Esto se basará en mi juicio subjetivo ya que es mi representante el que entra en la recompensa, pero puedes confiar en mí para ser justo. ¡Ten en cuenta que tu respuesta debe contener una explicación suficiente para que entienda cómo funciona!) No tome el puntaje más alto, solo necesita hacerlo razonablemente bien en comparación con las respuestas existentes. Estoy particularmente interesado en ver soluciones basadas en redes neuronales recurrentes, pero otorgaré la recompensa a cualquier cosa que parezca lo suficientemente diferente de los modelos de Markov que dominan las puntuaciones más altas actuales.

O:

• Cualquier otra persona que supere la puntuación máxima de A. Rex (actualmente 444444), utilizando cualquier método.

Una vez que se reclame la recompensa de 200 puntos, lo más probable es que ofrezca una de 400 puntos, actualizando los requisitos en consecuencia.

/// , 2 * 1 + 1020874 = 1020876

Imprime un espacio.

Nodo.js, 2 * 224 + 524279 = 524727

Consulte el registro de cambios al final de esta publicación para obtener actualizaciones de puntaje.

Una función que toma y devuelve un 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 en un modelo PPM simple que mira los últimos 8 caracteres para predecir el siguiente.

Confiamos en un patrón de longitud L cuando lo hemos encontrado al menos T [L] veces, donde T es una matriz de umbrales arbitrarios: [1,1,2,1,2,3,5,2] . Además, siempre confiamos en un patrón cuyo primer carácter coincida [A-Z '"(].

Seleccionamos el patrón de confianza más largo y devolvemos la predicción con la puntuación más alta asociada a este patrón en el momento de la llamada.

Notas

• Obviamente, esto no está optimizado para la velocidad, pero se ejecuta en aproximadamente 15 segundos en mi computadora portátil.

• Si se nos permitiera repetir el proceso varias veces seguidas sin restablecer el modelo, el número de errores convergería a ~ 268000 después de 5 iteraciones.

• La tasa de éxito actual de la función de predicción es ~ 56.8%. Como notó @immibis en los comentarios, si las conjeturas incorrectas y correctas se mezclan, el resultado ni siquiera es legible.

  Por ejemplo, este fragmento cerca del final del libro:

  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.
  

  se convierte en:

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

  Al reemplazar las conjeturas erróneas con guiones bajos, tenemos una mejor idea de lo que funcionó correctamente:

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

  _{NB : El ejemplo anterior se creó con una versión anterior del código, trabajando en la primera versión del archivo de entrada.}

Código de prueba

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

Cambiar registro

• 524727 : ahorró 19644 puntos al cambiar a whale2.txt (actualización de desafío)
• 544371 : ahorró 327 puntos al forzar patrones que comienzan con una letra mayúscula, una comilla, una comilla doble o un paréntesis de apertura para que siempre se confíe
• 544698 : ahorró 2119 puntos al forzar patrones que comienzan con un espacio en el que siempre se puede confiar
• 546817 : ahorró 47 puntos ajustando los umbrales y jugando golf a la función de predicción
• 546864 : ahorró 1496 puntos al extender la longitud máxima del patrón a 8 caracteres
• 548360 : ahorró 6239 puntos al introducir la noción de patrones confiables, con umbrales que dependen de su longitud
• 554599 : ahorró 1030 puntos al mejorar la predicción de avance de línea
• 555629 : ahorró 22 puntos jugando al golf en la función de predicción
• 555651 : ahorró 40 puntos jugando al golf con la función de predicción
• 555691 - puntaje inicial

Perl, 2 · 70525 + 326508 = 467558

Vaticinador

$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 ejecutar este programa, necesita este archivo aquí , que debe nombrarse B. (Puede cambiar este nombre de archivo en la segunda instancia del carácter Banterior). Consulte a continuación cómo generar este archivo.

El programa utiliza una combinación de modelos de Markov esencialmente como en esta respuesta del usuario 2699 , pero con algunas pequeñas modificaciones. Esto produce una distribución para el siguiente personaje. Utilizamos la teoría de la información para decidir si aceptar un error o gastar bits de almacenamiento en Bsugerencias de codificación (y si es así, cómo). Usamos codificación aritmética para almacenar de manera óptima bits fraccionales del modelo.

El programa tiene una longitud de 582 bytes (incluida una nueva línea final innecesaria) y el archivo binario Btiene una longitud de 69942 bytes, por lo que, según las reglas para la puntuación de varios archivos , calificamosL como 582 + 69942 + 1 = 70525.

El programa casi seguramente requiere una arquitectura de 64 bits (little-endian?). Se tarda aproximadamente 2,5 minutos en ejecutarse en una m5.largeinstancia en Amazon EC2.

Código de prueba

# 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

El arnés de prueba asume que el envío está en el archivo submission.pl , pero esto se puede cambiar fácilmente en la segunda línea.

Comparación 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

Esta muestra (elegida en otra respuesta ) aparece bastante tarde en el texto, por lo que el modelo está bastante desarrollado en este punto. Recuerde que el modelo está aumentado por 70 kilobytes de "pistas" que lo ayudan directamente a adivinar los caracteres; no está impulsado simplemente por el breve fragmento de código anterior.

Generando pistas

El siguiente programa acepta el código de envío exacto anterior (en la entrada estándar) y genera el Barchivo exacto anterior (en la salida estándar):

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

Se tarda aproximadamente el tiempo de ejecución que el envío, ya que realiza cálculos similares.

Explicación

En esta sección, intentaremos describir lo que hace esta solución con suficiente detalle para que usted pueda "probarla en casa". La técnica principal que diferencia esta respuesta de las otras es algunas secciones más abajo como mecanismo de "rebobinado", pero antes de llegar allí, necesitamos establecer los conceptos básicos.

Modelo

El ingrediente básico de la solución es un modelo de lenguaje. Para nuestros propósitos, un modelo es algo que toma una cantidad de texto en inglés y devuelve una distribución de probabilidad en el siguiente carácter. Cuando usamos el modelo, el texto en inglés será un prefijo (correcto) de Moby Dick. Tenga en cuenta que el resultado deseado es una distribución , y no solo una suposición para el personaje más probable.

En nuestro caso, esencialmente utilizamos el modelo en esta respuesta por user2699 . No utilizamos el modelo de la respuesta con la puntuación más alta (que no sea la nuestra) de Anders Kaseorg precisamente porque no pudimos extraer una distribución en lugar de una sola conjetura. En teoría, esa respuesta calcula una media geométrica ponderada, pero obtuvimos resultados algo pobres cuando lo interpretamos demasiado literalmente. "Robamos" un modelo de otra respuesta porque nuestra "salsa secreta" no es el modelo sino el enfoque general. Si alguien tiene un modelo "mejor", entonces debería poder obtener mejores resultados utilizando el resto de nuestras técnicas.

Como comentario, la mayoría de los métodos de compresión como Lempel-Ziv pueden verse como un "modelo de lenguaje" de esta manera, aunque uno podría tener que entrecerrar los ojos un poco. (¡Es particularmente complicado para algo que hace una transformación de Burrows-Wheeler!) Además, tenga en cuenta que el modelo por user2699 es una modificación de un modelo de Markov; esencialmente nada más es competitivo para este desafío o tal vez incluso modelar texto en general.

Arquitectura general

A los efectos de la comprensión, es bueno dividir la arquitectura general en varias piezas. Desde la perspectiva de más alto nivel, debe haber un poco de código de administración de estado. Esto no es particularmente interesante, pero para completar, queremos enfatizar que en cada punto al programa se le pide la siguiente suposición, tiene disponible un prefijo correcto de Moby Dick. No utilizamos nuestras conjeturas incorrectas pasadas de ninguna manera. En aras de la eficiencia, el modelo de lenguaje probablemente puede reutilizar su estado de los primeros N caracteres para calcular su estado para los primeros (N + 1) caracteres, pero en principio, podría volver a calcular las cosas desde cero cada vez que se invoca.

Dejemos a un lado este "controlador" básico del programa y echemos un vistazo dentro de la parte que adivina el siguiente personaje. Ayuda conceptualmente a separar tres partes: el modelo de lenguaje (discutido anteriormente), un archivo de "pistas" y un "intérprete". En cada paso, el intérprete le pedirá al modelo de lenguaje una distribución para el siguiente carácter y posiblemente leerá alguna información del archivo de sugerencias. Luego combinará estas partes en una suposición. Más adelante se explicará con precisión qué información está en el archivo de sugerencias y cómo se usa, pero por ahora ayuda a mantener estas partes separadas mentalmente. Tenga en cuenta que, en cuanto a la implementación, el archivo de sugerencias es literalmente un archivo separado (binario), pero podría haber sido una cadena o algo almacenado dentro del programa. Como una aproximación,

Si se está utilizando un método de compresión estándar como bzip2 como en esta respuesta , el archivo de "sugerencias" corresponde al archivo comprimido. El "intérprete" corresponde al descompresor, mientras que el "modelo de lenguaje" es un poco implícito (como se mencionó anteriormente).

¿Por qué usar un archivo de pistas?

Elija un ejemplo simple para analizar más a fondo. Suponga que el texto tiene Ncaracteres largos y bien aproximados por un modelo en el que cada carácter es (independientemente) la letra Econ probabilidad ligeramente inferior a la mitad, de Tmanera similar con probabilidad ligeramente inferior a la mitad y Acon probabilidad 1/1000 = 0.1%. Supongamos que no hay otros personajes posibles; en cualquier caso, el Aes bastante similar al caso de un personaje nunca antes visto de la nada.

Si operamos en el régimen L 0 (como lo hacen la mayoría, pero no todas, las otras respuestas a esta pregunta), no hay mejor estrategia para el intérprete que elegir una de Ey T. En promedio, obtendrá aproximadamente la mitad de los caracteres correctos. Entonces E ≈ N / 2 y el puntaje ≈ N / 2 también. Sin embargo, si usamos una estrategia de compresión, podemos comprimir a un poco más de un bit por carácter. Como L se cuenta en bytes, obtenemos L ≈ N / 8 y, por lo tanto, puntaje ≈ N / 4, el doble de bueno que la estrategia anterior.

Lograr esta tasa de un poco más de un bit por carácter para este modelo es ligeramente no trivial, pero un método es la codificación aritmética.

Codificación aritmética

Como es comúnmente conocido, una codificación es una forma de representar algunos datos usando bits / bytes. Por ejemplo, ASCII es una codificación de 7 bits / caracteres de texto en inglés y caracteres relacionados, y es la codificación del archivo Moby Dick original en consideración. Si algunas letras son más comunes que otras, entonces una codificación de ancho fijo como ASCII no es óptima. En tal situación, muchas personas buscan la codificación de Huffman . Esto es óptimo si desea un código fijo (sin prefijo) con un número entero de bits por carácter.

Sin embargo, la codificación aritmética es aún mejor. En términos generales, es capaz de usar bits "fraccionales" para codificar información. Hay muchas guías de codificación aritmética disponibles en línea. Omitiremos los detalles aquí (especialmente de la implementación práctica, que puede ser un poco complicada desde una perspectiva de programación) debido a los otros recursos disponibles en línea, pero si alguien se queja, tal vez esta sección se pueda desarrollar más.

Si uno tiene texto realmente generado por un modelo de lenguaje conocido, entonces la codificación aritmética proporciona una codificación esencialmente óptima del texto de ese modelo. En cierto sentido, esto "resuelve" el problema de compresión para ese modelo. (Por lo tanto, en la práctica, el problema principal es que el modelo no se conoce, y algunos modelos son mejores que otros para modelar texto humano). Si no se permitió cometer errores en este concurso, entonces en el lenguaje de la sección anterior , una forma de producir una solución a este desafío habría sido usar un codificador aritmético para generar un archivo de "sugerencias" a partir del modelo de lenguaje y luego usar un decodificador aritmético como "intérprete".

En esta codificación esencialmente óptima, terminamos gastando -log_2 (p) bits para un personaje con probabilidad p, y la tasa de bits general de la codificación es la entropía de Shannon . Esto significa que un carácter con probabilidad cercana a 1/2 toma aproximadamente un bit para codificar, mientras que uno con probabilidad 1/1000 toma aproximadamente 10 bits (porque 2 ^ 10 es aproximadamente 1000).

Pero la métrica de puntuación para este desafío fue bien elegida para evitar la compresión como la estrategia óptima. Tendremos que encontrar alguna forma de cometer algunos errores como compensación para obtener un archivo de sugerencias más corto. Por ejemplo, una estrategia que podría probarse es una estrategia de ramificación simple: generalmente intentamos usar la codificación aritmética cuando podemos, pero si la distribución de probabilidad del modelo es "mala" de alguna manera, simplemente adivinamos el carácter más probable y no lo hacemos ' Intenta codificarlo.

¿Por qué cometer errores?

Analicemos el ejemplo anterior para motivar por qué podríamos querer cometer errores "intencionalmente". Si usamos codificación aritmética para codificar el carácter correcto, gastaremos aproximadamente un bit en el caso de un Eo T, pero unos diez bits en el caso de un A.

En general, esta es una codificación bastante buena, gastando un poco más de un bit por personaje, aunque hay tres posibilidades; básicamente, Aes bastante improbable y no terminamos gastando sus diez bits correspondientes con demasiada frecuencia. Sin embargo, ¿no sería bueno si pudiéramos cometer un error en el caso de un A? Después de todo, la métrica para el problema considera que 1 byte = 8 bits de longitud son equivalentes a 2 errores; Por lo tanto, parece que uno debería preferir un error en lugar de gastar más de 8/2 = 4 bits en un personaje. ¡Gastar más de un byte para guardar un error definitivamente suena subóptimo!

El mecanismo de "rebobinado"

Esta sección describe el principal aspecto inteligente de esta solución, que es una forma de manejar conjeturas incorrectas sin costo alguno.

Por el simple ejemplo que hemos estado analizando, el mecanismo de rebobinado es particularmente sencillo. El intérprete lee un bit del archivo de sugerencias. Si es un 0, adivina E. Si es un 1, adivina T. La próxima vez que se llame, verá cuál es el carácter correcto. Si el archivo de sugerencias está bien configurado, podemos asegurarnos de que en el caso de una Eo T, el intérprete adivine correctamente. ¿Pero que pasa A? La idea del mecanismo de rebobinado es simplemente no codificar Aen absoluto . Más precisamente, si el intérprete luego se entera de que el carácter correcto era un A, metafóricamente " rebobina la cinta": devuelve el bit que leyó anteriormente. El bit que lee tiene la intención de codificar EoT, Pero no ahora; Se usará más tarde. En este simple ejemplo, esto básicamente significa que sigue adivinando el mismo personaje ( Eo T) hasta que lo haga bien; luego lee otro bit y continúa.

La codificación para este archivo de sugerencias es muy simple: convierta todos los Es en 0 bits Tys en 1 bits, todo mientras ignora los As por completo. Mediante el análisis al final de la sección anterior, este esquema comete algunos errores pero reduce el puntaje general al no codificar ninguno de los As. Como efecto más pequeño, también ahorra en la longitud del archivo de sugerencias, porque terminamos usando exactamente un bit para cada uno Ey T, en lugar de un poco más de un bit.

Un pequeño teorema

¿Cómo decidimos cuándo cometer un error? Supongamos que nuestro modelo nos da una distribución de probabilidad P para el siguiente carácter. Vamos a separar los posibles personajes en dos clases: codificados y no codificados . Si el carácter correcto no está codificado, terminaremos usando el mecanismo de "rebobinado" para aceptar un error sin costo alguno. Si se codifica el carácter correcto, usaremos alguna otra distribución Q para codificarlo mediante codificación aritmética.

Pero, ¿qué distribución Q deberíamos elegir? No es demasiado difícil ver que los caracteres codificados deberían tener una probabilidad más alta (en P) que los caracteres no codificados. Además, la distribución Q solo debe incluir los caracteres codificados; después de todo, no estamos codificando los otros, por lo que no deberíamos estar "gastando" entropía en ellos. Es un poco más complicado ver que la distribución de probabilidad Q debería ser proporcional a P en los caracteres codificados. Poner estas observaciones juntas significa que debemos codificar los caracteres más probables pero posiblemente no los caracteres menos probables, y que Q es simplemente P reescalado en los caracteres codificados.

Además, resulta que hay un teorema genial sobre qué "corte" se debe elegir para los caracteres de codificación: debe codificar un carácter siempre que sea al menos 1 / 5.393 tan probable como los otros caracteres codificados combinados. Esto "explica" la aparición de la constante aparentemente aleatoria 5.393más cerca del final del programa anterior. El número 1 / 5.393 ≈ 0.18542 es la solución a la ecuación -p log (16) - p log p + (1 + p) log (1 + p) = 0 .

Quizás sea una idea razonable escribir este procedimiento en código. Este fragmento está en 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;
}

Poniendolo todo junto

Desafortunadamente, la sección anterior es un poco técnica, pero si juntamos todas las otras piezas, la estructura es la siguiente. Cada vez que se le pide al programa que prediga el siguiente carácter después de un carácter correcto dado:

1. Agregue el carácter correcto al prefijo correcto conocido de Moby Dick.
2. Actualice el modelo (Markov) del texto.
3. La salsa secreta : si la suposición anterior era incorrecta, rebobine el estado del decodificador aritmético a su estado antes de la suposición anterior.
4. Pídale al modelo de Markov que prediga una distribución de probabilidad P para el siguiente carácter.
5. Transforme P a Q utilizando la subrutina de la sección anterior.
6. Solicite al decodificador aritmético que decodifique un carácter del resto del archivo de sugerencias, de acuerdo con la distribución Q.
7. Adivina el personaje resultante.

La codificación del archivo de sugerencias funciona de manera similar. En ese caso, el programa sabe cuál es el siguiente carácter correcto. Si es un carácter que debe codificarse, entonces, por supuesto, uno debe usar el codificador aritmético en él; pero si es un carácter no codificado, simplemente no actualiza el estado del codificador aritmético.

Si comprende los antecedentes teóricos de la información, como las distribuciones de probabilidad, la entropía, la compresión y la codificación aritmética, pero intentó y no entendió esta publicación (excepto por qué el teorema es verdadero), háganoslo saber y podemos intentar aclarar las cosas. ¡Gracias por leer!

Python 3, 2 · 267 + 510193 = 510727

Vaticinador

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 una combinación bayesiana ponderada del orden 0,…, 16 modelos de Markov, con pesos [1, 6, 12, 30, 65, 99, 87, 117, 118, 89, 95, 118, 96, 184, 126, 219, 126].

El resultado no es muy sensible a la selección de estos pesos, pero los optimicé porque pude, utilizando el mismo algoritmo de escalada de aceptación tardía que utilicé en mi respuesta a "Formar una mayoría del Senado" , donde cada mutación candidata es solo un incremento de ± 1 a un solo peso.

Código de prueba

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

Pruébalo en línea!

Una función que usa variables globales. A medida que avanza, construye un modelo a nivel de palabra: dado lo que se ha visto hasta ahora en esta palabra , ¿cuál es el siguiente carácter más común? A medida que entra más información, aprende palabras comunes del texto bastante bien, y también aprende el carácter más común para comenzar la siguiente palabra.

Por ejemplo:

• Si lo que se ha visto hasta ahora es 'Captai', predice una "n"
• Si es "Capitán" predice un espacio
• Si es el comienzo de una palabra, y la última palabra fue "Capitán", predice una 'A'
• Si la palabra hasta ahora es 'A', predice una 'h' (y luego 'a' y 'b'; de manera similar para 'C').

Al principio no funciona muy bien, pero al final salen grandes partes de palabras reales. La opción de reserva es un espacio, y después de un solo espacio es una "a", a menos que la letra anterior sea una de "nedtfo", un dígito o un guión o apóstrofe. También predice agresivamente los saltos de línea después de 71 caracteres, o si se esperaba un espacio después de 66. Ambos se ajustaron a los datos ("t" es mucho más común después de un espacio, pero ya se ha predicho más a menudo, así que " un "es una mejor suposición fuera de esos seis casos especiales).

Aprender qué pares de palabras se unieron y presentar el mapeo resultó no valer la pena.

Termina con un 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 de la entrada:

todo a su alrededor.

"Lo vi casi en ese mismo instante, señor, que el Capitán Ahab lo hizo, y grité", dijo Tashtego.

"No es el mismo instante; no es lo mismo, no, el doblón es mío, Fate me reservó el doblón. Yo solo; ninguno de ustedes podría haber criado a la Ballena Blanca primero. ¡Allí ella sopla! ¡Allí sopla!" -¡Allí ella sopla!

Puedes ver dónde los sustantivos propios en particular salen bastante bien, pero los extremos de las palabras también son en su mayoría correctos. Cuando se ve "dou" espera "duda", pero una vez que aparece la "l" se pone "doblón".

Si lo ejecuta por segunda vez con el mismo modelo que acaba de construir, inmediatamente obtiene otros 92k correctos (51.7% -> 59.3%), pero siempre es inferior al 60% desde la segunda iteración.

El código de medición está en el enlace TIO, o aquí hay una versión un poco mejor:

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 tiene la salida adivinada al final.

C ++, puntaje: 2 * 132 + 865821 = 866085

¡Gracias a @Quentin por guardar 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;}

Una solución muy simple que, dado un carácter, solo genera el carácter que aparece con más frecuencia después del carácter de entrada.

Verifique el puntaje con:

#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: el uso whale2.txtda una mejor puntuación.

Python, 2 * 516 + 521122 = 522154

Algoritmo:

Otra presentación de Python, este algoritmo calcula la próxima letra más probable mirando secuencias de longitud 1, ..., l. Se usa la suma de probabilidades, y hay algunos trucos para obtener mejores 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 galimatías, aunque puede ver que se repite en la frase ocasional, como "Padre 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 de prueba:

Bastante simple, muestra algunos ejemplos del texto en diferentes puntos. Utiliza whale2.txt, ya que esto evita cierta lógica adicional para calcular nuevas líneas.

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 conjeturas incorrectas

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

Pruébalo en línea!

Actualización: ~ 27000 puntos con archivo actualizado, 16 puntos (8 bytes) con una función mejor desarrollada.

Explicación

La forma en que esto funciona es que a medida que el código se ejecuta a través del texto, memoriza el último carácter que finalizó cualquier secuencia de 4 caracteres y devuelve ese valor. Algo similar al enfoque de Arnauld anterior, pero se basa en la probabilidad inherente de que dos secuencias de 4 caracteres dadas terminen de la misma manera.

De-golf:

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 por el archivo bzip2-comprimido whale2.txt con el primer byte perdido

Ignora su entrada; da como resultado la respuesta correcta. Esto proporciona una línea de base en un extremo; daniero proporciona una línea de base en el otro extremo.

Script de constructor:

#!/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 prueba de E / S (tcc; corte la primera línea para gcc). Cualquiera puede utilizar este arnés de prueba en una plataforma adecuada que envíe un programa completo que espere lectura / escritura de E / S. Utiliza la E / S byte-at-a-time para evitar trampas. El programa secundario debe vaciar la salida después de cada byte para evitar el bloqueo.

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

Pruébalo en línea!

... Los /// respuesta que imprime un espacio obtiene 10 votos a favor, mientras que mi código solo puede obtener 3 ...

Explicación:

Para cada personaje, el programa:

• incrementar frequency[prev][char]
• Encuentra el personaje que aparece más veces en frequency[char]
• y sacarlo.

• Código no protegido en el enlace TIO, comentado.
• El código es de 131 bytes.
• El código que se ejecuta en mi máquina informa:

879504 / 1215235
Time: 62.01348257784468

que tienen la puntuación total

2*131 + 879504 = 879766

Como no hay forma de cargar un archivo grande en TIO (excepto preguntarle a Dennis), el ejemplo que se ejecuta en el enlace TIO solo ejecuta el programa para una pequeña parte del texto.

En comparación con la respuesta anterior, esta tiene 362 caracteres incorrectos más, pero el código es más corto en 255 bytes. El multiplicador hace que mi presentación tenga una puntuación más baja.

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

Este enfoque utiliza una tabla de búsqueda para aprender el carácter más común que sigue a una cadena dada. Las teclas de la tabla de búsqueda tienen un máximo de 4 caracteres, por lo que la función primero actualiza la tabla de búsqueda con el carácter actual y luego simplemente verifica qué carácter es más probable que suceda después de los 4 anteriores, incluido el actual. . Si esos 4 caracteres no se encuentran en la tabla de búsqueda, imprime un espacio.

Esta versión utiliza el whale2.txtarchivo, ya que mejora en gran medida el número de conjeturas exitosas.

El siguiente es el código utilizado para probar la clase:

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

El código se ejecuta en apenas 2 segundos. Solo para el registro, esto es lo que obtengo cuando modifico el tamaño de las claves de la tabla de búsqueda (incluye los resultados de una segunda ejecución sin restablecer el 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

Sería interesante saber por qué un tamaño de clave de 4 caracteres es la mejor opción en este algoritmo.

Comparación 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!"

Recreado:

"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 

Suposiciones:

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

Cambiar registro

• 569279 : se modificó whale2.txty, por lo tanto, se eliminó la optimización.
• 577366 : optimizado con código que intentó adivinar cuándo devolver un avance de línea.
• 590354 - versión original.

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

Java es una mierda para programas pequeños. De todos modos, probé varios enfoques extremadamente complejos y complicados que produjeron resultados sorprendentemente malos. Posteriormente volví y simplemente hice un enfoque simple, que resultó en un tamaño de programa más pequeño y mejores resultados.

Este enfoque es realmente extremadamente simple. Alimenta ciegamente los caracteres x anteriores (además de todas las subcadenas de esos caracteres) en una tabla hash, asignada al carácter actual. Luego realiza un seguimiento de qué patrones predicen con mayor precisión el carácter actual. Si los patrones que preceden a ciertos personajes se encuentran varias veces, tienen éxito en predecir el personaje. Da prioridad a las cadenas más largas y da prioridad a cualquier carácter que siga con mayor frecuencia una cadena dada. Este algoritmo no sabe nada sobre el tipo de documento o el idioma inglés.

Me decidí a usar 9 caracteres e intentar unir palabras enteras con esos 9 caracteres anteriores cuando sea posible. Cuando no intenta hacer una coincidencia de palabras dentro de las cadenas, la longitud óptima es de 6 caracteres, produciendo varios miles de predicciones más.

Una observación interesante fue que el uso de 20 caracteres resultó en malas predicciones la primera vez, pero con una precisión del 99.9 por ciento en los pases posteriores. El algoritmo fue básicamente capaz de memorizar el libro en trozos superpuestos de 20 bytes, y esto fue lo suficientemente distinto como para permitirle recordar todo el libro de un personaje a la vez.

• (1950 * 2 + 532919) 536819
• (2406 * 2 + 526233) 531045 comprobando la puntuación para hacer mejores conjeturas
• (1995 * 2 + 525158) 529148 más retoques, jugaron un poco de palabrería

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

Intenté esto de forma independiente, pero terminé con lo que efectivamente es una versión inferior de la respuesta de Michael Homer. Espero que eso no vuelva mi respuesta completamente obsoleta.

Esto construye con el tiempo un diccionario de palabras (definido crudamente como cadenas terminadas por o \n, distingue entre mayúsculas y minúsculas e incluye puntuación). Luego busca en este diccionario palabras que comiencen con lo que hasta ahora conoce de la palabra actual, ordena la lista resultante por frecuencia de ocurrencia (lentamente) y adivina que el siguiente carácter es el siguiente en la palabra coincidente más común. Si ya tenemos la palabra coincidente más común, o ya no existe una palabra coincidente, devuelve .

También crea un diccionario repugnantemente ineficiente de pares de palabras. Al llegar al límite de una palabra, adivina que el siguiente carácter es la primera letra de la segunda palabra en el par de palabras coincidentes más comunes, o tsi no hay una coincidencia. Sin embargo, no es muy inteligente. A continuación Moby, el programa adivina correctamente que el siguiente personaje esD , pero luego olvida todo sobre el contexto y generalmente termina llamando a la ballena "Pato Moby" (porque la palabra "holandés" parece ser más frecuente en la primera mitad del texto). ) Sería fácil solucionar esto priorizando los pares de palabras sobre las palabras individuales, pero espero que la ganancia sea marginal (ya que generalmente es correcta desde el tercer carácter en adelante, y los pares de palabras no son tan útiles en primer lugar).

Podría ajustar esto para que coincida mejor con el texto proporcionado, pero no creo que el ajuste manual del algoritmo basado en el conocimiento previo de la entrada esté realmente en el espíritu del juego, aparte de elegir t como el personaje alternativo después de un espacio ( y probablemente tampoco debería haber hecho eso), lo evité. Ignoré la longitud de línea conocida del archivo de entrada y en su lugar inserté\n después de cada 13 espacios; esto es casi seguro una coincidencia muy pobre, la intención principal era mantener la longitud de línea razonable en lugar de coincidir con la entrada.

El código no es exactamente rápido (~ 2 horas en mi máquina), pero en general obtiene la mitad de los caracteres correctos (49%). Espero que el puntaje sea marginalmente mejor si se ejecuta whale2.txt, pero no lo he hecho.

El inicio de la salida se ve así:

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

pero al final, se parece un poco más a ... algo. Mi pasaje favorito casi al final del libro,

y como ninguno puede ser mío, déjame remolcar en pedazos, mientras te persigo, aunque atado a ti, ¡maldita ballena! ¡ASÍ, renuncio a la lanza! "

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

Eso habría hecho que The Wrath of Khan fuera mucho más confuso. Y "solitario" → "hormigueo" es una sustitución particularmente satisfactoria.

Editar: guardado un byte eliminando un espacio extraño

Puntuación

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

Esto ejecuta el programa para el texto de Moby Dick y genera el texto "predicho" en stdout, y abusa de stderr para escribir la partitura. Recomiendo redirigir la salida a un archivo.

C ++, 2 · 62829 + 318786 = 444444

Para ejecutar este programa, necesita este archivo aquí , que debe nombrarse C.

El programa usa la misma combinación de modelos de Markov que en nuestra respuesta anterior . Como antes, esta combinación es esencialmente el modelo de esta respuesta del usuario 2699 , pero con algunas pequeñas modificaciones.

Al ver cómo esta respuesta usa exactamente el mismo modelo que antes, la mejora es un mejor mecanismo teórico de información que el mecanismo de "rebobinado" descrito anteriormente. Esto le permite cometer menos errores y al mismo tiempo tener una longitud combinada más pequeña. El programa en sí no se juega mucho al golf porque no es el principal contribuyente a la puntuación.

El programa tiene una longitud de 2167 bytes (incluidas todas las pestañas para la sangría y muchos otros caracteres innecesarios, pero antes del código de prueba), y el archivo binario Ctiene una longitud de 60661 bytes, por lo que, según las reglas para calificar múltiples archivos , calificamos Lcomo 2167 + 60661 + 1 = 62829.

El programa tarda aproximadamente 8 minutos en ejecutarse en una m5.4xlargeinstancia en Amazon EC2 y utiliza un poco más de 16 GB de memoria. (Este uso excesivo de memoria no es necesario, simplemente tampoco lo optimizamos).

#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, errores 526092 (usando whale2.txt). Esto definitivamente es capaz de mejorar aún más, pero ha alcanzado la etapa de "lo suficientemente bueno 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))

La idea es almacenar las frecuencias de todas las ejecuciones de 2, 3, 4, ..., 10 caracteres. Para cada una de estas longitudes L, verificamos si los caracteres L-1 más recientes coinciden con un patrón almacenado; si es así, nuestra suposición g _L es el siguiente carácter más frecuente que sigue ese patrón. Recopilamos hasta nueve conjeturas de esta manera. Para decidir qué suposición usar, ponderamos la frecuencia de cada patrón por su longitud hasta la octava potencia. Se elige la suposición con la mayor suma de frecuencias ponderadas. Si no hay patrones que coincidan, adivinamos el espacio.

(La longitud máxima del patrón y el exponente de ponderación se eligieron por prueba y error para dar la menor cantidad de conjeturas incorrectas).

Aquí está mi versión sin trabajo de trabajo en progreso:

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

Y el arnés de prueba:

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

Aquí hay algunos resultados de muestra desde cerca del comienzo del texto. Ya empezamos a ver la posibilidad de terminar las palabras comunes después de ver su primera carta ( in, to, and, by, también, al parecer,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 

Cerca del final, todavía hay muchos errores, pero también muchas secuencias muy buenas ( shmage seashawkspor ejemplo).

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

Es interesante observar algunos de los errores y adivinar qué palabra "esperaba" el algoritmo. Por ejemplo, después sail, el programa dos veces predice o--para sailor, supongo. O de nuevo, después de , alo nesperado, posiblemente debido a la ocurrencia común de, and .

Registro de cambios:

• 274 * 2 + 526092 = 526640 Golfed el algoritmo, a costa de algunos errores adicionales
• 306 * 2 + 526089 = 526701 Versión original

Python 2, puntaje: 2 * (407 + 56574) + 562262 = 676224

Las búsquedas de palabras que coinciden con los caracteres anteriores a partir de una lista de  todas las  mayoría de las palabras utilizadas en el texto, ordenados por el número de sus apariciones.

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"

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

Banco de pruebas:

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: el uso whale2.txtda una mejor puntuación.

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

Otra presentación de frecuencia de prefijo. Sigue corriendo whale2.txty obtén un puntaje similar (ligeramente peor) que otros.

#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 busca con avidez la cadena más larga que comienza con un sufijo de la historia, y si hay múltiples candidatos, desempate con cadenas más cortas.

Por ejemplo: si los últimos 7 caracteres son abcdefgh, y la cadena abcdefghiy abcdefghjaparece con la frecuencia más grande en todas las cadenas de la forma abcdefgh*, la salida será io j, desempate con sufijos más cortos ( bcdefgh,cdefgh , ...).

Por razones desconocidas, nada más que 7 y mi computadora no tiene suficiente RAM para ejecutarlo. Incluso con 7, necesito cerrar todos los navegadores web para ejecutarlo.

Código de prueba:

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

Sin golf:

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