Cryptography Reference
In-Depth Information
a
c
b
b
t
3
n
Figure 6.3: This tree stores the frequency data for a file with
layers
th
-order statistics. Access is substantially faster.
The dashed lines show where nodes are omitted. The only complete
word shown here is “at”. It occurs three times in the sample.
n
of branching for
The fourth solution, going fishing, is a bit more complicated. The
idea is to randomly select positions in the text and use this to ran-
domize the search. Not all of the data can be kept in a table so all of
the choices won't be available at each juncture. Therefore, you must
live with what you can find. The most extreme version of this algo-
rithm simply searches the entire file and constructs the right table
entry on the fly. Here is a more sensible approach:
1. Choose a location in the source file at random. Call this charac-
ter
. This random source must be duplicated during decoding
so it must come from a pseudo-random number generator that
is synchronized.
i
2. If you are constructing an
n
th
-order mimicry, search forward
1
characters in question. The next char-
acter may be the one you desire.
n −
until you find the
3. Let there be
k
characters in the source file. Go to position
i
+
k
2
mod
k
. Search forward until the right combination of
n −
1
characters are found.
4. If the next character suggested by both positions is the same,
then nothing can be encoded here. Send out that character and
repeat.
