<p>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).</p>

<p>That is, of course, assuming that:</p>

<ol>
<li>you know the target string and its length,</li>
<li>you are in a binary setting,</li>
<li>you indeed want to use the Hamming distance.</li>
</ol>

<p>Since you're using the word "alignment" and refer to bioinformatics in your above comment, you might want to take a look at <a href="http://en.wikipedia.org/wiki/Sequence_alignment" rel="nofollow">sequence alignment</a> and <a href="http://en.wikipedia.org/wiki/Edit_distance" rel="nofollow">edit distances</a>, in particular the <a href="http://en.wikipedia.org/wiki/Levenshtein_distance" rel="nofollow">Levenshtein distance</a> (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.</p>

CC BY-SA 2.5
2010-11-17T10:24:15.060Z
Yes, but I would like to minimize the subset generation, and eliminate it if at all possible. See http://stackoverflow.com/questions/1146026/fastest-way-to-find-minimal-hamming-distance-to-any-substring
PoorLuzer
CC BY-SA 2.5
2010-11-17T15:19:27.047Z
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ε
CC BY-SA 2.5
2010-11-17T18:48:04.117Z
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
CC BY-SA 2.5
2010-11-18T03:11:21.577Z
@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
CC BY-SA 2.5
2010-11-17T10:12:27.257Z
2010-11-17T10:12:27.257Z
Anthony Labarre
<p>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.</p>

<p>Consider the target string, that is, say, 4 characters long, to be:</p>

<pre><code>targetString -&gt; '1111'
</code></pre>

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

<pre><code>nonEmptySubStrings -&gt; ['110101']
</code></pre>

<p>Substrings of the above that are 4 characters long:</p>

<pre><code>nGramsSubStrings -&gt; ['0101', '1010', '1101']
</code></pre>

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

<pre><code>someMagicFunction -&gt; ['1101']
</code></pre>

<p>Some more examples:</p>

<pre><code>nonEmptySubStrings -&gt; ['101011']
nGramsSubStrings -&gt; ['0101', '1010', '1011']

someMagicFunction -&gt; ['1011']

nonEmptySubStrings -&gt; ['10101']
nGramsSubStrings -&gt; ['0101', '1010']

someMagicFunction -&gt; ['0101', '1010']
</code></pre>

<p><strong>Is this "Magic Function" a well known substring problem?</strong></p>

CC BY-SA 2.5
2010-11-17T09:46:40.430Z
If you really want an implementation, http://stackoverflow.com/ will be more appropriate (and more efficient).
Anthony Labarre
CC BY-SA 2.5
2010-11-17T09:56:58.240Z
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
CC BY-SA 2.5
2010-11-17T10:12:29.603Z
The magic function would return substrings with the smallest Hamming Distance from the given substring.
Dave Clarke
CC BY-SA 2.5
2010-11-17T10:23:11.580Z
Yes, but I would like to minimize the subset generation, and eliminate it if at all possible. See http://stackoverflow.com/questions/1146026/fastest-way-to-find-minimal-hamming-distance-to-any-substring
PoorLuzer
CC BY-SA 2.5
2010-11-17T11:30:29.060Z
I suggest that you have a look at Navarro (2001): [A guided tour to approximate string matching](http://dx.doi.org/10.1145/375360.375365). In particular, search for the keyword "Hamming distance".
Jukka Suomela
CC BY-SA 2.5
2010-11-18T03:04:47.557Z
@PoorLuzer: Please edit your first line, asking for code is not a *theoretical* computer science question.
Kaveh
<string-matching>
Locate "N Gram" substrings that are smallest distance away from a target string N character long
PoorLuzer
# Locate "N Gram" substrings that are smallest distance away from a target string N character long

(Asked by: username_0 on 2010-11-17)

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?

**Tags:** string-matching

> **Comments:**
> **username_1**: If you really want an implementation, http://stackoverflow.com/ will be more appropriate (and more efficient).  
> **username_0**: 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.  
> **username_2**: The magic function would return substrings with the smallest Hamming Distance from the given substring.  
> **username_0**: Yes, but I would like to minimize the subset generation, and eliminate it if at all possible. See http://stackoverflow.com/questions/1146026/fastest-way-to-find-minimal-hamming-distance-to-any-substring  
> **username_3**: I suggest that you have a look at Navarro (2001): [A guided tour to approximate string matching](http://dx.doi.org/10.1145/375360.375365). In particular, search for the keyword "Hamming distance".  
> **username_4**: @username_0: Please edit your first line, asking for code is not a *theoretical* computer science question.  

---

## 1 answers

### Answer by username_1 on 2010-11-17. Score: 4 | Accepted answer

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](http://en.wikipedia.org/wiki/Sequence_alignment) and [edit distances](http://en.wikipedia.org/wiki/Edit_distance), in particular the [Levenshtein distance](http://en.wikipedia.org/wiki/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.

> **Comments:**
> **username_0**: Yes, but I would like to minimize the subset generation, and eliminate it if at all possible. See http://stackoverflow.com/questions/1146026/fastest-way-to-find-minimal-hamming-distance-to-any-substring  
> **username_5**: 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.  
> **username_0**: 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.  
> **username_4**: @username_0: 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).  

---

