Array Example - Counting Frequencies of Letters

Suppose you wish to write a program to help break a text message that has been encrypted with one of the historical ciphers. 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 frequently used 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 of the English language 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 us 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 terminal.

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. 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 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++;
    }
}

Note that we will have to make a minor modification to this class later in this example to enable us to sort an array of objects from this class that we’ll cover later.

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 terminal.

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 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 entire definition of AnalyzeFreq is:

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
  } 
} 

Licenses and Attributions


Speak Your Mind