This PR tries to introduce fuzzy matching in flashtext, as mentioned in these issues:

• Support Fuzzy Matching
• Handle spell error idea

Guidelines

• rely the most we can on the existing algorithm : only trigger fuzzy matching when we have a mismatch, so we keep a focus on performance
• if adding new parameters, the function should keep the exact same behaviour when this parameter is left to its default value, so we don't get any conflict with the other tests
• modify the less code as possible

Features included

1. KeywordProcessor.extract_keywords and KeywordProcessor.replace_keywords both have a new optional parameter : max_cost, which is the maximum levensthein distance accepted to perform fuzzy matching on a single keyword
2. KeywordProcessor implements a levensthein function, which tries to find a match with a given word, with respect to a provided max_cost, and returns a node in the trie, which will be used to continue the search
3. a new function has been included : get_next_word, which just retrieve the next word in the sequence. Tests are included in test/test_kp_next_word.py

Optimizations to keep focus on performance

• We set the current_dict to the first node yielded by the levenshtein function, so we get back to static matching as soon as possible
• We decrement the current cost (initialized to max_cost) every time we trigger fuzzy matching (on a word), so if all the cost from max_cost already have been "consumed" by other words in the current keyword, we do not trigger fuzzy matching. E.g : when trying to extract the keyword "here you are" from "heere you are" with a max_cost of 1, the current cost will gets all consumed after the first word ("heere"), so no fuzzy matching will be performed on the other words ("you" and "are")

Limitations

• Well, as this is a pure python implementation don't expect this to be blazingly fast, even if we cut the recursion inside the levenshtein inner function ASAP, fuzzy matching still requires a lot more operations than exact matching

kp = KeywordProcessor()
kp.add_keyword("a a")
kp.add_keyword("a b")
print(kp.extract_keywords("a a b", span_info = True)) # where is "a b"?
print(kp.extract_keywords("a a b a a", span_info = True)) # where is "a b" and second "a a"?

kp2 = KeywordProcessor()
kp2.add_keyword("a b")
kp2.add_keyword("b c d e")
print(kp2.extract_keywords("a b c d e", span_info = True)) # where is _longest_ "b c d e"?

You can use regular Aho–Corasick for you program if you include word boundary symbol in keywords.

Or you can use whole words as symbols - this will be much faster in python.

Hi, This is very useful. for below case do we have any option? I want to replace one particular word with 'Nothing'/null/blank. currently if i give space it is working.

below is not working, (I just want to replace new delhi with empty):

keyword_processor.add_keyword('New Delhi', '') new_sentence = keyword_processor.replace_keywords('I love Big Apple and new delhi.') new_sentence

below is working with Space:

keyword_processor.add_keyword('New Delhi', ' ') new_sentence = keyword_processor.replace_keywords('I love Big Apple and new delhi.') new_sentence

see https://github.com/vi3k6i5/flashtext/blob/master/test/keyword_extractor_test_cases.json#L92

I am afraid the keywords_case_sensitive is not correct, and the test script did not check the keywords_case_sensitive cases.

Most regex libraries also give the location of the matches found. Can this information also be provided by FlashText?

For example:

>>> from flashtext import KeywordProcessor
>>> keyword_processor = KeywordProcessor()
>>> # keyword_processor.add_keyword(<unclean name>, <standardised name>)
>>> keyword_processor.add_keyword('Big Apple', 'New York')
>>> keyword_processor.add_keyword('Bay Area')
# Maybe something like
>>> keywords_found = keyword_processor.extract_keywords('I love New York and Bay Area.', spanInfo=True)
>>> keywords_found
>>> # {'New York': (8,15), 'Bay Area': (21,28)}

I was trying to use a key word dict like this:

from flashtext import KeywordProcessor
keyword_processor = KeywordProcessor()
keyword_dict = {
    "java": ["java_2e", "java programing"],
    "product management": ["PM", "java_2e", "product manager"]
}

I thought the keyword "jave_2e" would trigger both "java" and "product management".

However, the output for the following code is:

keyword_processor.extract_keywords('I am a programmer for a java_2e platform')

Output:

['product management']

Expected output:

['java', 'product management']

It seems to be confused. I was wondering what is the correct way to trigger multiple entries by the same keyword.

You may get the best of both worlds (good algorithm, native-speed matcher) by actually compiling your trie to a regexp as https://github.com/ZhukovAlexander/triegex does...

Thanks for open-sourcing flashtext.

I discovered a minor issue. I'm looking for genes in biological texts. I noticed that the gene ire1 is not recognized in the following passage:

