Voici un fichier texte de 1.2Mb ASCII contenant le texte de Moby-Dick de Herman Melville ; ou la baleine . Votre tâche consiste à écrire un programme ou une fonction (ou une classe, etc. - voir ci-dessous) qui recevra ce fichier caractère par caractère et à chaque étape, il devra deviner le caractère suivant.

C'est un défi de code . Votre score sera

2*L + E

où Lest la taille de votre soumission en octets et Ele nombre de caractères qu’il devine de manière incorrecte. Le score le plus bas gagne.

Autres détails

Votre soumission sera un programme ou une fonction (etc.) qui sera appelée ou invoquée ou des données envoyées plusieurs fois. (1215235 fois pour être exact.) Quand il sera appelé pour la n- ^ème fois, il recevra le n- ^ème caractère de whale.txtou whale2.txtet devra deviner pour le ( n + 1 ) ^ème caractère. La Ecomposante de sa partition sera le nombre total de caractères qu'il devine de manière incorrecte.

La plupart des soumissions devront stocker un état entre les invocations, afin de pouvoir suivre le nombre de fois où elles ont été appelées et les entrées précédentes. Vous pouvez le faire en écrivant dans un fichier externe, en utilisant staticdes variables globales, en soumettant une classe plutôt qu’une fonction, en utilisant une monade d’état ou tout ce qui fonctionne pour votre langue. Votre soumission doit inclure tout code nécessaire pour initialiser son état avant la première invocation.

Votre programme doit fonctionner de manière déterministe, de sorte qu'il émette toujours les mêmes suppositions avec la même entrée (et obtienne donc toujours le même score).

Votre réponse doit inclure non seulement votre soumission, mais également le code que vous avez utilisé pour calculer la Epartie de son score. Cela ne doit pas nécessairement être écrit dans la même langue que votre soumission et ne sera pas compté dans son décompte en octets. Vous êtes encouragé à le rendre lisible.

En ce qui concerne l'interface entre votre soumission et ce programme de calcul du score, tout va bien, à condition que votre programme donne toujours un octet de sortie avant de recevoir son prochain octet d'entrée. (Ainsi, par exemple, vous ne pouvez pas simplement lui transmettre une chaîne contenant toutes les entrées et obtenir une chaîne contenant toutes les sorties.)

Vous devez réellement exécuter votre programme de test et calculer / vérifier votre score avant de soumettre votre candidature. Si votre soumission est trop lente pour que vous puissiez vérifier son score, elle n'est pas qualifiée pour concurrencer, même si vous savez quel est son score en principe.

La Lcomposante de votre score sera calculée selon les règles habituelles pour les défis de golf de code. Si votre soumission doit contenir plusieurs fichiers, veuillez noter les règles relatives à l' évaluation et à la structure des répertoires dans ce cas. Toutes les données utilisées par votre code doivent être incluses dans votre Lscore.

Vous pouvez importer des bibliothèques existantes mais ne pas charger d’autres fichiers externes et votre code peut ne pas accéder au whale.txtouwhale2.txtdéposer de toute autre manière que celle décrite ci-dessus. Vous ne pouvez pas charger de réseaux neuronaux pré-formés ni d'autres sources de données statistiques. (C'est bien d'utiliser des réseaux de neurones, mais vous devez inclure les données de poids dans votre soumission et les compter dans votre nombre d'octets.) Si, pour une raison quelconque, votre langue ou vos bibliothèques incluent une fonctionnalité qui fournit tout ou partie du texte de Moby Dick , vous ne pouvez pas utiliser cette fonctionnalité. En dehors de cela, vous pouvez utiliser toute autre fonctionnalité intégrée ou de bibliothèque que vous aimez, y compris celles relatives au traitement, à la prédiction ou à la compression de texte, à condition qu'elles fassent partie de votre langage ou de ses bibliothèques standard. Pour des routines plus exotiques et spécialisées incluant des sources de données statistiques, vous devez les implémenter vous-même et les inclure dans votre nombre d'octets.

Il est probable que certaines soumissions incluront des composants générés par le code. Si tel est le cas, veuillez inclure dans votre réponse le code qui a été utilisé pour les produire et expliquer comment cela fonctionne . (Tant que ce code n'est pas nécessaire pour exécuter votre soumission, il ne sera pas inclus dans votre nombre d'octets.)

Pour des raisons historiques, il existe deux versions du fichier et vous pouvez utiliser l’une ou l’autre dans une réponse. Dans whale2.txt(lien ci-dessus), le texte n'est pas encapsulé, de sorte que les nouvelles lignes apparaissent uniquement à la fin des paragraphes. Dans l'original, whale.txtle texte est entouré d'une largeur de 74 caractères. Vous devez donc prévoir la fin de chaque ligne ainsi que le texte. Cela rend le défi plus délicat, il whale2.txtest donc recommandé pour de nouvelles réponses. Les deux fichiers ont la même taille, 1215236 octets.

Pour résumer, toutes les réponses devraient inclure les éléments suivants:

