FlashText: The Regex Alternative for Blazing Fast NLP Keyword Matching

As natural language processing (NLP) datasets have exploded in size in recent years, the need for efficient text preprocessing and pattern matching algorithms has grown immensely. A common task in many NLP pipelines is searching for and replacing specific keywords in massive corpora containing millions of documents.

Traditionally, most developers and data scientists have reached for regular expressions (regex) as the tool of choice for pattern matching in strings. However, regex engines struggle to scale to very large keyword dictionaries, with runtimes often ballooning to many minutes or even hours.

In 2017, Vikash Singh open-sourced a new Python library called FlashText that promised to revolutionize the performance of keyword matching and replacement in NLP. By employing an optimized trie-based algorithm, FlashText claims to be hundreds of times faster than regex while having a much smaller memory footprint.

In this post, we‘ll dive into the computer science behind FlashText to understand what makes it so fast. We‘ll benchmark its performance against regex on huge keyword dictionaries and explore how it can be used to dramatically speed up text preprocessing pipelines. Finally, we‘ll consider the future of FlashText and other optimized algorithms within the NLP ecosystem.

Regex Matching is Slow for Huge Numbers of Keywords

To understand the need for a library like FlashText, let‘s first examine why using regular expressions for keyword matching can be problematic at a large scale. Consider the task of searching a corpus of text for any of a predefined set of tens of thousands of keywords.

The naive approach would be to iterate through the list of keywords and check each one against the corpus using regex. In Python, it might look something like this:

import re

def regex_match(keywords, text):
    matches = []
    for keyword in keywords:
        if re.search(r‘\b‘ + keyword + r‘\b‘, text):
            matches.append(keyword)
    return matches

This code loops through each keyword, checks if it appears in the text surrounded by word boundaries, and if so, adds it to the list of matches.

The problem is that the regex engine has to scan through the full input string looking for matches of the given pattern every single time we call re.search(). For a list of 10,000 keywords, that‘s 10,000 full scans of the text!

We could combine all the keywords into a single regex pattern to avoid multiple scans, but this still scales poorly. Regex matching time increases linearly with the number of characters in the pattern. For a very large keyword list, the pattern string itself becomes huge and slow to match.

The Aho-Corasick Algorithm: Fast Keyword Matching with a Trie

FlashText takes a completely different approach that allows it to match keywords in O(n) time, independent of the number of keywords. Under the hood, it implements the Aho-Corasick string searching algorithm.

Aho-Corasick works by storing the keywords in a trie data structure that allows for very fast retrieval. A trie, or prefix tree, is an ordered tree where each node represents a character and a path from the root to a node represents a prefix of one or more strings.

Here‘s an example of a trie containing the keywords "he", "she", "his", "hers":

Each leaf node (shaded in green) represents a complete keyword that can be matched. The special end-of-keyword symbol $ denotes the end of a word.

Aho-Corasick matches keywords using this trie through the following steps:

1. Construct the trie from the list of keywords
2. Initialize the search at the root node of the trie and the first character of the input string
3. For each character in the input string:
   • If the current node has a child edge for the character, follow it
   • If the current node is a leaf, match the keyword corresponding to the path from the root
   • If there is no matching child edge, follow the node‘s fail link to the next potential match
4. Repeat step 3 until the end of the input string

The fail links (denoted by dashed lines in the diagram) allow the algorithm to jump ahead to the next potential point in the trie that could match, rather than having to backtrack to the root each time.

Because of how the trie is constructed, Aho-Corasick guarantees that every keyword matched will be found in a single pass through the input string. The time complexity is O(n) where n is the length of the input, regardless of the number of keywords!

Compared to the quadratic worst-case complexity of naive regex search, this is a huge win. We can match a virtually unlimited number of keywords against huge corpora in seconds instead of hours.

FlashText Performance Benchmarks

Let‘s see just how much faster FlashText is compared to regex for different keyword matching scenarios. The FlashText documentation provides some benchmark data that we can examine:

For just 10 keywords, FlashText is already 4-6 times faster than the equivalentregex. As the number of keywords increases, the speedup becomes enormous.

At 1,000 keywords, FlashText is over 800 times faster than compiled regex. And at 10,000 keywords, it‘s a whopping 13,000 times faster! You‘d need a microscope to even see the FlashText bar on that benchmark chart.

The author of FlashText also ran some benchmarks on a 2.5 GB text corpus to compare FlashText and regex replace performance:

