title: Python: Pandas, fastest way to count occurrences of substring in dataframe
body: <p>I have a dataframe that has approximately 100,000 rows. "sequence" column in the dataframe has some long string as its value. I basically want to calculate the occurrence of substring in the "sequence" column with overlap <strong>(i.e. if the value is aaaaaa, and the substring is aa, then the frequency should be 5, not 3)</strong>. </p>
  
  <p>Below is the reproducible code that is similar to the actual code.</p>
  
  <pre><code>import pandas as pd
  import re
  import itertools
  import time
  from random import choice
  
  # generate 100,000 random strings of fixed size for demo purpose
  alphabet = "abcdefghijk"
  str_list = []
  
  for i in range(100000):
       str_list.append(''.join(choice(alphabet) for i in range(100)))
  # make pandas dataframe
  df = pd.DataFrame(columns=['sequence'], data=str_list)
  
  # get a list of substrings to count its frequency in the dataframe
  # for the sake of demo, make substrings from "alphabet" with length of 3
  # actual application can have up to substrings of length 5 (i.e. 11^5 substrings)
  words = [''.join(p) for p in itertools.product(alphabet, repeat=3))]
  
  # calculate frequency of words in the dataframe
  for word in words:
      tic = time.time()
      df['frequency'] = df['sequence'].apply(lambda x: len(re.findall('(?={0})'.format(word), x)))
      print("{}s took for one iteration".format(time.time() - tic))
  </code></pre>
  
  <p>Note that Pandas built-in function, "pd.Series.str.count", would count the occurrence of substring <strong>without</strong> overlaps, so I had to use apply in conjunction with regular expression.</p>
  
  <p>The problem is, on my computer it takes ~0.5 seconds to calculate frequency per each substring, and since there are 11^3 to 11^5 number of substrings, it could take up to 80,000 seconds (or 11 hours) in the worst case.</p>
  
  <p>It seems that lambda operation is slowing down the computational time since it has to be compiled in python instead of cython (which is inarguably faster than python), but I don't know how else to do this.</p>
  
  <p>I was wondering if there are ways to speed up this operation?</p>
  
  <p>p.s. I am using Python 3.5.2</p>