# Locate “N Gram” substrings that are smallest distance away from a target string N character long

I am looking for an algorithm, or code, preferably in Python that would help me locate substrings, N characters long, of exisiting strings that are closest to a target string N character long.

Consider the target string, that is, say, 4 characters long, to be:

targetString -> '1111'


Assume this is the string I have available with me ( I will generate substrings of this for "best alignment" matching ):

nonEmptySubStrings -> ['110101']


Substrings of the above that are 4 characters long:

nGramsSubStrings -> ['0101', '1010', '1101']


I want to write/use a "Magic Function" that would select the string closest to targetString :

someMagicFunction -> ['1101']


Some more examples:

nonEmptySubStrings -> ['101011']
nGramsSubStrings -> ['0101', '1010', '1011']

someMagicFunction -> ['1011']

nonEmptySubStrings -> ['10101']
nGramsSubStrings -> ['0101', '1010']

someMagicFunction -> ['0101', '1010']


Is this "Magic Function" a well known substring problem?

• If you really want an implementation, stackoverflow.com will be more appropriate (and more efficient). – Anthony Labarre Nov 17 '10 at 9:46
• I am interested in knowing an answer to the last ( bolded ) line of my question above. My requirement seems to be something that should be fairly frequent in bioinformatics? Oh it might be as trivial as being based on the Hamming distance ( in which case I would modify my question to remove the ngram generation step ). I basically want to find the min. number of changes in nonEmptySubStrings so that it would have targetString as a substring. – PoorLuzer Nov 17 '10 at 9:56
• The magic function would return substrings with the smallest Hamming Distance from the given substring. – Dave Clarke Nov 17 '10 at 10:12
• Yes, but I would like to minimize the subset generation, and eliminate it if at all possible. See stackoverflow.com/questions/1146026/… – PoorLuzer Nov 17 '10 at 10:23
• I suggest that you have a look at Navarro (2001): A guided tour to approximate string matching. In particular, search for the keyword "Hamming distance". – Jukka Suomela Nov 17 '10 at 11:30

It seems to me you have already done all the work: if $a$ is your available string and $b$ your target string of length $|b|$, you can generate the set $S$ of all substrings of length $|b|$ in linear time by just scanning $a$ from left to right, and then just keep all strings in $S$ with minimal Hamming distance (I don't know whether you want to keep all of them, or just one).

That is, of course, assuming that:

1. you know the target string and its length,
2. you are in a binary setting,
3. you indeed want to use the Hamming distance.

Since you're using the word "alignment" and refer to bioinformatics in your above comment, you might want to take a look at sequence alignment and edit distances, in particular the Levenshtein distance (code available on that page) which allows deletions and insertions of characters as well as plain changes and will work with any alphabet. In this case, however, you may want to use more clever algorithms and data structures than the naive approach I gave above, since you'll have way more substrings to deal with, but I hope that the links I provided should, if not give you the answer right away, at least point you in the right direction.

• Yes, but I would like to minimize the subset generation, and eliminate it if at all possible. See stackoverflow.com/questions/1146026/… – PoorLuzer Nov 17 '10 at 10:24
• Why? There are only n-N substrings to consider, and you can easily list them all in O(n) time, where n is the length of the text. This is not the bottleneck. – Jeffε Nov 17 '10 at 15:19
• I don't want to know anything about the substrings except to find the min. number of changes in string_ so that it would have target_string as a substring. The function to compute the 'min. number of changes' needs to be as fast as possible as it will be processing thousands of strings. The strings are numeric and binary ( i.e. it has only two different digits ) in case this helps. – PoorLuzer Nov 17 '10 at 18:48
• @PoorLuzer: this seems to be different from what you have asked. I don't think you can do better than linear time, and if you are only interested in the min hamming distance between substrings of $a$ and $b$ just compute the min distance up to that point and don't store the substrings with min distance. It might be possible to modify KMP algorithm to do better (but it will still be linear time). – Kaveh Nov 18 '10 at 3:11