• Votre soumission elle-même. (Le code, ainsi que tous les fichiers de données qu'il utilise - il peut s'agir de liens s'ils sont volumineux.)
• Une explication du fonctionnement de votre code. Veuillez expliquer la méthode d’E / S ainsi que la manière dont elle prédit le caractère suivant. L'explication de votre algorithme est importante et de bonnes explications vous rapporteront des primes.
• Le code que vous avez utilisé pour évaluer votre score. (Si cela est identique à une réponse précédente, vous pouvez simplement créer un lien vers celle-ci.)
• Tout code que vous avez utilisé pour générer votre soumission, avec une explication de ce code. Cela inclut le code que vous avez utilisé pour optimiser les paramètres, générer des fichiers de données, etc. (Ceci ne compte pas dans votre nombre d'octets mais doit être inclus dans votre réponse.)

Classement

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>

Primes

De temps en temps, je proposerai des primes pour encourager différentes approches.

Le premier, 50 points, a été attribué à A. Rex pour la réponse la plus performante à l’époque.

Le deuxième, 100 points, a également été attribué à A. Rex, pour la même réponse, car ils ont ajouté une très bonne explication à leur réponse existante.

La prochaine prime, 200 points , sera attribuée soit à

• Une réponse compétitive qui utilise une nouvelle technique. (Cela sera basé sur mon jugement subjectif puisque c'est mon représentant qui entre dans la prime, mais vous pouvez vous fier à moi pour être juste. Notez que votre réponse doit contenir suffisamment d'explications pour que je puisse comprendre comment cela fonctionne!) Ne prenez pas le score le plus élevé, il faut qu’il réussisse raisonnablement par rapport aux réponses existantes. Je suis particulièrement désireux de voir des solutions basées sur des réseaux de neurones récurrents, mais je vais attribuer la prime à tout ce qui semble assez différent des modèles de Markov qui dominent les meilleurs scores actuels.

Ou:

• Toute autre personne qui bat le meilleur score de A. Rex (actuellement 444444), quelle que soit la méthode employée.

Une fois la prime de 200 points réclamée, je proposerai très probablement une prime de 400 points, mettant à jour les exigences en conséquence.

/// , 2 * 1 + 1020874 = 1020876

Imprime un espace.

Node.js, 2 * 224 + 524279 = 524727

Veuillez vous reporter au journal des modifications à la fin de cet article pour connaître les mises à jour des scores.

Une fonction prenant et retournant un octet.

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

Il consiste en un modèle PPM simple qui examine les 8 derniers caractères pour prédire le prochain.

Nous faisons confiance à un modèle de longueur L lorsque nous l'avons rencontré au moins T [L] fois, où T est un tableau de seuils arbitraires: [1,1,2,1,2,3,5,2] . De plus, nous faisons toujours confiance à un motif dont le premier caractère correspond [A-Z '"(].

Nous sélectionnons le modèle de confiance le plus long et renvoyons la prédiction avec le score le plus élevé associé à ce modèle au moment de l'appel.

Remarques

• Ce n'est évidemment pas optimisé pour la vitesse, mais cela dure environ 15 secondes sur mon ordinateur portable.

• Si nous pouvions répéter le processus plusieurs fois de suite sans réinitialiser le modèle, le nombre d'erreurs convergerait vers ~ 268000 après 5 itérations.

• Le taux de réussite actuel de la fonction de prévision est d'environ 56,8%. Comme @immibis l’a remarqué dans les commentaires, si les suppositions correctes et correctes sont mélangées, le résultat n’est même pas à peine lisible.

  Par exemple, cet extrait de code vers la fin du livre:

  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.
  

  devient:

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

  En remplaçant les mauvaises suppositions par des tirets bas, nous avons une meilleure idée de ce que la fonction a obtenu:

  _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 : L'exemple ci-dessus a été créé avec une version précédente du code, travaillant sur la première version du fichier d'entrée.}

Code de test

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

Changer le journal

• 524727 - 19644 points enregistrés en passant à whale2.txt (mise à jour du défi)
• 544371 - 327 points enregistrés en forçant les modèles commençant par une lettre majuscule, une citation, une double citation ou une parenthèse ouvrante
• 544698 - 2119 points enregistrés en forçant les modèles commençant par un espace à être toujours fiables
• 546817 - A enregistré 47 points en ajustant les seuils et en jouant au golf avec la fonction de prédiction
• 546864 - 1496 points enregistrés en étendant la longueur maximale du motif à 8 caractères
• 548360 - 6239 points économisés en introduisant la notion de modèles de confiance, avec des seuils dépendant de leur longueur
• 554599 - gain de 1030 points en améliorant la prévision de saut de ligne
• 555629 - 22 points enregistrés en jouant au golf avec la fonction de prédiction
• 555651 - a enregistré 40 points en jouant au golf avec la fonction de prédiction
• 555691 - score initial

Perl, 2 · 70525 + 326508 = 467558

Prédicteur

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

Pour exécuter ce programme, vous avez besoin de ce fichier ici , qui doit être nommé B. (Vous pouvez modifier ce nom de fichier dans la deuxième instance du caractère Bci-dessus.) Voir ci-dessous pour savoir comment générer ce fichier.

Le programme utilise une combinaison de modèles de Markov essentiellement comme dans cette réponse de l'utilisateur 2699 , mais avec quelques modifications mineures. Cela produit une distribution pour le caractère suivant. Nous utilisons la théorie de l'information pour décider d'accepter une erreur ou de dépenser une partie de la mémoire en Bindices de codage (et si oui, comment). Nous utilisons le codage arithmétique pour stocker de manière optimale les bits fractionnaires du modèle.

Le programme a une longueur de 582 octets (y compris une nouvelle ligne inutile) et le fichier binaire, une Blongueur de 69942 octets. Ainsi, selon les règles de notation de plusieurs fichiers , nous obtenons le score Lsuivant: 582 + 69942 + 1 = 70525.

Le programme nécessite presque certainement une architecture 64 bits (little-endian?). Il faut environ 2,5 minutes pour s'exécuter sur une m5.largeinstance sur Amazon EC2.

Code de test

# 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

Le harnais de test suppose que la soumission est dans le fichier submission.pl, mais cela peut facilement être modifié dans la deuxième ligne.

Comparaison de texte

"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

Cet échantillon (choisi dans une autre réponse ) apparaît assez tard dans le texte, le modèle est donc assez développé à ce stade. Rappelez-vous que le modèle est complété par 70 kilo-octets "d'indices" qui l'aident directement à deviner les caractères; il ne s'agit pas simplement du court extrait de code ci-dessus.

Générer des astuces

Le programme suivant accepte le code de soumission exact ci-dessus (sur l'entrée standard) et génère le Bfichier exact ci-dessus (sur la sortie standard):

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

Il faut environ autant de temps que la soumission pour s'exécuter, car il effectue des calculs similaires.

Explication

Dans cette section, nous tenterons de décrire ce que fait cette solution avec suffisamment de détails pour que vous puissiez "l'essayer à la maison" vous-même. La technique principale qui différencie cette réponse des autres consiste à utiliser quelques étapes comme mécanisme de "rembobinage", mais avant d’y parvenir, nous devons définir les bases.

Modèle

L'ingrédient de base de la solution est un modèle de langage. Pour nos besoins, un modèle est quelque chose qui prend une certaine quantité de texte anglais et renvoie une distribution de probabilité sur le caractère suivant. Lorsque nous utiliserons le modèle, le texte anglais sera un préfixe (correct) de Moby Dick. Veuillez noter que la sortie souhaitée est une distribution et non une simple estimation du caractère le plus probable.

Dans notre cas, nous utilisons essentiellement le modèle dans cette réponse par utilisateur2699 . Nous n'avons pas utilisé le modèle de la réponse la plus élevée (autre que la nôtre) d'Anders Kaseorg, précisément parce que nous ne pouvions pas extraire une distribution plutôt qu'une seule hypothèse. En théorie, cette réponse calcule une moyenne géométrique pondérée, mais nous avons obtenu des résultats quelque peu médiocres en interprétant cela trop littéralement. Nous avons "volé" un modèle sur une autre réponse parce que notre "sauce secrète" n'est pas le modèle mais plutôt l'approche globale. Si quelqu'un a un "meilleur" modèle, il devrait être en mesure d'obtenir de meilleurs résultats en utilisant le reste de nos techniques.

Comme remarque, la plupart des méthodes de compression telles que Lempel-Ziv peuvent être considérées comme un "modèle de langage" de cette manière, bien que l'on puisse avoir à plisser les yeux un peu. (C'est particulièrement délicat pour quelque chose qui transforme Burrows-Wheeler!) Notez également que le modèle créé par l'utilisateur 2699 est une modification du modèle de Markov; Essentiellement, rien d’autre n’est concurrentiel pour ce défi ou même pour la modélisation de texte en général.

Architecture globale

Pour faciliter la compréhension, il est agréable de décomposer l’architecture globale en plusieurs parties. Du plus haut niveau, il faut un peu de code de gestion d’état. Ce n’est pas particulièrement intéressant, mais pour être complet, nous tenons à souligner qu’à chaque étape du programme, on demande au programme de supposer, qu’il dispose du préfixe correct de Moby Dick. Nous n'utilisons en aucun cas nos suppositions incorrectes du passé. Pour des raisons d'efficacité, le modèle de langage peut probablement réutiliser son état parmi les N premiers caractères pour calculer son état pour les premiers caractères (N + 1), mais il peut en principe recalculer les éléments à partir de zéro chaque fois qu'il est appelé.

Mettons de côté ce "pilote" de base du programme et jetons un coup d'œil à l'intérieur de la partie qui suppose le prochain caractère. Conceptuellement, il est utile de séparer trois parties: le modèle de langage (décrit ci-dessus), un fichier "astuces" et un "interprète". À chaque étape, l'interprète demandera au modèle de langage une distribution du prochain caractère et lira éventuellement certaines informations du fichier d'indications. Ensuite, il va combiner ces parties dans une supposition. Les informations contenues dans le fichier de conseils ainsi que la manière dont elles seront utilisées seront expliquées ultérieurement, mais pour le moment, il est utile de garder ces parties séparées mentalement. Notez que, du point de vue de la mise en œuvre, le fichier d'indications est littéralement un fichier séparé (binaire), mais il pourrait s'agir d'une chaîne ou de quelque chose stocké dans le programme. À titre approximatif,

Si vous utilisez une méthode de compression standard telle que bzip2 comme dans cette réponse , le fichier "hints" correspond au fichier compressé. L '"interprète" correspond au décompresseur, alors que le "modèle de langage" est un peu implicite (comme mentionné ci-dessus).

Pourquoi utiliser un fichier indice?

Prenons un exemple simple pour approfondir l'analyse. Supposons que le texte comporte des Ncaractères longs et bien approximés par un modèle dans lequel chaque caractère est (indépendamment) la lettre Eavec une probabilité légèrement inférieure à la moitié, de Tmême avec une probabilité légèrement inférieure à la moitié et Aavec une probabilité de 1/1000 = 0,1%. Supposons qu'aucun autre caractère ne soit possible; en tout cas, le cas Aest assez similaire au cas d'un personnage auparavant invisible, sorti de nulle part.

Si nous avons fonctionné dans le régime L 0 (comme le font la plupart des réponses à cette question, mais pas toutes), il n'y a pas de meilleure stratégie pour l'interprète que de choisir l'une des options suivantes: Eet T. En moyenne, environ la moitié des caractères seront corrects. Donc E ≈ N / 2 et le score ≈ N / 2 également. Cependant, si nous utilisons une stratégie de compression, nous pouvons alors compresser un peu plus d'un bit par caractère. Puisque L est compté en octets, nous obtenons L ≈ N / 8 et obtenons ainsi N / 4, deux fois plus performant que la stratégie précédente.

Obtenir ce taux d'un peu plus d'un bit par caractère pour ce modèle est légèrement non trivial, mais une méthode est le codage arithmétique.

Codage arithmétique

Comme on le sait communément, un codage est une manière de représenter certaines données en bits / octets. Par exemple, ASCII est un codage de 7 bits / caractères de texte anglais et de caractères associés, ainsi que le codage du fichier Moby Dick d'origine à l'étude. Si certaines lettres sont plus courantes que d'autres, un codage à largeur fixe comme ASCII n'est pas optimal. Dans une telle situation, beaucoup de gens se tournent vers le codage de Huffman . Ceci est optimal si vous voulez un code fixe (sans préfixe) avec un nombre entier de bits par caractère.

Cependant, le codage arithmétique est encore meilleur. Grosso modo, il est capable d’utiliser des bits "fractionnaires" pour coder des informations. Il existe de nombreux guides sur le codage arithmétique disponibles en ligne. Nous allons ignorer les détails ici (en particulier de la mise en œuvre pratique, ce qui peut être un peu délicat du point de vue de la programmation) en raison des autres ressources disponibles en ligne, mais si quelqu'un se plaint, cette section sera peut-être plus complète.

Si le texte est réellement généré par un modèle de langage connu, le codage arithmétique fournit un codage essentiellement optimal du texte de ce modèle. Dans un certain sens, cela "résout" le problème de compression pour ce modèle. (Ainsi, dans la pratique, le principal problème est que le modèle n'est pas connu et que certains modèles sont meilleurs que d'autres pour la modélisation de texte humain.) S'il n'était pas permis de commettre des erreurs dans ce concours, dans le langage de la section précédente. Pour résoudre ce problème, une solution aurait consisté à utiliser un encodeur arithmétique pour générer un fichier "astuces" à partir du modèle de langage, puis à utiliser un décodeur arithmétique comme "interprète".

Dans ce codage essentiellement optimal, nous finissons par dépenser -log_2 (p) bits pour un caractère de probabilité p, et le débit global du codage correspond à l' entropie de Shannon . Cela signifie qu’un caractère dont la probabilité est proche de 1/2 nécessite environ un bit à encoder, tandis que celui ayant une probabilité de 1/1000 utilise environ 10 bits (car 2 ^ 10 équivaut à environ 1000).

Mais la métrique de score pour ce défi a été bien choisie pour éviter la compression comme stratégie optimale. Nous devrons trouver un moyen de faire des erreurs comme compromis pour obtenir un fichier d'indices plus court. Par exemple, une stratégie que l’on pourrait essayer est une stratégie de branchement simple: nous essayons généralement d’utiliser un encodage arithmétique lorsque nous le pouvons, mais si la distribution de probabilité du modèle est "mauvaise" d’une certaine manière, nous devinons simplement le caractère le plus probable et ne le faisons pas. Ne pas essayer de l’encoder.

Pourquoi faire des erreurs?

Analysons l'exemple d'avant afin de motiver pourquoi nous pourrions vouloir faire des erreurs "intentionnellement". Si nous utilisons le codage arithmétique pour coder le caractère correct, nous dépenserons environ un bit dans le cas d’un Eou T, mais environ dix bits dans le cas d’un A.

Globalement, il s’agit d’un très bon encodage, dépensant un peu plus par caractère même s’il existe trois possibilités; fondamentalement, cela Aest assez improbable et nous ne finissons pas par dépenser trop souvent les dix bits correspondants. Cependant, ne serait-il pas agréable de pouvoir commettre une erreur dans le cas d'un A? Après tout, la métrique du problème considère que 1 octet = 8 bits de longueur équivaut à 2 erreurs; il semble donc qu'il faille préférer une erreur au lieu de dépenser plus de 8/2 = 4 bits sur un caractère. Dépenser plus d'un octet pour enregistrer une erreur semble définitivement sous-optimal!

Le mécanisme de "rembobinage"

Cette section décrit le principal aspect astucieux de cette solution, à savoir un moyen de gérer gratuitement les suppositions incorrectes.

Pour l'exemple simple que nous avons analysé, le mécanisme de rembobinage est particulièrement simple. L'interprète lit un bit du fichier d'indications. Si c'est un 0, il devine E. Si c'est un 1, il devine T. La prochaine fois qu'il est appelé, il voit quel est le bon caractère. Si le fichier d’indications est bien configuré, nous pouvons nous assurer que dans le cas d’un Eou T, l’interprète devine correctement. Mais qu'en est-il A? L'idée du mécanisme de rembobinage est de ne pas coder Adu tout . Plus précisément, si l'interprète apprend plus tard que le caractère correct est un A, il métaphoriquement " rembobine la bande": il renvoie le bit lu précédemment. Le bit lu a bien l'intention de coder EouT, mais pas maintenant; il sera utilisé plus tard. Dans cet exemple simple, cela signifie qu’il continue à deviner le même caractère ( Eou T) jusqu’à ce qu’il comprenne bien; alors il lit un autre bit et continue.

Le codage de ce fichier de conseils est très simple: convertissez tous les Es en 0 bits et Ts en 1 bits, tout en ignorant As complètement. D'après l'analyse à la fin de la section précédente, ce schéma fait quelques erreurs mais réduit le score dans son ensemble en ne codant aucun des As. En tant qu'effet plus petit, il enregistre en fait la longueur du fichier d'indications également, car nous finissons par utiliser exactement un bit pour chacun Eet Tau lieu de légèrement plus qu'un peu.

Un petit théorème

Comment décidons-nous quand faire une erreur? Supposons que notre modèle nous donne une distribution de probabilité P pour le caractère suivant. Nous allons séparer les caractères possibles en deux classes: codée et non codée . Si le caractère correct n'est pas codé, nous utiliserons ensuite le mécanisme de "rembobinage" pour accepter une erreur sans frais en longueur. Si le bon caractère est codé, nous utiliserons une autre distribution Q pour le coder en utilisant un codage arithmétique.

Mais quelle distribution Q devrions-nous choisir? Il n'est pas trop difficile de voir que les caractères codés devraient tous avoir une probabilité plus élevée (en P) que les caractères non codés. En outre, la distribution Q ne devrait inclure que les caractères codés; après tout, nous ne codons pas les autres, nous ne devrions donc pas "dépenser" de l'entropie sur eux. Il est un peu plus délicat de voir que la distribution de probabilité Q devrait être proportionnelle à P sur les caractères codés. Rassembler ces observations signifie que nous devrions coder les caractères les plus probables, mais peut-être pas les caractères les moins probables, et que Q est simplement redimensionné sur les caractères codés.

De plus, il s'avère qu'il existe un théorème intéressant concernant la "coupure" à choisir pour les caractères de codage: vous devez coder un caractère tant qu'il est au moins égal à 1 / 5.393 aussi vraisemblable que les autres caractères codés combinés. Ceci "explique" l'apparition de la constante apparemment aléatoire vers 5.393la fin du programme ci-dessus. Le nombre 1 / 5.393 ≈ 0.18542 est la solution à l'équation -p log (16) - p log p + (1 + p) log (1 + p) = 0 .

C'est peut-être une idée raisonnable d'écrire cette procédure en code. Cet extrait 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;
}

