Étant donné deux séquences, trouver le chevauchement maximal entre la fin de l'un et le début de l'autre

11

J'ai besoin de trouver un (pseudo) code efficace pour résoudre le problème suivant:

Compte tenu de deux séquences de (pas nécessairement distinctes) entiers (a[1], a[2], ..., a[n])et (b[1], b[2], ..., b[n]), trouver le maximum de dtelle sorte que a[n-d+1] == b[1], a[n-d+2] == b[2]... et a[n] == b[d].

Ce ne sont pas des devoirs, j'ai trouvé cela en essayant de contracter deux tenseurs sur autant de dimensions que possible. Je soupçonne qu'un algorithme efficace existe (peut O(n)- être ?), Mais je ne peux pas trouver quelque chose qui ne l'est pas O(n^2). L' O(n^2)approche serait la boucle évidente dpuis une boucle intérieure sur les articles pour vérifier la condition requise jusqu'à atteindre le maximum d. Mais je soupçonne que quelque chose de mieux que cela est possible.

Becko
la source
Si un hachage roulant peut être calculé pour un groupe d'objets dans votre tableau, je pense que cela peut être fait plus efficacement. Calculez le hachage pour les éléments b[1] to b[d], puis accédez au tableau de ahachage de calcul pour a[1] to a[d]si cela correspond, c'est votre réponse, sinon calculez le hachage pour a[2] to a[d+1]en réutilisant le hachage calculé pour a[1] to a[d]. Mais je ne sais pas si les objets du tableau peuvent être calculés sur un hachage roulant.
SomeDude
2
@becko Désolé, je pense que je comprends enfin ce que vous essayez d'accomplir. Ce qui est de trouver le chevauchement maximum entre la fin aet le début de b. Comme ça .
user3386109
1
Il me semble que le problème est une variation de la correspondance des chaînes, qui peut être résolue avec une variation de l' algorithme Knuth – Morris – Pratt . Le temps d'exécution serait O (m + n) où mest le nombre d'éléments dans a, et nest le nombre d'éléments dans b. Malheureusement, je n'ai pas suffisamment d'expérience avec KMP pour vous dire comment l'adapter.
user3386109
1
@ user3386109 ma solution est également une variante d'un algorithme d'appariement de chaînes appelé Rabin-Karp , utilisant la méthode de Horner comme fonction de hachage.
Daniel
1
@Daniel Ah, je savais que j'avais vu un hachage roulant utilisé quelque part, mais je ne me souvenais pas où :)
user3386109

Réponses:

5

Vous pouvez utiliser l' algorithme z , un algorithme de temps linéaire ( O (n) ) qui:

Étant donné une chaîne S de longueur n, l'algorithme Z produit un tableau ZZ [i] est la longueur de la plus longue sous-chaîne à partir de S [i] qui est également un préfixe de S

Vous devez concaténer vos tableaux ( b + a ) et exécuter l'algorithme sur le tableau construit résultant jusqu'au premier i tel que Z [i] + i == m + n .

Par exemple, pour a = [1, 2, 3, 6, 2, 3] & b = [2, 3, 6, 2, 1, 0], la concaténation serait [2, 3, 6, 2, 1 , 0, 1, 2, 3, 6, 2, 3] ce qui donnerait Z [10] = 2 satisfaisant Z [i] + i = 12 = m + n .

Amit
la source
Beau! Merci.
Becko
3

Pour la complexité temps / espace O (n), l'astuce consiste à évaluer les hachages pour chaque sous-séquence. Considérez le tableau b:

[b1 b2 b3 ... bn]

En utilisant la méthode de Horner , vous pouvez évaluer tous les hachages possibles pour chaque sous-séquence. Choisissez une valeur de base B(supérieure à toute valeur dans vos deux tableaux):

from b1 to b1 = b1 * B^1
from b1 to b2 = b1 * B^1 + b2 * B^2
from b1 to b3 = b1 * B^1 + b2 * B^2 + b3 * B^3
...
from b1 to bn = b1 * B^1 + b2 * B^2 + b3 * B^3 + ... + bn * B^n

Notez que vous pouvez évaluer chaque séquence en temps O (1), en utilisant le résultat de la séquence précédente, d'où tous les coûts de travail O (n).

Vous avez maintenant un tableau Hb = [h(b1), h(b2), ... , h(bn)], où Hb[i]est le hachage de b1jusqu'à bi.

Faites la même chose pour le tableau a, mais avec une petite astuce:

from an to an   =  (an   * B^1)
from an-1 to an =  (an-1 * B^1) + (an * B^2)
from an-2 to an =  (an-2 * B^1) + (an-1 * B^2) + (an * B^3)
...
from a1 to an   =  (a1   * B^1) + (a2 * B^2)   + (a3 * B^3) + ... + (an * B^n)

Vous devez noter que lorsque vous passez d'une séquence à une autre, vous multipliez toute la séquence précédente par B et ajoutez la nouvelle valeur multipliée par B. Par exemple:

from an to an =    (an   * B^1)

for the next sequence, multiply the previous by B: (an * B^1) * B = (an * B^2)
now sum with the new value multiplied by B: (an-1 * B^1) + (an * B^2) 
hence:

from an-1 to an =  (an-1 * B^1) + (an * B^2)