targets relative to targets of the IRE1/XBP1s and PERK arms of the UPR

Prior to utilizing your script I used regexes and I padded each search terms with \b hence I was able to pick up genes that occurred in form of geneA/geneB.

Thanks again, Axel

While experimenting with the Flashtext performance, I've added exact check between the replacement results by different methods. By doing that, I've noticed that if the sentence ends with beginning of some keyword, that last word of sentence would be lost.

flashtext is great, thank you for building, documenting, and writing a post about it!

I've incorporated it into our pipeline and saw a 60x speedup with respect to the regex matching we were doing. If you'd like to link back to our project (as proof yours is being used in the wild), feel free, or I can submit a PR for that. If not, thanks again for the quick drop-in library!

We can currently do if extract_keywords(...) (will get True if one or more instances found), but it has to go through the entire text.

To reduce time consumption for this use case, does it possible to just return True when the first instance was found?

Thank you.

Hi guys,

first of all, thanks a lot for your great library, it is a huge help on my current project. I have one question though: I need to find the indices of certain tags (':F50:') in a string that I get from an XML file. These tags come after a linebreak, which in xml is represented by '&#xD'. However, some of the tags are followed by an '/' whereas others are not. When I add ':F50:' to the list of keywords, the keyword processor is able to find the tags that are being followed by the '/', but not the other ones. Only if I add ':F50' to the keyword list, the ones without a '/' are found. My concern is, that with ':F50' as part of the keyword list, the keyword processor finds more tags than I desire. Is there an explanation for that behavior? If yes, can I somehow work around it? Would it make sense to replace the xml formatted linebreak with a different value?

Thanks a lot in advance for any help provided!

In this example:

test_replacer = KeywordProcessor(case_sensitive=True)
test_replacer.add_keyword("aa", "b")
test_replacer.add_keyword("cc", "d")
test_replacer.set_non_word_boundaries("")

teststring = "aacc"
replacedstring = test_replacer.replace_keywords(teststring)

print("Teststring:\n" + teststring)
print("Replacedstring:\n" + replacedstring)

I get this output:

Teststring:
aacc
Replacedstring:
bcc

I expect to get bd. Am I misunderstanding the intended behaviour, or is this a bug?

Problem

On aarch64, ‘pip install flashtext’ builds the wheels from the source code and then installs it. It requires the user to have a development environment installed on his system. Also, it takes some time to build the wheels than downloading and extracting the wheels from PyPI.

Resolution

On aarch64, ‘pip install flashtext’ should download the wheels from PyPI.

@vi3k6i5 and Team, Please let me know your interest in releasing aarch64 wheels. I can help in this.

from flashtext import KeywordProcessor

#text = "@苍月轶 再次核实:骆然5月8日持24小时核酸从宜昌回蓉，到成都24小时内核酸一次，9号回泸定，24小时内又做一次核酸，均阴性，健康码绿码。宜昌不是 AB区域。" text = "成都到北京高铁3小时，郑州到成都2小时"

print(text) kp = KeywordProcessor() kp.add_keyword("到成都", ("成都", "ab")) kp.add_keyword("宜昌", ("宜昌", "ab"))

print(len(kp)) print(kp) word_index = kp.extract_keywords(text, span_info=True) print(word_index) for item in word_index: print(text[item[1]:item[2]])

print('finished')

Hey, consider the following example:

from flashtext import KeywordProcessor
keyword_processor = KeywordProcessor()
# keyword_processor.add_keyword(<unclean name>, <standardised name>)
keyword_processor.add_keyword('Big Apple')#, 'New York')
keyword_processor.add_keyword('Bay Area')

text1_keywords = 'I love Big Apple and Bay Area.'
text2_keywords = 'I love Big  Apple and Bay Area.'

keywords_found_1 = keyword_processor.extract_keywords(text1_keywords)
keywords_found_2 = keyword_processor.extract_keywords(text2_keywords)

keywords_found_1," vs. ",keywords_found_2

For every-day-use it would be beneficiary, that the algorithm has the option to not distinguish between a single and multiple whitespaces. (A version, where the maximal number of whitespaces to be considered as one would be even better)

For text extraction, we can easily preprocess the text and reduce multiple whitespaces a priori to just one. For text replacement the task is much more complicated, since we might want to reduce the whitespaces only in this expression, not for the complete text.

My question is hence: Is it possible to implement this case sensitivity into the algorithm (even if regex patterns are not supported in general)?

The same question arises for line breaks "\n"