Regex was taking 5 days to run. So I built a tool that did it in 15 minutes.
Tags: opensource, python, nlp, informationretrieval
Published: 2017-12-10 11:10:00

---
title: Regex was taking 5 days to run. So I built a tool that did it in 15 minutes.
published: true
description: Regex is quite slow when number of terms to find/replace is in thousands.
tags: opensource,python,NLP,InformationRetrieval
cover_image: https://thepracticaldev.s3.amazonaws.com/i/03gb8bcdfh6mnlknxw8n.jpg
canonical_url: https://github.com/vi3k6i5/flashtext
---

When developers work with text, they often need to clean it up first. Sometimes it’s by replacing keywords. Like replacing “Javascript” with “JavaScript”. Other times, we just want to find out whether “JavaScript” was mentioned in a document.

Data cleaning tasks like these are standard for most Data Science projects dealing with text.

## Data Science starts with data cleaning.

I had a very similar task to work on recently. I work as a Data Scientist at [Belong.co](https://belong.co/) and Natural Language Processing is half of my work.

When I trained a Word2Vec model on our document corpus, it started giving synonyms as similar terms. “Javascripting” was coming as a similar term to “JavaScript”.

To resolve this, I wrote a regular expression (Regex) to replace all known synonyms with standardized names. The Regex replaced “Javascripting” with “JavaScript”, which solved 1 problem but created another.

```
Some people, when confronted with a problem, think 
“I know, I’ll use regular expressions.” Now they have two problems.
```

The above quote is from this [stack-exchange question](https://softwareengineering.stackexchange.com/questions/223634/what-is-meant-by-now-you-have-two-problems) and it came true for me.

It turns out that Regex is fast if the number of keywords to be searched and replaced is in the 100s. But my corpus had over 10s of Thousands of keywords and a few Million documents.

When I benchmarked my Regex code, I found it was going to take **5 days** to complete one run. My reaction:

![Oh the horror.](https://cdn-images-1.medium.com/max/1600/1*GpNMd7fBtrH4TvVZRglfNg.jpeg)

**Clearly something needed to be done.**

[Update]

I started with trying to optimise the Regex I was using. I learned that compiled regex are faster so I switched to it. To replace multiple terms together ther is group option and I adapted that. I was still having trouble with keywords having special characters like 'C++', '.Net' [Link](https://stackoverflow.com/questions/45813658/regex-not-replacing-word-starting-with-or-ending-with-like-net-or-c).
Sorting the keywords when loading into regex also improved the performance.

My best learnings came from this [Link](https://www.reddit.com/r/programming/comments/7j3433/regex_was_taking_5_days_to_run_so_i_built_a_tool/). Trie Based regex are faster [Link](https://stackoverflow.com/questions/42742810/speed-up-millions-of-regex-replacements-in-python-3/42789508#42789508) I didn't Know about this when I started my project, But I went in the same direction of using a Trie.

I don't mean to say that Regex in general are bad, It's just really hard to understand so many different implementations. I was using the Python version, where as RUST has a compiled version which is even faster. Also there are c++ versions which are even more faster.

If you are solely looking for speed maybe you can try one of those. I needed more control and simplicity in use so I built a tool. This helped me abstract the details out making sure anyone with little knowledge of Regex could use it.

[Update End]

I asked around in my office and on stack-overflow. And a couple of suggestions came up. Both [Vinay](https://www.linkedin.com/in/vinay-pande-54810813/), [Suresh](https://www.linkedin.com/in/suresh-lakshmanan/) and [Stack Overflow](https://stackoverflow.com/questions/44178449/regex-replace-is-taking-time-for-millions-of-documents-how-to-make-it-faster) pointed towards this beautiful algorithm called [Aho-Corasick algorithm](https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm) and [Trie](https://en.wikipedia.org/wiki/Trie) dictionary approach. I looked for some existing solutions but couldn’t find much. 

So I wrote my own implementation and [FlashText](https://github.com/vi3k6i5/flashtext) was born.

Before we get into what is FlashText and how it works, let’s have a look at how it performs.

Time taken by FlashText to find terms in comparison to Regex.
![Time taken by FlashText to find terms in comparison to Regex.](https://thepracticaldev.s3.amazonaws.com/i/xruf50n6z1r37ti8rd89.png)

The chart shown above is a comparison of Complied Regex against FlashText for 1 document. As the number of keywords increase, the time taken by Regex grows almost linearly. Yet with FlashText it doesn’t matter.

## FlashText reduced our run time from 5 days to 15 minutes!!

![We are good now :)](https://cdn-images-1.medium.com/max/1600/1*ZfRhHGtxhbEB0dS-3BHOAw.png)

Time taken by FlashText to replace terms in comparison to Regex.
![Time taken by FlashText to replace terms in comparison to Regex.](https://thepracticaldev.s3.amazonaws.com/i/k44ghwp8o712dm58debj.png)

Code used for the benchmark shown above is linked [here] (https://gist.github.com/vi3k6i5/604eefd92866d081cfa19f862224e4a0), and [here] (https://gist.github.com/vi3k6i5/dc3335ee46ab9f650b19885e8ade6c7a).


## So what is FlashText?

FlashText is a Python library that I open sourced on [GitHub](https://github.com/vi3k6i5/flashtext). It is efficient at both extracting keywords and replacing them.

To use FlashText first you have to pass it a list of keywords. This list will be used internally to build a Trie dictionary. Then you pass a string to it and tell if you want to perform replace or search.

For `replace` it will create a new string with replaced keywords. For `search` it will return a list of keywords found in the string. This will all happen in one pass over the input string.

Here is what one happy user had to say about the library:

{% twitter 904989624589803520 %}

Radim Rehurek is the creator of Gensim.


## Why is FlashText so fast ?

Let’s try and understand this part with an example. Say we have a sentence which has 3 words `I like Python`, and a corpus which has 4 words `{Python, Java, J2ee, Ruby}`.

If we take each word from the corpus, and check if it is present in sentence, it will take 4 tries.

```
is 'Python' in sentence? 
is 'Java' in sentence?
...
```

If the corpus had `n` words it would have taken `n` loops. Also each search step `is <word> in sentence?` will take its own time. This is kind of what happens in Regex match.

There is another approach which is reverse of the first one. For each word in the sentence, check if it is present in corpus.

```
is 'I' in corpus?
is 'like' in corpus?
is 'python' in corpus?
```

If the sentence had `m` words it would have taken `m` loops. In this case the time it takes is only dependent on the number of words in sentence. And this step, `is <word> in corpus?` can be made fast using a dictionary lookup.

FlashText algorithm is based on the second approach. It is inspired by the Aho-Corasick algorithm and Trie data structure.

The way it works is: First a Trie dictionary is created with the corpus. It will look somewhat like this

![Trie dictionary of the corpus.](https://cdn-images-1.medium.com/max/1600/1*N09Y_XEQFhFMxVpgEeqExQ.png)


`Start` and `EOT` (End Of Term) represent word boundaries like `space`, `period` and `new_line`. A keyword will only match if it has word boundaries on both sides of it. This will prevent matching apple in pineapple.

Next we will take an input string `I like Python` and search it character by character.

```
Step 1: is <start>I<EOT> in dictionary? No
Step 2: is <start>like<EOT> in dictionary? No
Step 3: is <start>Python<EOT> in dictionary? Yes
```

![<Start> Python <EOT> is present in dictionary.](https://cdn-images-1.medium.com/max/1600/1*noWWci3fCrbcbrj40B4UaA.png)


Since this is a character by character match, we could easily skip `<start>like<EOT>` at `<start>l` because `l` is not connected to `start`. This makes skipping missing words really fast.

The FlashText algorithm only went over each character of the input string ‘I like Python’. The dictionary could have very well had a million keywords, with no impact on the runtime. This is the true power of FlashText algorithm.

You can get similar speed by building Trie based Regex [Link](https://stackoverflow.com/questions/42742810/speed-up-millions-of-regex-replacements-in-python-3/42789508#42789508) 

## So when should you use FlashText?

Simple Answer: When Number of keywords > 500

![FlashText outperforms Regex for Find when Number of keywords > 500](https://thepracticaldev.s3.amazonaws.com/i/kzg3ol40sfuzpodazspp.png)

Complicated Answer: Regex can search for terms based on regular expression special characters like `^,$,*,\d,.` all this is not supported in FlashText. All FlashText understands the Start and End of terms. Simply speaking it understands `\w,\b`.
So it’s no good if you want to match partial words like `word\dvec`. But it is excellent for extracting complete words like `word2vec`.

## How to use FlashText

To Find Terms:

{% gist https://gist.github.com/vi3k6i5/eabca9de9853e523d142beed46654d4e %}

To Replace Terms:

{% gist https://gist.github.com/vi3k6i5/eebf91c643adfb1b38ae04a6c5d01e77 %}


## What Next?

If you know someone who works on Entity recognition, NLP, Word2vec, Keras, Tensorflow please share this blog with them. This library has been really useful for us. I am sure it would be useful for others also.

Originally posted [here] (https://medium.freecodecamp.org/regex-was-taking-5-days-flashtext-does-it-in-15-minutes-55f04411025f)

:wq