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[:-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, self.textA, self.filenameA, 20) self.findInText(out, 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 # 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: