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

Question

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.

Answer 1

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.

Answer 2

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.