Oto plik tekstowy ASCII o wielkości 1,2 MB zawierający tekst Moby-Dicka Hermana Melville'a ; lub Wieloryb . Twoim zadaniem jest napisanie programu lub funkcji (lub klasy itp. - patrz poniżej), które otrzymają ten plik po jednym znaku na raz, i na każdym kroku należy odgadnąć następny znak.

To jest wyzwanie kodowe . Twój wynik będzie

2*L + E

gdzie Ljest rozmiar twojego przesłania w bajtach, i Eliczba znaków, które odgaduje niepoprawnie. Najniższy wynik wygrywa.

Dalsze szczegóły

Twoje zgłoszenie będzie programem lub funkcją (itp.), Które będą wielokrotnie wywoływane, wywoływane lub wysyłane. (1215235 razy, aby być dokładne). Kiedy to się nazywa po n ^th czasie będzie mieć n ^th charakteru whale.txtlub whale2.txti to musi zgadywać jego wyjście dla ( n + 1 ) ^th charakteru. ESkładnikiem jego wynik będzie łączna liczba znaków, że domyśla się nieprawidłowo.

Większość zgłoszeń będzie musiała przechowywać pewien stan pomiędzy wywołaniami, aby mogli śledzić, ile razy zostały wywołane i jakie były poprzednie dane wejściowe. Możesz to zrobić, pisząc do zewnętrznego pliku, używając staticzmiennych globalnych, podając klasę zamiast funkcji, używając monady stanu lub cokolwiek innego, co działa w twoim języku. Twoje zgłoszenie musi zawierać dowolny kod wymagany do zainicjowania jego stanu przed pierwszym wywołaniem.

Twój program powinien działać deterministycznie, aby zawsze tworzył te same domysły przy tych samych danych wejściowych (a zatem zawsze otrzymuje ten sam wynik).

Twoja odpowiedź musi zawierać nie tylko przesłanie, ale także kod użyty do obliczenia Eczęści wyniku. Nie musi to być napisane w tym samym języku co przesłanie i nie będzie wliczane do liczby bajtów. Zachęcamy do uczynienia go czytelnym.

Jeśli chodzi o interfejs między twoim zgłoszeniem a programem do obliczania wyników, wszystko jest w porządku, o ile twój program zawsze podaje jeden bajt danych wyjściowych przed otrzymaniem kolejnego bajtu danych wejściowych. (Na przykład nie można po prostu przekazać ciągu zawierającego wszystkie dane wejściowe i uzyskać ciąg zawierający wszystkie dane wyjściowe).

Musisz faktycznie uruchomić swój program testowy i obliczyć / zweryfikować swój wynik przed przesłaniem zgłoszenia. Jeśli twoje zgłoszenie przebiega zbyt wolno, abyś mógł zweryfikować swój wynik, nie kwalifikuje się do konkurowania, nawet jeśli wiesz, jaki byłby jego wynik.

LSkładnikiem swój wynik zostanie obliczona zgodnie ze zwykłymi zasadami wyzwań kod golfowych. Jeśli Twoje zgłoszenie będzie zawierać wiele plików, zwróć uwagę na zasady dotyczące oceniania i struktury katalogów w tym przypadku. Wszelkie dane używane przez kod muszą być uwzględnione w Lwyniku.

Możesz importować istniejące biblioteki, ale nie możesz ładować żadnych innych plików zewnętrznych, a twój kod może nie mieć dostępu do whale.txtlubwhale2.txtplik w jakikolwiek inny sposób niż opisano powyżej. Nie możesz ładować żadnych przeszkolonych sieci neuronowych ani innych źródeł danych statystycznych. (Korzystanie z sieci neuronowych jest w porządku, ale musisz dołączyć dane o wadze do swojego zgłoszenia i policzyć je do liczby bajtów.) Jeśli z jakiegoś powodu twój język lub biblioteki zawierają funkcję, która udostępnia część lub całość tekstu Moby Dick , nie możesz korzystać z tej funkcji. Oprócz tego możesz używać dowolnych innych wbudowanych lub bibliotekowych funkcji, w tym związanych z przetwarzaniem tekstu, prognozowaniem lub kompresją, o ile są one częścią twojego języka lub jego standardowych bibliotek. W przypadku bardziej egzotycznych, specjalistycznych procedur, które zawierają źródła danych statystycznych, należy je zaimplementować samodzielnie i uwzględnić w liczbie bajtów.

Prawdopodobnie niektóre zgłoszenia będą zawierać komponenty, które same są generowane przez kod. W takim przypadku prosimy o dołączenie do odpowiedzi kodu użytego do ich wytworzenia i wyjaśnienie, jak to działa . (Tak długo, jak ten kod nie jest potrzebny do uruchomienia przesyłania, nie będzie uwzględniony w liczbie bajtów).

Ze względów historycznych istnieją dwie wersje pliku i możesz użyć jednej z nich w odpowiedzi. W whale2.txt(połączony powyżej) tekst nie jest zawijany, więc znaki nowej linii pojawiają się tylko na końcu akapitów. W oryginale whale.txttekst jest zawinięty do szerokości 74 znaków, więc musisz przewidzieć koniec każdej linii, a także przewidzieć tekst. To sprawia, że ​​wyzwanie jest bardziej skomplikowane, dlatego whale2.txtjest zalecane w przypadku nowych odpowiedzi. Oba pliki mają ten sam rozmiar, 1215236 bajtów.

Podsumowując, wszystkie odpowiedzi powinny zawierać następujące rzeczy:

