2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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()
\$\endgroup\$
1
\$\begingroup\$

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)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.