# Fuzzy / approximate text matching program in Python

I'm trying to build a program that will find approximate text matches between two texts. Basically, I'd like to find a way of identifying quotations, so that when an author quotes, say, the King James Bible, Heroditus, or James Joyce, this program will identify the match, and show where it happens in the text, given the full text of both. Here's what I have so far:

import nltk
import re
from nltk.util import ngrams
from difflib import SequenceMatcher
from string import punctuation
from termcolor import colored
from fuzzysearch import find_near_matches

class Matcher:
def __init__(self, fileA, fileB, threshold, ngramSize):
"""
Gets the texts from the files, tokenizes them,
cleans them up as necessary.
"""
self.threshold = threshold

self.filenameA = fileA
self.filenameB = fileB

textATokens = self.tokenize(self.textA)
textBTokens = self.tokenize(self.textB)

self.textAgrams = list(ngrams(textATokens, ngramSize))
self.textBgrams = list(ngrams(textBTokens, ngramSize))

""" Reads the file in memory. """

def tokenize(self, text):
""" Tokenizes the text, breaking it up into words. """
return nltk.word_tokenize(text.lower())

def gramsToString(self, grams):
"""
Takes a list of tuples (3-grams, 4-grams, etc.)
and stitches it back together into a string, so that
we can search the non-tokenized text for the string later.
"""
string = " ".join(grams[0][:-1])
for gram in grams:
lastGram = gram[-1]
if lastGram not in punctuation:
string += " " + lastGram
else:
string += lastGram
return string

def getMatch(self, match, textA, textB):
"""
Takes the match object returned by get_matching_blocks() and
gets the matched n-gram. It uses gramsToString() to
reformat this into a string.
"""
textAs, textBs = [], []
for i in range(match.size):
textAs.append(textA[match.a+i])
textBs.append(textB[match.b+i])
return (self.gramsToString(textAs), self.gramsToString(textBs))

def match(self):
"""
This does the main work of finding matching n-gram sequences between
the texts.
"""
sequence = SequenceMatcher(None,self.textAgrams,self.textBgrams)
matchingBlocks = sequence.get_matching_blocks()

# Only return the matching sequences that are higher than the
# threshold given by the user.
highMatchingBlocks = [match for match in matchingBlocks if match.size > self.threshold]

for match in highMatchingBlocks:
out = self.getMatch(match, self.textAgrams, self.textBgrams)
print('\n', out)
self.findInText(out[0], self.textA, self.filenameA, 20)
self.findInText(out[1], self.textB, self.filenameB, 20)

def findInText(self, needle, haystack, haystackName, context):
"""
This takes the matches found by match() and tries to find that match
again in the text, so that we can return some context. Uses the
fuzzysearch library, because I couldn't find anything better.
"""
m = find_near_matches(needle, haystack, max_l_dist=2)

if len(m) > 0:
m = m[0] # just get the first match for now. TODO: get all of them

before = haystack[m.start-context:m.start]
match  = colored(haystack[m.start:m.end], 'red')
after  = haystack[m.end:m.end+context]

contextualized = before + match + after
cleaned = re.sub( '\s+', ' ', contextualized ).strip()
print(colored(haystackName, 'green') + ": " + cleaned)
else:
print('Couldn\'t find this match in file: ', haystackName)

myMatch = Matcher('milton.txt', 'kjv.txt', 2, 3)
myMatch.match()


Sample output, using Milton and the King James Bible:

 (', and thou shalt be', ', and thou shalt be')
milton.txt: e of streaming light, And thou shalt be our star of Arcady,
kjv.txt: hall bruise thy head, and thou shalt bruise his heel. 3:16


This match isn't so great, since "and thou shalt be our star" is very different from "and thous shalt bruise his heel." I think it's matching on "thou shalt b" but not comparing "be our" with "bruise," which are very different.

 ('for god did vex them with all adversity.', 'for god did vex them with all adversity.')
