Title: Replace or Retrieve Keywords In Documents at Scale,
Abstract: In this paper we introduce, the FlashText algorithm for replacing keywords or
finding keywords in a given text. FlashText can search or replace keywords in
one pass over a document. The time complexity of this algorithm is not
dependent on the number of terms being searched or replaced. For a document of
size N (characters) and a dictionary of M keywords, the time complexity will be
O(N). This algorithm is much faster than Regex, because regex time complexity
is O(MxN). It is also different from Aho Corasick Algorithm, as it doesn't
match substrings. FlashText is designed to only match complete words (words
with boundary characters on both sides). For an input dictionary of {Apple},
this algorithm won't match it to 'I like Pineapple'. This algorithm is also
designed to go for the longest match first. For an input dictionary {Machine,
Learning, Machine learning} on a string 'I like Machine learning', it will only
consider the longest match, which is Machine Learning. We have made python
implementation of this algorithm available as open-source on GitHub, released
under the permissive MIT License.