Trovare la distanza media di Hamming più bassa quando l'ordine delle corde è importante

Ho una sequenza di stringhe binarie che voglio trovare una corrispondenza tra un insieme di sequenze più lunghe di stringhe binarie. Una corrispondenza significa che la sequenza comparata fornisce la distanza media minima di Hamming quando tutti gli elementi della sequenza più corta sono stati abbinati a una sequenza in uno dei set più lunghi.

Fammi provare a spiegare con un esempio. Ho un set di frame video che sono stati sottoposti a hashing utilizzando un algoritmo di hashing percettivo in modo che i fotogrammi video che hanno lo stesso aspetto abbiano approssimativamente lo stesso hash. Voglio abbinare un breve video ad una serie di video più lunghi, per vedere se la clip è contenuta in uno di questi. Ciò significa che ho bisogno di scoprire dove la sequenza dei frame hash nel video breve ha la distanza media di Hamming più bassa rispetto ai video lunghi.

Il video breve è le sottostringhe Sub1, Sub2 e Sub3 e voglio abbinarle agli hash dei video lunghi in Src. L'indizio qui è che le stringhe devono corrispondere nell'ordine specifico in cui sono fornite, ad es. che Sub1 deve sempre corrispondere all'elemento prima di Sub2 e Sub2 deve sempre corrispondere all'elemento prima di Sub3. In questo esempio si mapperebbe così: Sub1-Src3, Sub2-Src4 e Sub3-Src5.

Quindi la domanda è questa: c'è un algoritmo per trovare la distanza minima di Hamming quando l'ordine degli elementi è comparato? L'approccio ingenuo per confrontare la sequenza di sottostringhe con ogni stringa sorgente ha vinto " Naturalmente, lo taglio, quindi ho bisogno di qualcosa che preferibilmente può abbinare una sottostringa (molto) più breve ad un insieme di milioni di elementi. Ho esaminato gli alberi MVP, gli alberi BK e simili, ma tutto sembra prendere in considerazione solo una stringa binaria e non una loro sequenza.

Sub1: 100111011111011101
Sub2: 110111000010010100
Sub3: 111111010110101101

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

Ho aggiunto un calcolo degli esempi di seguito. (Le distanze di Hamming non sono corrette, ma non importa)

**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

Quindi il vincitore qui è la sequenza 4 con una distanza media di 5.