title: Fast multiple search and replace in Python
body: <p>For a single large text (~4GB) I need to search for ~1million phrases and replace them with complementary phrases. Both the raw text and the replacements can easily fit in memory. The naive solution will literally takes years to finish as a single replacement takes about a minute.</p>
  
  <p>Naive solution:</p>
  
  <pre><code>for search, replace in replacements.iteritems():
      text = text.replace(search, replace)
  </code></pre>
  
  <p>The regex method using <code>re.sub</code>is x10 slower:</p>
  
  <pre><code>for search, replace in replacements.iteritems():
      text = re.sub(search, replace, text)
  </code></pre>
  
  <p>At any rate, this seems like a great place use Boyer-Moore string, or Aho-Corasick; but these methods as they are generally implemented only work for <em>searching</em> the string and not also replacing it. </p>
  
  <p>Alternatively, any tool (outside of Python) that can do this quickly would also be appreciated. </p>
  
  <p>Thanks!</p>