Fast/Optimize N-gram implementations in python

by

Some attempts with some profiling. I thought using generators could improve the speed here. But the improvement was not noticeable compared to a slight modification of the original. But if you don’t need the full list at the same time, the generator functions should be faster.

import timeit
from itertools import tee, izip, islice

def isplit(source, sep):
    sepsize = len(sep)
    start = 0
    while True:
        idx = source.find(sep, start)
        if idx == -1:
            yield source[start:]
            return
        yield source[start:idx]
        start = idx + sepsize

def pairwise(iterable, n=2):
    return izip(*(islice(it, pos, None) for pos, it in enumerate(tee(iterable, n))))

def zipngram(text, n=2):
    return zip(*[text.split()[i:] for i in range(n)])

def zipngram2(text, n=2):
    words = text.split()
    return pairwise(words, n)


def zipngram3(text, n=2):
    words = text.split()
    return zip(*[words[i:] for i in range(n)])

def zipngram4(text, n=2):
    words = isplit(text, ' ')
    return pairwise(words, n)


s = "Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum."
s = s * 10 ** 3

res = []
for n in range(15):

    a = timeit.timeit('zipngram(s, n)', 'from __main__ import zipngram, s, n', number=100)
    b = timeit.timeit('list(zipngram2(s, n))', 'from __main__ import zipngram2, s, n', number=100)
    c = timeit.timeit('zipngram3(s, n)', 'from __main__ import zipngram3, s, n', number=100)
    d = timeit.timeit('list(zipngram4(s, n))', 'from __main__ import zipngram4, s, n', number=100)

    res.append((a, b, c, d))

a, b, c, d = zip(*res)

import matplotlib.pyplot as plt

plt.plot(a, label="zipngram")
plt.plot(b, label="zipngram2")
plt.plot(c, label="zipngram3")
plt.plot(d, label="zipngram4")
plt.legend(loc=0)
plt.show()

For this test data, zipngram2 and zipngram3 seems to be the fastest by a good margin.

enter image description here

More Related Contents:

  1. Computing N Grams using Python
  2. Fast n-gram calculation
  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. Classification using movie review corpus in NLTK/Python
  10. n-grams in python, four, five, six grams?
  11. Convert words between verb/noun/adjective forms
  12. nltk NaiveBayesClassifier training for sentiment analysis
  13. NLTK Named Entity recognition to a Python list
  14. Using NLTK and WordNet; how do I convert simple tense verb into its present, past or past participle form?
  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