Frequent words in one pass
You need to find the most frequent words of a long stream, but there is memory for only k counters. The Misra–Gries algorithm does it like this. The counters are pairs “word, number”. For the next word:
- if the word already has a counter, increase it by 1;
- otherwise, if fewer than k counters are taken, create a counter for the word with the value 1;
- otherwise decrease all k counters by 1 and delete those that become zero; the word itself is not recorded anywhere.
Pass the stream through the algorithm and print what is left in the counters. Among the tests is “War and Peace”.
Input
The first line holds n and k (1 ≤ n ≤ 2·105, 1 ≤ k ≤ 1000). The second holds n words separated by spaces, each of lowercase Latin or Cyrillic letters and digits, up to 20 characters long.
Output
The first line is the number of remaining counters c. Then c lines “word number”: in decreasing order of the number, and on ties by the word (in UTF-8 byte order).
Examples
Example 1
7 2 мир война мир труд мир май мир
2 мир 3 май 1
Example 2
11 3 a b c a b c d a b e a
2 a 2 b 1
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 8 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
Decreasing all counters costs O(k). How many times can it happen over a stream of n words?
2The idea
Each decrease “eats” k + 1 occurrences at once: one from each of the k words in the counters and the arriving word itself. There are n occurrences in all, so there are at most n/(k + 1) decreases, and they take O(n) in total. So a direct implementation is enough: a dictionary “word → number” and a pass over it on a decrease.
3Walkthrough
The same count gives the main property. A word's counter is underestimated by the number of decreases while it was in the counters plus the number of its occurrences eaten by decreases, and there are at most n/(k + 1) decreases in all. So for each word with frequency f the final counter is at least f − n/(k + 1). Every word occurring more than n/(k + 1) times is bound to stay in the counters. The converse is false: a rare word may end up in the counters too if it came at the end. That is why candidates are checked with a second pass if one is possible.
On “War and Peace” with 30 counters the threshold is 120,000/31 ≈ 3871. Only «и» (“and”) is above it, 5781 times, and it survives with a counter of 1974, as promised: 1974 ≥ 5781 − 3871. The other nine places are taken by random words with a counter of 1. With one counter the algorithm turns into the Boyer–Moore majority vote: it finds the word occurring more than half the time, if there is one; the novel has none, and the fifth test ends with an empty answer. The Count-Min sketch from the article answers another question, the frequency of any word with an error from above, while Misra–Gries keeps only candidates but is deterministic and errs from below.
3+Solution
4Complexity
O(n) time and O(k) memory.
5Common mistakes
- Evicting the smallest counter. The new word gets the evicted counter plus one: that is how the Space-Saving algorithm works, with other numbers and other guarantees. The first sample already shows it.
- Recording the word after a decrease. The arriving word is itself “eaten” by the decrease and does not get into the counters, even if some counter has been freed.
- Output order. In decreasing order of the number, and on ties by the word.