• Twoje samo zgłoszenie. (Kod oraz wszelkie używane przez niego pliki danych - mogą być linkami, jeśli są duże).
• Wyjaśnienie, jak działa Twój kod. Proszę wyjaśnić metodę we / wy, a także sposób przewidywania następnego znaku. Wyjaśnienie twojego algorytmu jest ważne, a dobre wyjaśnienia przyniosą ode mnie nagrody.
• Kod użyty do oceny wyniku. (Jeśli jest to identyczna z poprzednią odpowiedzią, możesz po prostu link do niej.)
• Każdy kod użyty do wygenerowania zgłoszenia wraz z objaśnieniem tego kodu. Obejmuje to kod użyty do optymalizacji parametrów, generowania plików danych itp. (Nie wlicza się to do liczby bajtów, ale powinno zostać uwzględnione w odpowiedzi).

Tabela liderów

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>

Nagrody

Od czasu do czasu oferuję nagrody, aby zachęcić do różnych podejść.

Pierwszy, 50 punktów, został przyznany A. Rexowi za najlepszą wówczas odpowiedź.

Druga, 100 punktów, została również przyznana A. Rexowi za tę samą odpowiedź, ponieważ dodali bardzo dobre wyjaśnienie do swojej istniejącej odpowiedzi.

Następna nagroda, 200 punktów , zostanie przyznana jednemu z nich

• Konkurencyjna odpowiedź wykorzystująca nową technikę. (Będzie to oparte na moim subiektywnym osądzie, ponieważ to mój przedstawiciel wchodzi na nagrodę, ale możesz mi zaufać, że jestem uczciwy. Pamiętaj, że twoja odpowiedź musi zawierać wystarczające wyjaśnienie, aby zrozumieć, jak to działa!) Takiej odpowiedzi potrzebowałem nie ma najwyższego wyniku, musi po prostu dobrze sobie poradzić w porównaniu z istniejącymi odpowiedziami. Szczególnie zależy mi na rozwiązaniach opartych na cyklicznych sieciach neuronowych, ale nagrodę przyznam za wszystko, co wydaje się wystarczająco inne niż modele Markowa, które dominują w obecnych najlepszych wynikach.

Lub:

• Każdy inny, kto bije najlepszy wynik A. Rexa (obecnie 444444), przy użyciu dowolnej metody.

Po odebraniu nagrody za 200 punktów najprawdopodobniej zaoferuję 400 punktów, odpowiednio aktualizując wymagania.

/// , 2 * 1 + 1020874 = 1020876

Drukuje spację.

Node.js, 2 * 224 + 524279 = 524727

Informacje na temat aktualizacji wyników można znaleźć w dzienniku zmian na końcu tego postu.

Funkcja pobierająca i zwracająca bajt.

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

Składa się z prostego modelu PPM, który patrzy na ostatnie 8 znaków, aby przewidzieć następny.

