Sorting, Searching, and Merging - Advanced Topics in Java: Core Concepts in Data Structures - page 20

1.8 Example: Word Frequency Count
Let's write a program to read an English passage and count the number of times each word appears. Output consists
of an alphabetical listing of the words and their frequencies.
We can use the following outline to develop our program:

while there is input
get a word
search for word
if word is in the table
add 1 to its count
else
add word to the table
set its count to 1
endif
endwhile
print table

This is a typical “search and insert” situation. We search for the next word among the words stored so far. If the search
succeeds, the only thing to do is increment its count. If the search fails, the word is put in the table and its count set to 1.
A major design decision here is how to search the table, which, in turn, will depend on where and how a new
word is inserted in the table. The following are two possibilities:

1. A new word is inserted in the next free position in the table. This implies that a sequential

search must be used to look for an incoming word since the words would not be in any
particular order. This method has the advantages of simplicity and easy insertion, but
searching takes longer as more words are put in the table.

2. A new word is inserted in the table in such a way that the words are always in alphabetical

order. This may entail moving words that have already been stored so that the new word
may be slotted in the right place. However, since the table is in order, a binary search can
be used to search for an incoming word.

For (2), searching is faster, but insertion is slower than in (1). Since, in general, searching is done more frequently
than inserting, (2) might be preferable.
Another advantage of (2) is that, at the end, the words will already be in alphabetical order and no sorting will be
required. If (1) is used, the words will need to be sorted to obtain the alphabetical order.
We will write our program using the approach in (2). The complete program is shown as Program P1.7.

Program P1.7

import java.io.*;
import java.util.*;
public class WordFrequency {
final static int MaxWords = 50;
public static void main(String[] args) throws IOException {
String[] wordList = new String[MaxWords];
int[] frequency = new int[MaxWords];
FileReader in = new FileReader("passage.txt");
PrintWriter out = new PrintWriter(new FileWriter("output.txt"));
for (int h = 0; h < MaxWords; h++) {
frequency[h] = 0;
wordList[h] = "";
}