Analysing the most common words in a text, and replacing them with a single byte
Perl - 154 bytes (KJB in ~1.94s)

while(&lt;&gt;){push@w,/[\w\']+|\W/g}
\@c{length&gt;1?$w{$_}++?():/./g:$_}for@w;
@t{sort{$w{$b}-$w{$a}}keys%w}=grep!exists$c{$_},map{chr}0..255;
print$t{$_}//$_ for@w

This is substantially golfed, but I can say with confidence that it hasn't affected the performance in any noticable way.
Sample Usage:
$ perl encoder.pl &lt; king-james-bible.txt &gt; kjb.cmp

The created filesize is 3,253,677 bytes, runtime is approximately 1.94 seconds. If you want to test the correctness, you can export a translation table by appending the following three lines of code:
;use Storable;
%u=reverse%t;
store\%u,'trans.tbl'

This will create, and possibly overwrite, a file named trans.tbl in the current working directory. Then, decode with the following script:
#!perl -n0
use Storable;
%t=%{retrieve 'trans.tbl'};
print$t{$_}//$_ for/./sg

Sample usage:
$ perl decoder.pl &lt; kjb.cmp &gt; kjb.txt

The output is exactly 4,452,069 bytes, as expected.

Unrolled and commented
while(&lt;&gt;){      # for each line
  push@w,/[\w\']+|\W/g # tokenize, add tokens to array
}

\@c{            # mark the following chars
  length&gt;1?     # token is 2 or more chars
    $w{$_}++    # increment occurrence in word hash
    ?           # if this word has already been seen
      ()        # mark nothing
    :           # else
      /./g      # mark each char individually
  :             # else
    $_          # mark the single char
}for@w;         # iterate over all tokens

@t{             # create the translation table
  sort{$w{$b}-$w{$a}}keys%w # most frequent words
}=grep!exists$c{$_},map{chr}0..255; # assign to an unmarked char

print           # output
  $t{$_}        # the value in the trans hash
    //          # or, if previous value is undefined
  $_            # output the untranslated string
for@w           # iterate over the tokens previously found


Time analysis
Min: 1.843s
Max: 1.984s
Avg: 1.939s
1.953, 1.953, 1.953, 1.843, 1.921, 1.937, 1.921, 1.953, 1.953, 1.921, 1.937, 1.968, 1.906, 1.984, 1.937, 1.968, 1.953, 1.921, 1.921, 1.937, 1.968, 1.937, 1.890, 1.968, 1.937, 1.953, 1.937, 1.937, 1.937, 1.953
According to profiling, the time usage for each statement is approximately the following:
1.09s:
while(&lt;&gt;){push@w,/[\w\']+|\W/g}
31.3ms:
\@c{length&gt;1?$w{$_}++?():/./g:$_}for@w;
15.6ms:
@t{sort{$w{$b}-$w{$a}}keys%w}=grep!exists$c{$_},map{chr}0..255;
750ms:
print$t{$_}//$_for@w
Note that for the purpose of time usage analysis, the result was actually written to a file. Excluding the final output, or piping to /dev/null instead produces times 600ms to 750ms faster.

Major Performance Gains

The individual characters of a word are marked only the first time the word is seen, instead of every time. As noted by @VadimR, this alone saves around 2s, over 25% of the previous execution time.
The most frequent words are translated with unmarked characters, and marked characters left untranslated. This saves a great deal of time during output, because words not in the translation table can be output directly, without having to translate each individual character.
Tokenizing the file one line at a time - instead of all at once - is quite a bit faster.