Mini Project 10 — Word Frequency¶

Difficulty: Intermediate · Estimated effort: 4 hours · Prerequisites: Module 14 — The STL with OOP, Module 5 — Operators and Static Members · Combines: associative containers, algorithms with lambdas, an ordered type, measured container choices

No complete solution is provided. The marking is not "does it count words" — it is "can you justify each container and each algorithm you used".

1. Scenario¶

You are checking whether two chapters of the same book are statistically alike, starting from the obvious measurement: word frequency. You want counts, the most common words, a comparison of two texts, and a report that is stable — the same input must always produce the same output, in the same order.

2. Problem statement¶

Build a WordIndex class that reads text from an std::istream, counts normalised words, and answers queries: how many times a word occurs, the top n, the distinct-word count, and the words shared with, or unique to, another index.

Stability is a requirement: ties in the top-n list must be broken deterministically.

3. User requirements¶

[ ] Load a text and see how many distinct words it has and how many words in total.
[ ] Ask for the count of one word.
[ ] See the n most frequent words with their counts.
[ ] Compare two texts and see the words they share and the words unique to each.
[ ] Get the identical report every time for the same input, including on ties.

4. Functional requirements¶

[ ] WordIndex::add(std::istream&), and a constructor or factory from a file path.
[ ] Normalisation: case folding, punctuation stripped from the ends, empty tokens discarded.
[ ] count(const std::string&), distinctWords(), totalWords(), top(n).
[ ] top(n) returns pairs sorted by count descending, ties broken alphabetically.
[ ] Set operations against another index: shared words, words unique to one.
[ ] A documented, printed report.

5. Non-functional requirements¶

[ ] Every container choice justified in writing against an alternative.
[ ] Queries do not re-read the input; the index is built once.
[ ] count() on a missing word returns 0 and does not insert it.
[ ] Algorithms, not hand-written index loops, wherever the STL has one.
[ ] Builds warning-free with g++ -std=c++17 -Wall -Wextra -Werror, and any comparison in the tests uses a tolerance-free, exact rule.

6. Suggested features¶

A stop-word list, loaded from a file, with the effect on the counts reported.
Word length histogram.
A "similarity" number between two texts, with the definition stated precisely.
Counting bigrams, and a note on how much more expensive that is.

7. OOP concepts involved¶

Concept	Where it appears
Encapsulation	The index owns its container; callers ask questions rather than walking it
Ordered vs unordered containers	`std::map` for stable order, `std::unordered_map` for speed — choose and justify
Algorithms and lambdas	`std::sort`, `std::count_if`, `std::set_intersection` instead of loops
Operator overloading	`operator<` on a small `WordCount` type so the standard algorithms apply
Composition	A `Report` holding or formatting an index; a `WordIndexSet` over two indices
Value semantics	Copying an index is cheap and meaningful; say what it costs

8. Suggested design considerations¶

Choose the container deliberately. std::map gives ordered iteration and locking the tie break for free; std::unordered_map is usually faster but has no order, so sorting happens anyway. Write the choice and one sentence of reasoning in the header. "It was convenient" is an acceptable reason if you say so.

Normalise in one place. A single normalise(std::string) function, tested directly, is better than normalising at four call sites — the fourth will disagree.

Make ties deterministic. "Top ten" with equal counts is ambiguous unless you impose a second ordering key. Your requirement set demands determinism, so this is not optional.

Do not count while answering. count() must not insert. Reaching for operator[] on a map inside a query is the classic way to corrupt a word index, and the distinctWords() test will prove it.

9. Minimum viable version¶

WordIndex with normalisation, an internal count container, count, distinctWords, totalWords and a main printing a short report for a paragraph embedded in the program.

10. Intermediate extension¶

Add top(n) with the deterministic tie break, then test it on a text engineered to have three words with identical counts. Verify that two runs and two differently-ordered inputs produce the identical list.

11. Advanced extension¶

Add the two-index comparison using std::set_intersection and std::set_difference, then measure: time the build of an index over a large generated text with std::map and with std::unordered_map, and present a small table with the numbers you actually observed. State which you would ship, and why the numbers did or did not decide it.

12. Testing checklist¶

[ ] "The cat, the CAT!" counts as two occurrences of the and two of cat
[ ] Punctuation-only tokens are discarded and do not create an empty word
[ ] count("absent") returns 0, and distinctWords() is unchanged afterwards
[ ] totalWords() equals the sum of all counts
[ ] top(3) on equal counts returns the alphabetically-first three, in a fixed order
[ ] top(n) with n larger than the vocabulary returns every word, not an error
[ ] Shared words between a text and itself is its whole vocabulary
[ ] Words unique to an empty index comparison is that index's vocabulary
[ ] Empty input yields zero distinct words and zero total words

13. Documentation checklist¶

[ ] The normalisation rule written precisely enough to reimplement from the description
[ ] Each container choice with the alternative considered
[ ] The tie-break rule for top(n)
[ ] The meaning of the similarity number, if you added one
[ ] Any measured timing table, with the machine and build flags it was measured under

14. Self-evaluation rubric¶

Criterion	Excellent looks like	Weight
Correctness	Normalisation, counts and set operations all verified on awkward inputs	30%
STL use	Algorithms and containers chosen with reasons, not defaults	25%
Design	Index owns its state; queries are `const` and side-effect free	20%
Determinism	Identical output for identical input, on every run	10%
Evidence	Container choice supported by a measurement or a clear argument	10%
Documentation	Normalisation and tie-break rules written down	5%