Ufamy wzorowi długości L, gdy napotkaliśmy go co najmniej T [L] razy, gdzie T jest tablicą dowolnych progów: [1,1,2,1,2,3,5,2] . Ponadto zawsze ufamy wzorowi, którego pierwsza postać pasuje [A-Z '"(].

Wybieramy najdłuższy zaufany wzór i zwracamy prognozę z najwyższym wynikiem związanym z tym wzorem w momencie połączenia.

Notatki

• To oczywiście nie jest zoptymalizowane pod kątem prędkości, ale działa na około 15 sekundach na moim laptopie.

• Gdybyśmy mogli powtórzyć proces kilka razy z rzędu bez resetowania modelu, liczba błędów zbiegnie się do ~ 268000 po 5 iteracjach.

• Aktualny wskaźnik skuteczności funkcji prognozowania wynosi ~ 56,8%. Jak zauważył @immibis w komentarzach, jeśli błędne i prawidłowe domysły zostaną zmieszane razem, wynik nie będzie nawet ledwo czytelny.

  Na przykład ten fragment kodu na końcu książki:

  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.
  

  staje się:

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

  Zastępując błędne domysły znakami podkreślenia, mamy lepsze pojęcie o tym, co funkcja zadziałała:

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

  _{Uwaga : powyższy przykład został utworzony przy użyciu poprzedniej wersji kodu, działającej na pierwszej wersji pliku wejściowego.}

Kod testowy

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

Zmień dziennik

• 524727 - zapisano 19644 punktów, przechodząc na whale2.txt (aktualizacja wyzwania)
• 544371 - zaoszczędzono 327 punktów, zmuszając wzorce zaczynające się od dużej litery, cytatu, podwójnego cytatu lub nawiasu otwierającego, aby zawsze być zaufanym
• 544698 - zapisano 2119 punktów, zmuszając wzorce rozpoczynające się od miejsca, któremu zawsze można zaufać
• 546817 - zaoszczędzono 47 punktów, dostosowując progi i grając w funkcję przewidywania
• 546864 - zapisano 1496 punktów poprzez zwiększenie maksymalnej długości wzoru do 8 znaków
• 548360 - zapisano 6239 punktów, wprowadzając pojęcie zaufanych wzorów, z progami zależnymi od ich długości
• 554599 - zaoszczędzono 1030 punktów, poprawiając przewidywanie przesunięcia linii
• 555629 - zaoszczędzono 22 punkty, grając w golfa w funkcji przewidywania
• 555651 - zapisano 40 punktów, grając w golfa w funkcji przewidywania
• 555691 - wynik początkowy

Perl, 2 · 70525 + 326508 = 467558

Urządzenie prognozujące

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

Aby uruchomić ten program, potrzebujesz tego pliku tutaj , który musi mieć nazwę B. (Możesz zmienić tę nazwę pliku w drugim wystąpieniu Bpowyższego znaku .) Zobacz poniżej, jak wygenerować ten plik.

Program wykorzystuje kombinację modeli Markowa zasadniczo jak w tej odpowiedzi użytkownika 2699 , ale z kilkoma niewielkimi modyfikacjami. To tworzy rozkład dla następnej postaci. Korzystamy z teorii informacji, aby zdecydować, czy zaakceptować błąd, czy wydać fragmenty pamięci na Bkodowanie wskazówek (a jeśli tak, to w jaki sposób). Używamy kodowania arytmetycznego do optymalnego przechowywania ułamkowych bitów z modelu.

Program ma długość 582 bajtów (w tym niepotrzebną końcową Bnową linię ), a plik binarny ma długość 69942 bajtów, więc zgodnie z regułami oceniania wielu plików oceniamy Ljako 582 + 69942 + 1 = 70525.

Program prawie na pewno wymaga architektury 64-bitowej (little-endian?). Uruchomienie m5.largeinstancji na Amazon EC2 zajmuje około 2,5 minuty .

Kod testowy

# 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

Wiązka testowa zakłada, że ​​przesłanie znajduje się w pliku submission.pl, ale można to łatwo zmienić w drugim wierszu.

Porównanie tekstu

"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

Ta próbka (wybrana w innej odpowiedzi ) pojawia się dość późno w tekście, więc model jest dość rozwinięty do tego momentu. Pamiętaj, że model jest powiększony o 70 kilobajtów „podpowiedzi”, które bezpośrednio pomagają odgadnąć postacie; nie jest napędzany po prostu krótkim fragmentem kodu powyżej.

Generowanie wskazówek

Poniższy program akceptuje dokładny kod przesłania powyżej (na standardowym wejściu) i generuje dokładny Bplik powyżej (na standardowym wyjściu):

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

Uruchomienie zajmuje około tyle samo czasu co przesłanie, ponieważ wykonuje podobne obliczenia.

Wyjaśnienie

W tej sekcji postaramy się opisać wystarczająco szczegółowo to rozwiązanie, abyś mógł sam „wypróbować go w domu”. Główną techniką, która odróżnia tę odpowiedź od innych, jest kilka sekcji w dół jako mechanizm „przewijania”, ale zanim do tego dojdziemy, musimy skonfigurować podstawy.

Model

Podstawowym składnikiem rozwiązania jest model językowy. Dla naszych celów model jest czymś, co wymaga pewnej ilości tekstu w języku angielskim i zwraca rozkład prawdopodobieństwa dla następnego znaku. Gdy użyjemy modelu, tekst w języku angielskim będzie jakimś (poprawnym) prefiksem Moby Dicka. Należy pamiętać, że pożądanym wyjściem jest rozkład , a nie tylko jedno odgadnięcie najbardziej prawdopodobnej postaci.

W naszym przypadku zasadniczo używamy modelu w tej odpowiedzi użytkownika 2699 . Nie wykorzystaliśmy modelu z odpowiedzi o najwyższym wyniku (innej niż nasza) Andersa Kaseorga właśnie dlatego, że nie byliśmy w stanie wyodrębnić dystrybucji, a nie pojedynczego najlepszego przypuszczenia. Teoretycznie ta odpowiedź oblicza ważoną średnią geometryczną, ale otrzymaliśmy nieco słabe wyniki, gdy interpretowaliśmy to zbyt dosłownie. „Ukradliśmy” model z innej odpowiedzi, ponieważ nasz „sekretny sos” nie jest modelem, ale raczej ogólnym podejściem. Jeśli ktoś ma „lepszy” model, powinien być w stanie uzyskać lepsze wyniki przy użyciu pozostałych naszych technik.

Jako uwaga, większość metod kompresji, takich jak Lempel-Ziv, może być postrzegana jako „model językowy” w ten sposób, choć może trzeba trochę zmrużyć oczy. (Jest to szczególnie trudne w przypadku czegoś, co powoduje transformację Burrowsa-Wheelera!) Ponadto zauważ, że model użytkownika 2699 jest modyfikacją modelu Markowa; zasadniczo nic innego nie jest konkurencyjne w stosunku do tego wyzwania, a może nawet do modelowania tekstu w ogóle.

Ogólna architektura

Dla zrozumienia dobrze jest podzielić ogólną architekturę na kilka części. Z perspektywy najwyższego poziomu musi być trochę kodu zarządzania stanem. Nie jest to szczególnie interesujące, ale dla kompletności chcemy podkreślić, że w każdym momencie program jest proszony o kolejne przypuszczenia, ma dostępny poprawny prefiks Moby Dick. W żaden sposób nie wykorzystujemy naszych niepoprawnych domysłów. Ze względu na wydajność, model językowy może prawdopodobnie ponownie użyć swojego stanu z pierwszych N znaków do obliczenia swojego stanu dla pierwszych (N + 1) znaków, ale w zasadzie może za każdym razem przywoływać obliczenia od zera.

Odłóżmy ten podstawowy „sterownik” programu na bok i zajrzyjmy do części odgadującej następny znak. Pomaga koncepcyjnie oddzielić trzy części: model języka (omówiony powyżej), plik „podpowiedzi” i „tłumacza”. Na każdym kroku tłumacz zapyta model językowy o rozkład dla następnego znaku i może odczytać pewne informacje z pliku wskazówek. Następnie połączy te części w zgadywanie. Dokładnie, jakie informacje znajdują się w pliku wskazówek, a także jak są wykorzystywane zostaną wyjaśnione później, ale na razie pomaga zachować te części osobno. Zauważ, że pod względem implementacji plik wskazówek jest dosłownie osobnym (binarnym) plikiem, ale mógł być łańcuchem lub czymś przechowywanym w programie. W przybliżeniu

Jeśli ktoś używa standardowej metody kompresji, takiej jak bzip2, jak w tej odpowiedzi , plik „podpowiedzi” odpowiada skompresowanemu plikowi. „Tłumacz” odpowiada dekompresorowi, podczas gdy „model językowy” jest nieco niejawny (jak wspomniano powyżej).

Dlaczego warto korzystać z pliku podpowiedzi?

Wybierzmy prosty przykład do dalszej analizy. Załóżmy, że tekst to Nznaki długie i dobrze przybliżone przez model, w którym każdy znak jest (niezależnie) literą Ez prawdopodobieństwem nieco mniejszym niż połowa, Tpodobnie z prawdopodobieństwem nieco mniejszym niż połowa, i Az prawdopodobieństwem 1/1000 = 0,1%. Załóżmy, że żadne inne postacie nie są możliwe; w każdym razie Ajest bardzo podobny do przypadku wcześniej niewidzianej postaci nieoczekiwanej.

Jeśli działaliśmy w trybie L 0 (jak większość, ale nie wszystkie, inne odpowiedzi na to pytanie), nie ma lepszej strategii dla tłumacza niż wybranie jednego z Ei T. Średnio uzyska około połowy poprawnych znaków. Więc E ≈ N / 2 i wynik ≈ N / 2 również. Jeśli jednak zastosujemy strategię kompresji, możemy skompresować ją do nieco więcej niż jednego bitu na znak. Ponieważ L jest liczone w bajtach, otrzymujemy L ≈ N / 8 i tym samym osiągamy ≈ N / 4, dwa razy więcej niż poprzednia strategia.

Osiągnięcie tej szybkości nieco więcej niż jednego bitu na znak dla tego modelu jest nieco nietrywialne, ale jedną z metod jest kodowanie arytmetyczne.

Kodowanie arytmetyczne

Jak powszechnie wiadomo, kodowanie jest sposobem reprezentowania niektórych danych przy użyciu bitów / bajtów. Na przykład ASCII to 7-bitowe kodowanie znaków w tekście angielskim i powiązanych znakach, a także kodowanie oryginalnego rozważanego pliku Moby Dick. Jeśli niektóre litery są bardziej powszechne niż inne, wówczas kodowanie o stałej szerokości, takie jak ASCII, nie jest optymalne. W takiej sytuacji wiele osób sięga po kodowanie Huffmana . Jest to optymalne, jeśli chcesz mieć stały (bez prefiksów) kod z liczbą całkowitą bitów na znak.

Jednak kodowanie arytmetyczne jest jeszcze lepsze. Z grubsza mówiąc, jest w stanie używać „ułamkowych” bitów do kodowania informacji. Istnieje wiele przewodników po kodowaniu arytmetycznym dostępnych online. Pominiemy tutaj szczegóły (szczególnie praktyczne wdrożenie, które może być nieco trudne z punktu widzenia programowania) ze względu na inne zasoby dostępne online, ale jeśli ktoś narzeka, może ten rozdział można rozwinąć bardziej.

Jeśli tekst jest generowany przez znany model językowy, wówczas kodowanie arytmetyczne zapewnia zasadniczo optymalne kodowanie tekstu z tego modelu. W pewnym sensie „rozwiązuje” to problem kompresji tego modelu. (Tak więc w praktyce głównym problemem jest to, że model nie jest znany, a niektóre modele są lepsze niż inne w modelowaniu tekstu ludzkiego.) Jeśli nie dopuszczono się błędów w tym konkursie, to w języku poprzedniej sekcji , jednym ze sposobów na rozwiązanie tego problemu byłoby użycie kodera arytmetycznego do wygenerowania pliku „wskazówek” z modelu językowego, a następnie użycie dekodera arytmetycznego jako „interpretera”.

W tym zasadniczo optymalnym kodowaniu ostatecznie wydajemy -log_2 (p) bitów na znak o prawdopodobieństwie p, a ogólną przepływnością kodowania jest entropia Shannona . Oznacza to, że znak o prawdopodobieństwie bliskim 1/2 zajmuje około jednego bitu do zakodowania, a znak o prawdopodobieństwie 1/1000 zajmuje około 10 bitów (ponieważ 2 ^ 10 to w przybliżeniu 1000).

Ale wskaźnik punktacji dla tego wyzwania został dobrze wybrany, aby uniknąć kompresji jako optymalnej strategii. Będziemy musieli wymyślić jakiś sposób na popełnienie błędów jako kompromis w uzyskaniu krótszego pliku wskazówek. Na przykład jedna strategia, którą można wypróbować, jest prostą strategią rozgałęziania: na ogół staramy się stosować kodowanie arytmetyczne, kiedy tylko możemy, ale jeśli rozkład prawdopodobieństwa z modelu jest „zły”, to po prostu odgadujemy najbardziej prawdopodobną postać i nie „ spróbuj go zakodować.

Po co popełniać błędy?

Przeanalizujmy wcześniejszy przykład, aby uzasadnić, dlaczego możemy chcieć popełniać błędy „umyślnie”. Jeśli użyjemy kodowania arytmetycznego do zakodowania poprawnego znaku, wydamy około jednego bitu w przypadku Elub T, ale około dziesięciu bitów w przypadku A.

Ogólnie rzecz biorąc, jest to całkiem dobre kodowanie, wydające nieco ponad nieco na postać, mimo że istnieją trzy możliwości; w zasadzie Ajest to raczej mało prawdopodobne i nie spędzamy zbyt często odpowiadających mu dziesięciu bitów. Czy jednak nie byłoby miło, gdybyśmy mogli zamiast tego popełnić błąd w przypadku A? W końcu metryka problemu uważa, że ​​1 bajt = 8 bitów długości jest równoważny 2 błędom; dlatego wydaje się, że należy preferować błąd zamiast wydawać więcej niż 8/2 = 4 bity na znak. Wydanie więcej niż bajtu, aby zapisać jeden błąd, zdecydowanie brzmi nieoptymalnie!

Mechanizm „przewijania do tyłu”

W tej sekcji opisano główny sprytny aspekt tego rozwiązania, który jest sposobem obsługi niepoprawnych domysłów bez żadnych kosztów.

W tym prostym przykładzie, który analizowaliśmy, mechanizm przewijania jest szczególnie prosty. Tłumacz interpretuje jeden bit z pliku wskazówek. Jeśli jest to 0, zgaduje E. Jeśli jest to 1, zgaduje T. Przy następnym wywołaniu zobaczy, jaki jest prawidłowy znak. Jeśli plik podpowiedzi jest dobrze skonfigurowany, możemy zapewnić, że w przypadku Elub Tinterpreter zgadnie poprawnie. Ale co z tym A? Pomysł z mechanizmem zwijania jest po prostu nie kodować Aw ogóle . Mówiąc ściślej, jeśli interpreter dowie się później, że poprawny znak był A, metaforycznie „ przewija taśmę”: zwraca fragment, który wcześniej przeczytał. Bit, który odczytuje, ma zamiar kodować ElubT, ale nie teraz; zostanie wykorzystany później. W tym prostym przykładzie, w zasadzie oznacza to, że utrzymuje zgadywania ten sam znak ( Elub T), aż robi się to dobrze; potem odczytuje kolejny kawałek i kontynuuje.

Kodowanie tego pliku wskazówek jest bardzo proste: zamień wszystkie Es na 0 bitów is Tna 1 bit, jednocześnie Acałkowicie ignorując s. Według analizy pod koniec poprzedniej sekcji, ten schemat popełnił pewne błędy, ale zmniejsza ogólny wynik, nie kodując żadnego z nich A. Jako mniejszy efekt, faktycznie oszczędza również na długości pliku wskazówek, ponieważ ostatecznie używamy dokładnie jednego bitu na każdy Ei Tzamiast nieco więcej niż nieco.

Trochę twierdzenia

Jak decydujemy, kiedy popełnić błąd? Załóżmy, że nasz model podaje rozkład prawdopodobieństwa P dla następnego znaku. Rozdzielimy możliwe znaki na dwie klasy: zakodowane i niekodowane . Jeśli prawidłowy znak nie zostanie zakodowany, wówczas skorzystamy z mechanizmu „przewijania”, aby zaakceptować błąd bez żadnych kosztów. Jeśli prawidłowy znak jest zakodowany, użyjemy innej dystrybucji Q do zakodowania go za pomocą kodowania arytmetycznego.

Ale jaki rozkład Q wybrać? Nietrudno dostrzec, że wszystkie zakodowane znaki powinny mieć większe prawdopodobieństwo (w P) niż znaki niekodowane. Także rozkład Q powinien zawierać tylko zakodowane znaki; w końcu nie kodujemy pozostałych, więc nie powinniśmy „wydawać” na nie entropii. Trochę trudniej jest dostrzec, że rozkład prawdopodobieństwa Q powinien być proporcjonalny do P na zakodowanych znakach. Zebranie tych obserwacji razem oznacza, że ​​powinniśmy kodować najbardziej prawdopodobne znaki, ale być może nie mniej prawdopodobne, i że Q jest po prostu przeskalowane P na znakach kodowanych.

Okazuje się ponadto, że istnieje fajne twierdzenie dotyczące tego, który „punkt odcięcia” należy wybrać dla znaków kodujących: należy zakodować znak, o ile jest on co najmniej 1 / 5.393 tak prawdopodobny, jak inne zakodowane znaki łącznie. To „wyjaśnia” pojawienie się pozornie losowej stałej 5.393bliżej końca powyższego programu. Liczba 1 / 5,393 × 0,18542 jest rozwiązaniem równania -p log (16) - p log p + (1 + p) log (1 + p) = 0 .

Być może rozsądnym pomysłem jest zapisanie tej procedury w kodzie. Ten fragment jest w 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;
}

