Finding top most N common character grams in English

Question

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

Answer 1

Building up on Caleth's answer:

• 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()

Answer 2

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)