6.1 Introduction to ``Hill-Climbing''

Figure 30 summarizes the distances of bigram tables for each key for Figure 29, reorganized as follows. The corners of the ``hexagon'' indicate each key with its corresponding bigram distance nearby. Two keys/corners are connected with a line if each key is obtainable from the other key by swapping two letters.

  

Figure 30: Reformulation of Keys and Distances from Figure 29

Rather than inspecting each key, here is a modifed approach. Consider trying to reach the best key "lna" from the starting key "aln" by traveling along a ``path'' in Figure 30. One ``path'' is from "aln" to "nla" to "lna", which has the property that from each key we go to its best ``neighboring'' key:

• start at "aln", which has distance 39.
  • from "aln", swap 'a' and 'l' to get to neighboring key "lan", which has distance 37.
  • from "aln", swap 'a' and 'n' to get to neighboring key "nla", which has distance 17.
  • from "aln", swap 'l' and 'n' to get to neighboring key "anl", which has distance 35.
• go the best neighbor "nla", which has distance 17.
  • from "nla", swap 'a' and 'l' to get to neighboring key "nal", which has distance 33.
  • from "nla", swap 'a' and 'n' to get to neighboring key "aln", which has distance 39.
  • from "nla", swap 'l' and 'n' to get to neighboring key "lna", which has distance 15.

• go to the best neighbor "lna", which has distance 15.
  • from "lna", swap 'a' and 'l' to get to neighboring key "anl", which has distance 35.
  • from "lna", swap 'a' and 'n' to get to neighboring key "lan", which has distance 37.
  • from "lna", swap 'l' and 'n' to get to neighboring key "nla", which has distance 17.
• all the neighbors are worse, so stay at "lna" and stop looking.

This approach of going to the best neighbor is hill-climbing and is fleshed out in Section 7.1. In the meantime, note the following:

• We do not have to skip keys we've already seen. (Doing so takes time and space and doesn't always save time in the long run.)
• We do not have to store all the keys or even all the neighbors: Compute the keys as needed and ``throw away'' the rest.
• You can get from ``anywhere'' to ``anywhere''. That is, you can get from every key in Figure 30 to every other key in Figure 30 by a path of 0 or more swaps.

Swaps keep coming up! This suggests we should take a closer look at swaps.

Roadmap
Section 3.7	Encipher plaintext $\Rightarrow$ scramble frequencies.
Section 3.7	Decipher ciphertext $\Rightarrow$ unscramble frequencies.
Section 4.2	(Hope) Unscramble frequencies $\Rightarrow$ decipher ciphertext
Section 4.3	Unscramble = Bring ``close'' to intrinsic frequencies
	Approximate intrinsic frequencies with training text
	Assume ciphertext is medium to large so that unscrambled frequencies resemble intrinsic frequencies
Section 4.4	Use the L1 distance to measure ``closeness''; ignore labels.
Section 5.1	Sorting unigram frequencies does not work, but ``almost'' does.
	(Hope) When the frequency table for ciphertext matches the table for training text, read the encryption key off of the labels
Section 5.2	``Sort bigram frequencies'' is problematic.
Section 5.3	Exhaustive search is too slow; therefore, need an incomplete search.
Section 6.2	Q: How do we perform an effective, incomplete search?
Section 6.1	(Idea) Hill-Climbing: pick the best ``neighbor''
$(\rightarrow)$     Section 6.2	Why swaps are so important, e.g. used to generate ``neighbors''