Mettre tous ensemble

La section précédente est malheureusement un peu technique, mais si nous assemblons toutes les autres pièces, la structure est la suivante. Chaque fois que le programme est invité à prédire le caractère suivant après un caractère correct donné:

1. Ajoutez le caractère correct au préfixe correct connu de Moby Dick.
2. Mettez à jour le modèle (Markov) du texte.
3. La sauce secrète : Si la supposition précédente était incorrecte, ramenez l’état du décodeur arithmétique à son état antérieur à la précédente!
4. Demandez au modèle de Markov de prédire une distribution de probabilité P pour le prochain caractère.
5. Transformez P en Q en utilisant le sous-programme de la section précédente.
6. Demandez au décodeur arithmétique de décoder un caractère du reste du fichier d'indices, en fonction de la distribution Q.
7. Devinez le personnage résultant.

L'encodage du fichier d'indications fonctionne de la même manière. Dans ce cas, le programme sait quel est le bon caractère suivant. Si c'est un caractère qui devrait être codé, alors bien sûr, vous devriez utiliser le codeur arithmétique dessus; mais s'il s'agit d'un caractère non codé, il ne met simplement pas à jour l'état du codeur arithmétique.

Si vous comprenez le contexte théorique de l'information tel que les distributions de probabilité, l'entropie, la compression et le codage arithmétique mais que vous avez essayé de comprendre cet article (sauf pourquoi le théorème est vrai), laissez-nous savoir et nous pouvons essayer de clarifier les choses. Merci d'avoir lu!

