Processing vast amounts of text data is a common task in modern computing, whether for log analysis, natural language processing, or data cleaning. When dealing with millions of records, even seemingly simple operations like regular expression replacements can become significant performance bottlenecks. If you’re finding that your Python 3 scripts are grinding to a halt when attempting to speed up millions of regex replacements in Python 3, you’re not alone. This challenge often arises due to the inherent overhead of regex engine operations and Python’s string handling. Fortunately, with a strategic approach to code optimization and an understanding of Python’s re module, you can dramatically reduce execution times and ensure your data processing pipelines run efficiently, transforming what once seemed like an insurmountable task into a manageable one.

Understanding Python’s re Module and Performance Bottlenecks

Python’s built-in re module is a powerful tool for pattern matching and string manipulation. However, its flexibility comes with a cost, especially when performing a high volume of replacements. A primary reason for slowdowns is the dynamic compilation of regex patterns. Each time you call functions like re.sub() with a string pattern, Python’s regex engine must compile that pattern into an internal bytecode representation before it can execute the search and replace operation. While this is negligible for a few operations, repeating this compilation millions of times accumulates substantial overhead.

Another factor contributing to performance issues is Python’s string immutability. Every time a replacement occurs, a new string object is created in memory, copying parts of the original string and inserting the replacement. For numerous replacements within a large string, or across many strings, this constant memory allocation and deallocation can lead to increased garbage collection activity and cache misses, further degrading performance. Understanding these foundational aspects is crucial for identifying where optimizations can yield the most significant gains in your large-scale string processing tasks.

According to a benchmark analysis by Real Python, using re.compile() can offer substantial speed improvements for repeated regex operations, precisely because it avoids this repeated compilation step. This emphasizes the importance of pre-compiling patterns when working with extensive datasets or within performance-critical loops, serving as a fundamental first step toward achieving better Python regex performance.

Strategies for Optimizing Single-Pattern Replacements

When your task involves replacing a single, consistent regex pattern across millions of strings, the most impactful optimization is to pre-compile your regular expression. The re.compile() function takes your regex pattern as an argument and returns a regex object. This object has methods like sub() and subn() that perform the replacement without needing to re-compile the pattern each time. This technique significantly reduces the overhead associated with pattern interpretation and is a cornerstone for efficient regex handling in Python 3.

For scenarios where you simply need to replace a fixed substring with another fixed substring, bypass the regex engine entirely by using Python’s built-in string methods like .replace(). The str.replace() method is highly optimized in C and is orders of magnitude faster than re.sub() for literal string replacements because it avoids the complexity of regex parsing. Only resort to regular expressions when your pattern involves actual patterns (e.g., wildcards, character sets, quantifiers).

Consider the following steps to optimize single-pattern replacements:

1. Analyze Your Pattern: Determine if your replacement truly requires regular expressions or if a simple string replacement will suffice. If it’s a fixed string-to-string replacement, use str.replace().
2. Compile Your Regex: If a regex is necessary, compile the pattern once outside your loop using compiled_pattern = re.compile(r’your_pattern’).
3. Execute Replacements: Inside your loop, call compiled_pattern.sub(‘replacement_string’, target_string). This ensures that the pattern is compiled only once, greatly enhancing execution speed for repeated operations.

This approach to re module optimization ensures that the most time-consuming part of regex processing—pattern compilation—is handled just once, leaving the regex engine to focus purely on the pattern matching and replacement, which is critical for large-scale string processing.

Handling Multiple Regex Patterns Efficiently

When you need to apply several different regex patterns and their corresponding replacements to a large body of text or a collection of strings, simply iterating through each pattern and applying re.sub() individually can quickly become inefficient. A more optimized approach involves consolidating your patterns and replacements and applying them systematically. Instead of multiple passes over the data, we aim to minimize passes or combine operations where possible. This is where strategic use of compiled patterns and potentially more advanced techniques like the Aho-Corasick algorithm (for fixed string matching, though less direct for complex regex) can make a substantial difference in large-scale string processing.