Kładąc wszystko razem

Poprzednia sekcja jest niestety trochę techniczna, ale jeśli połączymy wszystkie pozostałe elementy razem, struktura będzie następująca. Ilekroć program jest proszony o przewidzenie następnego znaku po danym poprawnym znaku:

1. Dodaj poprawny znak do znanego poprawnego prefiksu Moby Dick.
2. Zaktualizuj model tekstu (Markowa).
3. Tajny sos : Jeśli poprzednie przypuszczenie było błędne, przewijanie stan dekodera arytmetycznego do stanu sprzed poprzedniego odgadnięcia!
4. Poproś model Markowa, aby przewidział rozkład prawdopodobieństwa P dla następnej postaci.
5. Przekształć P w Q, używając podprogramu z poprzedniej sekcji.
6. Poproś dekoder arytmetyczny, aby zdekodował znak z pozostałej części pliku wskazówek, zgodnie z rozkładem Q.
7. Zgadnij wynikową postać.

Kodowanie pliku wskazówek działa podobnie. W takim przypadku program wie, jaki jest poprawny następny znak. Jeśli jest to znak, który należy zakodować, to oczywiście należy użyć kodera arytmetycznego na nim; ale jeśli jest to niekodowany znak, po prostu nie aktualizuje stanu enkodera arytmetycznego.

