Fast n-gram calculation

by

Since you didn’t indicate whether you want word or character-level n-grams, I’m just going to assume the former, without loss of generality.

I also assume you start with a list of tokens, represented by strings. What you can easily do is write n-gram extraction yourself.

def ngrams(tokens, MIN_N, MAX_N):
    n_tokens = len(tokens)
    for i in xrange(n_tokens):
        for j in xrange(i+MIN_N, min(n_tokens, i+MAX_N)+1):
            yield tokens[i:j]

Then replace the yield with the actual action you want to take on each n-gram (add it to a dict, store it in a database, whatever) to get rid of the generator overhead.

Finally, if it’s really not fast enough, convert the above to Cython and compile it. Example using a defaultdict instead of yield:

def ngrams(tokens, int MIN_N, int MAX_N):
    cdef Py_ssize_t i, j, n_tokens

    count = defaultdict(int)

    join_spaces = " ".join

    n_tokens = len(tokens)
    for i in xrange(n_tokens):
        for j in xrange(i+MIN_N, min(n_tokens, i+MAX_N)+1):
            count[join_spaces(tokens[i:j])] += 1

    return count

More Related Contents:

  1. Computing N Grams using Python
  2. Fast/Optimize N-gram implementations in python
  3. How to use Stanford Parser in NLTK using Python
  4. Creating a new corpus with NLTK
  5. Python NLTK pos_tag not returning the correct part-of-speech tag
  6. Stopword removal with NLTK
  7. Ordinal numbers replacement
  8. How to config nltk data directory from code?
  9. n-grams in python, four, five, six grams?
  10. Convert words between verb/noun/adjective forms
  11. nltk NaiveBayesClassifier training for sentiment analysis
  12. NLTK Named Entity recognition to a Python list
  13. Using NLTK and WordNet; how do I convert simple tense verb into its present, past or past participle form?
  14. How do I tokenize a string sentence in NLTK?
  15. How to get rid of punctuation using NLTK tokenizer?
  16. English grammar for parsing in NLTK
  17. NLTK and language detection
  18. Extract Word from Synset using Wordnet in NLTK 3.0
  19. How do I do dependency parsing in NLTK?
  20. training data format for NLTK punkt
  21. Difference between Python’s collections.Counter and nltk.probability.FreqDist
  22. Saving nltk drawn parse tree to image file
  23. Creating a custom categorized corpus in NLTK and Python
  24. tag generation from a text content
  25. NLTK WordNet Lemmatizer: Shouldn’t it lemmatize all inflections of a word?
  26. What is NLTK POS tagger asking me to download?
  27. Implementing Bag-of-Words Naive-Bayes classifier in NLTK
  28. Using the Python NLTK (2.0b5) on the Google App Engine
  29. How to use malt parser in python nltk
  30. How to tweak the NLTK sentence tokenizer

Leave a Comment