# Finding the lowest average Hamming distance when the order of the strings matter

I have a sequence of binary strings that I want to find a match for among a set of longer sequences of binary strings. A match means that the compared sequence gives the lowest average Hamming distance when all elements in the shorter sequence have been matched against a sequence in one of the longer sets.

Let me try to explain with an example. I have a set of video frames that have been hashed using a perceptual hashing algorithm so that the video frames that look the same has roughly the same hash. I want to match a short video clip against a set of longer videos, to see if the clip is contained in one of these. This means that I need to find out where the sequence of the hashed frames in the short video has the lowest average Hamming distance when compared with the long videos.

The short video is the sub strings Sub1, Sub2 and Sub3, and I want to match them against the hashes of the long videos in Src. The clue here is that the strings need to match in the specific order that they are given in, e.g. that Sub1 always has to match the element before Sub2, and Sub2 always has to match the element before Sub3. In this example it would map thusly: Sub1-Src3, Sub2-Src4 and Sub3-Src5.

So the question is this: is there an algorithm for finding the lowest average Hamming distance when the order of the elements compared matter? The naïve approach to compare the substring sequence to every source string won't cut it of course, so I need something that preferably can match a (much) shorter sub string to a set of million of elements. I have looked at MVP-trees, BK-trees and similar, but everything seems to only take into account one binary string and not a sequence of them.

``````Sub1: 100111011111011101
Sub2: 110111000010010100
Sub3: 111111010110101101

Src1: 001011010001010110
Src2: 010111101000111001
Src3: 101111001110011101
Src4: 010111100011010101
Src5: 001111010110111101
Src6: 101011111111010101
``````

I have added a calculation of the examples below. (The Hamming distances aren't correct, but it doesn't matter)

``````**Run 1.**
dist(Sub1, Src1) = 8
dist(Sub2, Src2) = 10
dist(Sub3, Src3) = 12
average = 10

**Run 2.**
dist(Sub1, Src2) = 10
dist(Sub2, Src3) = 12
dist(Sub3, Src4) = 10
average = 11

**Run 3.**
dist(Sub1, Src3) = 7
dist(Sub2, Src4) = 6
dist(Sub3, Src5) = 10
average = 8

**Run 4.**
dist(Sub1, Src3) = 10
dist(Sub2, Src4) = 4
dist(Sub3, Src5) = 2
average = 5
``````

So the winner here is sequence 4 with an average distance of 5.

• You're probably looking for something more like Levenshtein distance, which does take this order into account. In any case, because you're dealing with a million elements, you're probably going to have to specify your problem with a little more detail than this. Try to provide us with some sample input and output, and there might be a chance we can formulate an algorithm. – Robert Harvey Oct 14 '13 at 17:51
• @RobertHarvey The input would be what I posted in my example, only with longer bit strings and a lot more of them. – user1049697 Oct 14 '13 at 18:06
• And what would the output look like? – Robert Harvey Oct 14 '13 at 18:28
• It would be an int describing the average distance between them. E.g. ( dist(Sub1, Src3) + dist(Sub2, Src4) + dist(Sub3, Src5) ) / 3 = 4 – user1049697 Oct 14 '13 at 18:34
• Can you give an order of magnitude how many subs and srcs are to be considered in a typical run of this algorithm? – TheMorph Oct 17 '13 at 16:27

Maybe you could just concatenate your srcs and subs respectively. After that you can use a sequence allignment algorithm of your taste, like the Smith-Waterman algorithm or the more general Needleman-Wunsch algorithm.

• Second answer as it states a completely different approach that emerged after further clarification of the question. – TheMorph Oct 17 '13 at 21:29
• I am unsure if this could work since this algorithm appears to find matches where there are "gaps" i.e. missing frames (bit strings) in my case. – user1049697 Oct 21 '13 at 12:55
• That is right, it matches even with gaps, but it will return a value of how good the matching is. You could work with a threshold. Maybe the more general Needleman–Wunsch algorithm is a better fit for your case. You should be able to define a big negative value for gaps inside the string but only a small or null negative value for missing parts at the beginning and end. – TheMorph Oct 23 '13 at 1:27
• I think that Needleman-Wunsch might work, so I am awarding you the bounty. Thanks for the help! – user1049697 Oct 25 '13 at 7:37

I don't know any algorithm specific for this problem, but this seems like an optimization problem.

I would suggest branch and bound as a starting point. Combined with a depth-first search to get upper bounds (your lowest hamming distance) for the bounding and you won't need to traverse all edges of the tree. If your accumulated hamming distance on a node is already bigger than the lowest already found from root to a leaf you can stop traversing subtrees of this node.

If you can find a good heuristic to chose what branch to visit next you may further reduce the number of paths to traverse. Something like expand subtrees with lowest accumulated hamming distance yet.

Another thing you could maybe incorporate in the heuristic is the distance to the end. The further you are away from the end of the video the bigger the chance to find a better match thus lower hamming distance. (If I understood your problem correctly)

If you use heuristics with some crossover of depth-first and breadth-first seach, but may be even faster (I didn't made the math yet). The idea would be to traverse strictly from root to leaf but after you are done you decide which subtree you want to expand next from root to tree, not only looking on all the nodes you discovered by the last traversal (in contrast to recursive depth-first search). Thus you may find lower bounds even sooner, but you will need more space for computation as you will most likely have more nodes in the list of unexplored ones and you can summarize the results for subtrees later.

• May be not suitable as I assumed the matchings wouldn't need to be contagious. Thus it may work not the way the asker intended. – TheMorph Oct 17 '13 at 21:32