[Question]
  [
[Here is a 1.2Mb ASCII text file](https://gist.githubusercontent.com/nathanielvirgo/73b4181917f83c0cd306bd0d8f4c998a/raw/208774322bad4e04715eae743d7d350b504fe5eb/whale2.txt) containing the text of Herman Melville's *Moby-Dick; or, The Whale*. Your task is to write a program or function (or class, etc. -- see below) which will be given this file one character at a time, and at each step must guess the next character.
This is [code-challenge](/questions/tagged/code-challenge "show questions tagged 'code-challenge'"). Your score will be
```
2*L + E
```
where `L` is the size of your submission in bytes, and `E` is the number of characters it guesses incorrectly. The lowest score wins.
**Further particulars**
Your submission will be a program or function (etc.) that will be called or invoked or sent data multiple times. (1215235 times to be exact.) When it is called for the *n*th time it will be given the *n*th character of `whale.txt` or `whale2.txt` and it must output its guess for the (*n+1*)th character. The `E` component of its score will be the total number of characters that it guesses incorrectly.
Most submissions will need to store some state in between invocations, so that they can track how many times they have been called and what the previous inputs were. You can do this by writing to an external file, by using `static` or global variables, by submitting a class rather than a function, using a state monad, or whatever else works for your language. Your submission must include any code required to initialise its state before the first invocation.
Your program should run deterministically, so that it always makes the same guesses given the same input (and hence always gets the same score).
Your answer must include not only your submission, but also the code you used to calculate the `E` part of its score. This need not be written in the same language as your submission, and will not be counted towards its byte count. You are encouraged to make it readable.
Regarding the interface between your submission and this score-calculating program, anything is fine, as long as your program always gives one byte of output before receiving its next byte of input. (So, for example, you can't just pass it a string containing all of the input and get a string back containing all of the output.)
You must actually run your test program and calculate/verify your score before submitting your entry. If your submission runs too slowly for you to verify its score then it is not qualified to compete, even if you know what its score would be in principle.
The `L` component of your score will be calculated according to the usual rules for code golf challenges. If your submission will contain multiple files, please take note of the rules on [scoring](https://codegolf.meta.stackexchange.com/a/4934/21034) and [directory structure](https://codegolf.meta.stackexchange.com/a/12821/21034) in that case. Any data that your code uses must be included in your `L` score.
You may import existing libraries but may not load any other external files, and your code may not access the `whale.txt` or `whale2.txt` file in any way other than described above. You may not load any pre-trained neural networks or other sources of statistical data. (It's fine to use neural networks, but you have to include the weight data in your submission and count it towards your byte count.) If for some reason your language or libraries include a feature that provides some or all of the text of Moby Dick, you may not use that feature. Aside from that you can use any other built-in or library features that you like, including ones relating to text processing, prediction or compression, as long as they're part of your language or its standard libraries. For more exotic, specialised routines that include sources of statistical data, you would have to implement them yourself and include them in your byte count.
It is likely that some submissions will include components that are themselves generated by code. If this is the case, **please include in your answer the code that was used to produce them, and explain how it works**. (As long as this code is not needed to run your submission it will not be included in your byte count.)
For historical reasons, there are two versions of the file, and you may use either of them in an answer. In [`whale2.txt`](https://gist.githubusercontent.com/nathanielvirgo/73b4181917f83c0cd306bd0d8f4c998a/raw/208774322bad4e04715eae743d7d350b504fe5eb/whale2.txt) (linked above) the text is not wrapped, so newlines appear only at the end of paragraphs. In the original [`whale.txt`](https://gist.githubusercontent.com/nathanielvirgo/5cdbb0504f473830074268a9d65e8b39/raw/3d1bdd13d10da999d3b3ca95fd134548ef8e4e67/whale.txt) the text is wrapped to a width of 74 characters, so you have to predict the end of each line as well as predicting the text. This makes the challenge more fiddly, so `whale2.txt` is recommended for new answers. Both files are the same size, 1215236 bytes.
---
To summarise, all answers should include the following things:
* Your submission itself. (The code, plus any data files it uses - these can be links if they're large.)
* **An explanation of how your code works.** Please explain the I/O method as well as how it predicts the next character. The explanation of your algorithm is important, and good explanations will earn bounties from me.
* The code you used to evaluate your score. (If this is identical to a previous answer you can just link to it.)
* Any code you used to generate your submission, **along with an explanation of that code.** This includes code that you used to optimise parameters, generate data files etc. (This doesn't count towards your byte count but should be included in your answer.)
# Leaderboard
```
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>
```
# Bounties
From time to time I'll offer bounties to encourage different approaches.
The first one, 50 points, was awarded to A. Rex for the best-scoring answer at the time.
The second, 100 points, was also awarded to A. Rex, for the same answer, because they added a very good explanation to their existing answer.
The next bounty, **200 points**, will be awarded to either
* A competitive answer that uses a new technique. (This will be based on my subjective judgment since it's my rep that goes into the bounty, but you can trust me to be fair. Note that your answer needs to contain sufficient explanation for me to understand how it works!) Such an answer needn't take the top score, it just needs to do reasonably well compared to existing answers. I'm particularly keen to see solutions based on recurrent neural networks, but I'll award the bounty to anything that seems different enough from the Markov models that dominate the current top scores.
Or:
* Anyone else who beats A. Rex's top score (currently 444444), using any method.
Once the 200 point bounty is claimed I will most likely offer a 400 point one, updating the requirements accordingly.
  
[Answer]
# [///](http://esolangs.org/wiki////), 2\*1 + 1020874 = 1020876
```
 
```
Prints a space.
[Answer]
# Perl, 2·70525 + 326508 = 467558
## Predictor
```
$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}
```
To run this program, you need [this file here](https://www.dropbox.com/s/0tuq5loupk95cdj/B), which must be named `B`. (You can change this filename in the *second* instance of the character `B` above.) See below for how to generate this file.
The program uses a combination of Markov models essentially as in [this answer by user2699](https://codegolf.stackexchange.com/a/153050/49643), but with a few small modifications. This produces a *distribution* for the next character. We use information theory to decide whether to accept an error or spend bits of storage in `B` encoding hints (and if so, how). We use [arithmetic coding](https://en.wikipedia.org/wiki/Arithmetic_coding) to optimally store fractional bits from the model.
The program is 582 bytes long (including an unnecessary final newline) and the binary file `B` is 69942 bytes long, so [under the rules for scoring multiple files](https://codegolf.meta.stackexchange.com/questions/4933/counting-bytes-for-multi-file-programs/4934#4934), we score `L` as 582 + 69942 + 1 = 70525.
The program almost certainly requires a 64-bit (little-endian?) architecture. It takes approximately 2.5 minutes to run on an `m5.large` instance on Amazon EC2.
## Test code
```
# 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
```
The test harness assumes the submission is in the file `submission.pl`, but this can easily be changed in the second line.
## Text comparison
```
"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
```
This sample (chosen in [another answer](https://codegolf.stackexchange.com/a/152958/49643)) occurs rather late in the text, so the model is quite developed by this point. Remember that the model is augmented by 70 kilobytes of "hints" that directly help it guess the characters; it is not driven simply by the short snippet of code above.
## Generating hints
The following program accepts the exact submission code above (on standard input) and generates the exact `B` file above (on standard output):
```
@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],'}}'
```
It takes approximately as long to run as the submission, as it performs similar computations.
## Explanation
In this section, we will attempt to describe what this solution does in sufficient detail that you could "try it at home" yourself. The main technique that differentiates this answer from the other ones is a few sections down as the "rewind" mechanism, but before we get there, we need to set up the basics.
### Model
The basic ingredient of the solution is a language model. For our purposes, a *model* is something that takes some amount of English text and returns a *probability distribution* on the next character. When we use the model, the English text will be some (correct) prefix of Moby Dick. Please note that the desired output is a *distribution*, and not just a single guess for the most likely character.
In our case, we essentially use the model in [this answer by user2699](https://codegolf.stackexchange.com/a/153050/49643). We didn't use the model from the highest-scoring answer (other than our own) [by Anders Kaseorg](https://codegolf.stackexchange.com/a/152968/49643) precisely because we were unable to extract a distribution rather than a single best guess. In theory, that answer computes a weighted geometric mean, but we got somewhat poor results when we interpreted that too literally. We "stole" a model from another answer because our "secret sauce" isn't the model but rather the overall approach. If someone has a "better" model, then they should be able to get better results using the rest of our techniques.
As a remark, most compression methods such as Lempel-Ziv can be seen as being a "language model" in this way, though one might have to squint a little bit. (It's particularly tricky for something that does a Burrows-Wheeler transform!) Also, note that the model by user2699 is a modification of a Markov model; essentially nothing else is competitive for this challenge or perhaps even modeling text in general.
### Overall architecture
For the purposes of understanding, it's nice to break up the overall architecture into several pieces. From the highest-level perspective, there needs to be a little bit of state management code. This isn't particularly interesting, but for completeness we want to stress that at every point the program is asked for the next guess, it has available to it a correct prefix of Moby Dick. We do not use our past incorrect guesses in any way. For efficiency's sake, the language model can probably reuse its state from the first N characters to compute its state for the first (N+1) characters, but in principle, it could recompute things from scratch every time it is invoked.
Let's set this basic "driver" of the program aside and peek inside the part that guesses the next character. It helps conceptually to separate three parts: the language model (discussed above), a "hints" file, and an "interpreter". At each step, the interpreter will ask the language model for a distribution for the next character and possibly read some information from the hints file. Then it will combine these parts into a guess. Precisely what information is in the hints file as well as how it is used will be explained later, but for now it helps to keep these parts separate mentally. Note that implementation-wise, the hints file is literally a separate (binary) file but it could have been a string or something stored inside the program. As an approximation, we pretend that the model and interpreter are pretty short, so we can approximate that as "L ≈ 0".
If one is using a standard compression method such as [bzip2 as in this answer](https://codegolf.stackexchange.com/a/152931/49643), the "hints" file corresponds to the compressed file. The "interpreter" corresponds to the decompressor, while the "language model" is a bit implicit (as mentioned above).
### Why use a hint file?
Let's pick a simple example to analyze further. Suppose that the text is `N` characters long and well-approximated by a model wherein every character is (independently) the letter `E` with probability slightly less than a half, `T` similarly with probability slightly less than a half, and `A` with probability 1/1000 = 0.1%. Let's assume no other characters are possible; in any case, the `A` is pretty similar to the case of a previously unseen character out of the blue.
If we operated in the L 0 regime (as most, but not all, of the other answers to this question do), there's no better strategy for the interpreter than pick one of `E` and `T`. On average, it will get about half of the characters correct. So E ≈ N/2 and the score ≈ N/2 also. However, if we use a compression strategy, then we can compress to a little more than one bit per character. Because L is counted in bytes, we get L ≈ N/8 and thus score ≈ N/4, twice as good as the previous strategy.
Achieving this rate of a little more than one bit per character for this model is slightly nontrivial, but one method is arithmetic coding.
### Arithmetic coding
As is commonly-known, an *encoding* is a way of representing some data using bits/bytes. For example, ASCII is a 7 bit/character encoding of English text and related characters, and it is the encoding of the original Moby Dick file under consideration. If some letters are more common than others, then a fixed-width encoding like ASCII is not optimal. In such a situation, many people reach for [Huffman coding](https://en.wikipedia.org/wiki/Huffman_coding). This is optimal if you want a fixed (prefix-free) code with an integer number of bits per character.
However, [arithmetic coding](https://en.wikipedia.org/wiki/Arithmetic_coding) is even better. Roughly speaking, it is able to use "fractional" bits to encode information. There are many guides to arithmetic coding available online. We'll skip the details here (especially of the practical implementation, which can be a little tricky from a programming perspective) because of the other resources available online, but if someone complains, maybe this section can be fleshed out more.
If one has text actually generated by a known language model, then arithmetic coding provides an essentially-optimal encoding of text from that model. In some sense, this "solves" the compression problem for that model. (Thus in practice, the main issue is that the model isn't known, and some models are better than others at modeling human text.) If it was not allowed to make errors in this contest, then in the language of the previous section, one way to produce a solution to this challenge would have been to use an arithmetic encoder to generate a "hints" file from the language model and then use an arithmetic decoder as the "interpreter".
In this essentially-optimal encoding, we end up spending -log\_2(p) bits for a character with probability p, and the overall bit-rate of the encoding is the [Shannon entropy](https://en.wikipedia.org/wiki/Shannon_entropy). This means that a character with probability near 1/2 takes about one bit to encode, while one with probability 1/1000 takes about 10 bits (because 2^10 is roughly 1000).
But the scoring metric for this challenge was well-chosen to avoid compression as the optimal strategy. We'll have to figure out some way to make some errors as a tradeoff for getting a shorter hints file. For example, one strategy one might try is a simple branching strategy: we generally try to use arithmetic encoding when we can, but if the probability distribution from the model is "bad" in some way we just guess the most likely character and don't try encoding it.
### Why make errors?
Let's analyze the example from before to motivate why we might want to make errors "intentionally". If we use arithmetic coding to encode the correct character, we will spend roughly one bit in the case of an `E` or `T`, but about ten bits in the case of an `A`.
Overall, this is a pretty good encoding, spending a little over a bit per character even though there are three possibilities; basically, the `A` is fairly unlikely and we don't end up spending its corresponding ten bits too often. However, wouldn't it be nice if we could just make an error instead in the case of an `A`? After all, the metric for the problem considers 1 byte = 8 bits of length to be equivalent to 2 errors; thus it seems like one should prefer an error instead of spending more than 8/2 = 4 bits on a character. Spending more than a byte to save one error definitely sounds suboptimal!
### The "rewind" mechanism
This section describes the main clever aspect of this solution, which is a way to handle incorrect guesses at no cost in length.
For the simple example we've been analyzing, the rewind mechanism is particularly straightforward. The interpreter reads one bit from the hints file. If it is a 0, it guesses `E`. If it is a 1, it guesses `T`. The next time it is called, it sees what the correct character is. If the hint file is set up well, we can ensure that in the case of an `E` or `T`, the interpreter guesses correctly. But what about `A`? The idea of the rewind mechanism is to simply *not code `A` at all*. More precisely, if the interpreter later learns that the correct character was an `A`, it metaphorically "*rewinds* the tape": it returns the bit it read previously. The bit it read does intend to code `E` or `T`, but not now; it will be used later. In this simple example, this basically means that it *keeps* guessing the same character (`E` or `T`) until it gets it right; then it reads another bit and keeps going.
The encoding for this hints file is very simple: turn all of the `E`s into 0 bits and `T`s into 1 bits, all while ignoring `A`s entirely. By the analysis at the end of the previous section, this scheme makes some errors but reduces the score overall by not encoding any of the `A`s. As a smaller effect, it actually saves on the length of the hints file as well, because we end up using exactly one bit for each `E` and `T`, instead of slightly more than a bit.
### A little theorem
How do we decide when to make an error? Suppose our model gives us a probability distribution P for the next character. We will separate the possible characters into two classes: *coded* and *not coded*. If the correct character is not coded, then we will end up using the "rewind" mechanism to accept an error at no cost in length. If the correct character is coded, then we will use some other distribution Q to encode it using arithmetic coding.
But what distribution Q should we choose? It's not too hard to see that the coded characters should all have higher probability (in P) than the not coded characters. Also, the distribution Q should only include the coded characters; after all, we're not coding the other ones, so we shouldn't be "spending" entropy on them. It's a little trickier to see that the probability distribution Q should be proportional to P on the coded characters. Putting these observations together means that we should code the most-likely characters but possibly not the less-likely characters, and that Q is simply P rescaled on the coded characters.
It furthermore turns out that there's a cool theorem regarding which "cutoff" one should pick for the coding characters: you should code a character as long as it is at least 1/5.393 as likely as the other coded characters combined. This "explains" the appearance of the seemingly random constant `5.393` nearer the end of the program above. The number 1/5.393 ≈ 0.18542 is the solution to the equation [-p log(16) - p log p + (1+p) log(1+p) = 0](https://www.wolframalpha.com/input/?i=solve+-p+log%2816%29+-+p+log+p+%2B+%281%2Bp%29+log%281%2Bp%29+%3D+0+for+p).
Perhaps it's a reasonable idea to write out this procedure in code. This snippet is in 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;
}
```
### Putting it all together
The previous section is unfortunately a little technical, but if we put all of the other pieces together, the structure is as follows. Whenever the program is asked to predict the next character after a given correct character:
1. Add the correct character to the known correct prefix of Moby Dick.
2. Update the (Markov) model of the text.
3. The **secret sauce**: If the previous guess was incorrect, *rewind* the state of the arithmetic decoder to its state before the previous guess!
4. Ask the Markov model to predict a probability distribution P for the next character.
5. Transform P to Q using the subroutine from the previous section.
6. Ask the arithmetic decoder to decode a character from the remainder of the hints file, according to the distribution Q.
7. Guess the resulting character.
The encoding of the hints file operates similarly. In that case, the program knows what the correct next character is. If it is a character that should be coded, then of course one should use the arithmetic encoder on it; but if it is a not coded character, it just doesn't update the state of the arithmetic encoder.
If you understand the information-theoretic background like probability distributions, entropy, compression, and arithmetic coding but tried and failed to understand this post (except why the theorem is true), let us know and we can try to clear things up. Thanks for reading!
[Answer]
# Node.js, 2\*224 + 524279 = 524727
*Please refer to the change log at the end of this post for score updates.*
A function taking and returning a byte.
```
a=[...l='14210100'],m={},s={},b={}
f=c=>a.some((t,n)=>x=s[y=l.slice(n)]>t|/^[A-Z '"(]/.test(y)&&b[y],l+=String.fromCharCode(c),a.map((_,n)=>(m[x=l.slice(n)]=-~m[x])<s[y=l.slice(n,8)]||(s[y]=m[x],b[y]=c)),l=l.slice(1))&&x||32
```
It consists of a simple [PPM model](https://en.wikipedia.org/wiki/Prediction_by_partial_matching) that looks at the last 8 characters to predict the next one.
We trust a pattern of length **L** when we have encountered it at least **T[L]** times, where **T** is an array of arbitrary thresholds: **[1,1,2,1,2,3,5,2]**. Furthermore, we always trust a pattern whose first character matches `[A-Z '"(]`.
We select the longest trusted pattern and return the prediction with the highest score associated to this pattern at the time of the call.
### Notes
* This is obviously not optimized for speed, but it runs in about 15 seconds on my laptop.
* If we were allowed to repeat the process several times in a row without resetting the model, the number of errors would converge to ~268000 after 5 iterations.
* The current success rate of the prediction function is ~56.8%. As noticed by @immibis in the comments, if bad and correct guesses are mixed together, the result is not even barely readable.
For instance, this snippet near the end of the book:
```
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.
```
becomes:
```
"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,
```
By replacing bad guesses with underscores, we have a better idea of what the function got right:
```
_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**: The above example was created with a previous version of the code, working on the first version of the input file.
### Test code
```
/**
  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)
```
---
### Change log
* **524727** - saved 19644 points by switching to [**whale2.txt**](https://gist.githubusercontent.com/nathanielvirgo/73b4181917f83c0cd306bd0d8f4c998a/raw/208774322bad4e04715eae743d7d350b504fe5eb/whale2.txt) (challenge update)
* **544371** - saved 327 points by forcing patterns starting with a capital letter, a quote, a double-quote or an opening parenthesis to be also always trusted
* **544698** - saved 2119 points by forcing patterns starting with a space to be always trusted
* **546817** - saved 47 points by adjusting the thresholds and golfing the prediction function
* **546864** - saved 1496 points by extending the maximum pattern length to 8 characters
* **548360** - saved 6239 points by introducing the notion of trusted patterns, with thresholds depending on their length
* **554599** - saved 1030 points by improving the line feed prediction
* **555629** - saved 22 points by golfing the prediction function
* **555651** - saved 40 points by golfing the prediction function
* **555691** - initial score
[Answer]
# Python 3, 2·267 + 510193 = 510727
### Predictor
```
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]
```
This uses a weighted Bayesian combination of the order 0, …, 16 Markov models, with weights [1, 6, 12, 30, 65, 99, 87, 117, 118, 89, 95, 118, 96, 184, 126, 219, 126].
The result is not very sensitive to the selection of these weights, but I optimized them because I could, using the same [late acceptance hill-climbing](http://www.yuribykov.com/LAHC/) algorithm that I used in [my answer to “Put together a Senate majority”](https://codegolf.stackexchange.com/a/132498/39242), where each candidate mutation is just a ±1 increment to a single weight.
### Test code
```
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)
```
[Answer]
# [Python 3](https://docs.python.org/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
```
[Try it online!](https://tio.run/##ZVRdb9s2FH3nr7jNC@1adiNs6AA7LDAURTMsWx@aYgiyYKAp2iJMkQ5JSTWK/vbsXspyvvgi8n6ecy6p/SHV3v3y8FCJRvz4yaIoWV90gvPinFV6A5uJmi4ZbK1fSwt90RRdEYuKgdlAD84nMA6aZXPb31E@tIK2q/ZW3QlFvhakq6CckcUHKFfdTJSre@EEB77qRf82ztQqCvVGuGPVXPG/wolGfp9MqN7t7q7YTTeYv8teNE0ZaIvhcV4unajQzJ2u0sZz7McT94FLPsTwORdCYZQazmf8bDjzOEa84xfqgi85GRc84@g@/Pp24t6I@@ns/Xuy/@sGR1xWVAl36uJ@iQxul/Pybna/6kQU5wyCTm1w4B6yfkcBcZ00hKaAroBYQJUdz6XM7EAAqYkr01dkGHczKHPzUQlkEDWUObqHmQA1Vo1D48Ex2mlFPJ3nU0cJQ65DI@djbgcfBPxWPlbI7qwBriz9cVLPIl6MDJ7P7La8e0xXILAi8BctJD@dMYgGC@Nkl4BjSCOCqF9kwgn869LEuHxMxLpPdBrCkdtzvfgjku4k2DhdxtgejX97p1kw2zrliOQTjph2zDR7HxLEQ2TY4jq0T@CSKpaYoXcRU2XcImhZWeN0nEwf48bYPGv73H7EvifsagkDhtMwny4Sh67hKwcRcK@sA4dcaR@MSxP@4ye8w/u4hE/4xvkCETUyTXLHYgg/fmA@4JhOH9in65u/vlx9@XyzYGzytd3vrdEVrA8g4UomDR@9i22zT6bT8C3WOmAJ9H0OsmlkgK@q9t5OGbuuNeylPQbN56kmqdYyaBJFeYkYai0Dfta@OhT5f7MO0rgV/AFRa6hNw5zvF3CpoZcRdIfNqjYm47bojOBtBVZ/Nwoh5fTtAAJfaG9SjajuW60Dq9G300HVRm/wFXu1wwr2ALpZa2sN4quOCdZCQtxbeYCNlVtssSEjI@MOseAFkslQO3SQsffBVhmh9R2WQS0I4QneiGgFJrHoG137HhpjK2wfdGNchUlIlOpRToN3T1qTDqj@2T@1Qf0OvoUkd1k2YkI9YlYZPEIgtkdr0lLVBKuhefW1TMzJRqMOuLd6vkGqgE0wdK1BITGd36lvaYhu2yILLTuS17d0Rerg223NzNb5IJ3SReZsdUo4iUtUuTaKVGs8UpYW3xT@SHY6ZRAQMc9sjMqKIUF2FKwqMqcK/yY00YQ4j5UQG/1PEz66xRnM55e/f/zz6tvNNfsf "Python 3 – Try It Online")
A function using global variables. Learns as it goes, building a model at the word level: given what it's seen so far *in this word*, what's the most common next character? As more input comes in it learns common words from the text pretty well, and it also learns the most common character to start the *next* word.
For example:
* If what it's seen so far is 'Captai' it predicts an "n"
* If it's "Captain" it predicts a space
* If it's the start of a word, and the last word was "Captain" it predicts an 'A'
* If the word so far is 'A' it predicts an 'h' (and then 'a' and 'b'; similarly for 'C').
It doesn't do very well at the start, but by the end there are large parts of actual words coming out. The fallback option is a space, and after a single space it's an "a", unless the preceding letter was one of "nedtfo", a digit, or a hyphen or apostrophe. It also aggressively predicts line breaks after 71 characters, or if a space was expected after 66. Both of those were just tuned to the data ("t" is far more common after a space, but has more often already been predicted, so "a" is a better guess outside those six special cases).
Learning what word pairs went together and preseeding the mapping turned out not to be worthwhile.
---
It ends up with text like this:
```
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!
```
which corresponds to this part of the input:
> 
> 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!
> 
> 
> 
You can see where proper nouns in particular come out pretty well, but the ends of words are mostly right as well. When it's seen "dou" it expects "doubt", but once the "l" appears it gets "doubloon".
If you run it a second time with the same model it just built it immediately gets another 92k correct (51.7%->59.3%), but it's always just under 60% from the second iteration on.
---
The measuring code is in the TIO link, or here's a slightly better version:
```
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` has the guessed output at the end.
[Answer]
# C++, score: 2\*132 + 865821 = 866085
*Thanks to @Quentin for saving 217 bytes!*
```
int f(int c){return c-10?"t \n 2  sS \n  -  08........       huaoRooe oioaoheu thpih eEA \n   neo    enueee neue hteht e"[c-32]:10;}
```
A very simple solution that, given a character, just outputs the character that most frequently appears after the input character.
**Verify the score with:**
```
#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:** Using `whale2.txt` gives a better score.
[Answer]
## Python, 2\*516 + 521122 = 522154
### Algorithm:
Yet another python submission, this algorithm calculates the most likely next letter looking at sequences of length 1,...,l.
The sum of probabilities is used, and there are a few tricks to get better results.
```
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')]
```
### Results:
Mostly gibberish, although you can see it picks up on the occasional phrase, such as "Father 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
```
### Test code:
Pretty simple, outputs some examples of the text at different points.
Uses whale2.txt, as this avoids some extra logic to calculate newlines.
```
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'))
```
[Answer]
# [C (gcc)](https://gcc.gnu.org/), ~~679787~~ 652892
~~84~~ 76 bytes, ~~679619~~ 652740 incorrect guesses
```
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];}
```
[Try it online!](https://tio.run/##XZDRauMwEEWf7a@YGkLtRFm3@1Qs9NhAobAf4PpBGUuyWEUOklKzLfn19UoqtGURiOEyc@bOxb1CXNdzf//zYfjvo5wcCZKRqnpq3s89H/rj0OPQjwOb6MSiwqJwZFFCNkadTQO9rtoGOHFt61Rwp5AATtxtt/DavJfF4en5cQuayfksbP3a3w@kclVDyyJ1gUViFLujbWuxAyuWpBIwqgPDfVAX4X1ZJPTC7kjInUsHi5utIhA6CHPgpiyWSRtR1xaZVCJgrZsGbhg8/jokE4WWtVF7iw0sux2FttUy8yEvAO3tbYAwCfD8JID7XEsn/GT@gBN8zDdxDCKa0xadOInkKaKjfRX3Nokag/gt8mzmErh4bdUX7IsSB88uniXraoNVzOBjPmugAwE5OzAX8/YjdoYPz98W56sB54vNrGv5SXux6T1ZnJ0TGLrN2G7GF1uRhYSUukQzexHzoeWVruX6F6Xhyq/75R8 "C (gcc) – Try It Online")
Update: ~27000 points off with updated file, 16 points (8 bytes) with a better-golfed function.
## Explanation
The way this works is that as the code runs through the text, it memorizes the last character that terminated any given 4-character sequence, and returns that value. Somewhat similar to Arnauld's approach above, but relies on the inherent likelihood of two given 4-character sequences terminating the same way. 
De-golfed:
```
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.
}
```
[Answer]
# C++, 2·62829 + 318786 = 444444
To run this program, you need [this file here](https://www.dropbox.com/s/285u647xlzdb0ia/C), which must be named `C`.
The program uses the same combination of Markov models as in [our earlier answer](https://codegolf.stackexchange.com/a/153218/49643). As before, this combination is essentially the model from [this answer by user2699](https://codegolf.stackexchange.com/a/153050/49643), but with a few small modifications.
Seeing as how this answer uses the exact same model as before, the improvement is a **better information-theoretic mechanism** than the "rewind" mechanism described earlier. This allows it to make fewer errors while also having a smaller combined length. The program itself isn't golfed very much because it is not the major contributor to the score.
The program is 2167 bytes long (including all the tabs for indentation and lots of other unnecessary characters, but before the test code), and the binary file `C` is 60661 bytes long, so [under the rules for scoring multiple files](https://codegolf.meta.stackexchange.com/questions/4933/counting-bytes-for-multi-file-programs/4934#4934), we score `L` as 2167 + 60661 + 1 = 62829.
The program takes approximately 8 minutes to run on an `m5.4xlarge` instance on Amazon EC2 and uses a little over 16 GB of memory. (This excessive memory usage isn't necessary -- we just didn't optimize that either.)
```
#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;
}
```
[Answer]
### sh+bzip2, 2\*364106 = 728212
2\*381249 + 0 = 762498
```
dd if=$0 bs=1 skip=49|bunzip2&exec cat>/dev/null
```
followed by the bzip2-compressed whale2.txt with the first byte missing
Ignores its input; outputs the correct answer. This provides a baseline on one end; daniero provides a baseline on the other end.
Builder script:
```
#!/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
```
I/O test harness (tcc; cut off first line for gcc). This test harness can be used by anybody on a suitable platform that submits a complete program that expects read/write I/O. It uses byte-at-a-time I/O to avoid cheating. Child program must flush output after every byte to avoid blocking.
```
#!/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;
}
```
[Answer]
# [Python 3](https://docs.python.org/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])
```
[Try it online!](https://tio.run/##bVTbbttGEH32fsUkAmqykVgrfpOgh0Ko4qIOYiA2AkMWjBU5FBda7qrLpS4I8u3uGUq@pO2TxLmcOecMh5tDrLy7fHqaTebzi8Wvw4@XpQ/0SMZR0G7FCSLpQt1MLj@qgksqk2k6Wlm/1JZuxtOJDwUi49n8ZjGfLj5MhuObyXQcOLbBUV6FpNb7hF1bc9CRkxmK0v6aDxOr62WhaT/az4eLFLPTJ9WjO7fytuSCcl8wLdn6nUK4DPx3yy4/0ISeedL/Eu3RJvAWZeDboyPjvNIhHamzHp2IS4k8SgKloqGrkdjLqLlULeaSWNCHCQ0lWxv3aFzBe7SJMnWG4Ku81@auLe13echF@YtgEsUClhKkyJ8TZemRx7fuPc8DN2XqjQ@RmkPz/Deamk1U3WZq1k0bOBGlpbEMQFRmTSxgUY/8hl0Szqejh42O1UP0D1L0sKu05Szu4zkmRN5HtEkiC6yLJD1CZbn1DcuTcbkPgXMpu1BnQtz4tnk8OSkAnSbZTRfD7C44HC3A62zVctPIiOSnViC/gYbZxsXkWPvu6EtXUVLyWvULXewvZ7NZShNwIe0K@qlDxoGgIJ1//0FZlp1noFXr@AqSCuy/RXRrUG9af6PvP/7b2ycLR0VcOhgCSJ0abrGT0dsO@NqtKTv@JKdF9QmvzZLDZJgqtD@pP27vP3@5/vLpPlMq@dpuNtbgEJYH0nSNl4um3jVtvYlmy3TXVBwoeuQ@BV3XIP41r7y34HFbMW2w1WPRYBAr2eVSB5Zt5F6DesU64Gfpi0O/s24ZtHFj@pMaZqpMrZzfZXTFtNMN8RbDiraJxq2QbMjbAur3Jgelo/NHEk2fdiZWYIUz4KAq5NYc8spw2afa52sg2AMxhFtrwK84NVhLEbxX@kCl1SuMKCWoJLgGF0dORyPjkJDgzgdbdAyt3wIGXgjDF3rPjMaEA2l8zZXf4XxtgfGBazmqQoQKnvTUuCdtTTzA/fffKjmgg28p6nVnmyiRGU3nMnlQELWnaGSdV0Krln3hpqJyumb40N3XoIRUwhCULplyCMNwoPpWlujw3sJOvRV7fYu9YGW@XVXKrJzH1y3nfqfZcozYxBVcrkwurtUekrX1jvE5WnPsSFCDPlOavHMMAtXJsKLfaSrYGtloBM8TErg5j@9JaDl7T4PB1e/Tv67v7m/VPw "Python 3 – Try It Online")
---
... The `///` answer which prints a space get 10 upvotes, while my code can only get 3 ...
Explanation:
For each character, the program:
* increase `frequency[prev][char]`
* Find the character that appear the most times in `frequency[char]`
* and output it.
---
* Ungolfed code in TIO link, commented out.
* The code is 131 bytes.
* The code run on my machine reports:
```
879504 / 1215235
Time: 62.01348257784468
```
which have the total score
```
2*131 + 879504 = 879766
```
Because there is no way to upload a large file to TIO (except asking Dennis), the example run in the TIO link only runs the program for a small part of the text.
In comparison with the older answer, this one have 362 more incorrect characters, but the code is shorter by 255 bytes. The multiplier makes my submission have lower score.
[Answer]
# 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:' ';}}
```
This approach uses a look-up table to learn the most common character that follows a given string. The keys of the look-up table have a maximum of 4 characters, so the function first updates the look-up table with the current character and then just checks which character is the most likely to happen after the 4 previous ones including the current one. If those 4 characters are not found in the look-up table, it prints a space.
This version uses the `whale2.txt` file, as it greatly improves the number of successful guesses.
Following is the code used to test the class:
```
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();
    }
}
```
The code runs in barely 2 seconds. Just for the record, this is what I get when I modify the size of the keys of the look-up table (includes the results of a second run without resetting the model):
```
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
```
It would be interesting to know why a key size of 4 characters is the best choice in this algorithm.
**Text comparison**
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!"
```
Recreated:
```
"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 
```
Guesses:
```
"_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__
```
**Change log**
* **569279** - changed to `whale2.txt` and thus removed the optimization.
* **577366** - optimized with code that tried to guess when to return a line feed.
* **590354** - original version.
[Answer]
# Java 7, 1995 characters, (1995\*2+525158) 529148
Java sucks for small program sizes. Anyway, I tried several extremely complex and tricky approaches that produced surprisingly crap results. I subsequently went back and just did a simple approach, which resulted in a smaller program size and better results. 
This approach is actually extremely simple. It blindly feeds the previous x characters (in addition to all substrings of those characters) into a hashtable, mapped to the current character. It then keeps track of which patterns most accurately predict the current character. If patterns that precede certain characters are encountered multiple times, they succeed in predicting the character. It gives precedence to longer strings and it gives precedence to whichever character most often follows a given string. 
This algorithm knows nothing about the type of document or the english language. 
I settled on using 9 characters and attempting to match whole words within those previous 9 characters when possible. When you don't try to do word matching within the strings, the optimum length is 6 characters, producing several thousand more mispredictions. 
One interesting observation was that using 20 characters resulted in bad predictions the first time through but 99.9 percent accuracy on subsequent passes. The algorithm was basically able to memorize the book in overlapping 20 byte chunks, and this was distinct enough to allow it to recall the entire book a character at a time. 
* (1950\*2+532919) **536819**
* (2406\*2+526233) **531045** checking for punctuation to make better guesses
* (1995\*2+525158) **529148** more tweaking, golfed away some 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); }
```
[Answer]
# 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
```
I attempted this independently, but ended up with what's effectively an inferior version of Michael Homer's answer. I hope that doesn't render my answer completely obsolete.
This builds over time a dictionary of words (crudely defined as strings terminated by  or `\n`, case-sensitive and including punctuation). It then searches this dictionary for words beginning with what it so far knows of the current word, sorts the resulting list by frequency of occurrence (slowly), and guesses that the next character is the next character in the most common matching word. If we already have the most common matching word, or no longer matching word exists, it returns .
It also builds up a disgustingly inefficient dictionary of word pairs. Upon hitting a word boundary, it guesses that the next character is the first letter of the second word in the most common matching word pair, or `t` if there is no match. It's not very clever, though. Following `Moby`, the program correctly guesses that the next character is `D`, but then it forgets all about the context and usually ends up calling the whale "Moby Duck" (because the word "Dutch" seems to be more frequent in the first half of the text). It would be easy to fix this by prioritising word pairs over individual words, but I expect the gain would be marginal (since it's usually correct from the third character on, and the word pairs aren't that helpful in the first place).
I could tune this to better match the provided text, but I don't think manually tuning the algorithm based on prior knowledge of the input is really in the spirit of the game so, other than choosing t as the fallback character after a space (and I probably shouldn't have done that either), I avoided that. I ignored the known line length of the input file, and instead inserted `\n` after every 13 spaces—this is almost certainly a very poor match, the main intention was to keep the line length reasonable rather than to match the input.
The code isn't exactly fast (~2 hours on my machine), but overall gets about half the characters right (49%). I expect the score would be marginally better if run on `whale2.txt`, but I haven't done that.
The start of the output looks like this:
> 
> `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`
> 
> 
> 
but by the end, it looks a bit more like... something. My favourite passage from near the end of the book,
> 
> "I turn my body from the sun. What ho, Tashtego! let me hear thy hammer.
>  Oh! ye three unsurrendered spires of mine; thou uncracked keel; and only
>  god-bullied hull; thou firm deck, and haughty helm, and Pole-pointed
>  prow,--death-glorious ship! must ye then perish, and without me? Am I
>  cut off from the last fond pride of meanest shipwrecked captains? Oh,
>  lonely death on lonely life! Oh, now I feel my topmost greatness lies in
>  my topmost grief. Ho, ho! from all your furthest bounds, pour ye now in,
>  ye bold billows of my whole foregone life, and top this one piled comber
>  of my death! Towards thee I roll, thou all-destroying but unconquering
>  whale; to the last I grapple with thee; from hell's heart I stab at
>  thee; for hate's sake I spit my last breath at thee. Sink all coffins
>  and all hearses to one common pool! and since neither can be mine, let
>  me then tow to pieces, while still chasing thee, though tied to thee,
>  thou damned whale! THUS, I give up the spear!"
> 
> 
> 
comes out as
> 
> `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 "`
> 
> 
> 
That would have made *The Wrath of Khan* a lot more confusing. And "lonely" → "tingly" is a particularly satisfying substitution.
**Edit:** Saved one byte by deleting an extraneous space
# Scoring
```
#! /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
```
This runs the program for the text of Moby Dick and outputs the "predicted" textto stdout, and abuses stderr to write the score. I'd recommend redirecting the output to a file.
[Answer]
# Python 3, 526640
274 bytes, 526092 errors (using `whale2.txt`). This is definitely capable of further improvement, but it has reached the "good enough to post" stage.
```
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))
```
The idea is to store the frequencies of all runs of 2, 3, 4, ..., 10 characters. For each of these lengths L, we check whether the most recent L-1 characters match a stored pattern; if so, our guess gL is the most frequent next character following that pattern. We collect up to nine guesses in this way. To decide which guess to use, we weight the frequency of each pattern by its length to the 8th power. The guess with the largest sum of weighted frequencies is chosen. If there are no patterns that match, we guess space.
(The maximum pattern length and the weighting exponent were chosen by trial-and-error to give the fewest incorrect guesses.)
Here's my ungolfed work-in-progress version:
```
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))
```
And the test harness:
```
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))
```
---
Here's some sample output from near the beginning of the text. Already we begin to see the ability to finish common words after seeing their first letter (`in`, `to`, `and`, `by`; also, apparently, `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 
```
Near the end, there are still plenty of mistakes, but also plenty of very good sequences (`shmage seashawks`, for instance).
```
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
```
It's interesting to look at some of the mistakes and guess what word the algorithm "expected." For instance, after  `sail`, the program both times predicts `o`--for `sailor`, I presume. Or again, after `, a` it expects `n`--possibly because of the common occurrence of `, and`.
---
Changelog:
* 274 \* 2 + 526092 = **526640** Golfed the algorithm, at the cost of a few extra errors
* 306 \* 2 + 526089 = **526701** Original version
[Answer]
# Python 2, score: 2\*(407+56574) + 562262 = 676224
Searches for words matching the previous characters from a list of ~~all~~ most words used in the text, sorted by the number of their 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"
```
**Data: <https://www.dropbox.com/s/etmzi6i26lso8xj/d?dl=0>**
**Test suite:**
```
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:** Using `whale2.txt` gives a better score.
[Answer]
# C++ (GCC), 725 × 2 + 527076 = 528526
Yet another prefix-frequency submission. Run on `whale2.txt`, and get similar (slightly worse) score than others.
```
#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]];}
```
This one greedily find the longest string that starts with a suffix of the history, and if there are multiple candidates, tiebreak with shorter strings.
For example: If the last 7 characters are `abcdefgh`, and the string `abcdefghi` and `abcdefghj` appears with the largest frequency in all strings of the form `abcdefgh*`, the output will be either `i` or `j`, tiebreak with shorter suffixes (`bcdefgh`, `cdefgh`, ...).
For unknown reasons, anything more than 7 and my computer doesn't have enough RAM to run it. Even with 7, I need to close all web browsers to run it.
---
Testing code:
```
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]];
}
```
---
Example output:
```
~ ~s  ta~ hard ts tt~~~~~~~ ~doam ~~ ar~ ~ i~~~ ~~~ ~he~~~~,a~ t~~~~ t~ ho~si~  
n--as his wont at intervals--stepped forth from the scuttle in which he leaned, 
~~~ thr~ ~~ t~~ crp~~~~~~~~ a~ wap~~~~~ a~eo~~ h~~ o~~ s~~~ or~~y~ ~  boog~e~~ t
and went to his pivot-hole, he suddenly thrust out his face fiercely, snuffing u
~ a~~ ~h~ ~n~ onitn~oi~~~~~~ ~~a~ ~ cewsoat~  a~ tae~~~~ ~e~~t~~ te~~ ouc~s~i~~ 
p the sea air as a sagacious ship's dog will, in drawing nigh to some barbarous 
ct as I~ iisk~~~~ ~~e~ tls~~~~ i~~~ ~~ soe~e Ae ~ ~~e~ tar~~~~~ trd~  ot ~ h~~~ 
isle. He declared that a whale must be near. Soon that peculiar odor, sometimes 
```
This one is near the end of the text. Most long words are predicted quite accurately (`intervals`, `pivot-hole`, `distance`)
```
 au t  tf weu~i~ aor~ mre~g~~~ m~t~~ ~~~  ~"NC~X~t~ti~  ~~n~ SNsh A FNECnSERTR O
 on as it rolled five thousand years ago./////Epilogue//"AND I ONLY AM ESCAPED A
NL~~,S~ ~HR~ yO~ -/s~n "~A~~ laeu~ta Vew~, S~e s~~  s~ ~ ain~ t~d ~t~ oirept~~ ~
LONE TO TELL THEE" Job.//The drama's done. Why then here does any one step forth
```
Upper-case doesn't seem good.
[Answer]
# Python 2, 756837
Uses something that might be Markov chains?
```
import zlib
a=eval(zlib.decompress('x\x9cM\x9cis\xda\xcc\xd2\x86\xff\x8a2\xf5\xd4\x81\xb8,\x977l\'\xf9\x90\x12 \x02f\x11G\x02c||*%@,a\x11a1\xe0S\xef\x7f\x7fC\x13\xf75\xdf\xda\xaaa4\xd3\xcb\xddw\xf7\x8c\xfc\xbf\xcc\x8f\xd7E\xe6\xab\x93if\xce\x9d\xcc\x8f\xefG\xd1\x11\xf1\x1b\xa2At\x8e\xa2\'\xe2\xc5Q\xfc,\xa2{\x14+"\x9e3\xf63b\x87\x9f\xb5\x8fb$b\xeb(\x96E\x8c\x18\x1b2\xb6{\x14/D\xfcq\x14\x03\x11}\xc6zG\xb1.b\xc0\xd3\x06\xcb\xa9\xf1\xb3\xcaQl\x88X>\x8a-\x11\xb7G1\x11q\x85\x98\x1c\xc5\x95\x88\xf1Q\xec\x89\x98\x1e\xc5\x81\x88\xa2\xb3X\xc4\x19\xe2\xe4(\xbe\x898\xd6\xc9F\xa8\xe4E\x16\x19\x8a\xc8r^|U\xc9\x8b\xc7\xd8\xfcQ\xf4\x8f\xe2\xbf\x1c\x06\xbc\xa8v6\xef\xba\xb2\x17V\xf6\x92\xe8r6\x07\x9d\xcc\x95EN\xe4\xe9FW\xb6\xd9\xea6M\xa2K\xdf\xact\x86\xf9\xc976Gy\xf2\xce\xef\x96G1\x15q\xf1\xf1\xd4\xcc3\xe6\x8f\xb8\x96\xdf}\xd27\xcf\x1d\x9da\x8e\x1f\xcd\xc5c\\\x11Q\xcf\xfc\x02Q\x9c\xe7\\\xd6\xbe;\x8acY\xe5\x8c\x17\xcfu9F\xc4\x83\xfc\x0c\x076\x0b\x1d;\xc7\x97\xe7_U\x9c\xacT\xfc\xc2\x1a\xbe\xb0\x06\x83\r7b\xd9\x85<\x9d\xe8\x86\xbe|Q\xff\xfc\xf2\xa0\xe2d\xa7?\xfbr\xc5\xbc\x97\x8c\xbd\xd1\xbd}\xb9f@\x8e\x01\xb7\x88\xf7\x88w*\xce\x13v1\xc1ZCv\x1c\xebz\xe7=]\xce\x1c\x9d\xcdg\xe8,U/\x98/\x18`\xed\xf8\x8d\xa7\xe21\'\x1bo\xd4,sk\x80\xb8\xc6L\xc45Oq\xa9M\xac\x9e8\xc7?k\xb8\x9fY\xe9\x80\x9a\x8c\x9d\x8a\x98\xea\xde\x8c\xcc\xbb\x94\xa7\x13\x06\xc8\xca\xfa"\x1e\x98\xa1\xa4\xe1R\xfb\xa1\xb1W+\xf2b\xc0\xa4\x96W\xac\xa8\x15\x10=\x8d\xd3ZC#\xb2F \xd7j\xccP\xd78\xadU\x8fbWD"\xbd\xd6Q\xb7\xaf\xb5\x98\x0cH\xac\x85\xfc\x0cH\xac5\x15(k\xdd\x8f\xa7\xa6&\xf1v\xfa\x19\x00Q\xc3\x7fkxuM\xe2\xad(\xa2D\xd6\xabX\xb6&\xfeyy\x14\x1d\xdc\xa4v\x8azY\xdbU\xa4P\xf9\xc4\xcc?\x0fj\x8d\x9f\x135\xf8O\xde\xf7\xd3Q?Ym\xf4\xe9\n\xefY\xe12\xab\x9d:\xc7\n`Y\xfd>\x8a[\x11\xf1\x88\xd5\x9a\xc9\xf6\xcc\x80#\xad\xde\xd5+W\x03\x9e\x12/\xab!\xf3\x8e\x98\x81xY\xf5\x18\xd0g2\xe2e5g\xb2\x05+\x13\x07\x9d\x8b8fCD\xd1j\xca\xcf,X]\x81X+\xb0i\xa5\x88\xf5\'\x1c\x14VW`\xe9\n\x84]\x19u\xaa\x15\x16X\x81\xb0+\x0c\xb7"\'\xbf.N\xab0\xa7?n\xd5\x13^\x179\xb5\xf9\xebB<\xe4\xe1$_[c\x04\xc3\x06\'\x99W\xbd.\xb2\x1ap\xaf\x8b\xb3\x8fy\xcc\x9fW\x19\xe6t\xacE\x18\x1d\xffoR\xf1\xeb\xa2k\xc9/\x96\xfc\x1fk\xfa\x96Z\xe7u\xd1VLx]<\xa9Q^\x17\x1dkL\xd3\x9a\xe7\xdfj\xe4\xd7Eh\x8d\x8fT\xc3\xaf\x8b\x9a5\xben\xc9\ru\xd2\xd7E\xa0\xf6}]\x94\xad1\x15k\x8b\x8f\xd6\xf8\xaa\xf5\xae\xa25\xde\xb7\xe6)Y\xe3\x7fX\xb2g\x8d\xc9[\xeb/(:\xfc[\xd4P9=>X?}\xb7\xe4\x8d\xa5\x92\xad5\xe5\x9b\xb5\x9c\x9d5Fbru\x92\x7f[\xaf]Y\xe3\xd7\x96\xdaf\xd6\x16\xe7\x1a\t\xaf\x8b\x85\xb5\x06\t\x96\xe1I\x1e[\xf3L\xac\xf5\xfc\xb2~;\xb5\x9e\x0f\xac\xf1\x12\xd7\xfb\x93<\xb4\xe6\x1fYk\x8e\xad\xdf\xf6\xac\xdf\xf6u\xfc\x80\x00\x19\x10A\x03\xdcz\xa0ac\x06\x84\xe3\x00>3 2\x07D\xe6\x80\xd8\x1e\x10\xdb\x03\xd8\xc8\xc0\x02\x82\x01\xb9w \xea\xd9\x89\x08\xee\x0c\xe6\xaa\xd8\x01\xba\x19L\xf9\x19\x9a\x1c\xa0\xc8\x01\x807\x00\xf0\x06hq\x00\xd9\x1d\xf4\xd0\x89\xa5\x9e\x985\x80\xb4\x837\xd6\x00\x82\x0f\xf0\xae\x01\x19y\x80\xaf\x0c@\xf0\xc1\xf2cCf\x87Vw\xe8o\x87Vw\x98h\x87]vXk\x07a\xdc\xa1\xf6\x1d\xba\xdea\x81K\x012aR\x977\x88\x97\no\x97W<\x85u]\n\x17;e\xceK(\xda%\xc4\xed\x12\x16x\t7\xdcYV\xbe\x94-I\xba\xbcd\xa3\x97\xec\xee\xf2\\W\xb1\xc3r;l\xb4\xc3r\xbb\xbe\xea}\xd7C\x14s\x9dt\t\xb5\xdb-\xd0\x04>\xb5#)\xed\xe0\xb5;\x12\xd8\x0e\x84\xd8Q8\xec0\xe2\x8e\xe4\xbc[2\x00?\xb9\xc4#\nl\xb3\x80\xe5\n\xa2\x12![\x05\x81G!\x1e\x05AP)\xed\n\x02\xac\x02\xfa\x85\x80\xa75\xc5\xba\x02t\xad  )\xc5l\x01jW\xe8"\x86\xbcB\xd0RrR\xa1\xc5+\x08\x9d\xc2X\xd5W \xbd\x17f\xba\xcd\x82\xa8Z\xd2N!Q\xf5\x15\xdeU}\x85\x83\xc6@a\xa5\x01U\x10\xa5\x9e\xd8\xee@\x9fN 4\x06,3#\xd5\xaf\x01\xc9\x0c$\xc5\x10\xa8\x13\xe0y\xb2\xd4\x1dO0\x96I\xd5\x16\x93\xadnh\x82\x85\xcc/f \x1f\x18\x06L\xc6\xba\x9c\t\xc8c\xc8\x17\x13j\x8c\xc9L}}\x92\xea\xd2\'\xe2\x88#\x11\xd9\xd0\x04\xaa5\xe9\xf1\xb3D]\xd9\x90\xce&#\xc6\x0e\xd9[\x11\x9d\xf9\xe8\x97dj\xc8\xa5\xc6\xd3\x080dRSP\xbb\x99\x1ac\xeb<%\xf3\x9b\x00\x9d\x91\xf7\ri\xdf<2/I\xdf\xc0Y\x0c\x94\xc5<1\x03\x84\xc5\xc0W\x0ct\xc5\x84,\x07\xb2b\xe0KO\xb2\xb7\x9ah\x07\xf43\xaf\x19uv\x039\x7f\x12MI\x1d\xf3$k/\xc8\x80\x0b\xc5.s\x06\xe6=\xc9\x9e\xa58\x99\xb8\xea\xd7\x13"yr\x81\xed\x01\xb7\x89\xbcN\xb2\xd9\xc4\xe8l\x7f\xcah\x85|\xc3:\x9fp\x89\'0\xefi\xa2\xa29\x81\xe9\xdf\x15\xa5j\xc7\xc9\xe9\xb9\xbc&Gc)\x87\xeb\xe6@\xe4\x1c8\x9d\xcb)\xde\xe6\xc0\xf4\x1cew\x8e\x04\x90#-\xe4.u\xc99RHN\x12\x8b$\xa1\x1cj\xc9\x01{9\xf8w\x19L*\xd3\xf2*S\xf5\x95\x9fxJ\xff\xac\xdcb\x00uc\xb9\x82\xd8`\x00Uj\xb9\xce\x0c@d\x19\x88,\x1f\xd4ve\xca\xb4\xf2\x04\x11RR\x8e\xd5\x1ce*\xab\xb2m\x992&-\x7fV\xfd\x94/\xac\x11(\xa8\xec\xaac\x95\xb5\x92\xfd\x13VZ\xdf\xfeG\xb4\xd2\x16Q;d&\xf3\xcd\xe8l\xaf\x19\xcb\xb52\xce\x87k\x99\x8c{\x14]\x11\xcf\xcd\xc7\x0b\x17$8\x8br.\x00\xbf\x05yqA\xb6\xb4\xe8\xec\x02\xb6v"\xb3\x12\x86\'\xaey\x12\xa1R\'\xa6y\x1aKM\xba@s\'\xea*\x00qb\xae\xa7\xa7{\x9e\x92N\x17$\x97/\x04\x96E\xd2-\x8enQ\xf4\x05I`AA\xbe \tX\xf4\x7f\xa1t\xcedv\xe6o\xf8\x98\xcc\x9b\xf9;\xc0d\xb6\xe6\xef6Mf\xf3\xa1T\x93Y#\xae\x18\xfb\xdb\xfc]\x8e\xc9,\x8d\xce{`\xc0\x88\xa7C\xf3Wg&\x93\x98\xbf+3\x7fx\xb6\xce\xdb?\x8a3\x11{\xcc\x1b36\xe5\xe9\xe2\x8fh2\xe6(\xce\x99a\xc6\x0c\x13\xf3\xd7\xf2&3f9\x1dv\xfc\xc4\xd3\x16O#\xdc\x08&\xba\xb8\xc0-\x9bFm\x01\x81]\x00\x88\x0b\xc3\xd8\xae\xbe\xe2T!\x9f\x94\xea\x1f\xc5\xbd\x88E\xb4S@\xcc\xb3M\xcf\xa8{~g\xde\x80\xf56\xf8Y\xfdc\xac\xc9\xd4\xcc_\xe72\x99\n\xda)\x7f\x8c\xcd|eo_\x1du\xb9\xaf\xf4\x1a\xbeZ\xe1\xfe\'Gj\xac\xd6\x8f\x1b\x15\xbdg\xea\x8e\xe6\x9c:\xd3\xd5\t\xfc:\xc8X\x07%\xea\xf0\xf7\xfa\xe9%\x1d\x91\xe9l\xd7\xc9\x12u\x89>\xe9\x82\xd7\x01\xab:\xb5G}\xc3\xc4+D"\xaa\x0e\x08\xd6i\xf6\xd5\x0b\x9a\x0e\xeb4\x06\xeb\x02\xa3\xc2\x1e\xeb5\x05\xad:8[o(\xce\xd6+\xec\xbe\xcd\xcf\x9a\ne\xf5\x88\xe5\x90\x0c\xce_9[X[\x95\xc3\x1aD]S\xca\xac\xd1\xd59f:G\xdb\xe7g\x0c \xf9\x9c\xd3\xeeYgu\x99k\xcc\xb1f\x865\xf6ZS\xf1\xae\xf1\xe7\xb5z\xb9Yg48\xce\x1f\xf4\x15\xdfu2\xf3\x9d\x01\xdfA\xec\xccwG\xcd\xbc\xc62k@kM\x07y\r\xc0\xad\xa98\xd6t\xdd\xd7\x18\x7f\r\xd6\xad\xa1\xab\xeb_\x8a\xcdk\xe0\x7f\r\xb5]\xc3\xf6\xd7\x00\xfd\x1a\xf8_\x93\x14\xd6}\x85\xdeu\x8f\xa7\xb4\xb9\xd7#\xd6\x0b\xd0\xaf\x81\xff55@H\xb9\x15&\xba\x86P&\x93f[\xc8\xca\xc2\xb1\xbe-\x94]\x08\xa7\x0e\xe1\x07!\xdd\xa0\xf0\tQ\xb8\x84\x90\xa3\xb0\xa9\x8e\x1dBAB(H\x88[\x86\xf4\xccC\x02&\xfc\xa1\x8e\x1dz\x1a0a^}<\xa49\x15R\xb0\x85\xb0\x91P\x02F\x90#\xa4\xb8\x0b\xe9\x99\x87\xd4\x84!\xce\x1e\x12\x02!\xbd\xd2\x10\x18\n\xc5\xa3\xaeD\xc4\x81C\xf1\xc4\xbc\x888{\x08\xf6\x84\xa7\x88\x93pH(e\x12J\x99$Us&\xd4\xd4\t\x0c5\xa1\r\x93L\x15\x91\x12|.I\xd4\xc8\t| !\xf3\'\x94\x7f\tT+\xe9+\x16$\x90\x8b\x84pI\xf6\x0c\xe0\xb0.\x81\xcd%DC\xb2C$\xf3\'\x84VB\x01\x99\x10\x86\tgf\xc9\xcf\xa3(\\7\x01,\x12t\x9d\xa0\xe0\x84\xfeY\x02\xedO\x80\x90\x84\x92$!\xc5$\xd8;\x01\xfd\x12L\x7fA\xa1\x92\x9c\x0c\'S\xec\xa1w\xfb\x89jjO3dO\t\xbf\'\xa8\xf7\xf0\xb4}\xac\x10\xb2O4\xf8\xf6\xa2\xebO"\x82<{\x94\xb6\xa7E\xb2\xdf\xaa\xc7\\\xd1\x1d\xdd\xa3\x93=\x9a\xda\x8b\xfe$\x87\xedE\x11R\xaf\xecU=f\x8f\xd2\xf6\xec~om\xf9\xeaR\xadqE=rE\xa3\xeb\x8a:\xe7\x8a:\xe7J\xea\x9c{\x11\xa9s\xae\xa8\x94\xae\x04\xc5\xafE$\xbf\\\xd1l\xbb\xa2_u\xc5\xe6\x8a\x12\xca\x82\xe7\xc5\x9a\xc6z\xb1\xae\xb8P$\xc0\x8b`H\xb1\xa8\x10Q\xf4\x15N\x8ad\xe5"\x80T\xa4<*\xb6\x15\xc7\x8a\x1c\xa0\x15#\x85\x93"\xed\x87\xe2D-[\x84P\x14c\x05\xd0"\xa7\x87\xc5\xad\x1a\xaeH\xfe)\x9e\xd4.(S\xb4\xb6\xac\xf64\xc5\x8cr\xb2"\x14\xa8\x88\xbb\x17\xf1\xe6\x8e\xaf\x88\xd4\xa1r\xefp\x9b\xa1C=\xd7\x81rt\xd0_\x87\xf6X\x87\xc2\xb7#\xbb\xff&"-\xafN\x131Q\x07\xed\xd01\xec\x80n\x1d\x1a\x82\x1d\x02\xaa\xa3\x8a0\x1d\xd0\xb6\xe3\xb02\xee\x85t\xb8\x17\xd2\xb1N\x1d;\xec~\xcb\x81\xdf/p\xeaZ\xbc2\'O\'\x1a\x1a\xbf\x12\xb5\xdc/Y\xb0T>\xbfR5\xd7\x1d\xfc\xe6\x8e\xe0\xba\xc3Dw\x04\xc9\x1d\xa5\xfc\x1dArG\xe8\xdc\x11$w9\x8d\x81;\t\x129\x0e\xbb\x93EJ\x82\xb9\xa3\x9dp\xf7E\xc3\xa1\xc5\xed\x8a;\xab\x81F\xeb\xbeb\xc5o\x05\x9dT@\xbd\n\xc0ZaG\x15vT\xc1\xa7*\n\xa1\xa6\x92\xf9(r2\x95g\xf4^\xe1\xeeH\xa5\xc9\xefH\xf7\x95\x10\xb1\xad\xc1S\xc1\xa9*O\xea>\x95\x8a\xee\xb9R\xd7\xf0\xabp\xdf\xa6\x12\xa8\x87V\xc4\x85\x7f\x88\xc8\x8d\x9dJ\x81\xc9\xf2\xea(\x15\xc8E\xa5\xc8\x80\x1f\xac\xa1\xc4S*\xe4\n9\xaaB\xa3\xb5B\xc2\xab\x08\xceK\xbb\xadB2\xaf\x88\xf7\x08\xa2WH\xe6\x15\x12Ae\xa4\xc8Q\xa1\xd7\x98\xa5\xb0\xce\xaeu\rY\x8a\xf0,\r\xd1,\xb6\xf7\xb0a\x16\x92\x90\x85\x82f9O\xce\x92\xad\xb2\x9c\xa8e\xa1$Y\xc8f\x96s\x80,\xa1\x9c\x85E\\\x8b\x01\xe4\xf8?\x0b\xad\xcc\x82\x0b\xd9H\x8d\x95m\xf26i;\n^g\xe9@e\xf1\x87lU\xed\x96-3\x96.h\x96r(+\xfe \x80\x9e\xad\xf1b\n\xaa,\x9d\xd8l\x81\x9fy\n\xb6\xd9\x92:W\x96\xcb\x1c\xd9"/\xf6\xd9\x85\xc4\xf71\xb1\x99\xe3!\xb3\xc6@jUT\x0b\xfbv\x13\xa7*\x9eL\xf8$\xa3\x89\xb4\x94PL1c\n\xb1I\xc9\xd1)Q\x99\xd2\x01H\x89\xeb\x94hO\xc9\xe7\xdf\xa8\xae\xbei\xae5\xdf\xa8\x98\xbeQ\xcb}\xb3\x96#\x9e"\x97`R|8\xc5SR\xf1\x1fa0)EP\xfa\x0b\x11\x0fL\xc7\x1a\x10)\xa7\x85)\xae\x9f\xd2\x92O!\xafi\x9f5\xd0\xbeOi\x87y\xa1z`\n7M\x0f\xea\xb8\xe9\x9e\xc9\xe0\xa6\xdf\xacb8%\x1b\xa7\xc4u\xca-\xa3\x14r\x9a\xc2\xc9R\x98Z\x83}6\xe8f6h&4\x92\x8f\xa7\xa6Erk\xf0\xe2\x06i\xb7\x81\xef7\xa08\r*\x9b\x06\xd7\x85\x1a\xa4\xf3\x06d\xa6Am\xd4\xa0\xbaj\xf8\xfc\xec\x07O\x9f\x11\xe1@\r\x9a\t\r\x88O\x03Do\xb4\x18@\x0f\xa2\x01\x8c7:\xec\xc2J\xd1\r\\\xbcA\xc9\xd4\xb0\xda\xb7\x0b\x92m\x03\x8e\xd3\x80\xb36,\x05\xe2\xee\x0bk\xe2\x93me\xff16\x88\x01\xdf\x18W\x8aa+1n\x17\xe3\xa2\xf1P\x8d\x14c\xe6x\xccX\\?\xc6\xf5c\xc2$&-\xc4\x80o\xbc\xd0\xe0\x89q\xaax\xc9\xdb\xc8<\xf1\x8a\xb1\xb0\x99\x18g\x8d9(\x8f\xa9\xbabJ\xb8\x983\xc0\x980\xb9\x82\xac,\x80\x8b\x05Zm\x9dTy#\xbf\x03|b(A\x0c:\xc5\x90\xf7\x98c\x9c\x18\xc3\xc4\xa0^\xcc;b\xe0+\xb6\x88\x8b\xebk`\xbb\x9c\xc0\xb9\x9c\xb5\xb9\x82\xda\x92O\\\xf1}I\x85.G\xb6n\x9e\xb1u\xc4\x1a?\xe3\xac\xcd%\xa6\\\xb2\x8c[\xe6gD\xa5\xfb\xc8+\xda\xea\x11.\'p.gm.w\x86\\\xce\xda\xdc&\xf3r\xd6\xe6\x86\xfa\xd4!\xc5\xba\x9c\xc09\xdc>q)\xf5]2\x8ck\r\xa0#\xe4\x12\x03.g\xba.\xa5\xbeK\xa9\xba\xd9\xf1\x94\xbb4.Wl\\b`\x83\x83\xba\xdc\xa3q9\xecp\xc5W\x85\x1a\xb9\x90\x95\r5\xb2\x8b\xaf\xba\xc4\x80\x0bww\xd7h\x12\xf6\xb5\xe1\xfe\xc2\x86\x1do\xe8vm8\xe1s9~\xdap\x14\xecr\xd8\xe1\xda\xa7K\x1b+s;\xd6\xd5f\x1a\xe0\xaev\xd33\x1bBf\x83;\xbbV\xf7\xd1u1.a\xe0f\x99\x98\x88\xd80`\xe3\xa2,x\xc0\x86H\xdb\x90\xd07\xf0\x80\r\x01\xea\xa0\xee\x11\x17\\G4\x17#\x16\x1c\xb1\x8d\x88P\x8ch]E\x16:G\xb24\xc92\x11\x0b\x8e\xe4\xcdB\x1a"\xbd\xc8o"\x80::\xe9\xb5$\xf2A\x8d\x13a\xf4\x88l\x1a\x01f\x11\x1d\xd7h\xc3\xd8\xa9*0\xa2=\x16QKF)K#\xcfG@r\x84\x0fF\x84D$\x81"\x146J\x18\x10)4DT\xb9Q\x07Q@@\xca\xeb\x88\xcb\xb7\x11\x17u#\x92{TV\x18\x89\xe8JF\xa0OTg\x00\xd9?\x82\xb7Fy\xe6\xf5\x18Ku3\xc4\x9eC\xac<\x14\xd3\xca\x9d\xcc!.3\xc4e\x86\xda\x1e3C<mH6\x1eb\xef!$q\x88\x07\x8f\xf0\x9e\xa1\x15GC\x02w\x08b\x0c\xe9h\r\xe9h\ri\xb6\x0fi\x97\x0ci\x9a\r\xb1\xcb\x10\xee8\x04\x94\x86\xdc\xe4\x1f\x02kC\xcd\xbbf\xc4\xe6\x1c\xa9\xb4\xa5\xfe>\xb0\xcf\x03\x9b;\xb0\xe5\x03\xfb<\xa0\xb4\x03\xaa<\xa0\xbf\x03\xaf8`\x81\x03v9\xa0\xa9\x11o\xbb\xa63p\xcd\xd5\xafk\xdag\x07K\xab\xd7\\\xfb\xbf&\x8b_\xd3r\xb8\xa6\xe5pM\x1b\xe1\x9a\x0e\xdc\xb5\xac]: \xd7\xec\xf3\xda\xda\'Z=PU\x1e\xe6\xfa\xb3\x03\x08y\xa0\xbds\xe0`\xe3@\xf7\xeb\x00\xf8\x1e\xc8<\x07\x0e+\x0e\xc0\xf7\x81\xabI\x07\xa0\xfe\xb0d\x06\xfc\xe8@\xff\xec\x00\xe8\x1d(\x93}\x0bz|\xd0\xcbg\xcb\xbe\x85o\xbe\xc2\x9e\xf1\x81/\x1f\x8b\xfb\xdc\x88\xf7Aa\x1f\x83\xfaX\xdc\xa7\x7f\xe1\x13\xcb~\xa0p\xe1K\xdcK\xe9\xea\x83\x11~Y\xd1\xc0\x87u\xf8\x12\xe1/"B\xea}>_\xf2\xa9b}j\x01\xbf\xc0\x0cy\x96\x0e\xd5\xf7\xa5\x00\x10\x92\xed\xbf\xf0bN{\xfc\x0e?\x83\xdf\xfb\x94\xf0>=\x1f\x9f\n\xc1\xa7\xe7\xe3\xd3"\xf1q\x19\x9f\xfbZ>\xc7L>W\xe3|\xf1\x08a\xbd\xbex\x84d.\x9fF\x84Oq\xe8\xe3S\xfe\x9e\xb7Au}\x9af>\xd0\xe3C@|r\x91\xbfd\x91\xe2i\xbfE\xa47\xf3|\xf2)1\xe73\x01\xf3\x8co<\x8b9\x9fE\xa4_\xf5La\xf6\x0c\xbd}~V\x13\xfd#\x88$\x14\xfa\x1f.\xc5?\x8b1\xa4)\xf1\x0c\xb3\x99Zh0\xe5lc\x8a\xafN9?\x9d\x02ISh\xfa\x94\xb5O\xc1\xa1)\xa11\xc5\x99\xa7\xc0\xd7\x14o\xbfg\x86{\x1a\xf6\xf7\xf4Y\xef\xef\xf4m\xf79]\xef=Pw\x0fN\xdd\x83^\xf7|\xe0t\x0f\xd2\xdd\x0bzIk\xf4\x1eL\x9bb\xfb)\x1f\xd5Ma\x86\xd3\xa1b\xc4\x14\xc0\x99\x02oS\xe0mJG\x7f\n\xeb\x9d\x92J\xa6P\x87)04\xe5\xb6\xea\x14\xef\x99\xc2d\xa6$\xb9)e\xd9c\xa0\x0e\xf1\xe8+L=J\xf8J[\xf3\x99\xf3\xd5GV\xf6(K\x17\xa2\xf2\x88C<ri\xf4\x11k>b\xa1,*1\x0c\xf8\xafM\x80?c\xf0\xcf\x18\xfc3\xa3?\xe3\x1c\x9f/x\xca\x8d\xa1\xcf\xa0\xe2\x92\x88Y\xa2\xaa%Lo\x89~\x96\x1bDBu\x89\xaa\x96\\D^\xd2\x96\xfcl/~I\xd5\xb4D-K\xd8\xe2\x12;/\xb1\xfe\x92\x84\xb5D\xc7K>\xbf\\b\xfd\x1b\xf2\xe7\xd2\x8a\xbf%j[\x12\x1cK\xd8\xc1\x92\xfe\xc5\x92P\\\xc2:\x96\x98i\x89\x8a\x97(\xfe\x86\xa7\x01c\x03W!\'\xb0\x06h\x88\x9b\x80,\x16\x80\x0c\x01\x9d\x95\xe0\xb4\r\xf1\xb6\x806_@\x9a\x0fh\xf3\x05c\x8d\xe6\x00\xfa\x15\xd0Y\t\xf8\x10"\xe0\x849\x80\xd6\x05 n@\xfb+ u\x07DR@\xc6\x0f$P\xaa"rn\x15\xd4\x11\xb9\x04\x10Ty\xca\xf5\xc5\xa0\xac0\x1cH\xd2\x14\n\x1d\x94\x18\xcb\xd7\xb2\x01\x07\x04A\x01M\xf1\xe1l\xe0\xf1TR\xa9\xa4\x82\xa0\xc3+\xc8\x94\x01\xb7\xc1\x03:\xdc\x01UE\x10\xaaO\x05Z`\x98\x1en\xd2\xe3\x10\xbb\x87\r{\xd8\xbb\x87\x9b\xf4\xf0\x8d\x1e\xde\xd5\x83\xfd\xf7\xbe2\x16\xaf\xed\xbd\x02v\xbd\x81Z\xa0\x07\\\xf6F\x0c\x80\x8f\xf7z\x0c\x00\x18{TZ=\x82\xab\x97j\x18\xf5\xc6LF \xf6h\x9f\xf56\n\x97=\xdc\xa4\xf7\xc6\xcap\xa9\x1e\x05F\x8f\xa6m\x0f\xe8\xb8\xb0Ab{\xfaC\xc0\xd3\xa13ra5)\xb7\x84\xf0\x05J\xbe@\xc9[\x14wA$]X7E/2\x1c\rl\xad\x1f2\xdd\x96\x8b}[\x8e\xd5\xb6\xd8w\x0b\xa6n\x7f\xf2\xbe\xba:\xcbE\x11\xd1G,!\xfe\x97=]p\'\xec\xa2\xa3\xe2\x16%m\x856\t\xff\xd9\nmz\x17\x91\x8b\x9c[\xda\x8d[\x94\xbf\xc5$\x17\t\xf3\x02\xf7[\x92\xc0\x16\x1e\xb8\x05S\xb6|c\xbe\xa5\'\xba\xe5\x90xK\x83uK\xf9\xb7\xa5\xed\xb5\xe5\xde\xfeVPI\x9aV\xdbX]hK\xf1\xb1\xed)\xae\xb5\x0e\xba\x9c\x16m/\xcf\xeaA\xb6V\xaa\x93{\x0b\xed[\xb4\x17Zd\x94\x16I\xb9ES\xb9\x05]\xf5\x08\xe3\x960\xedc\xef\xdbx\x1c\xc3\xb4\xba\x8a\t-\xb1\x91\x90\xf9\x96\x80\x86\xd4\x0b-\x81\x12\xa9\x17<q*\xb9l\xdd\x82t{\xe2T\xc2*[\xfc\xb3\x82\x16\xa7\x04-N\xc8Z\x94\x19\xad\no\xa3\xa0hq\x87\xbf\x05qm\t\xf4\xc9)\x96WPP\xf6\xf2\xac\xc1\xfa\x19q\xe2q\x19\xc3\x13\x0f\x15\xa6\xe3Uto\x1e\xb7\r<\xaa\x1e\x0f\x84\xf7X\xba\xc7\xb1c\xcb*\xde\xbc\xa6\xc6\xa2\x17\xb1`\xce\x19<\xa0\xd8\xa3\xc0\xf1:<}\xd2\xdd{\x94H\xde3O_P\x8f\xa3\x9e\xdf"j\xbd\xbeb\xa3\x07/\xf5\x06\n}\xde\x08\x91\xa3\x05\x0f\x14\xf4\xe8cyP\x97\x16\xf7\xe8<\xd0\xd5\xe3h\xc1#v<J\x19\x8f\xa3c\x8f\x98\xf4V,\x92\xf3\x04\x8f\x00\xf7 f\x1e\x9f\xe3y\xf4R=>\xfc\x1c1\xd6\xa1\x976\x82\xef\x8e\xacf$k\x18\x81\x0b\x0e\xa1\xec\xf0\xbd\xbeC#\xd9\xa1\xbd\xecp\x99\xd2Ag\x0e\xd9\xcb\xa1m=\x02\xdd\x1c(\xdc\x88\xb3\x9d\xd1P\xb53"\xd3\x8d\xe8D8\xb0\x15\x87\x96\xc2\x88;\x98\x0e-n\xc7R\t\xc7\xed#\x8c\xe5\xf0\xa5\xd1\x88\xa5\x8f\xc6\xea\x04\x0e\x07\xd5\x0e\x9f\x0c9\x1cn8|t\xe4p\x10\xe2p<\xe2\xf0\xb9\xaf\xc3\xd7\xc1\x0e\xdf\t9|S\xe4p\xce\xe1\xf0\xfd\x91\xc3\x99\x88\xc3\xb7J\x0e\xe7\'\x0e\xdf\t9\x9c]8|S\xe4p\xce\xe1p\xfa\xe1p&\xe2pR\xe2\xf0\xad\x92\xf3\xc2+\x9e\x99\x8c\xd3\x8f\x11\xe1\xe4H>\x94v\x80c\x14+\x1c>\xffv\xfe\xf5!\x1a\'ct\xb2\x7f\x8eO\xa5\xdf\xe7\xc8\x89\xb7\x90=\'\x8b\xc8\xb5\xbf\x11\xd5\x8fC\xfev\xa4B\x95km\x0eu\xab\xc3\xb7\xec\x8e\x94\xbbR\x04\x8f(\x84\x1c)w\x856;R\x04Ki<\x82\xaa9R\xcd~\x11\x91\nc\x04\x81\x1bY\xe9\xe7\x1d\xa2\xf5N\xbd\xf2N&z\xc7\xbb\xde\xb9d\xf8\x0e\x1f\x7f\x87\xa5\xbf\x13#\xef\xef\x1a\xb2\xef\x94`74\x9b\x1cB\xf6f\xa0;z\x87\xd3\xbc\xbb\xbc\xcd\xda\xdcZ\r\xf7\x0ef\xbe\x83\x99m\x0e|\x1c\xf0\xea\x86\n\xff\x06]\xdf\xd0#\xb8\xa1\xefyC\x8f\xe0\x86/\xacnh\x9d\xde\xd0P\xbd\xa1\xf7pC+\xe4\x86\xf5>nu\x17\x0eHZ\x12\xbf\x17\xe4/\xd1\xe5/\xd1\xfb/q\x03\xa9D7\xbeTR\xff,q\xd7\xa8D]R\xa23X\xe2\xba\x7f\tU\x97\xb0E\x89{\x0f%\x0c[\xe2\xf3\x84\x12Ek\x89\xa3\xe6\x92u ^\x82\xaf\x96\xc4\x02R\x14\x948\xed)\xb9\xcc\xc6\x8d\xbb.\xed\xc9.]\xcd\xae,X\x9a\x80]z\x16]v\xdf\xa5\x90\xea\xc2R\xba\xa2\xbfS\xce\xee\xd28\xee\xe2\xa0].\x83t\xed\xcfA\xce!K)\xd0|N\xa4u\t\x99\xae\xab\xf6\xe8\xe2\xa2]\x8b/t\xf5\x03a\xd3\xa5L\xeeBZ\xba\x14\x02c\x9e\xce\xa8|g\xe4\x92\x19\xb7\x07f\xe4\x92\x19]\x8bY_w:\xa3\xee\x98Q\x1f\xcd\xb8:2\x9b1\xc3\\\x83c\xcd\xe6f\x84\xf8\x0cE\xccH\xc53\x92\xf9\x0c\x7f\x9e\xe1V3R\xf1\x8c+\xd93:\xa63\x90\xe1\x9c/\xd8g\x00\x91\x99Q\xa2\xce0\xc1\x8c\xae\xc7\x8c\x18\x9f\x11_3\xac1\x03Zg\xd6\xe6P\xfb\x0c\x18\x9ea\x81\x07&{`\xb2\x07y\xb1$\x93\x87\x07\x9erq\xf2\xe1Zq\xfa\xe1F\x01\xf7\x81\xcd=\\\xf1\x14\xecx\x00Q\x1e\x04;$\x83<\x08\xa2H/\xb2\xea|\xc4\xb8\xa9\xe2GUb\xaaj9]\x95\x05W\xd9Q\xf5\xa4V\x89\xaaj\xacJ\xa9R\xefT\xb1x\x15\x86X%\xca\xab\x90\x8e*uK\xd5\xd7x\xaf\x12\xc3\xd5\x9a\x06n\x95\xb8\xac\x86\x8aUU\xae\xe5U\xb9\xb1Y\x85\x13\x9f\x91\xc4\xcf:\xfa\xe2\xb3\xa6\xae\xec\x0c\x1ap\x161\x00\xd2q\xc6\xbf$;\xcb\xeb\x80\xefv\xad~\x86{\x9cQ\r\x9f\xd9C.\xf1\x95\xdfh\xb6\x85\xf8\x9b\xff\xfe\xd2\xa4Q\xd0\xdc \xc2T\x9b\x07u\xdd&`\xd4\x14#\xc8\x19@\x13\xf6\xd9\x9c\xa8\xb75Sf\x00\x80\x9b\xdc\x82lF\xaa\xcd\xa6hH0\xbe\xd9A$\xa34\xf9\xf8\xb6\xd9U\xfcmr\xa2\xd3\xa4\xbejr7\xb2)\x8a\x95z\xb0I\x1ai\xd2\x15kr\x81\xac\xe9\xf06"\xa9\x89\xce\x9a\x94LM\xeb\xf8\xac\xcf\xc7\xab\xfd\x89j\xb5\xcfU\xa8>t\xa4\x0fI\xe9S\x15\xf4\xa9\xc9\xfb\x16HR\xe6\xf4\xb9\x98\xd1\x07\x7f\xfa`U\x1f\x04\xeb\x93\x9c\xfb\xd8\xb0\xbfa26\xd7\'\xab\xf5\xd9g\x1f|\xeaS\x9c\xf7\t\xcb>\xf0\xd3\xc7\xd1\xfaV\x8b\xe0\x8d\x1d\xbd\xd1s~#X\xdf\xf8\x94\xfc\x8d\xb5\xbf\xb1\xe07\xdd\xa7y\xcb\x18\xfd\x19k\xcfc\xf0<\xdfB\xe5\xa9\xb8\xf3T\xc6\xf9@a$O\xb8\xe7\xdb\xcc\x00\x8d\xc9\x13\xf9y\x02;O\xea\xcd\xd3\xe7\xcb\xe3\xd7y6\x94\xe7\x7ft\xe5\xe9\xd2\xe5\xe9\xe0\xe6\xb1\xe1F\x9b&&\x0fH\xe692\xcbc\x97\xbc\x85\x97yL\xd0fD\x1b\xf5\xb4\x15}3#,\xd7\xde\xe8z\\\x98q\x9b\xfbDm\xc9\xab\xc2\xfd\xda3\x1d\xdb\x06D7\xd6\xcf\xba\n\xa2m)S\xe4\x18\xb6M7\xb7\xcd1M\x9bo\xdf\xda(\xb8\r\x18\xb4\xeb\x1a\xa9m1\x9c\xb0\xc7\xb6\x18NZ\x1am\xba\x1bmxb\x9b\xeb\x9b\xed\xa2\x86r\xfb\x87"@\xdbS#\xb7i\xcc\xb4\xf3\x1a\xcac4\xf9\x89\x1c\xfd\xc9\xba\xaf4\xe6\x9e\xd3\'\x98\xd6\'2\xf3\'\xeb\xbf6|\x02\x9c\xc7\xf0\xe81\x86\x19c\xae\xb15\x96W\x8f9\x14\x19C%>\xd9\xf0>\xb6\x0fY\x80\xe41~5\x06\xd4\xc7\xc0\xc4\x98\x92b\x0cL\x8c\xe1Gc\xf8\xd1\x98o#\xc7\xf4\xa5\xc7\xb0\xea1\x1cm\x0c]\x1ds\x9bjLwaL\x95:\x86\xad\x8f\xb9\xc60\x16\xca(g\xdd\xe3\x01\x1b\x02\r7P\xc6[J\xa0[\xa11\xc2<n\xa1&\xb7P\x93[\xbe\xbc\xbd\xcd\xa99n\xf9\xc7\x11\xb7\x14Q\xb7\xfc\x93\x89[\x8a\xa8[Lw\xcbY\xee\x85e\xf2[<~\x04t\x8e\xfeZ\xf4\xff\xfe\x1f\xfa\xddI\x97'))
global t
t=' '
def f(k):
 global t
 r=a[t+k]if t+k in a else'e';t=k
 return r
```
[Answer]
## Haskell, (1904 + 1621 + 208548 + 25646) \* 2 + 371705 = 847143
```
{-# LANGUAGE FlexibleInstances, DeriveGeneric #-}
import Control.Arrow
import Control.Monad
import Control.Monad.Trans.State
import Data.List
import System.IO
import Data.ByteString (ByteString)
import qualified Data.ByteString as BS
import qualified Data.ByteString.Lazy as BSL
import qualified Data.ByteString.Char8 as BC8
import Data.Ord
import Data.Char
import Data.Monoid
import Data.Maybe (fromJust, catMaybes)
import Data.Function
import qualified Data.Map as Map
import Codec.Compression.Lzma
import Data.Flat
import GHC.Word
maxWordLen :: Integral n => n
maxWordLen = 20
wordSeqDictSize :: Integral n => n
wordSeqDictSize = 255
predict :: [Trie] -> Char -> State ([Either Char Int], String) Char
predict statDict c = do
   (nextChar:future, begunWord) <- get
   case nextChar of
     Left p -> do
       put (future, [])
       return p
     Right lw -> do
       let wpre = begunWord++[c]
       put (future, wpre)
       return $ trieLook (tail wpre) (case drop lw statDict of{(t:_)->t;_->Trie[]})
newtype Trie = Trie [(Char,Trie)] deriving (Show, Generic)
instance Flat Trie
trieLook :: String -> Trie -> Char
trieLook [] (Trie ((p,_):_)) = p
trieLook (c:cs) (Trie m)
 | Just t' <- lookup c m  = trieLook cs t'
trieLook _ _ = ' '
moby :: IO (String -> String)
moby = do
    approxWSeq <- BSL.unpack . decompress <$> BSL.readFile "wordsseq"
    Right fallbackTries <- unflat <$> BS.readFile "dicttries"
    seqWords <- read <$> readFile "seqwords"
    let rdict = Map.fromList $ zip [maxWordLen..wordSeqDictSize] seqWords
    return $ \orig ->
      let reconstructed = approxWSeq >>= \i
             -> if i<maxWordLen then let l = fromIntegral i+1
                                     in replicate l $ Right l
                                else Left <$> rdict Map.! i
      in (`evalState`(reconstructed, ""))
              $ mapM (predict fallbackTries) (' ':orig)
```
Example:
```
Call me Ishmael. Some years ago--never mind how long precisely--having
 ap  me ,nhmael.  Hme ?ears |ce--never  usd how long .aacesely--|ubing
little or no money in my purse, and nothing particular to interest me on
little or no ?ivey in my ?efse, and ,uwhing .hrticular to Bdaenest me on
shore, I thought I would sail about a little and see the watery part of
?neae, I thought I would  cfl about a little and see the |rkers part of
the world. It is a way I have of driving off the spleen and regulating
the world. It is a way I have of ,uiving off the |kli   and .ia       
the circulation. Whenever I find myself growing grim about the mouth;
the Ca         . B        I  rtd |yself ,haoing  eom about the ?ivlh;
whenever it is a damp, drizzly November in my soul; whenever I find
Baieever it is a  'mp, ,uiv    Bar      in my  cfl; Baieever I  rtd
```
Uses three pre-computed auxiliary files:
* `seqwords` contains the 236 most common words.
* `wordsseq` contains an LZMA-compressed sequece of these words, and for all words not among the 236 most common, the length.
* `dicttries` contains, for each word-length, a decision tree that contains all remaining words. From these tries, entries are picked as we go.
This way, we achieve significantly lower error rate than all the other lossy schemes; unfortunately, the `wordsseq` file is still too big to be competitive.
Here's a completed version that creates the files and does the analysis:
```
depunct :: String -> [String]
depunct (p:l) = (p:take lm1 wordr) : depunct (drop lm1 wordr ++ srcr)
 where lm1 = maxWordLen-1
       (wordr, srcr) = (`span`l) $ if isAlpha p
                 then \c -> isLetter c || c=='\''
                 else not . isAlpha
depunct []=[]
mhead :: Monoid a => [a] -> a
mhead (h:_) = h
mhead [] = mempty
limit :: [Int] -> [Int]
limit = go 0
 where go z (n:l) | z<100 = n : go (z+n) l
       go _ l = take 1 l
packStr :: String -> Integer
packStr = go 0
 where go n [] = n
       go n (c:cs)
        | c>='a' && c<='z'  = go (28*n + fromIntegral
                                   (1 + fromEnum c - fromEnum 'a')) cs
        | otherwise         = go (28*n) cs
mkTrie :: [String] -> Trie
mkTrie [] = Trie []
mkTrie strs = Trie [ (c, mkTrie . filter (not . null) $ tail<$>l)
                   | l@((c:_):_) <- sortBy (comparing length)
                                  . groupBy ((==)`on`head)
                                  $ sortBy (comparing head) strs ]
mkTries :: [String] -> [Trie]
mkTries rsrc = [ mkTrie $ filter ((==l) . length) rsrc
               | l <- [0..maximum (length<$>rsrc)] ]
main :: IO ()
main = do
    orig <- readFile "whale.txt"
    let wordchopped = depunct orig
        dictRes
          = take 5000
          . map mhead
          . sortBy (comparing $ negate . length)
          . group . sort
          $ wordchopped
        dict = Map.fromList $ zip dictRes [maxWordLen..wordSeqDictSize]
        rdict = Map.fromList $ zip [maxWordLen..wordSeqDictSize] dictRes
        approxWSeq = [ case Map.lookup w dict of
                        Just i -> i
                        Nothing -> fromIntegral (length w - 1) :: Word8
                     | w <- wordchopped ]
        fallbackTries = mkTries . drop (wordSeqDictSize-maxWordLen) $ dictRes
        reconstructed = approxWSeq >>= \i
             -> if i<maxWordLen then let l = fromIntegral i+1
                                     in replicate l $ Right l
                                else Left <$> rdict Map.! i
        predicted = (`evalState`(reconstructed, ""))
              $ mapM (predict fallbackTries) (' ':orig)
        incorrects = length . filter id $ zipWith (/=) orig predicted
    putStrLn $ "longest word: "++show(maximum $ length<$>wordchopped)
    putStrLn $ show incorrects++" errors / "++show (length orig)++" chars"
    BSL.writeFile "wordsseq" . compress $ BSL.pack approxWSeq
    BS.writeFile "dicttries" $ flat fallbackTries
    writeFile "seqwords" . show $ take (256-maxWordLen) dictRes
    writeFile "whale-approx.txt" . unlines $ coLines orig predicted
coLines :: String -> String -> [String]
coLines [] _ = [[],[]]
coLines ('\n':l) (_:m) = []:[]:coLines l m
coLines l ('\n':m) = coLines l ('|':m)
coLines (c:l) (d:m) = case coLines l m of
   (lt:mt:r) -> (c:lt):(d:mt):r
```
[Answer]
## sh+[bzip3](https://repology.org/project/bzip3/versions), 2\*321,287+0 = 642574
Based on [this](https://codegolf.stackexchange.com/a/152931/61379) submission - except bzip3 manages to get a substantially better compression ratio. Building the file:
```
#!/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 | bzip3 -e -c >> $3
chmod +x $3
```
And the framework:
```
dd if=$0 bs=1 skip=50|bzip3 -d&exec cat>/dev/null
```
[Answer]
# C++ (WIP), 1923\*2 + 1017344 = 1021190
```
#include <map>
#include <random>
#include <string>
#include <type_traits>
#include <vector>
using namespace std;
constexpr minstd_rand::result_type seed = 10087702;
template<typename T>
class discrete_mapped_distribution {
private:
    discrete_distribution<size_t> distr;
    vector<T> values;
public:
    discrete_mapped_distribution() :
            distr(), values() {
    }
    template<typename I, typename = typename enable_if<is_arithmetic<I>::value,
            I>::type>
    discrete_mapped_distribution(map<T, I> distribution) :
            values() {
        vector<I> counts;
        values.reserve(distribution.size());
        counts.reserve(distribution.size());
        for (typename map<T, I>::const_reference count : distribution) {
            values.push_back(count.first);
            counts.push_back(count.second);
        }
        distr = discrete_distribution<size_t>(counts.cbegin(), counts.cend());
    }
    discrete_mapped_distribution(const discrete_mapped_distribution&) = default;
    discrete_mapped_distribution& operator=(const discrete_mapped_distribution&) = default;
    template<typename URNG>
    T operator()(URNG& urng) {
        return values.at(distr(urng));
    }
};
class generator2 {
private:
    static map<char, discrete_mapped_distribution<char>> letters;
    minstd_rand rng;
public:
    static void initDistribution(const string& text) {
        map<char, map<char, uint64_t>> letterDistribution;
        string::const_iterator it = text.cbegin();
        char oldLetter = *it++;
        for (; it != text.cend();) {
            ++(letterDistribution[oldLetter][*it]);
            oldLetter = *it++;
        }
        generator2::letters = map<char, discrete_mapped_distribution<char>>();
        for (map<char, map<char, uint64_t>>::const_reference letter : letterDistribution) {
            generator2::letters[letter.first] = discrete_mapped_distribution<char>(letter.second);
        }
    }
    generator2() :
            rng(seed) {
    }
    char getNextChar(char in) {
        return letters.at(in)(rng);
    }
};
map<char, discrete_mapped_distribution<char>> generator2::letters;
```
As it stand this solution is WIP and therefore ungolfed. Also considering that the actual code size barely has any impact on the score I thought I post my answer first before starting to micro optimize it.  
*(Full code available here: <https://github.com/BrainStone/MobyDickRNG> - Includes full program and seed search)*
This solution is based on a RNG. First I analyze the text. I create a map that counts the occurrences of two consecutive characters. Then I create a distribution map. This is all done statically so should be in accordance of the rules.
Then while trying to print the text I do a lookup and pull a random character of the possible ones. While this usually produces worse results than just outputting the most common following letter, there could are likely god seeds that will produce better results. That's why the seed is hard coded. I'm currently searching for the best seed. And I will update this answer once I find better seeds. So stay posted!
If anyone wants to search for seeds themselves or use different RNGs feel free to fork the repo.
Method used to calculate score: <https://github.com/BrainStone/MobyDickRNG/blob/master/src/search.cpp#L15>
*Note even though the total score is the worst at the moment, it beats the error count of just outputting spaces. And the chances are good that the score will drop, by checking more seeds.*
## Changelog
* **2018/01/24**: Posted inital answer.  
Checked seeds: 0-50000. Score: 2305\*2 + 1017754 = 1022364
* **2018/01/24**: Did some minimal golfing. Added link to score calculation method.  
Checked seeds: 0-80000. Score: 1920\*2 + 1017754 = 1021594 (-770)
* **2018/02/02**: New seed (10087702) (didn't find the time to fix the submission)  
Checked seeds: 0-32000000. Score: 1923\*2 + 1017344 = 1021190 (-404)
[Answer]
# Ruby, 1164418 (ouch)
I just wanted to see how well I could do without checking any other answers.  
I'm not sure if this is allowed because it includes a literal I generated via analyzing the file, but even if it wasn't it's not like it was in danger of beating anyone.
```
x="\"ect,htabsdd,in,\\nodniwlrfydbulkm;f?ckgwvi0,.*pr;\\\"uz17klI\\n-c'WSpA\\nTwqu8.77!-BeWO5.4.CoP\\n\\\"UHEFu2.?-9.jo6.NI3.MaLYDOGoOAR'QUECziJoxp(\\nYa:\\nVI);K\\nUS*IZEX\\n&\\n$\\n_y[S\""
f=->n{(x.include? n)? x[x.index(n)+1] : ' '}
```
## How I generated `x`
First, I generated `a.txt` with the following:
```
grep -o ".." whale2.txt | sort | uniq -c|sort -bn>a.txt
```
Then I generated `a.csv`:
```
cat a.txt | awk '{ print $1","$2 }'|sort -n|tac>a.csv
```
Then I parsed it into `x` with the following Ruby script:
```
f={}
File.open('./a.csv').each{|l|x=l.partition(',')
f[x.last[0..1]]=x.first}
n={}
r={}
f.each{|k,v|if((r.include? k[0]and v>n[k[0]])or not r.include? k[0])and not k[1].nil?
r[k[0]]=k[1]
n[k[0]]=v
end}
s=''
r.each{|k,v|s+=k+v}
puts s.inspect
```
## How I scored
```
w=File.read('whale2.txt')
x="ect,htabsdd,in,\nodniwlrfydbulkm;f?ckgwvi0,.*pr;\"uz17klI\n-c'WSpA\nTwqu8.77!-BeWO5.4.CoP\n\"UHEFu2.?-9.jo6.NI3.MaLYDOGoOAR'QUECziJoxp(\nYa:\nVI);K\nUS*IZEX\n&\n$\n_y[S"
f=->n{(x.include? n)? x[x.index(n)+1] : ' '}
score = 235
w.each_line{|l|v=l[0];l[0..-3].each_char{|n|v+=f[n]};v.split(//).each_with_index{|c,i|if l[i]==c
print c
else
print '_'
score+=1
end}}
puts "FINAL SCORE: #{score}"
```
[Answer]
# [Python 3](https://docs.python.org/3/) (644449\*2+0) 1288898 points
Perfect accuracy in *only* 644449 bytes
```
import zlib,base64 as s
t=enumerate(zlib.decompress(s.b64decode(b'###')).decode());a=lambda c:next(t)[1]
```
The full code cannot fit in an answer, so I have put it [here](https://github.com/Legorhin/mobydick/blob/master/modified.py) and replaced the large binary string literal with `b'###'` in the answer text.
This is generated with the following code, where `modified.py` is the generated file, and `cheatsheet.txt` is the `whale2.txt` file starting at the second character.
```
import zlib, base64
with open("modified.py","w") as writer:
    writer.write("import zlib,base64 as s\nt=enumerate(zlib.decompress(s.b64decode(")
    with open("cheatsheet.txt","rb") as source:
        text = source.read()
        writer.write(str(base64.b64encode(zlib.compress(text,9))))
    writer.write(')).decode());a=lambda c:next(t)[1]')
```
The code can be executed by adding the following to the end of `modified.py`. `whale2.txt` must be in the same directory as `modified.py`, and the output will be written to `out.txt`.
```
with open("out.txt","w") as writer:
    with open("whale2.txt","r") as reader:
        text = reader.read()
        for b in text:
            c = a(b)
            writer.write(c)
```
This answer does not directly access either `whale.txt` or `whale2.txt`. It makes use of existing standard compression libraries as explicitly allowed in the rules.
[Answer]
# [Python 3](https://docs.python.org/3/), (146\*2+879757) 880049 bytes
```
def f(c):return"\n                     t \n 2  sS \n  -  08........       huaoRooe oioaohue thpih eEA \n   neo    enueee neue hteht e"[ord(c)-10]
```
[Try it online!](https://tio.run/##bVRdb9s2FH0Of8VtAizyZnt28jK4yEMRNM2wDAWaBEPgGAEtXZmEKVKjKH@g6G/PzpXVJN2mF4n385xzeVXvkwn@/Pm54JLKLB/MIqc2@uNHT//3JILjjKi5lQ8aEU1@G/dPH2JaHb6EwBRs0MG0TMnU1hB//NDlkOcgcexbZsYJESaxScTH8xALgBhNJwv1rE7o3q@CK7mgPBRMS3Zhq2AuI//dss/3dEHz@WTx8/TsnMoQ6Ymsp6j9ijOYBgvE1pE3CDs/w3dP0ug4mKmjE1q5sNSuC5GjOBDaYZAYsb20mkvUYi6OBf1yQVPxVtY/WV/wDmmV3mXqCEYQqzjqxNlrcpc2GHb@NQtup6tloWk3o918upBiAwIV@eghS44cDxPBMWYv/YBN2aoOMVGzb75/JluxTUoJz4p100bOhGlpHaMgIsdNKiDRCYWafRZPL2ePtU7mMYVHCXrcGu14nHbpFB0S7xLSxDGOrItscCg1zl1oWE7W5yFGziVsoo4EuA1t89QrKQU6TjKbzobenXE6WwDX0arlppEW2Q@pqPymNMS2PmWH2HcHXbqIkrLXqJ9osju/uroa0AWwkPYF/ZAh7QBQKp1@/Ua4r6djwKp0ei0ykLL/JtGNQb1J/ZW@fvtv7pAcFBVyuL4opPqEO8xk9jYDunZjGh9eWT@oIeHaLDleTAcK6c/q493Dn59vPn96GCuV3bZ17SwWYbknTTe4XHQZfNNWdbIbpvvGcKQU4PsUdVUB@G1uQnDAcWeYakz1EDQaJSOzXOrIMo08aEA3rCNey1Dsh510y6itf0@/U4MVNbZSPmzHdM201Q3xBs2KtknWr@BsKLgC7Hc2B6SD8gcQzZC2NhmgwhpwVAa@NcfcWC6HVIV8jQpuTwzizlngK/oE5/DXYFrpPZVOr9CiFKMS4xpYPHmdrLSDQ4zbEF3RIXRhgzLQQhC@wPuO6D1hQZpQsQlbrK8r0D5yJUtVCFGpJzkV9kk7m/ZQ//gvIwu0Dy0lve5kEybSo@lUpgAIwra3Jta5EViVzAs7lZTXFUOHbr9GJagSmiB0yZSDGJqjamhliB73FnLqjcgbWswFIwvtyii78gF/t5yHHWfHKWES11DZ2FxUqwIoaxc843e05tSBoAZ5trR5pxgIql6wYthxKthZmWgCzr4SsPmA/0lseXxMo9H1h8s/bu4f7tQ/ "Python 3 – Try It Online")
Pretty straightforward frequency table. Each position in the string corresponds to the current character's ascii code (minus 10 = 0x0a = '\n', the lowest character in the file), and the character at each index is the most frequent next character. Assuming I calculated the frequencies right…
Tested with the code from [user202729's test](https://codegolf.stackexchange.com/a/152897/3112)
]