Python 3, 2 · 267 + 510193 = 510727

Prédicteur

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]

Il utilise une combinaison bayésienne pondérée de l’ordre 0,…, 16 modèles de Markov, avec des poids [1, 6, 12, 30, 65, 99, 87, 117, 118, 89, 95, 118, 96, 184, 126, 219, 126].

Le résultat n'est pas très sensible au choix de ces poids, mais je les ai optimisés car je pouvais utiliser le même algorithme d' acceptation tardive que celui que j'ai utilisé dans ma réponse à «Assembler une majorité au Sénat» , où chaque mutation candidate est juste un incrément de ± 1 pour un seul poids.

Code de test

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

Essayez-le en ligne!

Une fonction utilisant des variables globales. Apprend au fur et à mesure, en construisant un modèle au niveau du mot: étant donné ce que l’on voit jusqu’à présent dans ce mot , quel est le prochain caractère le plus courant? Au fur et à mesure que plus d’entrées entrent, il apprend assez bien les mots courants du texte et le caractère le plus courant pour commencer le mot suivant .

Par exemple:

• Si ce que l’on voit jusqu’à présent, c’est 'Captai', il prédit un "n"
• Si c'est "Captain", il prédit un espace
• Si c'est le début d'un mot et que le dernier mot était "Capitaine", cela prédit un 'A'
• Si le mot jusqu'à présent est "A", il prédit un "h" (puis "a" et "b"; de même pour "C").