Jeśli rozumiesz tło teoretyczne informacji, takie jak rozkłady prawdopodobieństwa, entropia, kompresja i kodowanie arytmetyczne, ale próbowałeś i nie zrozumiał tego postu (z wyjątkiem tego, dlaczego twierdzenie jest prawdziwe), daj nam znać, a my możemy spróbować wyjaśnić sytuację. Dziękuje za przeczytanie!

Python 3, 2 · 267 + 510193 = 510727

Urządzenie prognozujące

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]

Wykorzystuje ważoną kombinację bayesowską modeli 0,…, 16 modeli Markowa, z wagami [1, 6, 12, 30, 65, 99, 87, 117, 118, 89, 95, 118, 96, 184, 126, 219, 126].

Wynik nie jest bardzo wrażliwy na dobór tych wag, ale zoptymalizowałem je, ponieważ mogłem, stosując ten sam algorytm wspinaczki późnej akceptacji , który zastosowałem w odpowiedzi na „Ustaw większość senacką” , gdzie każda mutacja kandydująca jest zaledwie przyrost o ± 1 do pojedynczej masy.

Kod testowy

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

Wypróbuj online!

Funkcja wykorzystująca zmienne globalne. Uczy się, jak to się dzieje, budując model na poziomie słowa: biorąc pod uwagę to, co do tej pory widać w tym słowie , jaka jest najczęstsza następna postać? W miarę, jak pojawia się w nim więcej informacji, dość dobrze uczy się popularnych słów z tekstu, a także uczy najczęstszych znaków rozpoczynających następne słowo.