milton.txt: , and City of City, for God did vex them with all adversity. Be ye strong theref
kjv.txt: , and city of city: for God did vex them with all adversity. 15:7 Be ye strong


This match is pretty good.

 ('and the lord jesus christ, and the elect angels, that thou observe these things', 'and the lord jesus christ, and the elect angels, that thou observe these things')
Couldn't find this match in file:  milton.txt
Couldn't find this match in file:  kjv.txt


Here, the n-gram matcher found a match, but it couldn't find it again in the text. This is probably due to lower(), and the fact that fuzzysearch doesn't seem to have a case-insensitive search, so each of the case changes are recorded as edits. It's also a long string, so any edits at all will count toward the max edit distance.

I know I can improve on some standards stuff (line length, function names, etc), but what I'd really like to know is how to improve the overall function of this program. How can I make it do what it's supposed to do better? Is there a better library that could replace fuzzysearch, for instance? Also, is there a better approach to matching than to find with n-grams, and then to re-search the text to produce the output? That seems convoluted, but I don't know of a better way yet.

I'm a grad student in English Literature, so programming is really just a side thing for me, but one that I want to improve.

I just put this up on a GitHub repo, where you can see more detailed output there, along with the sample files I used:

https://github.com/JonathanReeve/text-matcher/blob/master/matching-experiments.ipynb

• I was tempted to edit out the mention that programming is a side thing since it's mostly noise in your question. Normally, when people say things like that i edit out the phrase and put the beginner tag. In your case, what you are doing is a bit more advance than what a beginner would do, so I will leave it here for the moment. – Marc-Andre Feb 24 '16 at 20:59
• I found 2 blog posts related to your problem: bommaritollc.com/2014/06/12/fuzzy-match-sentences-python and bommaritollc.com/2014/06/30/… (it does not seem that they use ngrams) – oliverpool Mar 7 '16 at 13:20

Instead of using your findInText() function, you can pull the match's indexes from the lowercase version made by tokenize(), and use that value to show the match in the original texts. Making the text lowercase doesn't change the location of any of the characters, so finding the indexes where the matching n-grams came from would allow you to plug that index value into the original text, then print a range x characters before and after that number.

For example:

# Get your index.
locationA = textA.lower().index('out[0]') # out[0] is the first n-gram in the output list, which is what we're trying to re-find.

# Print that same index from the original text as a range from 8 characters before to 8 characters after the length of the n-gram.
print(textA[(locationA - 8):(locationA + len('out[0]') + 8)])


A more simplified version of this concept would be like this:

str = 'This is a string.'
strLower = str.lower()
searchTerm = 'is a'

print(str[(strLower.index(searchTerm) - 3):(strLower.index(searchTerm) + len(searchTerm) + 3)]

# Prints "is a st"


This prints the range of characters from 3 chars before the first letter to 3 chars after the last. The indexes are the same whether the letters are capital or lowercase.

What was the point of all that? It saves your program from having to search for the matches again, possibly missing them like in your 3rd example.

My other suggestion would be to use larger n-grams for the arguments, like using four 5-grams (instead of two trigrams) in the given example. A larger threshold and n-gram size would allow for a much more precise result, more fitting of a direct quote.

myMatch = Matcher('milton.txt', 'kjv.txt',4,5)

• Although there's a lot to be said for saving the program from searching for matches again, I have a feeling this won't work for natural language texts like I'm using, since for any given n-gram, for instance "there is a," there are going to be multiple instances of it occuring in the text, so that .index isn't necessarily going to find the correct ngram. If the match has more than one n-gram, this could be a problem, since it won't find the longest match. – Jonathan Mar 5 '16 at 0:29
• You're absolutely right about this, come to think of it. You could have it lowercase the texts on the second search as well but then we have the problem of the strings showing in lowercase for the result. Alternately, you could limit the search to larger n-grams. The search you give in the example searches for 3-grams, needing only 2 to give a match (at least that's what I'm understanding), but a direct quote would be much larger. – diplomaticDeveloper Mar 5 '16 at 0:40