Top K or K-most frequent words in a document
Given a document (or stream) of words. Find the top k most frequent words in the document (or stream).
For example, if stream = "aa bb cc bb bb cc dd dd ee ff ee dd aa ee". That is, {"dd"=3, "ee"=3, "ff"=1, "aa"=2, "bb"=3, "cc"=2}. Then top 3 most frequent words are: {"dd", "ee", "bb"}.
One quick solution would be to create a pair object with the word and its frequency and then sort the pair array with respect to the frequency of the pair. Now, take the first k pairs from the sorted array of pairs. This is O(nlgn) solution.
O(nlgk) solution with O(n) space
But we can improve this solution. Note that we are only concern about the top k elements. Sorting the array means we are sorting all the n elements which is unnecessary as we are only concerned for first k. Any idea popping in? Yeah, I am sure you have the same feeling that we could use a Min Heap of size k to keep top k most frequent words. That's right. We also need to use a hashmap to keep frequency of each word.
- Calculated frequency of all the words in a hashmap from the word to its frequency.
- Start adding pair object of word and its frequency into a min heap where we use the frequency as the key for the min heap.
- If the heap is full then remove the minimum element (top) form the heap and add add the new word-frequency pair only if the frequency of this word has frequency greater than the top word in the heap.
- Once we scanned all the words in the map and the heap is properly updated then the elements contained in the min heap are the top k most frequents.
Below is a simple implementation of the above idea using pJava Priority Queue (Or we can use a generic min heap I have implemented in a previous post here). This solution is O(nlgk) time and O(n) space.
Read full article from Top K or K-most frequent words in a document - Algorithms and Problem SolvingAlgorithms and Problem Solving
No comments:
Post a Comment