Cela ne va pas très bien au début, mais à la fin, il y a beaucoup de mots qui sortent. L'option de secours est un espace et après un espace unique, un "a", à moins que la lettre précédente ne soit "nedtfo", un chiffre, un trait d'union ou une apostrophe. Il prédit également de manière agressive les coupures de ligne après 71 caractères, ou si un espace est attendu après 66. Ces deux paramètres ont été ajustés aux données ("t" est beaucoup plus courant après un espace, mais a déjà été prédit plus souvent, donc " un "est une meilleure hypothèse en dehors de ces six cas spéciaux).

Apprendre quelles paires de mots allaient ensemble et préconfigurer la cartographie s’est avéré inutile.

Il se termine avec un texte comme celui-ci:

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!

ce qui correspond à cette partie de l'entrée:

tout autour de lui.

"Je l'ai vu presque au même moment que le capitaine Achab, monsieur, et j'ai crié", a déclaré Tashtego.

"Pas le même instant; pas le même - non, le doublon est à moi, le destin m'a réservé le doublon. Moi seulement; aucun d'entre vous n'aurait pu élever la baleine blanche en premier. Là, elle souffle! - là, elle souffle! - -là elle souffle!

Vous pouvez voir où les noms propres en particulier ressortent plutôt bien, mais la fin des mots est également généralement juste. Quand on voit "dou", on s'attend à un "doute", mais une fois que le "l" apparaît, il devient "doubloon".