One effective strategy is to create a list of compiled regex objects and iterate through them for each target string. This still involves multiple passes over a single string, but ensures each regex is compiled only once. For very specific cases where patterns are simple and replacements are fixed, you might consider creating a dictionary mapping patterns to replacements and then iterating. However, for complex overlapping patterns, this can be tricky. A more sophisticated method for non-overlapping patterns or when replacement order matters is to manage a series of compiled regex objects.

Key considerations for optimizing multiple regex replacements:

• Pre-compile All Patterns: Just as with single patterns, compile every regex pattern you intend to use once, storing them in a list or dictionary.
• Order of Operations: The order in which you apply multiple replacements can significantly affect the outcome and efficiency, especially if patterns overlap or modify text that subsequent patterns might match. Plan your sequence carefully.
• Batch Processing: Instead of processing one string at a time, consider batching your strings. This can sometimes leverage CPU cache more effectively and reduce Python’s interpreter overhead, especially if you pass chunks of data to a function that processes them.

For highly complex scenarios involving hundreds or thousands of unique patterns that need to be applied concurrently, the standard re module might reach its limits. In such cases, exploring alternative modules like the regex module, which offers more advanced features and potentially better performance for certain operations, or even specialized text processing libraries could be beneficial for achieving higher regex efficiency. This module is a drop-in replacement for re and often provides extended functionality and performance improvements.

Advanced Techniques for Extreme Performance

When even compiled patterns and optimized single-pass strategies aren’t enough, it’s time to consider more advanced techniques. For datasets so large they strain single-core processing, leveraging concurrency is often the next step. Python’s multiprocessing module can distribute the workload across multiple CPU cores, allowing segments of your data to be processed in parallel. This is particularly effective for “embarrassingly parallel” tasks, where each string or chunk of text can be processed independently without affecting others. Carefully chunking your input data into manageable segments and assigning each chunk to a separate process can dramatically **speed up Question & Answer :
I have two lists:

- a list of about 750K “sentences” (long strings) - a list of about 20K “words” that I would like to delete from my 750K sentences

So, I have to loop through 750K sentences and perform about 20K replacements, but ONLY if my words are actually “words” and are not part of a larger string of characters.

I am doing this by pre-compiling my words so that they are flanked by the \b word-boundary metacharacter:

compiled_words = [re.compile(r'\b' + word + r'\b') for word in my20000words] 

Then I loop through my “sentences”:

import re for sentence in sentences: for word in compiled_words: sentence = re.sub(word, "", sentence) # put sentence into a growing list 

This nested loop is processing about 50 sentences per second, which is nice, but it still takes several hours to process all of my sentences.

- Is there a way to using the str.replace method (which I believe is faster), but still requiring that replacements only happen at word boundaries? - Alternatively, is there a way to speed up the re.sub method? I have already improved the speed marginally by skipping over re.sub if the length of my word is > than the length of my sentence, but it’s not much of an improvement.

I’m using Python 3.5.2

TLDR

Use this method if you want the fastest regex-based solution. For a dataset similar to the OP’s, it’s approximately 1000 times faster than the accepted answer.

If you don’t care about regex, use this set-based version, which is 2000 times faster than a regex union.

Optimized Regex with Trie

A simple Regex union approach becomes slow with many banned words, because the regex engine doesn’t do a very good job of optimizing the pattern.

It’s possible to create a Trie with all the banned words and write the corresponding regex. The resulting trie or regex aren’t really human-readable, but they do allow for very fast lookup and match.

Example -——

['foobar', 'foobah', 'fooxar', 'foozap', 'fooza'] 

The list is converted to a trie:

{ 'f': { 'o': { 'o': { 'x': { 'a': { 'r': { '': 1 } } }, 'b': { 'a': { 'r': { '': 1 }, 'h': { '': 1 } } }, 'z': { 'a': { '': 1, 'p': { '': 1 } } } } } } } 

And then to this regex pattern:

r"\bfoo(?:ba[hr]|xar|zap?)\b" 

