# Find the closest string to a fixed set of strings

I want to find the closest string to a fixed set of strings. The strings are all equal in length, and the number of strings in the set is relatively small (compared to all the possible strings of the fixed size). For this problem you can assume the strings only contain the characters 0-9, and if needed, the length will never be longer than 32 characters.

I measure closest by hamming distance, the distance between two strings is the number of places the two strings differ. I don't care about how ties are resolved, any string with the minimum distance is acceptable.

For example, with s1 = "123" and s2 = "321", the distance between them is 2. (All the pseudo code is in Python)

def distance(s1, s2):
return sum(a != b for a, b in zip(s1, s2))


I can complete a query in $$O(n)$$ time where $$n$$ is the number of strings in the set. The idea would be to loop over each string in the set and compute the distance between it and the target. The answer is the (first, with this implementation) string with the smallest distance.

def query(table, target):
return min(table, key=lambda t: distance(target, t))


Is there a way to do this in less than linear time? Can the set of strings be pre-processed to allow for a faster search?

Here is a testcase/example

target = '91814154'
table = [
'91812315',
'77403499',
'57579618',
'92354796',
'23425335',
'97722442',
'01824154']

distances = [4, 8, 8, 6, 8, 7, 2]


So the answer is the string '01824154'.

• Comments are not for extended discussion; this conversation has been moved to chat. – Raphael Nov 28 '19 at 18:21

However, the effectiveness of these methods depends heavily on the dimension (i.e., on the length of the strings). Practical experience is that for dimension $$\le 10$$, these are better than the naive linear-time search, but for very high dimension, usually they perform no better than the naive algorithm. This occurs due to the curse of dimensionality. In your context, that means that if the strings are short and $$n$$ is large, these data structures will probably be effective, but if the strings are long, I would not expect too much hope.
In the special case where strings are long and you expect the nearest neighbor to have very low Hamming distance, whereas the distance to most other strings will be very large, then there are techniques you can use. For instance, you might look into shingling the strings into $$n$$-grams, storing the $$n$$-grams in a hashtable, and doing a lookup on each $$n$$-gram from the query string. You can view this as a form of locality-sensitive hashing for the Hamming distance. Another approach is to use bit sampling as a locality-sensitive hash; this should be easy to implement.