Vous avez maintenant un tableau Ha = [h(an), h(an-1), ... , h(a1)], où Ha[i]est le hachage de aijusqu'à an.

Maintenant, vous pouvez comparer Ha[d] == Hb[d]toutes les dvaleurs de n à 1, si elles correspondent, vous avez votre réponse.


ATTENTION : il s'agit d'une méthode de hachage, les valeurs peuvent être grandes et vous devrez peut-être utiliser une méthode d'exponentiation rapide et une arithmétique modulaire , qui peuvent (à peine) vous donner des collisions , ce qui rend cette méthode pas totalement sûre. Une bonne pratique consiste à choisir une base Bcomme un très grand nombre premier (au moins plus grand que la plus grande valeur de vos tableaux). Vous devez également faire attention car les limites des nombres peuvent déborder à chaque étape, vous devrez donc utiliser (modulo K) dans chaque opération (où Kpeut être un nombre premier plus grand que B).

Cela signifie que deux séquences différentes peuvent avoir le même hachage, mais deux séquences égales auront toujours le même hachage.

Daniel
la source
Pouvez-vous s'il vous plaît commencer cette réponse par une évaluation des besoins en ressources?
greybeard
2

Cela peut en effet se faire en temps linéaire, O (n) et O (n) espace supplémentaire. Je suppose que les tableaux d'entrée sont des chaînes de caractères, mais ce n'est pas essentiel.

Une méthode naïve rechercherait - après avoir fait correspondre k caractères égaux - un caractère qui ne correspond pas, et reculerait de k-1 unités dans a , réinitialiser l'index en b , puis démarrer le processus de correspondance à partir de là. Cela représente clairement le pire des cas O (n²) .

Pour éviter ce processus de retour en arrière, nous pouvons observer que revenir en arrière n'est pas utile si nous n'avons pas rencontré le caractère b [0] lors du balayage des k-1 derniers caractères. Si nous avons fait constater que le caractère, retours en arrière alors à cette position ne serait utile, si ce k sized substring nous avons eu une répétition périodique.

Par exemple, si nous regardons la sous-chaîne "abcabc" quelque part dans a , et b est "abcabd", et que nous constatons que le caractère final de b ne correspond pas, nous devons considérer qu'une correspondance réussie peut commencer au deuxième "a" dans la sous-chaîne, et nous devons déplacer notre indice actuel en b en conséquence avant de poursuivre la comparaison.

L'idée est alors de faire un prétraitement basé sur la chaîne b pour enregistrer les références arrières dans b qui sont utiles pour vérifier quand il y a un décalage. Ainsi, par exemple, si b est "acaacaacd", nous pourrions identifier ces références arrières basées sur 0 (placées sous chaque caractère):

index: 0 1 2 3 4 5 6 7 8
b:     a c a a c a a c d
ref:   0 0 0 1 0 0 1 0 5

Par exemple, si nous avons un égal à "acaacaaca", le premier décalage se produit sur le caractère final. Les informations ci-dessus indiquent ensuite à l'algorithme de revenir en b à l'index 5, car "acaac" est courant. Et puis, en ne changeant que l'indice actuel dans b, nous pouvons continuer l'appariement à l'indice actuel de a . Dans cet exemple, la correspondance du dernier caractère réussit.

Avec cela, nous pouvons optimiser la recherche et nous assurer que l'index dans un peut toujours avancer.

Voici une implémentation de cette idée en JavaScript, en utilisant uniquement la syntaxe la plus basique de ce langage:

function overlapCount(a, b) {
    // Deal with cases where the strings differ in length
    let startA = 0;
    if (a.length > b.length) startA = a.length - b.length;
    let endB = b.length;
    if (a.length < b.length) endB = a.length;
    // Create a back-reference for each index
    //   that should be followed in case of a mismatch.
    //   We only need B to make these references:
    let map = Array(endB);
    let k = 0; // Index that lags behind j
    map[0] = 0;
    for (let j = 1; j < endB; j++) {
        if (b[j] == b[k]) {
            map[j] = map[k]; // skip over the same character (optional optimisation)
        } else {
            map[j] = k;
        }
        while (k > 0 && b[j] != b[k]) k = map[k]; 
        if (b[j] == b[k]) k++;
    }
    // Phase 2: use these references while iterating over A
    k = 0;
    for (let i = startA; i < a.length; i++) {
        while (k > 0 && a[i] != b[k]) k = map[k];
        if (a[i] == b[k]) k++;
    }
    return k;
}

console.log(overlapCount("ababaaaabaabab", "abaababaaz")); // 7

Bien qu'il existe des whileboucles imbriquées , celles-ci n'ont pas plus d'itérations au total que n . En effet, la valeur de k diminue strictement dans le whilecorps et ne peut pas devenir négative. Cela ne peut se produire que si a k++été exécuté autant de fois pour donner suffisamment de place à de telles diminutions. Donc, dans l'ensemble, il ne peut y avoir plus d'exécutions du whilecorps qu'il n'y a d' k++exécutions, et ce dernier est clairement O (n).

Pour terminer, vous pouvez trouver ici le même code que ci-dessus, mais dans un extrait interactif: vous pouvez saisir vos propres chaînes et voir le résultat de manière interactive:

trincot
la source