Most frequent words

Question

What's the most efficient way in Java to get the 50 most frequent words with their frequency out of a text?

I want to search around ~1,000,000 texts with each have around ~10,000 words and hope that it works in a reasonable time frame.

Answer 1

Most efficient would probably be using a Patricia trie that links to a max-heap. Every time you read a word, find it on the trie, go to the heap and increase-key. If it's not in the trie, add it and set its key in the heap appropriately.

With a Fibonacci heap, increase-key is O(1).

---

A not so unreasonable solution is to use a Map<String, Integer>, adding the count every time a word is encountered, and then custom-sorting its entrySet() based on the count to get the top 50.

If the O(N log N) sort is unacceptable, use selection algorithm to find the top 50 in O(N).

---

Which technique is better really depends on what you're asking for (i.e. the comment whether this is more of an [algorithm] question than a [java] question is very telling).

The Map<String, Integer> followed by selection algorithm is most practical, but the Patricia trie solution clearly beats it in space efficiency alone (since common prefixes are not stored redundantly).