Regex replace is taking time for millions of documents, how to make it faster?

Question

I have documents like:

documents = [
    "I work on c programing.",
    "I work on c coding.",
]

I have synonym file such as:

synonyms = {
    "c programing": "c programing",
    "c coding": "c programing"
}

I want to replace all synonyms for which I wrote this code:

# added code to pre-compile all regex to save compilation time. credits alec_djinn

compiled_dict = {}
for value in synonyms:
    compiled_dict[value] = re.compile(r'\b' + re.escape(value) + r'\b')

for doc in documents:
    document = doc
    for value in compiled_dict:
        lowercase = compiled_dict[value]
        document = lowercase.sub(synonyms[value], document)
    print(document)

Output:

I work on c programing.
I work on c programing.

But since the number of documents is a few million and the number of synonym terms are in 10s of thousands, the expected time for this code to finish is 10 days approx.

Is there a faster way to do this?

PS: with the output I want to train word2vec model.

Any help is greatly appreciated. I was thinking of writing some cpython code and putting it in parallel threads.

Answer 1

I have done string replacement jobs like this before, also for training word2vec models on very large text corpora. When the number of terms to replace (your "synonym terms") is very large, it can make sense to do string replacement using the Aho-Corasick algorithm instead of looping over many single string replacements. You can take a look at my fsed utility (written in Python), which might be useful to you.

Answer 2

Steps I'd take:

1. Create a direct algorithm without regex. Maybe event generate code based on the synonyms directly.
2. Partition the work on the documents so that you can run this algorithm directly on N/x documents, and split to make the most of the parallel resources (e.g. x = 4 if you have 4 cores) and run using a parallel approach (note: avoid using threads)
3. Maybe use a library to help with running this on parallel and if you have the resources on multiple nodes (e.g. using spark).

Answer 3

I would precompile all the regex strings and put them in a dict. In this way you avoid to compile over and over the same value. It will save lot's of time.

Your main loop would then become:

compiled_dict = {}
for value in synonyms:
        compiled_dict[value] = re.compile(r'\b' + re.escape(value) + r'\b')


for document in documents:
    for value in synonyms:
        lowercase = compiled_dict[value]
        document = lowercase.sub(synonyms[value], document)

Answer 4

First of all, the code you provided will not find c++ in c++. as the terminating dot does not give a match with \b. Instead of \b you could use (?!\w).

Assuming that most synonyms will be for single words (without spaces and special characters), you could get some optimisation by looking at each actual word in the document and replace it when it occurs as such in the synonyms list.

All the remaining synonyms keys (hopefully a minority) could then be treated like you did, but by first turning the keys into their regex equivalent.

Here is how that would look:

import re

# Get those synonyms that are not single words and turn them into regexes:
# Don't use \b to end a pattern; just require that no \w should follow 
complex_synonyms = [(r'\b' + re.escape(key) + r'(?!\w)', synonyms[key]) for key in synonyms if not re.match(r'[\w+]+$', key)]

for i, document in enumerate(documents):
    # Deal with the easy cases (words) in one go, by checking each word in the document
    document = re.sub(r'[\w+]+', lambda word: synonyms[word[0]] if word[0] in synonyms else word[0], document)
    # Replace the remaining synonyms by using regular expressions
    for find, repl in complex_synonyms:
        document = re.sub(find, repl, document)
    # Store the result back into the document
    documents[i] = document