Checking fuzzy/approximate substring existing in a longer string, in Python?
I use fuzzywuzzy to fuzzy match based on threshold and fuzzysearch to fuzzy extract words from the match.
process.extractBests
takes a query, list of words and a cutoff score and returns a list of tuples of match and score above the cutoff score.
find_near_matches
takes the result of process.extractBests
and returns the start and end indices of words. I use the indices to build the words and use the built word to find the index in the large string. max_l_dist
of find_near_matches
is 'Levenshtein distance' which has to be adjusted to suit the needs.
from fuzzysearch import find_near_matches
from fuzzywuzzy import process
large_string = "thelargemanhatanproject is a great project in themanhattincity"
query_string = "manhattan"
def fuzzy_extract(qs, ls, threshold):
'''fuzzy matches 'qs' in 'ls' and returns list of
tuples of (word,index)
'''
for word, _ in process.extractBests(qs, (ls,), score_cutoff=threshold):
print('word {}'.format(word))
for match in find_near_matches(qs, word, max_l_dist=1):
match = word[match.start:match.end]
print('match {}'.format(match))
index = ls.find(match)
yield (match, index)
To test:
query_string = "manhattan"
print('query: {}\nstring: {}'.format(query_string, large_string))
for match,index in fuzzy_extract(query_string, large_string, 70):
print('match: {}\nindex: {}'.format(match, index))
query_string = "citi"
print('query: {}\nstring: {}'.format(query_string, large_string))
for match,index in fuzzy_extract(query_string, large_string, 30):
print('match: {}\nindex: {}'.format(match, index))
query_string = "greet"
print('query: {}\nstring: {}'.format(query_string, large_string))
for match,index in fuzzy_extract(query_string, large_string, 30):
print('match: {}\nindex: {}'.format(match, index))
Output:
query: manhattan
string: thelargemanhatanproject is a great project in themanhattincity
match: manhatan
index: 8
match: manhattin
index: 49
query: citi
string: thelargemanhatanproject is a great project in themanhattincity
match: city
index: 58
query: greet
string: thelargemanhatanproject is a great project in themanhattincity
match: great
index: 29
The approaches above are good, but I needed to find a small needle in lots of hay, and ended up approaching it like this:
from difflib import SequenceMatcher as SM
from nltk.util import ngrams
import codecs
needle = "this is the string we want to find"
hay = "text text lots of text and more and more this string is the one we wanted to find and here is some more and even more still"
needle_length = len(needle.split())
max_sim_val = 0
max_sim_string = u""
for ngram in ngrams(hay.split(), needle_length + int(.2*needle_length)):
hay_ngram = u" ".join(ngram)
similarity = SM(None, hay_ngram, needle).ratio()
if similarity > max_sim_val:
max_sim_val = similarity
max_sim_string = hay_ngram
print max_sim_val, max_sim_string
Yields:
0.72972972973 this string is the one we wanted to find
How about using difflib.SequenceMatcher.get_matching_blocks
?
>>> import difflib
>>> large_string = "thelargemanhatanproject"
>>> query_string = "manhattan"
>>> s = difflib.SequenceMatcher(None, large_string, query_string)
>>> sum(n for i,j,n in s.get_matching_blocks()) / float(len(query_string))
0.8888888888888888
>>> query_string = "banana"
>>> s = difflib.SequenceMatcher(None, large_string, query_string)
>>> sum(n for i,j,n in s.get_matching_blocks()) / float(len(query_string))
0.6666666666666666
UPDATE
import difflib
def matches(large_string, query_string, threshold):
words = large_string.split()
for word in words:
s = difflib.SequenceMatcher(None, word, query_string)
match = ''.join(word[i:i+n] for i, j, n in s.get_matching_blocks() if n)
if len(match) / float(len(query_string)) >= threshold:
yield match
large_string = "thelargemanhatanproject is a great project in themanhattincity"
query_string = "manhattan"
print list(matches(large_string, query_string, 0.8))
Above code print: ['manhatan', 'manhattn']
The new regex library that's soon supposed to replace re includes fuzzy matching.
https://pypi.python.org/pypi/regex/
The fuzzy matching syntax looks fairly expressive, but this would give you a match with one or fewer insertions/additions/deletions.
import regex
regex.match('(amazing){e<=1}', 'amaging')