Section 9.4 Example: Counting Letter Frequencies
Suppose you wish to write a program to help break a text message that has been encrypted with one of the historical ciphers that we have discussed in the two previous chapters.
It is well known that historical ciphers often can be broken, that is, the plaintext can be found from the ciphertext, by examining the frequencies of letters and comparing them to the average frequencies of typical samples of plaintext. For example, E
and T
are the two most frequent letters in the English language. So, in a ciphertext encrypted with a Caesar cipher, E
and T
are good guesses as the plaintext letter corresponding to the most frequent letter in a ciphertext message.
Let's write a program that will count how many times each of the 26
letters appears in a given string. There are a number of ways to design such a program depending on how flexible you wish the program to be.
Let's keep this example simple by assuming that we will only be interested in counting occurrences of the letters A
through Z
and not of occurrences of spaces or punctuation marks. Assume further that we will change lowercase letters in our string sample to uppercase before counting letters and that we will want to print out the frequencies of letters to the console window.
Finally, assume that, later in the chapter after we discuss sorting arrays, we will want to enhance our program so that it can print out the letter frequencies in order of increasing frequency.
Subsection 9.4.1 A Class to Store the Frequency of One Letter
It is clear that an array should be used for storing the frequencies, but a decision must also be made as to what to store as the array elements. If we store letter frequencies as int
values, with the frequency of A stored at index 0, and the frequency of B at index 1, and so forth, we will not be able to rearrange the frequencies into increasing order without losing track of which letter corresponds to which frequency. One way of solving this problem is to create an array of objects, where each object stores both a letter and its frequency.
So let us design a LetterFreq
class that stores a letter in an instance variable of type char
and its frequency in an instance variable of type int
. These instance variables can be declared as:
private char letter; //A character being counted
private int freq; //The frequency of letter
We will want a constructor that can initialize these two values and two accessor methods to return these values. We are familiar enough with these kinds of methods that it will not be necessary to discuss them any further. We need one additional method to increment freq
whenever we encounter the letter while processing the string:
public void incrFreq() {
freq++;
} //setFreq()
A UML diagram for the LetterFreq
class is given in FigureĀ 9.4.1 and the class definition is given in ListingĀ 9.4.2.
Note that we will have to make a minor modification to this class later in this chapter to enable us to sort an array of objects from this class.
Subsection 9.4.2 A Class to Count Letter Frequencies
Now let us turn to designing a class named AnalyzeFreq
that will use an array of objects of type LetterFreq
to count the frequencies of the letters A
through Z
in a given string.
The array, let's call it freqArr
, will be the only instance variable of the class. The class needs a constructor to instantiate the array and to create the 26
array elements, each with a different letter and an initial frequency of 0
. This class should also have two methods: a method to count the frequencies of the 26
letters in a given string and a method that prints out the frequency of each letter to the console window. The UML diagram for the class is given in ListingĀ 9.4.3.
The array instance variable can be declared by:
private LetterFreq[] freqArr; //An array of frequencies
The constructor creates an array of 26
elements to store references to LetterFreq
objects with the statement
freqArr = new LetterFreq[26];
The indices of the array range from 0
to 25
and the elements at these locations should store the letters A
to Z
. Recall that in Java, char
data are a form of int
data and can be used in arithmetic. If we let k
be an integer that ranges between 0
and 25
, then the expression (char)('A' + k)
will correspond to the letters A
to Z
. . Thus, the following loop will initialize the array correctly.
for (int k = 0; k < 26; k++) {
freqArr[k] = new LetterFreq((char)('A' + k), 0);
} //for
The countLetters()
method must identify the array index for LetterFreq
object that stores a letter between A
and Z
. If let
is a char
variable that stores such a letter, then the expression (let - 'A')
will give the index of the array element corresponding to let
. Thus the following code will calculate the frequencies of the letters in the string parameter, str
:
public void countLetters(String str) {
char let; //For use in the loop.
str = str.toUpperCase();
for (int k = 0; k < str.length(); k++) {
let = str.charAt(k);
if ((let >= 'A') && (let <= 'Z')) {
freqArr[let - 'A'].incrFreq();
} //if
} //for
} //countLetters()
The definition of the printArray()
method is completely straight forward:
public void printArray() {
for (int k = 0; k < 26; k++) {
System.out.print("letter: " + freqArr[k].getLetter());
System.out.println(" freq: " + freqArr[k].getFreq());
} //for
} //printArray()
The entire definition of AnalyzeFreq
is given in FigureĀ 9.4.4.
We leave the coding of the main()
method as an exercise below. We will also modify this class later in the chapter to be able to sort the array after counting.
Exercises Self-Study Exercises
1. Letter Frequencies.
Add a main()
method to the AnalyzeFreq
class that will count the letter frequencies in the sentence āNow is the time for all good students to study computer related topicsā.