Na przykład:

• Jeśli do tej pory widziano „Captai”, przewiduje „n”
• Jeśli jest to „Kapitan”, przewiduje przestrzeń
• Jeśli jest to początek słowa, a ostatnim słowem było „Kapitan”, przewiduje „A”
• Jeśli dotychczasowe słowo to „A”, przewiduje „h” (a następnie „a” i „b”; podobnie dla „C”).

Na początku nie radzi sobie zbyt dobrze, ale pod koniec pojawiają się duże części prawdziwych słów. Opcją zastępczą jest spacja, a po pojedynczym spacji jest to „a”, chyba że poprzednia litera była jedną z „nedtfo”, cyfry, łącznika lub apostrofu. Agresywnie przewiduje także łamanie wiersza po 71 znakach lub spację po 66. Oba zostały właśnie dostrojone do danych („t” jest znacznie bardziej powszechne po spacji, ale częściej jest już przewidywane, więc „ „lepiej zgadnąć poza tymi sześcioma specjalnymi przypadkami”.

Uczenie się, jakie pary słów idą w parze i uprzedzanie mapowania, okazało się nie opłacalne.

Kończy się na nim taki tekst:

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!

co odpowiada tej części danych wejściowych:

wokół niego.

„Widziałem go niemal w tej samej chwili, co kapitan Ahab, i krzyknąłem” - powiedział Tashtego.

„Nie w tej samej chwili; nie w tym samym - nie, dublon jest mój, Los zarezerwował dla mnie dublon. Ja tylko; nikt z was nie mógł najpierw wychować Białego Wieloryba. Tam ona dmucha! - tam ona dmucha! - - tam ona wieje!

Widać, gdzie w szczególności właściwe rzeczowniki wychodzą całkiem nieźle, ale końcówki słów są również w większości właściwe. Kiedy zobaczysz „dou”, oczekuje „wątpliwości”, ale gdy pojawi się „l”, staje się „dublonem”.

Jeśli uruchomisz go po raz drugi z tym samym modelem, który właśnie zbudował, natychmiast uzyska kolejne 92k poprawności (51,7% -> 59,3%), ale zawsze jest nieco poniżej 60% od drugiej iteracji.

Kod pomiarowy znajduje się w łączu TIO lub oto nieco lepsza wersja:

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 ma zgadnięte wyjście na końcu.

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

Dzięki @Quentin za oszczędność 217 bajtów!

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

Bardzo proste rozwiązanie, które po podaniu znaku wypisuje znak, który najczęściej pojawia się po znaku wejściowym.

Sprawdź wynik za pomocą:

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

Edycja: Używanie whale2.txtdaje lepszy wynik.

Python, 2 * 516 + 521122 = 522154

Algorytm:

Jeszcze inne przesłanie pytona, ten algorytm oblicza najbardziej prawdopodobną następną literę, patrząc na sekwencje o długości 1, ..., l. Wykorzystywana jest suma prawdopodobieństw i istnieje kilka sztuczek, aby uzyskać lepsze wyniki.

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

Wyniki:

Przeważnie bełkot, choć można go zauważyć, od czasu do czasu pojawia się w zwrotach, takich jak „Ojciec 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

Kod testowy:

Całkiem proste, wyświetla kilka przykładów tekstu w różnych punktach. Używa pliku whale2.txt, ponieważ pozwala to uniknąć dodatkowej logiki obliczania nowych linii.

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 bajtów, 679619 652740 błędne domysły

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

Wypróbuj online!

Aktualizacja: ~ 27000 punktów zniżki przy zaktualizowanym pliku, 16 punktów (8 bajtów) z funkcją lepszej gry w golfa.

Wyjaśnienie

Działa to w ten sposób, że gdy kod przechodzi przez tekst, zapamiętuje ostatni znak, który zakończył dowolną 4-znakową sekwencję, i zwraca tę wartość. Nieco podobny do powyższego podejścia Arnaulda, ale opiera się na nieodłącznym prawdopodobieństwie dwóch danych sekwencji 4-znakowych kończących się w ten sam sposób.

Gra w golfa:

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

a następnie skompresowany przez bzip2 plik whale2.txt z brakującym pierwszym bajtem

Ignoruje swój wkład; wypisuje poprawną odpowiedź. Zapewnia to linię bazową na jednym końcu; daniero zapewnia linię bazową na drugim końcu.

Skrypt konstruktora:

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

Wiązka testowa we / wy (tcc; odetnij pierwszą linię dla gcc). Ta uprząż testowa może być używana przez każdego na odpowiedniej platformie, która przesyła pełny program, który oczekuje odczytu / zapisu We / Wy. Używa bajtów we / wy, aby uniknąć oszustwa. Program potomny musi opróżniać wyjście po każdym bajcie, aby uniknąć blokowania.

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

Wypróbuj online!

... The /// Odpowiedź, która wypisuje spację, otrzymuje 10 upvotes, podczas gdy mój kod może dostać tylko 3 ...

Wyjaśnienie:

Dla każdej postaci program:

• zwiększać frequency[prev][char]
• Znajdź postać, która pojawia się najczęściej frequency[char]
• i wyślij to.

• Skomentowano niepoznany kod w linku TIO.
• Kod ma 131 bajtów.
• Kod uruchamiany na moich komputerach zgłasza:

879504 / 1215235
Time: 62.01348257784468

które mają łączny wynik

2*131 + 879504 = 879766

Ponieważ nie ma możliwości przesłania dużego pliku do TIO (poza pytaniem Dennisa), przykładowe uruchomienie w łączu TIO uruchamia program tylko dla niewielkiej części tekstu.

W porównaniu ze starszą odpowiedzią ta zawiera 362 więcej niepoprawnych znaków, ale kod jest krótszy o 255 bajtów. Mnożnik sprawia, że ​​moje zgłoszenie ma niższy wynik.

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

Podejście to wykorzystuje tabelę przeglądową, aby poznać najczęstszy znak występujący po danym ciągu. Klawisze tabeli przeglądowej mają maksymalnie 4 znaki, więc funkcja najpierw aktualizuje tabelę przeglądową bieżącym znakiem, a następnie sprawdza, która postać jest najbardziej prawdopodobna po 4 poprzednich, w tym bieżącej . Jeśli te 4 znaki nie zostaną znalezione w tabeli przeglądowej, drukuje spację.

Ta wersja używa whale2.txt pliku, ponieważ znacznie poprawia liczbę udanych zgadnięć.

Oto kod użyty do przetestowania klasy:

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

Kod działa w zaledwie 2 sekundy. Dla przypomnienia, to właśnie otrzymuję, gdy modyfikuję rozmiar klawiszy tabeli przeglądowej (obejmuje wyniki drugiego uruchomienia bez resetowania modelu):

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

Interesujące byłoby wiedzieć, dlaczego kluczowy rozmiar 4 znaków jest najlepszym wyborem w tym algorytmie.

Porównanie tekstu

Oryginał:

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

Odtworzono:

"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 

Domysły:

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

Zmień dziennik

• 569279 - zmieniono whale2.txti tym samym usunięto optymalizację.
• 577366 - zoptymalizowany z kodem, który próbował zgadnąć, kiedy zwrócić wiersz.
• 590354 - wersja oryginalna.

Java 7, 1995 znaków, (1995 * 2 + 525158) 529148

Java jest do bani dla małych rozmiarów programów. W każdym razie wypróbowałem kilka niezwykle złożonych i podchwytliwych podejść, które przyniosły zaskakująco badziewne rezultaty. Potem wróciłem i po prostu zastosowałem proste podejście, które spowodowało mniejszy rozmiar programu i lepsze wyniki.

To podejście jest w rzeczywistości niezwykle proste. Ślepo podaje poprzednie znaki x (oprócz wszystkich podciągów tych znaków) do tablicy mieszającej, odwzorowanej na bieżący znak. Następnie śledzi, które wzory najdokładniej przewidują obecną postać. Jeśli wzorce poprzedzające określone znaki występują wielokrotnie, udaje im się przewidzieć postać. Daje pierwszeństwo dłuższym ciągom i daje pierwszeństwo każdemu znakowi, który najczęściej występuje po danym ciągu. Ten algorytm nie wie nic o rodzaju dokumentu ani języku angielskim.

Postanowiłem użyć 9 znaków i próbować dopasować całe słowa w tych poprzednich 9 znakach, jeśli to możliwe. Gdy nie próbujesz dopasowywać słów w łańcuchach, optymalna długość to 6 znaków, co powoduje kilka tysięcy nieporozumień.

Ciekawym spostrzeżeniem było to, że użycie 20 znaków spowodowało złe przewidywania za pierwszym razem, ale 99,9 procent dokładności przy kolejnych podaniach. Algorytm w zasadzie był w stanie zapamiętać książkę w nakładających się na siebie 20 bajtowych fragmentach, a było to na tyle wyraźne, że mogło przywołać całą książkę na raz.

• (1950 * 2 + 532919) 536819
• (2406 * 2 + 526233) 531045 sprawdzanie interpunkcji w celu lepszego odgadywania
• (1995 * 2 + 525158) 529148 więcej poprawek, grałem w golfa trochę gadatliwości

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

Próbowałem tego niezależnie, ale skończyło się na tym, że faktycznie jest to gorsza wersja odpowiedzi Michaela Homera. Mam nadzieję, że to nie czyni mojej odpowiedzi całkowicie nieaktualną.

Z czasem buduje się słownik słów (zdefiniowany jako ciągi znaków zakończone przez lub \n, z rozróżnianiem wielkości liter i włączając interpunkcję). Następnie przeszukuje ten słownik pod kątem słów zaczynających się od tego, co do tej pory wie o bieżącym słowie, sortuje wynikową listę według częstotliwości występowania (powoli) i zgaduje, że następny znak jest następnym znakiem w najczęściej pasującym słowie. Jeśli mamy już najczęściej pasujące słowo lub nie istnieje już pasujące słowo, zwraca ono .

Tworzy również obrzydliwie nieefektywny słownik par słów. Po osiągnięciu granicy słowa zgaduje, że następny znak jest pierwszą literą drugiego słowa w najczęściej pasującej parze słów lub tjeśli nie ma dopasowania. Nie jest to jednak zbyt mądre. Następnie Mobyprogram poprawnie zgaduje, że jest następny znak D, ale potem zapomina o kontekście i zwykle nazywa wieloryba „Kaczką Moby” (ponieważ słowo „holenderski” wydaje się częściej w pierwszej połowie tekstu ). Łatwo byłoby to naprawić, ustawiając pary słów na pojedyncze słowa, ale spodziewam się, że zysk byłby marginalny (ponieważ zwykle jest poprawny od trzeciego znaku, a pary słów nie są tak pomocne).

Mógłbym dostroić to, aby lepiej pasowało do dostarczonego tekstu, ale nie sądzę, aby ręczne dostrojenie algorytmu na podstawie wcześniejszej wiedzy na temat danych wejściowych było naprawdę w duchu gry, więc poza wybraniem t jako zastępczego znaku po spacji ( i prawdopodobnie też nie powinienem był tego robić), unikałem tego. Zignorowałem znaną długość linii pliku wejściowego i zamiast tego wstawiłem\n co każde 13 spacji - jest to prawie na pewno bardzo słabe dopasowanie, głównym celem było utrzymanie rozsądnej długości linii, a nie dopasowanie do danych wejściowych.

Kod nie jest dokładnie szybki (~ 2 godziny na mojej maszynie), ale ogólnie dostaje około połowy prawidłowych znaków (49%). Spodziewam się, że wynik byłby marginalnie lepszy, gdyby został uruchomiony whale2.txt, ale tego nie zrobiłem.

Początek danych wyjściowych wygląda następująco:

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

ale pod koniec wygląda trochę bardziej jak ... coś. Mój ulubiony fragment z końca książki

a ponieważ żadna z nich nie może być moja, pozwólcie mi następnie holować na kawałki, goniąc cię, choć przywiązany do ciebie, przeklęty wielorybie! TO oddaję włócznię! ”

wychodzi jako

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 "

To sprawiłoby, że Gniew Khana byłby znacznie bardziej zagmatwany. A „samotny” → „mrowienie” jest szczególnie satysfakcjonującym zamiennikiem.

Edycja: Zapisano jeden bajt, usuwając niepotrzebne miejsce

Punktacja

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

Spowoduje to uruchomienie programu dla tekstu Moby Dicka i wyprowadzenie „przewidywanego” tekstu na standardowe wyjście, i nadużywa stderr do napisania partytury. Polecam przekierowanie wyjścia do pliku.

C ++, 2 62829 + 318786 = 444444

Aby uruchomić ten program, potrzebujesz tego pliku tutaj , który musi mieć nazwę C.

Program wykorzystuje tę samą kombinację modeli Markowa, co w naszej wcześniejszej odpowiedzi . Tak jak poprzednio, ta kombinacja jest zasadniczo modelem z tej odpowiedzi użytkownika 2699 , ale z kilkoma małymi modyfikacjami.

Zważywszy na to, że ta odpowiedź wykorzystuje dokładnie ten sam model, co poprzednio, ulepszenie jest lepszym mechanizmem teoretycznym niż opisany wcześniej mechanizm „przewijania”. Pozwala to popełnić mniej błędów, a jednocześnie ma mniejszą łączną długość. Sam program nie jest bardzo golfowy, ponieważ nie jest głównym czynnikiem wpływającym na wynik.

Program ma długość 2167 bajtów (w tym wszystkie zakładki wcięcia i wiele innych niepotrzebnych znaków, ale przed kodem testowym), a plik binarny Cma długość 60661 bajtów, więc zgodnie z zasadami oceniania wielu plików oceniamy Ljako 2167 + 60661 + 1 = 62829.

Uruchomienie programu na m5.4xlargeinstancji w Amazon EC2 zajmuje około 8 minut i zużywa nieco ponad 16 GB pamięci. (To nadmierne zużycie pamięci nie jest konieczne - po prostu też tego nie zoptymalizowaliśmy).

#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 bajty, 526092 błędy (za pomocą whale2.txt). To z pewnością jest w stanie poprawić, ale osiągnął etap „wystarczająco dobry, aby opublikować”.

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

Chodzi o to, aby zapisać częstotliwości wszystkich przebiegów 2, 3, 4, ..., 10 znaków. Dla każdej z tych długości L sprawdzamy, czy najnowsze znaki L-1 pasują do zapisanego wzoru; jeśli tak, to zgadujemy, że _L jest najczęstszą kolejną postacią stosowaną według tego wzoru. W ten sposób zbieramy do dziewięciu domysłów. Aby zdecydować, której zgadnąć użyć, ważymy częstotliwość każdego wzoru według jego długości do 8. potęgi. Wybrano przypuszczenie o największej sumie ważonych częstotliwości. Jeśli nie ma pasujących wzorów, domyślamy się miejsca.

(Maksymalna długość wzoru i wykładnik ważenia zostały wybrane metodą prób i błędów, aby dać najmniej błędnych domysłów.)

Oto moja niezakończona wersja w toku:

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

I uprząż testowa:

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

Oto przykładowe dane wyjściowe z początku tekstu. Już zaczynamy dostrzegać możliwości, aby zakończyć wspólne słowa po obejrzeniu swój pierwszy list ( in, to, and, by, również, jak widać,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 

Pod koniec wciąż jest mnóstwo błędów, ale także mnóstwo bardzo dobrych sekwencji ( shmage seashawksna przykład).

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

Interesujące jest spojrzenie na niektóre błędy i odgadnięcie, jakiego słowa algorytm „oczekiwał”. Na przykład, gdy sailprogram oba razy przewiduje o--for sailor, jak sądzę. Lub ponownie, gdy , asię spodziewa - nprawdopodobnie z powodu powszechnego występowania, and .

Dziennik zmian:

• 274 * 2 + 526092 = 526640 Algorytm poddał golfowi kosztem kilku dodatkowych błędów
• 306 * 2 + 526089 = 526701 Wersja oryginalna

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

Wyszukuje słowa pasujące do poprzednich znaków z listy  wszystkich  większości słów użytych w tekście, posortowanych według liczby ich wystąpienia.

Kod:

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"

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

Zestaw testowy:

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

Edycja: Używanie whale2.txtdaje lepszy wynik.

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

Jeszcze jedno przedłożenie częstotliwości. Uruchom whale2.txti uzyskaj podobny (nieco gorszy) wynik niż inni.

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

Ten łapczywie odnajduje najdłuższy ciąg, który zaczyna się od sufiksu historii, a jeśli jest wielu kandydatów, rozstaje się z krótszymi ciągami.

Na przykład: jeśli ostatnie 7 znaków to abcdefgh, a ciąg abcdefghii abcdefghjpojawia się z największą częstotliwością we wszystkich ciągach formularza abcdefgh*, wynikiem będzie albo, ialbo jtiebreak z krótszymi przyrostkami ( bcdefgh,cdefgh , ...).

Z nieznanych przyczyn cokolwiek więcej niż 7, a mój komputer nie ma wystarczającej ilości pamięci RAM, aby go uruchomić. Nawet w przypadku wersji 7 muszę zamknąć wszystkie przeglądarki internetowe, aby go uruchomić.

Kod testowy:

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

Nie golfowany:

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