Cryptography Reference
In-Depth Information
0
1
0
1
0
1
0
1
0
1
Fred and Barney went shooting in Timbuktu.
Fred and Barney went shooting in Minnesota.
0
1
Thelma and Louise went bungee-jumping
where
Bob and Ray went shooting
where
who
went fishing
where
0
1
Fred and Barney
verb5
.
0
1
Thelma and Louise
verb3
0
1
Laverne and Shirley
verb
Fred and Barney
verb4
Bob and Ray
verb2
Figure 7.7: A Huffman tree that converts bits into productions for the
variable
noun
from Table 7.3.3.
Normal Form used the rule that the leftmost variable is always ex-
panded in turn. This rule works well here, but it leads to an interest-
ing rearrangement. In the GNF examples, the first part of the sen-
tence was always related to the first bits. In this case, this fails. Here
the steps assuming the leftmost rule:
Bits of
Starting Choice Produces
noun
0010
who
went fishing
where
who
went fishing
where
0 Bob and Ray went fishing
where
Bob and Ray went 11 Bob and Ray went fishing
fishing
where
in Kalamazoo.
There is no reason why the sequence of productions needs to be
related with a leftmost first rule. A general parsing algorithm would
be able to discover the three different choices made in the creation
of this sentence but the GNF-limited parser could not. They could be
arranged in any predefined order used by both ends of the commu-
nications link. So the sentence “Bob and Ray went fishing in Kala-
mazoo” could be said to be generated by any of the six combinations
0010011, 0010110, 0001011, 0110010, 1100010, or 1100100.
This last section on expansions and contractions has ignored the
feature that allows a user to weight the choices according to some
predetermined agenda. These weights can be carried accurately
throughout the expansion and contraction process. If there is an ex-
pansion, the terms are multipled through. If there is a contraction,
they are gathered. Here's an example of expansion. The weightings
are shown as variables in parentheses.
