3 ms·
What is the tree (trie?) structure and sorting-and-aggregating that you mean? Assuming the corpus is not too big, the solution can be thrown together in Python
by ntoshev 17y ago
What is the tree (trie?) structure and sorting-and-aggregating that you mean?
Assuming the corpus is not too big, the solution can be thrown together in Python in a few minutes.
import re, collections
def words(text): return re.findall('[a-z]+', text.lower())
def train(features):
model = collections.defaultdict(lambda: 1)
for f in features:
model[f] += 1
return model
NWORDS = train(words(file('corpus.txt').read()))
import heapq, operator
freq_words = heapq.nlargest(10000, NWORDS.iteritems(), key=operator.itemgetter(1))
This code processes 12Mb of text in less than 5 seconds on my laptop.
- cperciva 17y agoWhat is the tree (trie?) structure and sorting-and-aggregating that you mean? The tree structure: Put all the unique words into a tree. You could use a trie, but considering how dense the tree is likely to end up, a traditional split-26-ways-on-each-byte tree would probably work just as well. The sorting-and-aggregating option: Run a traditional mergesort, but attach counters (initialized to 1) to each word; and every time you find yourself comparing two identical words, replace them by a single record with the sum of the counters.