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