Approximate string search in Python

Question

I have a long text (about 6,000,000 chars) and a short text (about 6,000 chars). The long text contains the short text, but not exactly - a small number of words are missing, abbreviated or just erroneous. So I want to do an approximate search.

There are several Python libraries that do fuzzy string matching. For example, FuzzySet accepts a list of candidates and a string and returns the candidate that is most similar to the string. However, here I do not have a list of candidates - I have just a very long text.

A naive solution is to take, as the list of candidates, all substrings of the long text. However, the number of candidates will be huge. So, now I use make several heuristic assumptions:

1. I assume that the first several characters at the start and end of the short text are not erroneous in the long text.
2. I assume that the length of the best match of the short text inside the long text is at least half and at most twice the length of the short text.

These assumptions allow me to reduce the number of candidates dramatically, so all of them can be checked in a reasonable time. Here is the current solution:

import re
from fuzzyset import FuzzySet

def fuzzyFind(needle:str, haystack:str, needleStart:str, needleEnd:str)->str:
    """
    needle: short text to look for.
    haystack: long text to look in.
    needleStart: first few chars in needle,
    needleEnd  : last few chars in needle - assumed to exist verbatim in haystack.

    returns a subset of haystack that is a best match for needle.
    """
    minPossibleLength = len(needle)//2
    maxPossibleLength = len(needle)*2
    possibleStarts = [m.start() for m in re.finditer(needleStart, haystack)]
    possibleEnds =   [m.end()   for m in re.finditer(needleEnd,   haystack)]
    possibleMatches = FuzzySet()
    for iStart in possibleStarts:
        for iEnd in possibleEnds:
            possibleLength = iEnd-iStart
            if minPossibleLength <= possibleLength and possibleLength <= maxPossibleLength:
                possibleMatch = haystack[iStart:iEnd]
                print("possible match from {} to {}".format(iStart,iEnd))
                possibleMatches.add(possibleMatch)
    matches = possibleMatches.get(needle)
    bestMatch = matches[0]
    bestMatchText = bestMatch[1]
    return bestMatchText

This heuristic solution is quick and quite accurate in practice, but of course it is not guaranteed to work. I would like to get rid of the assumptions, especically assumption #1. Is there a quick solution that does not need to assume anything about the first and last characters of the needle?

_{Note: before writing this function I tried to use the fuzzysearch library. However, this function requires an upper bound on the Levenshtein distance between the short text and its variant inside long text. Even with modest upper bounds (e.g, 60-70) it becomes quite slow.}

Answer 1

Since there is no answer yet - what I would try:

I would search words rather than characters. make a dictionary of words (bag of words) and count the frequency. your test bag of words should be a subset of the source bag of words mostly. by comparing to other sources you could analyze relevance of words and other measures.

The big advantage of words vs. characters is that the comparison resyncs with every whitespace. an insertion/deletion of a character will result in a single changed word. you are now talking in edit distance of words, rather than characters. so translate your strings to arrays of words (whatever representation you use for a word (sequential number, hash, reference, ...).

Now slide your test words over the source words and count the number of word matches. for your parameters this will be around 1,000 word over 1,000,000 words, which sounds reasonable. you get an array of match counts with length 1,000,999. it will have the following properties

• some noise floor of matches. the most frequent words of your language match by accident
• some (at least one) entries greater or equal to the longest matching subsequence
• some 'distribution' (near gaussian?) caused by inserted/deleted words indicating where to find your test file

this would be less heuristic than your approach, although you probably will again apply some more algorithms/heuristics to find the 'exact' match start/end.

---

EDIT: I simply had to try the bag of words approach

I simply slide a window of the probe words length ofer the text words in single word steps. for this text window i calculate the bag of words and compare it to the probe and sum the absolute difference values for every entry.

e. g.: 'so the the moon' vs. 'the moon moon is' resulting (so:1 the:2 moon:1) vs. (the:1 moon:2 is:1) wich results in a diff (so:1 the:1 moon:-1 is:-1) in absolute values (so:1 the:1 moon:1 is:1) summing up to the value 4.

This measure for my test set

• text size 100,000 chars (~ 16,000 words)
• probe size 6,000 chars (~ 1,000 words)
• probe edits (change, insert, delete) 300 chars (letters, digits, punctuation, whitespace)
• bag size for a 1000 words window from text ~ 500 words with frequencies from 20+ down to 1
• bag size of the (edited) probe ~ 600 words

gives the following result

This looks pretty robust to me. We see

• for the best match a word-edit-distance of 460 (inserting a whitespace may results in a distance of 3)
• for a non-matching region a word-edit-distance of 1200
• a near linear transition double as wide as the probe size

See the transition scaled up