With regex, replacing 100,000 keywords in the 2.5 GB corpus took an agonizing 11.5 hours. FlashText did it in just 2 minutes and 27 seconds, a 279x speedup!

As FlashText author Vikash Singh puts it:

I started working on a dataset where I had to replace about 25K keywords in 2M sentences. Running a simple regex was taking more than 5 hours! I knew that there had to be a better way. That‘s when I started looking into the Aho-Corasick algorithm and eventually developed FlashText. Now I can do the same replacements in under 3 minutes.

With results like these, it‘s clear that for large-scale keyword matching and replacement, FlashText outperforms regex by orders of magnitude. Let‘s look at how we can use FlashText in Python to speed up our text processing pipelines.

Using FlashText in Python

The FlashText API is straightforward and similar to how you‘d use regex for searching and replacing keywords. Here are the key steps:

1. Install FlashText using pip:

    pip install flashtext

2. Import the KeywordProcessor class and initialize it:

    from flashtext import KeywordProcessor
   
    keyword_processor = KeywordProcessor(case_sensitive=True)

   Setting case_sensitive to True will match keywords based on case. The default is False for case-insensitive matching.

3. Add keywords to match using add_keyword():

    keyword_processor.add_keyword(‘Apple‘)
    keyword_processor.add_keyword(‘banana‘)
    keyword_processor.add_keyword(‘Orange‘)

   If you have a lot of keywords, you can also add them all at once from a list using add_keywords_from_list().

4. To search for keywords in some text, use extract_keywords():

    text = ‘I love eating a juicy Apple and a ripe banana.‘
    keywords_found = keyword_processor.extract_keywords(text)
    print(keywords_found)

   Output:

    [‘Apple‘, ‘banana‘] 

5. To replace keywords in text with something else, use replace_keywords():

    keyword_processor.add_keyword(‘Apple‘, ‘Grape‘)
    new_text = keyword_processor.replace_keywords(text)
    print(new_text)

   Output:

    I love eating a juicy Grape and a ripe banana.

That‘s the gist of it! You can also update and delete keywords, set word boundaries for matching, get the trie structure, and more. Check out the FlashText docs for the full API.

Use Cases for FlashText

So what kind of NLP tasks and pipelines can FlashText help speed up? Here are some examples:

• Text normalization: Replace common misspellings, abbreviations, slang, and other non-standard words with standardized versions. For example, mapping "ur" to "your", "b4" to "before", etc.

• Emoji and emoticon replacement: Map the myriad ways of expressing a concept in emoji or emoticons to a single code. For instance, replacing ":)", ":-)", and "=)" with something like "HAPPY_FACE".

• Multi-word expression matching: Efficiently match longer phrases that should be treated as a single semantic unit, like "New York City" or "ice cream sundae".

• Anonymization: Replace sensitive personal information like names, phone numbers, email addresses, etc. with placeholder tokens to anonymize a dataset.

• Taxonomy mapping: Match entities to a predefined taxonomy or knowledge base and map them to a unique ID. For example, a restaurant name to its ID in a places database.

• Keyword-based classification: Categorize a document based on the presence of domain-specific keywords. Customer support tickets talking about a "crash" or "bug" might get auto-classified as software issues.

• Profanity filtering: Quickly check a document against a list of profane words and blank them out.

Anytime you have a large but finite set of keywords or phrases to match against, FlashText is worth considering to speed things up.

The Future of Optimized NLP Algorithms

FlashText is just one example of how optimizing fundamental algorithms in NLP can lead to huge performance improvements. Other promising approaches include using highly-tuned finite state machines, parallel processing on GPUs, and techniques from information retrieval like inverted indices.

As datasets continue to grow and models become more complex, the need for better algorithms will only accelerate. Libraries like FlashText show how much headroom there still is to speed up core NLP building blocks.

Looking ahead, as techniques from deep learning continue to advance, we‘ll likely see even more creative approaches emerge. Some interesting areas to watch are things like joint model architectures that handle multiple preprocessing steps at once, dynamic computation graphs for conditional transformations, and learned indexes for ultra-fast retrieval.

One thing is clear – we can‘t rely on Moore‘s Law alone to compensate for the computational demands of modern NLP. Faster hardware is great, but at the end of the day we need faster algorithms too. FlashText is a shining example of the kind of clever algorithmic innovation that will help us scale NLP to greater heights.

Have you used FlashText or other optimized algorithms in your NLP pipelines? Let me know in the comments!

Credit to Vikash Singh for creating FlashText and writing the great intro posts that much of the research here is based on. Check out his blog for more performance-oriented NLP content.