Si vous l'exécutez une seconde fois avec le même modèle, il vient de générer immédiatement une autre conversion correcte de 92k (51,7% -> 59,3%), mais elle reste toujours à un peu moins de 60% à partir de la deuxième itération.

Le code de mesure est dans le lien TIO, ou voici une version légèrement meilleure:

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 a la sortie devinée à la fin.

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

Merci à @Quentin d'avoir sauvé 217 octets!

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

Une solution très simple qui, à partir d’un caractère, n’affiche que le caractère qui apparaît le plus souvent après le caractère saisi.

Vérifiez le score avec:

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

Edit: Utiliser whale2.txtdonne un meilleur score.

Python, 2 * 516 + 521122 = 522154

Algorithme:

Encore une autre soumission en python, cet algorithme calcule la prochaine lettre la plus probable qui regarde les séquences de longueur 1, ..., l. La somme des probabilités est utilisée et il existe quelques astuces pour obtenir de meilleurs résultats.

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

Résultats:

Généralement du charabia, même si vous pouvez le voir reprendre une phrase occasionnelle, telle que "Père 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

Code de test:

Assez simple, sort quelques exemples du texte à différents points. Utilise whale2.txt, car cela évite une logique supplémentaire pour calculer les nouvelles lignes.

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 octets, 679619 652740 suppositions incorrectes

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

Essayez-le en ligne!

Mise à jour: ~ 27 000 points avec le fichier mis à jour, 16 points (8 octets) avec une fonction de meilleure qualité.

Explication

La façon dont cela fonctionne est que, lorsque le code parcourt le texte, il mémorise le dernier caractère qui a mis fin à une séquence de 4 caractères donnée et renvoie cette valeur. Un peu similaire à l'approche d'Arnauld ci-dessus, mais repose sur la probabilité inhérente que deux séquences de 4 caractères données se terminent de la même manière.

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

suivi du whale2.txt compressé avec bzip2 avec le premier octet manquant

Ignore son entrée; affiche la bonne réponse. Cela fournit une ligne de base à une extrémité; daniero fournit une ligne de base à l'autre extrémité.

Script de constructeur:

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

Faisceau de test I / O (tcc; couper la première ligne pour gcc). Ce faisceau de test peut être utilisé par n’importe qui sur une plate-forme appropriée qui soumet un programme complet qui attend des E / S en lecture / écriture. Il utilise des E / S octet à la fois pour éviter les tricheries. Le programme enfant doit vider la sortie après chaque octet pour éviter le blocage.

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

Essayez-le en ligne!

... La ///réponse qui imprime un espace obtient 10 votes positifs, alors que mon code ne peut en obtenir que 3 ...

Explication:

Pour chaque personnage, le programme:

• augmenter frequency[prev][char]
• Trouvez le personnage qui apparaît le plus souvent dans frequency[char]
• et le sortir.

• Code non-lié dans le lien TIO, commenté.
• Le code est 131 octets.
• Le code exécuté sur ma machine indique:

879504 / 1215235
Time: 62.01348257784468

qui ont le score total

2*131 + 879504 = 879766

Comme il n’existe aucun moyen de télécharger un fichier volumineux vers TIO (sauf demander à Dennis), l’exemple exécuté dans le lien TIO n’exécute le programme que pour une petite partie du texte.

En comparaison avec la réponse précédente, celle-ci comporte 362 caractères incorrects de plus, mais le code est plus court de 255 octets. Le multiplicateur fait que ma soumission a un score inférieur.

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

