Correction des chaînes de caractères à l’aide de la distance de Damerau-Levenshtein

Algorithmes à noyau unique

Dans cette section, nous développons quatre algorithmes à noyau unique à espace linéaire pour la correction des chaînes de caractères à l’aide de la distance DL. Les quatre s’exécutent en temps O(mn). Les deux premiers (LS_DL et Strip_DL) calculent uniquement le score Hmn de la trace optimale ; ils diffèrent par leur efficacité en matière de cache. Les deux derniers (LSDL_TRACE et Strip_TRACE) calculent une trace optimale.

L’algorithme d’espace linéaire L S_D L

Détendons s la taille de l’alphabet. Au lieu d’utiliser le tableau H utilisé dans DL, l’algorithme LS_DL utilise un tableau unidimensionnel U et un tableau bidimensionnel T. Ces deux tableaux ont un besoin en espace de O((s+1)n) = O(n) pour s constant. Lorsque m<n, on peut échanger A et B pour réduire la mémoire nécessaire. En ajoutant la mémoire nécessaire pour A et B, la complexité spatiale est O(s min{m,n}+m+n) = O(m+n) lorsque s est une constante.

Comme dans l’algorithme DL, les valeurs Hij sont calculées par rangées. Le tableau unidimensionnel U est utilisé pour sauvegarder les valeurs H calculées par l’algorithme DL lorsque la ligne i est en cours de calcul. Soit H la dernière ligne calculée pour le caractère c. Alors, T est la ligne w-1 de H. L’algorithme 2 donne le pseudocode de LS_DL. Son exactitude découle de l’exactitude de l’algorithme DL. Notez que swap(T],U) prend O(1) temps car les pointeurs vers 2 tableaux unidimensionnels sont échangés plutôt que le contenu de ces tableaux. Le nombre de cache-miss pour LS_DL est le même que pour DL lorsque n est suffisamment grand, car les deux ont le même modèle d’accès aux données. Cependant, pour les instances plus petites, LS_DL présente un bien meilleur comportement de cache. Par exemple, en raison de son utilisation de beaucoup moins de mémoire, nous pouvons avoir suffisamment de cache LLC pour stocker toutes les données dans LS_DL mais pas dans DL (O(sn) contre O(mn)).

L’algorithme d’espace linéaire efficace en cache S t r i p_D L

Lorsque (s+1)n est plus grand que la taille du cache LLC, nous pouvons réduire les manques de cache par rapport à l’algorithme LS_DL en calculant Hij par bandes de largeur q, pour un certain q inférieur à n (la dernière bande peut avoir une largeur inférieure à q). Cette méthode est illustrée à la figure 3. Les bandes sont calculées dans l’ordre 0, 1,… en utilisant l’algorithme LS_DL. Cependant, l’espace requis par T et U dans LS_DL est réduit à (s+1)q puisque la largeur de la bande est de q au lieu de n. En choisissant q suffisamment petit, nous pouvons nous assurer que les blocs des tableaux T et U utilisés par LS_DL ne sont pas évincés du cache une fois qu’ils sont introduits. Ainsi, si chaque entrée de T et U prend 1 mot, alors lorsque la taille du cache est lw, nous avons q<lw/(s+1). Notez qu’en plus de T et U, le cache doit contenir des partiels de A, B et d’autres tableaux nécessaires pour faire passer les données d’une bande à la suivante.

Calcul de H par bandes

Pour faire passer les données d’une bande à la suivante, nous utilisons une bande supplémentaire de tableau unidimensionnel de taille m et un tableau bidimensionnel s∗m V. La bande de tableau enregistre les valeurs de H calculées pour la colonne la plus à droite de la bande. V donne la valeur de H dans la colonne j la plus à droite de la ligne i de H qui est (a) dans une bande à gauche de celle en cours de calcul et (b) c=B.

Le pseudocode de Strip_DL est donné dans l’algorithme 3. Pour plus de clarté, ce pseudocode utilise deux tableaux de bandes (lignes 18 et 30) et deux tableaux de V (lignes 24 et 32). Un ensemble de tableaux est utilisé pour récupérer les données calculées pour la bande précédente et l’autre ensemble pour les données qui doivent être transmises à la bande suivante. Dans l’implémentation réelle, nous utilisons un seul tableau de bande et un seul tableau V écrasant les valeurs reçues de la bande précédente avec les valeurs à passer à la bande suivante.

