Capstone: counting words
This is the last lesson of the part on arrays and strings, and it is a whole small task: take a sentence, count how often each word appears, and print the words in alphabetical order with their counts. It is written twice, once with a map and once with arrays and sorting, and both programs print the same report.
The text
The input is one sentence with single spaces between the words and no punctuation, so a split(" ") is enough. A real text would need a regex that also matches punctuation and repeated spaces, and the method would be the same after that line.
Counting with a map
A TreeMap keeps its keys sorted, so the report comes out in alphabetical order without a second sort. merge is the counting idiom: it inserts 1 for a word it has not seen and adds 1 to the value it has.
The file WordCount.java:
import java.util.Map;
import java.util.TreeMap;
public class WordCount {
public static void main(String[] args) {
String text = "the quick brown fox jumps over the lazy dog the fox";
String[] words = text.split(" ");
Map<String, Integer> counts = new TreeMap<>();
for (String word : words) {
counts.merge(word, 1, Integer::sum);
}
for (Map.Entry<String, Integer> entry : counts.entrySet()) {
System.out.println(entry.getKey() + ": " + entry.getValue());
}
System.out.println("distinct: " + counts.size());
}
}
javac -Xlint:all WordCount.java
java WordCount
brown: 1
dog: 1
fox: 2
jumps: 1
lazy: 1
over: 1
quick: 1
the: 3
distinct: 8
The sentence has eleven words and eight distinct ones; fox appears twice and the three times. merge takes the key, the value to use when the key is absent, and a function that combines the old value with the new one, which is Integer::sum here.
Counting with arrays
Sorting the words first puts equal words next to each other, and then one pass counts each run. The index stays at the first word of the run, the inner while counts how far the run goes, and the outer loop skips the rest of the run because those words equal the one before them.
import java.util.Arrays;
public class ArrayCount {
public static void main(String[] args) {
String text = "the quick brown fox jumps over the lazy dog the fox";
String[] words = text.split(" ");
Arrays.sort(words);
int distinct = 0;
for (int i = 0; i < words.length; i++) {
if (i == 0 || !words[i].equals(words[i - 1])) {
distinct++;
int count = 1;
while (i + count < words.length && words[i + count].equals(words[i])) {
count++;
}
System.out.println(words[i] + ": " + count);
}
}
System.out.println("distinct: " + distinct);
}
}
javac -Xlint:all ArrayCount.java
java ArrayCount
brown: 1
dog: 1
fox: 2
jumps: 1
lazy: 1
over: 1
quick: 1
the: 3
distinct: 8
The two outputs are identical because both programs answer the same question. The array version sorts the words in place, so the original order is gone; the map version keeps the words as keys and never reorders the input.
The two reports compared
The map version is shorter and reads as what it does: count the words, then print the entries. It needs the collections part that comes later in the course, and it allocates one entry per distinct word. The array version uses only what this part taught, sorts in place in O(n log n), and needs care at the boundary between two runs.
A real word counter also lower-cases the words, strips punctuation and skips empty pieces, and every one of those steps is a string method of lesson 024 and 028. The counting loop and the report stay the same, which is the point of a capstone: the parts are smaller than the whole.
Exercises
- Change the sentence in both programs to one that has a word three times and check that both reports still agree.
- Add a line to WordCount.java that prints the most frequent word, with a loop over the entries.
- Lower-case every word before counting in both programs, and compare the new reports.
- Sort the map report by count instead of by word. Which of the two programs is easier to change, and why?
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
What does
counts.merge(word, 1, Integer::sum)do?Answer
Inserts 1 for a new word and adds 1 to an existing count
merge uses the third argument only when the key already has a value, so it counts.
-
Why does the map version print the words in alphabetical order?
Answer
A TreeMap keeps its keys sorted
TreeMap orders its keys by their natural order, which for strings is lexicographic.
-
Why does the array version sort the words first?
Answer
Equal words become adjacent, so one pass can count runs
Counting a run needs the equal words next to each other, which is what the sort gives.
-
What does this program print?
import java.util.Map; import java.util.TreeMap; public class Q1 { public static void main(String[] args) { Map<String, Integer> counts = new TreeMap<>(); for (String word : "b a b".split(" ")) { counts.merge(word, 1, Integer::sum); } System.out.println(counts); } }Answer
{a=1, b=2}
The map is sorted by key and b was counted twice.
-
What does this program print?
import java.util.Arrays; public class Q2 { public static void main(String[] args) { String[] words = "c a c".split(" "); Arrays.sort(words); System.out.println(Arrays.toString(words)); } }Answer
[a, c, c]
The sort orders the three pieces and keeps both copies of c.
-
What does this program print?
public class Q3 { public static void main(String[] args) { String text = "one two two"; String[] words = text.split(" "); int count = 0; for (String word : words) { if (word.equals("two")) { count++; } } System.out.println(count); } }Answer
2
The word two appears twice in the three words.
-
What does this program print?
import java.util.Map; import java.util.TreeMap; public class Q4 { public static void main(String[] args) { Map<String, Integer> counts = new TreeMap<>(); counts.put("b", 1); counts.put("a", 2); for (String key : counts.keySet()) { System.out.print(key); } System.out.println(); } }Answer
ab
keySet of a TreeMap is sorted by key, so a comes before b.
-
What does the outer loop of the array version do when it reaches a repeated word?
Answer
It skips it, because it equals the word before
Only the first word of a run passes the test, so each run is counted once.
-
What does
"a b".split(" ")return?Answer
Two strings, a and b
The separator is removed and the two words are the two elements.
-
What does the array version lose compared with the map version?
Answer
The original order of the words
Arrays.sort reorders the words in place, while the map keeps the input untouched.
The code on this page was built with OpenJDK 21.0.13 (javac and java) and run on Alpine Linux in a Docker container.
Article author: Arthur Isaev