The huge advantage is that to test if zoo matches, the regex engine only needs to compare the first character (it doesn’t match), instead of trying the 5 words. It’s a preprocess overkill for 5 words, but it shows promising results for many thousand words.

Note that (?:) non-capturing groups are used because:

- foobar|baz would match foobar or baz, but not foobaz - foo(bar|baz) would save unneeded information to a capturing group.

Code -—

Here’s a slightly modified gist, which we can use as a trie.py library:

import re class Trie(): """Regex::Trie in Python. Creates a Trie out of a list of words. The trie can be exported to a Regex pattern. The corresponding Regex should match much faster than a simple Regex union.""" def __init__(self): self.data = {} def add(self, word): ref = self.data for char in word: ref[char] = char in ref and ref[char] or {} ref = ref[char] ref[''] = 1 def dump(self): return self.data def quote(self, char): return re.escape(char) def _pattern(self, pData): data = pData if "" in data and len(data.keys()) == 1: return None alt = [] cc = [] q = 0 for char in sorted(data.keys()): if isinstance(data[char], dict): try: recurse = self._pattern(data[char]) alt.append(self.quote(char) + recurse) except: cc.append(self.quote(char)) else: q = 1 cconly = not len(alt) > 0 if len(cc) > 0: if len(cc) == 1: alt.append(cc[0]) else: alt.append('[' + ''.join(cc) + ']') if len(alt) == 1: result = alt[0] else: result = "(?:" + "|".join(alt) + ")" if q: if cconly: result += "?" else: result = "(?:%s)?" % result return result def pattern(self): return self._pattern(self.dump()) 

Test -—

Here’s a small test (the same as this one):

# Encoding: utf-8 import re import timeit import random from trie import Trie with open('/usr/share/dict/american-english') as wordbook: banned_words = [word.strip().lower() for word in wordbook] random.shuffle(banned_words) test_words = [ ("Surely not a word", "#surely_NöTäWORD_so_regex_engine_can_return_fast"), ("First word", banned_words[0]), ("Last word", banned_words[-1]), ("Almost a word", "couldbeaword") ] def trie_regex_from_words(words): trie = Trie() for word in words: trie.add(word) return re.compile(r"\b" + trie.pattern() + r"\b", re.IGNORECASE) def find(word): def fun(): return union.match(word) return fun for exp in range(1, 6): print("\nTrieRegex of %d words" % 10**exp) union = trie_regex_from_words(banned_words[:10**exp]) for description, test_word in test_words: time = timeit.timeit(find(test_word), number=1000) * 1000 print(" %s : %.1fms" % (description, time)) 

It outputs:

TrieRegex of 10 words Surely not a word : 0.3ms First word : 0.4ms Last word : 0.5ms Almost a word : 0.5ms TrieRegex of 100 words Surely not a word : 0.3ms First word : 0.5ms Last word : 0.9ms Almost a word : 0.6ms TrieRegex of 1000 words Surely not a word : 0.3ms First word : 0.7ms Last word : 0.9ms Almost a word : 1.1ms TrieRegex of 10000 words Surely not a word : 0.1ms First word : 1.0ms Last word : 1.2ms Almost a word : 1.2ms TrieRegex of 100000 words Surely not a word : 0.3ms First word : 1.2ms Last word : 0.9ms Almost a word : 1.6ms 

For info, the regex begins like this:

