Algorithm for generating a 'top list' using word frequency

I have a big collection of human generated content. I want to find the words or phrases that occur most often. What is an efficient way to do this?

Upvotes: 4

Answers (6)

Roopesh Majeti

Reputation: 554

Why not a simple map with key as the word and the Counter as the Value. It will give the top used words, by taking the high value counter. It is just a O(N) operation.

Upvotes: -1

pageman

Reputation: 3022

Maybe you can try using a PATRICIA trie or practical algorithm to retrieve information coded in alphanumeric trie?

Upvotes: 0

scott

Reputation: 746

Look into the Apriori algorithm. It can be used to find frequent items and/or frequent sets of items.

Like the wikipedia article states, there are more efficient algorithms that do the same thing, but this could be a good start to see if this will apply to your situation.

Upvotes: 1

Alex Martelli

Reputation: 881497

the basic idea is simple -- in executable pseudocode,

from collections import defaultdict

def process(words):
  d = defaultdict(int)
  for w in words: d[w] += 1
  return d

Of course, the devil is in the details -- how do you turn the big collection into an iterator yielding words? Is it big enough that you can't process it on a single machine but rather need a mapreduce approach e.g. via hadoop? Etc, etc. NLTK can help with the linguistic aspects (isolating words in languages that don't separate them cleanly).

On a single-machine execution (net of mapreduce), one issue that can arise is that the simple idea gives you far too many singletons or thereabouts (words occurring once or just a few times), which fill memory. A probabilistic retort to that is to do two passes: one with random sampling (get only one word in ten, or one in a hundred) to make a set of words that are candidates for the top ranks, then a second pass skipping words that are not in the candidate set. Depending on how many words you're sampling and how many you want in the result, it's possible to compute an upper bound on the probability that you're going to miss an important word this way (and for reasonable numbers, and any natural language, I assure you that you'll be just fine).

Once you have your dictionary mapping words to numbers of occurrences you just need to pick the top N words by occurrences -- a heap-queue will help there, if the dictionary is just too large to sort by occurrences in its entirety (e.g. in my favorite executable pseudocode, heapq.nlargest will do it, for example).

Upvotes: 3