Le temps et la complexité de Strip_DL sont, respectivement, O(mn) et O((s+1)m+(s+1)q+n) = O(sm+sq+n) = O(sm+n) car q est une constante. Lorsque m>n, nous pouvons commuter A et B pour conserver la mémoire et ainsi la complexité spatiale devient O(s min{m,n}+m+n) = O(m+n) pour s constant.

Lorsque nous analysons le cache miss, nous notons que q est choisi de telle sorte que U et T rentrent dans le cache. Nous faisons l’hypothèse raisonnable que la règle de remplacement LRU ne provoque pas l’éviction d’un bloc de U ou T pendant l’exécution de l’algorithme Strip_DL. Par conséquent, le nombre total de manques dans le cache dus à U et T est indépendant de m et n et peut donc être ignoré dans l’analyse. L’initialisation de Strip et V entraîne des accès en lecture de m/w et (s+1)m/w, respectivement. Le nombre d’accès en écriture est approximativement le même que le nombre d’accès en lecture. Le calcul pour chaque bande accède à la bande du tableau par ordre croissant d’index. Il en résulte (approximativement) le même nombre d’accès au cache que lors de la phase d’initialisation. Par conséquent, le nombre total de manques de cache dus aux bandes est approximativement de (2m/w)(n/q+1). Pour V, nous notons que lors du calcul de l’extraction actuelle, les éléments de toute ligne de V sont accédés dans l’ordre non décroissant de l’index (c’est-à-dire de gauche à droite) et que nous devons conserver, dans le cache, uniquement la valeur la plus récemment lue pour chaque caractère de l’alphabet (c’est-à-dire qu’il faut conserver au maximum s valeurs). En supposant qu’une valeur de V n’est évincée du cache que lorsqu’une nouvelle valeur pour le même caractère est accédée, le nombre total de lectures manquées de V lors du calcul d’une seule bande est sm/w. Le nombre de manques en écriture est approximativement le même. Ainsi, V contribue à (2sm/w)(n/q+1). Par conséquent, le nombre total de ratés de cache pour l’algorithme Strip_DL est ≈2(s+1)mn/(wq) lorsque m et n sont grands.

Rappelons que le nombre approximatif de ratés de cache pour les algorithmes DL et LS_DL est mn(1+3/w). C’est (wq+3q)/(2s+2) fois celui de Strip_DL.

L’algorithme de trace à espace linéaire L S D L_T R A C E

Bien que les algorithmes LS_DL et Strip_DL déterminent le score (coût) d’une trace optimale (et donc d’une séquence d’édition optimale) qui transforme A en B, ces algorithmes n’enregistrent pas suffisamment d’informations pour déterminer réellement une trace optimale. Pour déterminer une trace optimale à l’aide d’un espace linéaire, nous adoptons une stratégie de division et de conquête similaire à celle utilisée par Hirschberg pour le problème d’édition simple de chaînes de caractères (i.e., les transpositions ne sont pas autorisées) et Myers et Miller pour le problème d’alignement de séquences.

Nous disons qu’une trace a un croisement central si elle contient deux lignes (u1,v1) et (u2,v2), u1<u2 telles que v1>n/2 et v2≤n/2 (figure 4).

Les possibilités de fractionnement de la trace DL. a Sans croisement de centre b Avec croisement de centre

Détendons que T est une trace optimale qui satisfait les propriétés P2-P4. Si T ne contient aucun croisement central, alors ses lignes peuvent être partitionnées en ensembles TL et TR tels que TL contient toutes les lignes (u,v)∈T avec v≤n/2 et TR contient les lignes restantes (figure 4a). Puisqu’il n’y a pas de croisement central, toutes les lignes de TR ont une valeur u supérieure à la valeur u de chaque ligne de TL. Il découle des propriétés P2-P4 qu’il existe un i, 1≤i≤m tel que T est l’union d’une trace optimale pour A et B et de celle pour A et B. Soit H le coût de la première trace optimale et H′ celui de la seconde trace optimale. On voit que lorsque T n’a pas de croisement central, le coût de T est

Lorsque T contient un croisement central, ses lignes peuvent être partitionnées en 3 ensembles, TL, TM et TR, comme le montre la figure 4b. Soit (u1,v1) et (u2,v2) les lignes définissant le croisement central. Notez que TL contient toutes les lignes de T avec v<v2, TR contient toutes les lignes avec v>v1, et TM={(u1,v1),(u2,v2)}. Notons également que toutes les lignes dans TL ont un u<u1 et toutes dans TR ont un u>u2. De la propriété P1, il s’ensuit que TL est une trace optimale pour A et B et TR est une trace optimale pour A et B. De plus, puisque (u1,v1) et (u2,v2) sont des lignes équilibrées, le coût de TM est (u2-u1-1)+1+(v1-v2-1). Aussi, A≠A défaut, le remplacement des lignes se croisant au centre par (u1,v2) et (u2,v1) donne une trace de moindre coût. De la propriété P4, on sait que \(u_{1} = lastA\phantom {\dot {i}\!}\) et \(v_{2} = lastB\phantom {\dot {i}\!}\). Soit H le coût d’une trace optimale pour A et B et soit H′ celui d’une trace optimale pour A et B. Ainsi, lorsque T a une traversée centrale, son coût est

où, pour le min{}, on essaie 1≤u1<m et pour chaque tel u1, on fixe v1 comme étant le plus petit i>n/2 pour lequel \(b_{i} = a_{u_{1}}\phantom {\dot {i}\ !}\). Pour chaque u1, on examine tous les caractères autres que \(\phantom {\dot {i}\!}a_{u_{1}}\) dans l’alphabet. Pour chacun de ces caractères c, v2 est fixé au plus grand j≤n/2 pour lequel bj=c et u2 est le plus petit i>u1 pour lequel ai=c. Ainsi, le min est pris sur (s-1)m termes.

Laissons Utop et Ttop être les tableaux U et T finaux calculés par LS_DL avec les entrées B et A et Ubot et Tbot être ces tableaux lorsque les entrées sont l’inverse de B et A. À partir de ces tableaux, nous pouvons facilement déterminer les valeurs H et H′ nécessaires pour évaluer les équations 3 et 4. L’algorithme LSDL_TRACE (Algorithme 4) fournit le pseudocode pour notre calcul de l’espace linéaire d’une trace optimale. Il suppose que LS_DL a été modifié pour retourner à la fois les tableaux U et T.

Pour la complexité temporelle, nous voyons qu’au niveau supérieur de la récursion, nous invoquons LS_DL deux fois avec des chaînes de caractères A et B de taille m et n/2, respectivement. Cela prend au plus amn temps pour une certaine constante a. Le temps requis pour calculer les équations 3 et 4 est O(sn) et peut être absorbé dans amn en utilisant une constante a suffisamment grande. Au niveau suivant de la récursion, LS_DL est invoqué 4 fois. La somme des longueurs des chaînes A sur ces 4 invocations est au plus 2m et la chaîne B a une longueur au plus n/4. Donc, le temps pour ces quatre invocations est au plus amn/2. En généralisant aux autres niveaux de récurrence, on voit que l’algorithme LSDL_TRACE prend amn(1+1/2+1/4+1/8+…)<2amn=O(mn) temps. L’espace nécessaire est le même que pour LS_DL (notez que les paramètres de cet algorithme ont été intervertis). De l’analyse du temps, il résulte que le nombre de manques en cache est approximativement le double de celui de LS_DL lorsqu’il est invoqué avec des chaînes de taille m et n. Par conséquent, le nombre approximatif de manques en cache pour LSDL_TRACE est de 2mn(1+3/w).

Nous notons qu’une certaine réduction du temps d’exécution réel peut être obtenue en commutant A et B lorsque A est plus court que B assurant ainsi que la chaîne la plus courte est divisée à chaque niveau de récursion. Cela nous permet d’obtenir que la récursion se termine plus rapidement.

L’algorithme Strip trace S t r i p_T R A C E

Cet algorithme diffère de LSDL_TRACE en ce qu’il utilise une version modifiée de Strip_DL plutôt qu’une version modifiée de LS_DL. La version modifiée de Strip_DL renvoie les tableaux strip et V calculés par Strip_DL. De même, Strip_TRACE utilise Vtop et Vbot à la place de Ttop et Tbot. La complexité temporelle asymptotique de Strip_TRACE est également O(mn) et elle occupe la même quantité d’espace que Strip_DL (notez que les paramètres de Strip_DL sont intervertis par rapport à ceux de Strip_TRACE). Le nombre de manques de cache est approximativement le double de celui de Strip_DL.