Cette approche utilise une table de correspondance pour apprendre le caractère le plus courant qui suit une chaîne donnée. Les clés de la table de correspondance ont un maximum de 4 caractères. La fonction met donc d'abord à jour la table de correspondance avec le caractère actuel, puis vérifie simplement quel caractère est le plus susceptible de se produire après les 4 précédents, y compris celui en cours. . Si ces 4 caractères ne sont pas trouvés dans la table de correspondance, une espace est imprimée.

Cette version utilise le whale2.txtfichier, car elle améliore considérablement le nombre de suppositions réussies.

Voici le code utilisé pour tester la 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();
    }
}

Le code s'exécute en à peine 2 secondes. Pour mémoire, voici ce que je reçois lorsque je modifie la taille des clés de la table de correspondance (inclut les résultats d'une seconde exécution sans réinitialiser le modèle):

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

Il serait intéressant de savoir pourquoi une taille de clé de 4 caractères est le meilleur choix dans cet algorithme.

Comparaison de texte

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

Recréé:

"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 

Suppositions:

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

Changer le journal

• 569279 - remplacé whale2.txtpar l'optimisation ainsi supprimée.
• 577366 - optimisé avec un code qui essayait de deviner quand renvoyer un saut de ligne.
• 590354 - version originale.

Java 7, 1995 caractères, (1995 * 2 + 525158) 529148

Java est nul pour les petites tailles de programme. Quoi qu'il en soit, j'ai essayé plusieurs approches extrêmement complexes et délicates qui ont produit des résultats étonnamment nuls. Par la suite, j’y suis retourné et n’ai fait qu’une approche simple, ce qui a permis de réduire la taille du programme et d’améliorer les résultats.

Cette approche est en réalité extrêmement simple. Il introduit aveuglément les x caractères précédents (en plus de toutes les sous-chaînes de ces caractères) dans une table de hachage mappée sur le caractère actuel. Il garde ensuite trace des modèles qui prédisent le plus précisément le caractère actuel. Si les motifs qui précèdent certains caractères sont rencontrés plusieurs fois, ils parviennent à prédire le caractère. Il donne la priorité aux chaînes plus longues et au caractère qui suit le plus souvent une chaîne donnée. Cet algorithme ne sait rien du type de document ou de la langue anglaise.

J'ai choisi d'utiliser 9 caractères et d'essayer de faire correspondre les mots entiers de ces 9 caractères précédents lorsque cela était possible. Lorsque vous n'essayez pas de faire correspondre les mots dans les chaînes, la longueur optimale est de 6 caractères, ce qui génère plusieurs milliers de mauvaises prédictions.

Une observation intéressante était que l'utilisation de 20 caractères entraînait de mauvaises prédictions la première fois mais une précision de 99,9% lors des passages suivants. L'algorithme était fondamentalement capable de mémoriser le livre par superposition de morceaux de 20 octets, ce qui était suffisamment distinct pour lui permettre de rappeler le livre entier, un caractère à la fois.

• (1950 * 2 + 532919) 536819
• (2406 * 2 + 526233) 531045 vérifiant la ponctuation pour mieux deviner
• (1995 * 2 + 525158) 529148 plus de peaufinage, golfé quelques verbiage

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

J'ai essayé cela de façon indépendante, mais je me suis retrouvé avec une version inférieure de la réponse de Michael Homer. J'espère que cela ne rend pas ma réponse complètement obsolète.

Ceci construit au fil du temps un dictionnaire de mots (défini grossièrement comme des chaînes terminées par ou \n, sensibles à la casse et incluant la ponctuation). Il recherche ensuite dans ce dictionnaire les mots commençant par ce qu'il sait jusqu'ici du mot actuel, trie la liste résultante par fréquence d'apparition (lentement) et suppose que le caractère suivant est le caractère suivant du mot correspondant le plus commun. Si nous avons déjà le mot correspondant le plus commun ou s'il n'existe plus, le mot correspondant est renvoyé .

Il crée également un dictionnaire de paires de mots dégoûtant et inefficace. En atteignant une limite de mot, il devine que le caractère suivant est la première lettre du deuxième mot de la paire de mots correspondante la plus courante, ou ts'il n'y a pas de correspondance. Ce n'est pas très intelligent, cependant. Ensuite Moby, le programme devine correctement que le caractère suivant est D, mais il oublie tout du contexte et finit généralement par appeler la baleine "Moby Duck" (car le mot "néerlandais" semble être plus fréquent dans la première moitié du texte. ). Il serait facile de résoudre ce problème en donnant la priorité aux paires de mots aux mots individuels, mais je m'attends à ce que le gain soit marginal (puisqu'il est généralement correct à partir du troisième caractère et que les paires de mots ne sont pas très utiles au départ).

Je pourrais ajuster ceci pour mieux correspondre au texte fourni, mais je ne pense pas que le réglage manuel de l'algorithme basé sur une connaissance préalable de l'entrée est vraiment dans l'esprit du jeu, donc, à part choisir t comme caractère de secours après un espace ( et je n'aurais probablement pas dû le faire non plus), je l'ai évité. J'ai ignoré la longueur de ligne connue du fichier d'entrée et inséré à la place \ntoutes les 13 espaces; il s'agit certainement d'une correspondance très médiocre. L'intention principale était de garder la longueur de ligne raisonnable plutôt que de faire correspondre l'entrée.

Le code n'est pas très rapide (environ 2 heures sur ma machine), mais dans l'ensemble, environ la moitié des caractères sont corrects (49%). Je m'attends à ce que le score soit légèrement meilleur si on continue whale2.txt, mais je ne l'ai pas fait.

