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.
Subsection9.4.1A 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.
Figure9.4.1.The LetterFreq class.
public class LetterFreq {
private char letter; //A character being counted
private int freq; //The frequency of letter
public LetterFreq(char ch, int fre) {
letter = ch;
freq = fre;
}
public char getLetter() {
return letter;
}
public int getFreq() {
return freq;
}
public void incrFreq() {
freq++;
}
} //LetterFreq
Listing9.4.2.The LetterFreq class definition.
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.
Subsection9.4.2A 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.
Figure9.4.3.The LetterFreq class.
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.
public class AnalyzeFreq {
private LetterFreq[] freqArr; //An array of frequencies
public AnalyzeFreq() {
freqArr = new LetterFreq[26];
for (int k = 0; k < 26; k++) {
freqArr[k] = new LetterFreq((char)('A' + k), 0);
} //for
}
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
}
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
}
} //AnalyzeFreq
Listing9.4.4.The AnalyzeFreq class definition.
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.
ExercisesSelf-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”.
