Capstone: a word index
The collections part ends with the program every text tool starts from: a word index. Each word maps to the lines it appears on, the table prints one row per word, and the totals count the words and the distinct words. A second program checks those totals against a count made by hand, because a report that only looks plausible is not checked at all.
The text and the index
The text is three lines in the source, so the program has no file to read and the expected numbers can be counted on paper:
Line 1 has four words: the, quick, brown, fox. Line 2 has five: jumps, over, the, lazy, dog. Line 3 has three: the, dog, sleeps. That is twelve words, and the distinct ones are the, quick, brown, fox, jumps, over, lazy, dog and sleeps, which is nine.
The index is a TreeMap of a word to the list of its lines. computeIfAbsent creates the list, and the sorted map means the table comes out alphabetical with no second sort:
import java.util.ArrayList;
import java.util.Comparator;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
public class WordIndex {
public static void main(String[] args) {
String[] lines = {
"the quick brown fox",
"jumps over the lazy dog",
"the dog sleeps",
};
Map<String, List<Integer>> index = new TreeMap<>();
int total = 0;
for (int line = 0; line < lines.length; line++) {
for (String word : lines[line].split(" ")) {
index.computeIfAbsent(word, k -> new ArrayList<>()).add(line + 1);
total++;
}
}
System.out.printf("%-8s %5s %s%n", "word", "count", "lines");
for (Map.Entry<String, List<Integer>> entry : index.entrySet()) {
System.out.printf("%-8s %5d %s%n", entry.getKey(), entry.getValue().size(), entry.getValue());
}
System.out.println("words: " + total);
System.out.println("distinct: " + index.size());
List<Map.Entry<String, List<Integer>>> byCount = new ArrayList<>(index.entrySet());
byCount.sort(Comparator
.comparing((Map.Entry<String, List<Integer>> e) -> e.getValue().size()).reversed()
.thenComparing(Map.Entry::getKey));
System.out.println("first by count: " + byCount.get(0).getKey() + " " + byCount.get(0).getValue().size());
Map<String, Integer> onManyLines = new LinkedHashMap<>();
for (Map.Entry<String, List<Integer>> entry : index.entrySet()) {
if (entry.getValue().size() > 1) {
onManyLines.put(entry.getKey(), entry.getValue().size());
}
}
System.out.println("more than once: " + onManyLines);
}
}
javac -Xlint:all WordIndex.java
java WordIndex
word count lines
brown 1 [1]
dog 2 [2, 3]
fox 1 [1]
jumps 1 [2]
lazy 1 [2]
over 1 [2]
quick 1 [1]
sleeps 1 [3]
the 3 [1, 2, 3]
words: 12
distinct: 9
first by count: the 3
more than once: {dog=2, the=3}
The table
Nine rows, one per distinct word, in alphabetical order. The count column is the size of the list and the last column is the list itself, which is why the two agree by construction: there is one piece of data and two views of it. A table that stored a count beside the list could disagree with it after an edit; this one cannot.
The format is %-8s %5d %s%n, so the word is padded to eight characters, the count is right-aligned in five, and the line list is printed as it comes. The header uses the same format, which is why its columns line up with the rows.
The totals
total counts every word as it is indexed, and index.size() counts the distinct ones. The two numbers answer different questions and a report that prints only one of them is misleading: twelve words in nine distinct forms means three of them repeat.
The two last lines are the two questions a reader asks of an index. The sort by count answers which word is the most frequent, with the alphabetical order as the tie-break, and the filter answers which words appear on more than one line. Both are computed from the index and neither changes it.
The numbers checked
The second program builds the same index and compares its numbers with the ones counted by hand. The lines of a word are printed too, so a failure can be read:
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
public class Checks {
static final String[] LINES = {
"the quick brown fox",
"jumps over the lazy dog",
"the dog sleeps",
};
public static void main(String[] args) {
Map<String, List<Integer>> index = new TreeMap<>();
for (int line = 0; line < LINES.length; line++) {
for (String word : LINES[line].split(" ")) {
index.computeIfAbsent(word, k -> new ArrayList<>()).add(line + 1);
}
}
check("the", 3, index.get("the").size());
check("dog", 2, index.get("dog").size());
check("fox", 1, index.get("fox").size());
check("words", 12, countWords());
check("distinct", 9, index.size());
System.out.println("lines of the: " + index.get("the"));
System.out.println("lines of dog: " + index.get("dog"));
}
static int countWords() {
int total = 0;
for (String line : LINES) {
total += line.split(" ").length;
}
return total;
}
static void check(String name, int expected, int actual) {
System.out.printf("%-9s %s (%d)%n", name, expected == actual ? "ok" : "FAIL", actual);
}
}
javac -Xlint:all Checks.java
java Checks
the ok (3)
dog ok (2)
fox ok (1)
words ok (12)
distinct ok (9)
lines of the: [1, 2, 3]
lines of dog: [2, 3]
Every check prints the value it measured, so a FAIL line names the number that was wrong and not only the name. The first version of this program expected thirteen words and eleven distinct ones, which is the kind of mistake that a check exists to catch: the build was clean and the table looked right, and both totals were wrong.
Reading the output
Read the table against the text before you trust it. the is on lines 1, 2 and 3, which is the three occurrences; dog is on 2 and 3, which is two; fox is only on 1. The nine rows together hold twelve entries, which is the words line, and the three words that repeat are the, dog and the one that appears once on each of two lines.
The order of the table is the order of the keys, and the order of the last line is the order the words were first put in, which is why the and dog appear in that order there and the other way round would be wrong to expect. The count table is the one to read for frequency and the map is the one to read for membership, which is the difference lesson 073 drew.
Exercises
- Add a fourth line to the text and update the two totals by hand before you run the program.
- Print only the words that appear once, in alphabetical order.
- Change the index to a LinkedHashMap and print the table again to see the order it keeps.
- Add a check that every line number in the index is between 1 and the number of lines.
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
What is the value type of the word index?
Answer
A list of the line numbers the word appears on
The index keeps every position, and the count is the size of that list.
-
Why does the table come out alphabetical with no second sort?
Answer
The index is a TreeMap, so its keys iterate in their natural order
The sorted map keeps the keys in order as it stores them.
-
Why does the report print both the total and the distinct count?
Answer
They answer different questions, and the difference is the repetition
Twelve words in nine forms means three repeats, which neither number shows alone.
-
What does this program print?
import java.util.ArrayList; import java.util.List; import java.util.Map; import java.util.TreeMap; public class Q1 { public static void main(String[] args) { Map<String, List<Integer>> index = new TreeMap<>(); String[] words = {"a b a".split(" ")[0], "b", "a"}; for (int i = 0; i < words.length; i++) { index.computeIfAbsent(words[i], k -> new ArrayList<>()).add(i + 1); } System.out.println(index.get("a")); System.out.println(index.size()); } }Answer
[1, 3] / 2
The word a is at positions 1 and 3 of the array, and only two distinct words were added.
-
What does this program print?
import java.util.ArrayList; import java.util.List; import java.util.Map; import java.util.TreeMap; public class Q2 { public static void main(String[] args) { Map<String, List<Integer>> index = new TreeMap<>(); index.computeIfAbsent("b", k -> new ArrayList<>()).add(2); index.computeIfAbsent("a", k -> new ArrayList<>()).add(1); for (String key : index.keySet()) { System.out.print(key + " "); } } }Answer
a b
The sorted map iterates the keys in alphabetical order whatever the insertion order was.
-
What does this program print?
import java.util.ArrayList; import java.util.Comparator; import java.util.List; import java.util.Map; import java.util.TreeMap; public class Q3 { public static void main(String[] args) { Map<String, Integer> counts = new TreeMap<>(); counts.put("b", 2); counts.put("a", 2); counts.put("c", 1); List<Map.Entry<String, Integer>> list = new ArrayList<>(counts.entrySet()); list.sort(Comparator.comparing((Map.Entry<String, Integer> e) -> e.getValue()).reversed() .thenComparing(Map.Entry::getKey)); for (Map.Entry<String, Integer> e : list) { System.out.print(e.getKey() + e.getValue() + " "); } } }Answer
a2 b2 c1
The count order puts the two twos first, and the key breaks the tie.
-
What does this program print?
import java.util.ArrayList; import java.util.List; import java.util.Map; import java.util.TreeMap; public class Q4 { public static void main(String[] args) { Map<String, List<Integer>> index = new TreeMap<>(); index.computeIfAbsent("a", k -> new ArrayList<>()).add(1); index.computeIfAbsent("a", k -> new ArrayList<>()).add(2); System.out.println(index.get("a").size()); System.out.println(index.size()); } }Answer
2 / 1
The second call returns the existing list, so one key holds two positions.
-
What does this program print?
import java.util.ArrayList; import java.util.List; import java.util.Map; import java.util.TreeMap; public class Q5 { public static void main(String[] args) { Map<String, List<Integer>> index = new TreeMap<>(); String[] words = {"x", "y", "x", "z"}; for (int i = 0; i < words.length; i++) { index.computeIfAbsent(words[i], k -> new ArrayList<>()).add(i + 1); } int repeated = 0; for (List<Integer> lines : index.values()) { if (lines.size() > 1) { repeated++; } } System.out.println(repeated); System.out.println(index.size()); } }Answer
1 / 3
Only x repeats, and there are three distinct words.
-
What does the check method print for a value that does not match?
Answer
FAIL and the value it measured
The measured value is printed either way, so a failure names the number that was wrong.
-
Why can the count column not disagree with the list column?
Answer
The count is the size of the list, so both read one piece of data
There is one list per word, and the count is derived from it at print time.
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