Agorithmes multicœurs

Dans cette section, nous décrivons nos parallélisations de l’algorithme DL et des quatre algorithmes monocœurs de la section précédente. Ces parallélisations supposent que le nombre de processeurs est petit par rapport à la longueur de la chaîne. La convention de dénomination que nous adoptons pour les versions parallèles consiste à ajouter PP_ comme préfixe au nom de l’algorithme à noyau unique.

L’algorithme P P_D L

Notre version parallèle de l’algorithme DL, PP_DL, calcule les éléments dans le même ordre que DL. Cependant, il commence le calcul d’une ligne avant que le calcul de sa ligne précédente ne soit terminé. Chaque processeur se voit attribuer une ligne unique à calculer et il calcule cette ligne de gauche à droite. Soit p le nombre de processeurs. Le processeur z est initialement affecté au calcul de la boucle externe pour i=z, 1≤i≤p. Le processeur z commence après un décalage temporel approprié par rapport au démarrage du processeur z-1, de sorte que les données dont il a besoin pour son calcul ont déjà été calculées par le processeur z-1. Dans notre code, le décalage entre le début du calcul de deux lignes consécutives est le temps nécessaire pour calculer n/p éléments. A la fin du calcul de l’itération i, le processeur passe à l’itération i+p de la boucle externe. La complexité temporelle de PP_DL est O(mn/p).

L’algorithme P P_L S_D L

Bien que la stratégie générale de parallélisation de PP_LS_DL soit la même que celle utilisée dans PP_DL, une attention supplémentaire est nécessaire pour assurer un calcul identique à celui de LS_DL. La divergence des résultats est possible lorsque deux processeurs ou plus calculent simultanément différentes lignes de H en utilisant la même mémoire. Cela se produit par exemple lorsque A=aaabc⋯ et p≥3. Nous commençons avec le processeur i affecté au calcul de la ligne i de H, 1≤i≤p. Supposons que U=x et T=y initialement (notons que x et y sont des adresses en mémoire). En raison de l’instruction swap(T],U) dans LS_DL, le processeur 1 commence à calculer la rangée 1 de H en utilisant la mémoire commençant à l’adresse y. Si le processeur 2 commence avec un décalage approprié comme dans PP_DL, il calculera la rangée 2 de H en utilisant la mémoire commençant à l’adresse x. Avec un autre décalage, le processeur 3 commencera à calculer la ligne 3 de H en utilisant la mémoire commençant à l’adresse y. Maintenant, les processeurs 1 et 3 utilisent la même mémoire pour calculer différentes lignes de H et nous courons donc le risque d’écraser des valeurs de H qui pourraient être nécessaires pour des calculs ultérieurs. Comme autre exemple, considérons A=ababa⋯ et p≥4. Supposons que U=x et T= initialement. Le processeur 1 commence à calculer la ligne 1 en utilisant la mémoire y, puis, avec un décalage, le processeur 2 commence à calculer la ligne 2 en utilisant la mémoire z, puis le processeur 3 commence à calculer la ligne 3 en utilisant la mémoire x. Ensuite, le processeur 4 commence à calculer la ligne 4 en utilisant la mémoire y. A ce moment-là, le processeur 1 calcule la ligne 1 avec A=a et le processeur 4 calcule la ligne 4 avec A=b et les deux processeurs utilisent la même mémoire de ligne y.

Disons que p1 et p2 sont deux processeurs qui utilisent la même mémoire pour calculer les lignes r1<r2 de H et qu’aucun processeur n’utilise cette mémoire pour calculer une ligne entre r1 et r2. D’après le schéma de permutation utilisé dans LS_DL, il s’ensuit que p1 calcule la ligne \(r_{1} = lastA-1\phantom {\dot {i}\!}\). Les valeurs de H dans cette ligne sont nécessaires pour calculer les lignes r1+1 à r2 comme \(\phantom {\dot {i}\ !}r_{1} = lastA r_{1} < i \le r_{2}\). Ces valeurs ne sont pas nécessaires pour les lignes i>r2 car pour ces lignes \(\phantom {\dot {i}\!}lastA = r_{2} > r_{1} + 1 = lastA\). Soit j1 tel que \(\phantom {\dot {i}\!}b_{j} = a_{r_{2}} = a_{r_{1} + 1}\). Alors, pour j>j1, \(\phantom {\dot {i}\!}lastB \ge j_{1}\). Par conséquent, pour j>j1 les colonnes 1 à j1-2 de la ligne r1 ne sont pas nécessaires pour calculer un H dans les lignes entre r1 et r2.