> (?:a(?:(?:\’s|a(?:\’s|chen|liyah(?:\’s)?|r(?:dvark(?:(?:\’s|s))?|on))|b(?:\’s|a(?:c(?:us(?:(?:\’s|es))?|[ik])|ft|lone(?:(?:\’s|s))?|ndon(?:(?:ed|ing|ment(?:\’s)?|s))?|s(?:e(?:(?:ment(?:\’s)?|[ds]))?|h(?:(?:e[ds]|ing))?|ing)|t(?:e(?:(?:ment(?:\’s)?|[ds]))?|ing|toir(?:(?:\’s|s))?))|b(?:as(?:id)?|e(?:ss(?:(?:\’s|es))?|y(?:(?:\’s|s))?)|ot(?:(?:\’s|t(?:\’s)?|s))?|reviat(?:e[ds]?|i(?:ng|on(?:(?:\’s|s))?))|y(?:\’s)?|\é(?:(?:\’s|s))?)|d(?:icat(?:e[ds]?|i(?:ng|on(?:(?:\’s|s))?))|om(?:en(?:(?:\’s|s))?|inal)|u(?:ct(?:(?:ed|i(?:ng|on(?:(?:\’s|s))?)|or(?:(?:\’s|s))?|s))?|l(?:\’s)?))|e(?:(?:\’s|am|l(?:(?:\’s|ard|son(?:\’s)?))?|r(?:deen(?:\’s)?|nathy(?:\’s)?|ra(?:nt|tion(?:(?:\’s|s))?))|t(?:(?:t(?:e(?:r(?:(?:\’s|s))?|d)|ing|or(?:(?:\’s|s))?)|s))?|yance(?:\’s)?|d))?|hor(?:(?:r(?:e(?:n(?:ce(?:\’s)?|t)|d)|ing)|s))?|i(?:d(?:e[ds]?|ing|jan(?:\’s)?)|gail|l(?:ene|it(?:ies|y(?:\’s)?)))|j(?:ect(?:ly)?|ur(?:ation(?:(?:\’s|s))?|e[ds]?|ing))|l(?:a(?:tive(?:(?:\’s|s))?|ze)|e(?:(?:st|r))?|oom|ution(?:(?:\’s|s))?|y)|m\’s|n(?:e(?:gat(?:e[ds]?|i(?:ng|on(?:\’s)?))|r(?:\’s)?)|ormal(?:(?:it(?:ies|y(?:\’s)?)|ly))?)|o(?:ard|de(?:(?:\’s|s))?|li(?:sh(?:(?:e[ds]|ing))?|tion(?:(?:\’s|ist(?:(?:\’s|s))?))?)|mina(?:bl[ey]|t(?:e[ds]?|i(?:ng|on(?:(?:\’s|s))?)))|r(?:igin(?:al(?:(?:\’s|s))?|e(?:(?:\’s|s))?)|t(?:(?:ed|i(?:ng|on(?:(?:\’s|ist(?:(?:\’s|s))?|s))?|ve)|s))?)|u(?:nd(?:(?:ed|ing|s))?|t)|ve(?:(?:\’s|board))?)|r(?:a(?:cadabra(?:\’s)?|d(?:e[ds]?|ing)|ham(?:\’s)?|m(?:(?:\’s|s))?|si(?:on(?:(?:\’s|s))?|ve(?:(?:\’s|ly|ness(?:\’s)?|s))?))|east|idg(?:e(?:(?:ment(?:(?:\’s|s))?|[ds]))?|ing|ment(?:(?:\’s|s))?)|o(?:ad|gat(?:e[ds]?|i(?:ng|on(?:(?:\’s|s))?)))|upt(?:(?:e(?:st|r)|ly|ness(?:\’s)?))?)|s(?:alom|c(?:ess(?:(?:\’s|e[ds]|ing))?|issa(?:(?:\’s|[es]))?|ond(?:(?:ed|ing|s))?)|en(?:ce(?:(?:\’s|s))?|t(?:(?:e(?:e(?:(?:\’s|ism(?:\’s)?|s))?|d)|ing|ly|s))?)|inth(?:(?:\’s|e(?:\’s)?))?|o(?:l(?:ut(?:e(?:(?:\’s|ly|st?))?|i(?:on(?:\’s)?|sm(?:\’s)?))|v(?:e[ds]?|ing))|r(?:b(?:(?:e(?:n(?:cy(?:\’s)?|t(?:(?:\’s|s))?)|d)|ing|s))?|pti…

It’s really unreadable, but for a list of 100000 banned words, this Trie regex is 1000 times faster than a simple regex union!

Here’s a diagram of the complete trie, exported with trie-python-graphviz and graphviz twopi:

**