Le début de la sortie ressemble à ceci:

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

mais à la fin, ça ressemble un peu plus à ... quelque chose. Mon passage préféré de la fin du livre,

et comme aucun des deux ne peut être à moi, laissez-moi alors déchirer en lambeaux, tout en vous poursuivant, bien que vous soyez lié à toi, maudite baleine! AINSI, j'abandonne la lance! "

sort comme

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 "

Cela aurait rendu The Wrath of Khan beaucoup plus déroutant. Et "solitaire" → "tingly" est une substitution particulièrement satisfaisante.

Éditer: un octet enregistré en supprimant un espace superflue

Notation

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

Ceci exécute le programme pour le texte de Moby Dick et génère le texte "prédit" textto stdout, et abuse de stderr pour écrire le score. Je vous recommande de rediriger la sortie vers un fichier.

C ++, 2 · 62829 + 318786 = 444444

Pour exécuter ce programme, vous avez besoin de ce fichier ici , qui doit être nommé C.

Le programme utilise la même combinaison de modèles de Markov que dans notre réponse précédente . Comme précédemment, cette combinaison est essentiellement le modèle de cette réponse de l'utilisateur 2699 , mais avec quelques petites modifications.

Voyant comment cette réponse utilise exactement le même modèle qu'auparavant, l'amélioration est un meilleur mécanisme de théorie de l' information que le mécanisme de "rembobinage" décrit précédemment. Cela lui permet de faire moins d’erreurs tout en ayant une longueur combinée plus petite. Le programme lui-même ne joue pas beaucoup au golf, car il n’est pas le principal contributeur au score.

Le programme est 2167 octets (y compris tous les onglets pour l' indentation et beaucoup d'autres caractères inutiles, mais avant le code de test) et le fichier binaire Cest 60661 octets, donc dans les règles de notation fichiers multiples , nous marquons Len 2167 + 60661 + 1 = 62829.

Le programme prend environ 8 minutes pour s'exécuter sur une m5.4xlargeinstance sur Amazon EC2 et utilise un peu plus de 16 Go de mémoire. (Cette utilisation excessive de la mémoire n'est pas nécessaire - nous ne l'avons pas optimisée non plus.)

#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 octets, 526092 erreurs (utilisation whale2.txt). Ceci est certainement capable d'amélioration, mais il a atteint le stade "assez bon pour poster".

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

L'idée est de stocker les fréquences de toutes les exécutions de 2, 3, 4, ..., 10 caractères. Pour chacune de ces longueurs L, nous vérifions si les derniers caractères L-1 correspondent à un modèle enregistré; si tel est le cas, notre hypothèse g _L est le caractère suivant le plus fréquent suivant ce modèle. Nous recueillons jusqu'à neuf suppositions de cette façon. Pour décider quelle hypothèse utiliser, nous pondérons la fréquence de chaque motif par sa longueur jusqu'à la 8ème puissance. La supposition avec la plus grande somme de fréquences pondérées est choisie. Si aucun motif ne correspond, nous devinons l'espace.

(La longueur maximale du motif et l'exposant de pondération ont été choisis par essais pour donner le moins de suppositions incorrectes.)

Voici ma version de travail en cours non golfée:

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

Et le harnais de test:

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

Voici un exemple de sortie du début du texte. Déjà nous commençons à voir la possibilité de terminer mots après avoir vu leur première lettre ( in, to, and, by, aussi, apparemment, 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 

Vers la fin, il y a encore beaucoup d'erreurs, mais aussi de très bonnes séquences ( shmage seashawkspar exemple).

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

Il est intéressant de regarder certaines des erreurs et de deviner le mot "attendu" de l'algorithme. Par exemple, après sail, le programme prédit les deux fois o- pour sailor, je présume. Ou encore, après , aavoir nattendu - peut-être à cause de la fréquence courante de , and.

Changelog:

• 274 * 2 + 526092 = 526640 Golfé l'algorithme, au prix de quelques erreurs supplémentaires
• 306 * 2 + 526089 = 526701 Version originale

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

Recherches pour les mots qui correspondent aux caractères précédents dans une liste de  tous  les mots les plus utilisés dans le texte, triés par le nombre de leurs occurrences.

Code:

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"

Données: https://www.dropbox.com/s/etmzi6i26lso8xj/d?dl=0

Suite de tests:

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

Edit: Utiliser whale2.txtdonne un meilleur score.

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

Encore une autre soumission préfixe-fréquence. Courez dessus whale2.txtet obtenez un score similaire (légèrement pire) que les autres.

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

Celui-ci trouve avidement la plus longue chaîne qui commence par un suffixe de l'historique, et s'il y a plusieurs candidats, tie-break avec des chaînes plus courtes.

Par exemple: Si les 7 derniers caractères sont abcdefgh, et la chaîne abcdefghiet abcdefghjapparaît avec la plus grande fréquence dans toutes les chaînes de la forme abcdefgh*, la sortie sera soit iou j, tie - break avec des suffixes plus courtes ( bcdefgh, cdefgh, ...).

Pour des raisons inconnues, rien de plus de 7 et mon ordinateur n'a pas assez de RAM pour l'exécuter. Même avec 7, je dois fermer tous les navigateurs Web pour l'exécuter.

Code de test:

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