Notre code parallèle utilise un schéma de synchronisation qui est basé sur les observations du paragraphe précédent pour retarder l’écrasement des valeurs qui sont nécessaires pour les calculs ultérieurs et assurer un calcul correct de la distance DL. Notre schéma de synchronisation utilise un autre tableau W qui est initialisé à 1. Supposons qu’un processeur calcule la ligne i de H et que A=a. Lorsque ce processeur rencontre pour la première fois un a dans B, disons à la position j1, il incrémente W. Lorsque le a suivant est rencontré, disons à la position j2, il incrémente W de 1. Lorsque le processeur termine son calcul de la ligne i, les positions restantes de W sont incrémentées de 1. Le processeur affecté au calcul de la ligne q de H peut calculer U si W=q. D’après nos observations précédentes, il s’ensuit que lorsque W=q, les anciennes valeurs dans les positions de mémoire U peuvent être écrasées car elles ne sont pas nécessaires pour les calculs futurs.

La complexité temporelle de cet algorithme à p-processeurs PP_LS_DL dépend des ensembles de données car le délai de synchronisation dépend des données. Nous nous attendons cependant à une performance d’exécution d’environ O(mn/p) lorsque les caractères de B sont grossièrement distribués uniformément.

L’algorithme P P_S t r i p_D L

Dans la version parallèle PP_Strip_DL de Strip_DL, le processeur i est initialement affecté au calcul de la bande i, 1≤i≤p. À la fin de la bande j qui lui est actuellement assignée, le processeur procède au calcul de la bande j+p. Un signal de tableau est utilisé à des fins de synchronisation. Lors du calcul d’une ligne r dans la bande s qui lui est attribuée, un processeur doit attendre que signal=s. signal est mis à s par le processeur travaillant sur la bande s-1 lorsque les valeurs à gauche de la bande s nécessaires au calcul de la ligne r de la bande s ont été calculées et qu’il n’y a pas de risque que les calculs pour la ligne r de la bande s écrasent les valeurs V nécessaires aux autres processeurs. signal fonctionne de manière très similaire à W dans PP_LS_DL.

Notez que lorsque nous travaillons sur p bandes, nous avons besoin de p copies des tableaux U et T utilisés par Strip_DL.

La complexité temporelle de PP_Strip_DL dépend du délai de synchronisation et devrait se rapprocher de O(mn/p).

L’algorithme P P_D L_T R A C E

Cet algorithme utilise d’abord PP_DL pour calculer H. Ensuite, un seul processeur effectue un traceback pour construire la trace optimale. Pour des valeurs raisonnables de p, le temps d’exécution est dominé par PP_DL et donc, la complexité de PP_DL_TRACE est également O(mn/p).

Les algorithmes P P_L S D L_T R A C E et P P_S t r i p_T R A C E

Dans LSDL_TRACE (Strip_TRACE), nous partitionnons de manière répétée le problème en deux et appliquons soit LS_DL (Strip_DL) à chaque partition. La version parallèle PP_LSDL_TRACE (PP_Strip_TRACE) emploie la stratégie de parallélisation suivante :

• Chaque sous-problème est résolu à l’aide de PP_LS_DL (PP_Strip_DL) lorsque le nombre de sous-problèmes indépendants est faible ; tous les p processeurs sont affectés à la solution parallèle d’un seul sous-problème. C’est-à-dire que les sous-problèmes sont résolus en séquence.

• P les sous-problèmes sont résolus en parallèle en utilisant LS_DL (Strip_DL) pour résoudre chaque sous-problème en série lorsque le nombre de sous-problèmes indépendants est grand,

La complexité temporelle de PP_LSDL_TRACE et PP_Strip_TRACE est O(mn/p).

.