Find the closest string to a fixed set of strings

Question

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'.

Answer 1

This is a nearest-neighbor problem, and there are a variety of algorithms for the problem. The simplest is a k-d tree, and there are more sophisticated data structures as well. Another approach is to use locality-sensitive hashing.

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.

I also recommend taking a look at our questions in the nearest-neighbor topic, especially Why Is KD-Tree-based Nearest Neighbor Exponential in K?, Best data structure for high dimensional nearest neighbor search, Why is exact nearest neighbor search hard in high dimensional spaces?, What is the state of the art for k nearest neighbour search?.

We also have questions here about the harder problem of finding the nearest string, where nearest is measured by Levenshtein edit distance (e.g., Find all pairs of strings in a set with Levenshtein distance < d, How to speed up process of finding duplicates/similar items in a large amount of strings?, How fast can we identifiy almost-duplicates in a list of strings?, Matching strings in one set to strings in another based on Levenshtein distance).