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