# Finding top most N common character grams in English

I suspect there might be a much more efficient way to accomplish this task. I would appreciate a more clever hint for performance increase. I am also looking for feedback on style and simplification where appropriate.

I assume that the set of what counts as English words is a given and that I don't need to do something clever like an actual dictionary or use Google n-grams. That being said, the results could differ depending on the domain and also what is accepted as a word.

The original problem set M=3 (3-gram characters), which makes the results not so interesting (ans=[(u'the', 191279), (u'and', 92292), (u'ing', 57323), (u'her', 44627), (u'hat', 38609)]).

#gets the top N most common substrings of M characters in English words
from nltk import FreqDist
from nltk.corpus import gutenberg

def get_words():
for fileid in gutenberg.fileids():
for word in gutenberg.words(fileid):
yield word

def ngrams(N, which_list, strict=False):
list_size = len(which_list)
stop = list_size
if strict:
stop -= (N - 1)
for i in xrange(0, stop):
element = which_list[i]
ngram = [element]
j = 1
index = j + i
while j < N and index < list_size:
ngram.append(which_list[index])
j += 1
index += 1
yield ''.join(ngram)

def m_most_common_ngram_chars(M=5, N=3):
n_grams = []
for word in get_words():
for ngram in ngrams(N, word, strict=True):
n_grams.append(ngram)
f = FreqDist(n_grams)
return f.most_common(M)

l = m_most_common_ngram_chars(M=5, N=3)
print l


• Beware that:

def ngrams(N, word):
for i in xrange(len(word) - N):
yield word[i:i+N]


will not account for the last character:

for g in ngrams(3, "small"):
print(g)


will output

sma
mal


If it was the purpose of the strict parameter to allow to include/skip the last character (and be able to print the missing all), you can use it that way:

def ngrams(N, words, strict=True):
last = int(strict)
for i in xrange(len(word) - N + last):
yield word[i:i+N]


If, however, you wanted to allow to generate n_grams whose length is lower than N:

def ngrams(N, words, strict=True):
last = N - 1 if strict else 0
for i in xrange(len(word) - last):
yield word[i:i+N]

• As per the documentation, FreqDist accepts generators in its constructor. It is thus more memory efficient to turn the n_grams list into a generator:

n_grams = (ngram for ngram in ngrams(N, word) for word in get_words())

• Your top comment would be most suited as a docstring for the m_most_common_ngram_chars function. In fact, each function might need its own docstring.

• Since almost all your code is functions, you may want to put your last two lines into the module check if __name__ == "__main__":. It will allow you to run your code from the command line as usual and it will do exactly the same thing; but also to import it and call the function with other parameters without running anything at import time.

from nltk import FreqDist
from nltk.corpus import gutenberg

def get_words():
"""generate english words from the whole gutemberg corpus"""
for fileid in gutenberg.fileids():
for word in gutenberg.words(fileid):
yield word

def ngrams(N, word, strict=True):
"""generate a sequence of N-sized substrings of word.
if strict is False, also account for P-sized substrings
at the end of the word where P < N"""

last = N - 1 if strict else 0
for i in xrange(len(word) - last):
yield word[i:i+N]

def m_most_common_ngram_chars(M=5, N=3):
"""gets the top M most common substrings of N characters in English words"""
f = FreqDist(ngram for ngram in ngrams(N, word) for word in get_words())
return f.most_common(M)

if __name__ == "__main__":
# Uses the default values M=5, N=3
print m_most_common_ngram_chars()


ngrams seems overly verbose for generating substrings. You are just slicing the word. xrange() has a single parameter usage for starting at 0. I also don't like the identifier which_list, I prefer word or root_word in this context.

Also ignoring the parameter strict which is never false in your usage (and I think would be inconsistent with a normal definition of ngram)

def ngrams(N, word):
for i in xrange(len(word) - N):
yield word[i:i+N]


I don't know if FreqDist needs a list or just an iterable, the following list comprehension can be a generator if that is allowed.

def m_most_common_ngram_chars(M=5, N=3):
n_grams = [ngram for ngram in ngrams(N, word) for word in get_words()]
f = FreqDist(n_grams)
return f.most_common(M)