Fuzzy / approximate text matching program in Python

Question

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

        self.textA = self.readFile(fileA)
        self.textB = self.readFile(fileB)

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

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

    def readFile(self, filename): 
        """ Reads the file in memory. """
        return open(filename).read()

    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

Answer 1

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)