Corrección de cadenas usando la distancia Damerau-Levenshtein

by: adminPosted on:

Algoritmos de un solo núcleo

En esta sección, desarrollamos cuatro algoritmos de un solo núcleo de espacio lineal para la corrección de cadenas usando la distancia DL. Los cuatro se ejecutan en tiempo O(mn). Los dos primeros (LS_DL y Strip_DL) calculan sólo la puntuación Hmn del trazado óptimo; difieren en su eficiencia de caché. Los dos últimos (LSDL_TRACE y Strip_TRACE) calculan una traza óptima.

El algoritmo de espacio lineal L S_D L

Sea s el tamaño del alfabeto. En lugar de utilizar la matriz H utilizada en DL, el algoritmo LS_DL utiliza una matriz unidimensional U y una matriz bidimensional T. Estas dos matrices tienen un requisito de espacio de O((s+1)n) = O(n) para s constante. Cuando m<n, uno puede intercambiar A y B para reducir la memoria requerida. Sumando la memoria necesaria para A y B, la complejidad espacial es O(s min{m,n}+m+n) = O(m+n) cuando s es una constante.

Al igual que en el algoritmo DL, los valores Hij se calculan por filas. El array unidimensional U se utiliza para guardar los valores H calculados por el algoritmo DL cuando se está calculando la fila i. Sea H la última fila calculada para el carácter c. Entonces, T es la fila w-1 de H. El algoritmo 2 da el pseudocódigo de LS_DL. Su corrección se deduce de la corrección del algoritmo DL. Obsérvese que swap(T],U) requiere un tiempo de O(1) ya que se intercambian los punteros a 2 matrices unidimensionales en lugar del contenido de estas matrices. El recuento de fallos de caché para LS_DL es el mismo que para DL cuando n es convenientemente grande, ya que ambos tienen el mismo patrón de acceso a los datos. Sin embargo, para instancias más pequeñas, LS_DL mostrará un comportamiento de caché mucho mejor. Por ejemplo, debido a que utiliza mucha menos memoria, podemos tener suficiente caché LLC para almacenar todos los datos en LS_DL pero no en DL (O(sn) frente a O(mn)).

El algoritmo de espacio lineal eficiente en caché S t r i p_D L

Cuando (s+1)n es mayor que el tamaño de la caché LLC, podemos reducir las pérdidas de caché en relación con el algoritmo LS_DL calculando Hij por tiras de ancho q, para algún q menor que n (la última tira puede tener un ancho menor que q). Esto se muestra en la Fig. 3. Las franjas se calculan en el orden 0, 1,… utilizando el algoritmo LS_DL. Sin embargo, el espacio que necesitan T y U en LS_DL se reduce a (s+1)q ya que la anchura de la franja es q en lugar de n. Al elegir q lo suficientemente pequeño, podemos asegurar que los bloques de las matrices T y U utilizados por LS_DL no son desalojados de la caché una vez que son introducidos. Así, si cada entrada de T y U ocupa 1 palabra, entonces cuando el tamaño de la caché es lw, tenemos q<lw/(s+1). Obsérvese que, además de T y U, la caché necesita contener parciales de A, B y otras matrices necesarias para pasar los datos de una tira a la siguiente.

Fig. 3
figura3

Calcular H por tiras

Para pasar los datos de una tira a la siguiente, utilizamos una tira de array unidimensional adicional de tamaño m y un array V bidimensional s∗m. La tira de matrices registra los valores de H calculados para la columna más a la derecha de la tira. V da el valor de H en la columna j más a la derecha de la fila i de H que está (a) en una tira a la izquierda de la que se está calculando actualmente y (b) c=B.

El pseudocódigo para Strip_DL se da en el Algoritmo 3. Para mayor claridad, este pseudocódigo utiliza dos matrices de tiras (líneas 18 y 30) y dos matrices V (líneas 24 y 32). Un conjunto de matrices se utiliza para obtener los datos calculados para la tira anterior y el otro conjunto para los datos que se van a pasar a la tira siguiente. En la implementación real, utilizamos un único array de tiras y un único array de V sobrescribiendo los valores recibidos de la tira anterior con los valores que se pasarán a la siguiente tira.

El tiempo y la complejidad de Strip_DL son, respectivamente, O(mn) y O((s+1)m+(s+1)q+n) = O(sm+sq+n) = O(sm+n) ya que q es una constante. Cuando m>n, podemos intercambiar A y B para conservar la memoria y así la complejidad espacial se convierte en O(s min{m,n}+m+n) = O(m+n) para s constante.

Cuando analizamos el fallo de caché, observamos que q se elige de forma que U y T caben en la caché. Hacemos la suposición razonable de que la regla de sustitución LRU no hace que ningún bloque de U o T sea desalojado durante la ejecución del algoritmo Strip_DL. Como resultado, el número total de pérdidas de caché debidas a U y T es independiente de m y n, por lo que puede ser ignorado en el análisis. La inicialización de Strip y V resulta en m/w y (s+1)m/w accesos de lectura, respectivamente. El número de accesos de escritura es aproximadamente el mismo que el número de accesos de lectura. El cálculo de cada tira accede a la tira del array en orden ascendente de índice. Esto da como resultado (aproximadamente) el mismo número de accesos a la caché que los realizados durante la fase de inicialización. Por lo tanto, el número total de pérdidas de caché debidas a la tira es aproximadamente (2m/w)(n/q+1). En el caso de V, observamos que, al calcular la tira actual, se accede a los elementos de cualquier fila de V en orden no decreciente de índice (es decir, de izquierda a derecha) y que necesitamos retener, en la caché, sólo el valor leído más recientemente para cada carácter del alfabeto (es decir, hay que retener como máximo s valores). Suponiendo que un valor V se desaloja de la caché sólo cuando se accede a un nuevo valor para el mismo carácter, el número total de pérdidas de lectura de V al calcular una sola tira es de sm/w. El número de errores de escritura es aproximadamente el mismo. Por tanto, V contribuye con (2sm/w)(n/q+1). Por lo tanto, el número total de pérdidas de caché para el algoritmo Strip_DL es ≈2(s+1)mn/(wq) cuando m y n son grandes.

Recuerde que el recuento aproximado de pérdidas de caché para los algoritmos DL y LS_DL es mn(1+3/w). Esto es (wq+3q)/(2s+2) veces el de Strip_DL.

El algoritmo de trazado en espacio lineal L S D L_T R A C E

Aunque los algoritmos LS_DL y Strip_DL determinan la puntuación (coste) de un trazado óptimo (y por tanto de una secuencia de edición óptima) que transforma A en B, estos algoritmos no guardan suficiente información para determinar realmente un trazado óptimo. Para determinar una traza óptima utilizando el espacio lineal, adoptamos una estrategia de «divide y vencerás» similar a la utilizada por Hirschberg para el problema de edición de cadenas simples (es decir las transposiciones no están permitidas) y Myers y Miller para el problema de alineación de secuencias.

Declaramos que un trazado tiene un cruce central si contiene dos líneas (u1,v1) y (u2,v2), u1<u2 tales que v1>n/2 y v2≤n/2 (Fig. 4).

Fig. 4
figure4

Oportunidades de división de trazos de DL. a Sin cruce central b Con cruce central

Sea T un trazado óptimo que satisface las propiedades P2-P4. Si T no contiene ningún cruce central, entonces sus líneas pueden dividirse en conjuntos TL y TR tales que TL contiene todas las líneas (u,v)∈T con v≤n/2 y TR contiene las líneas restantes (Fig. 4a). Como no hay ningún cruce central, todas las líneas en TR tienen un valor u mayor que el valor u de cada línea en TL. Se deduce de las propiedades P2-P4 que hay un i, 1≤i≤m tal que T es la unión de un trazado óptimo para A y B y el de A y B. Sea H el coste el primer trazado óptimo y H′ el del segundo trazado óptimo. Vemos que cuando T no tiene ningún cruce central, el coste de T es

$$ costeNoCC(T) = \min_{1 \le i \le m}{ H + H’\} $$
(3)

Cuando T contiene un cruce central, sus trazos pueden dividirse en 3 conjuntos, TL, TM y TR, como se muestra en la Fig. 4b. Sean (u1,v1) y (u2,v2) las líneas que definen el cruce central. Observa que TL contiene todas las líneas de T con v<v2, TR contiene todas las líneas con v>v1, y TM={(u1,v1),(u2,v2)}. Obsérvese también que todas las líneas en TL tienen una u<u1 y todas en TR tienen u>u2. De la propiedad P1, se deduce que TL es un trazado óptimo para A y B y TR es un trazado óptimo para A y B. Además, como (u1,v1) y (u2,v2) son líneas equilibradas, el coste de TM es (u2-u1-1)+1+(v1-v2-1). Además, A≠A como en el caso contrario, al sustituir las líneas de cruce central por (u1,v2) y (u2,v1) se obtiene un trazado de menor coste. A partir de la propiedad P4, sabemos que \(u_{1} = últimoAnfantoma {\dot {i}!}) y \(v_{2} = últimoAnfantoma {\dot {i}!}). Sea H el coste de un trazado óptimo para A y B y sea H′ el de un trazado óptimo para A y B. Por tanto, cuando T tiene un cruce central, su coste es

$$ {\begin{aligned} costeCC(T) \,=,& \min\{H + H’ \\\\&+ (u_{2}-u_{1}-1) + 1 + (v_{1}-v_{2}-1)\} |end{aligned}} ¡$$
(4)

donde, para el min{}, probamos 1≤u1<m y para cada uno de tales u1, establecemos que v1 es el menor i>n/2 para el que \(b_{i} = a_{u_{1}}phantom {\dot {i}\!}\). Para cada u1, examinamos todos los caracteres que no sean \(\phantom {\dot {i}\!}a_{u_{1}}) en el alfabeto. Para cada uno de esos caracteres c, v2 se fija en el mayor j≤n/2 para el que bj=c y u2 es el menor i>u1 para el que ai=c. Por lo tanto, el mínimo se toma sobre (s-1)m términos.

Dejemos que Utop y Ttop sean las matrices finales de U y T calculadas por LS_DL con las entradas B y A y que Ubot y Tbot sean estas matrices cuando las entradas son la inversa de B y A. A partir de estas matrices, podemos determinar fácilmente los valores de H y H′ necesarios para evaluar las Ecs. 3 y 4. El algoritmo LSDL_TRACE (Algoritmo 4) proporciona el pseudocódigo para nuestro cálculo de espacio lineal de una traza óptima. Supone que LS_DL ha sido modificado para devolver las matrices U y T.

Para la complejidad temporal, vemos que en el nivel superior de la recursión, invocamos LS_DL dos veces con cadenas A y B de tamaño m y n/2, respectivamente. El tiempo requerido para calcular las ecuaciones 3 y 4 es O(sn) y puede ser absorbido en amn utilizando una constante a adecuadamente grande. La suma de las longitudes de las cadenas A a través de estas 4 invocaciones es como máximo 2m y la cadena B tiene una longitud máxima de n/4. Por lo tanto, el tiempo de estas cuatro invocaciones es como máximo amn/2. Generalizando al resto de niveles de recursión, vemos que el algoritmo LSDL_TRACE tarda amn(1+1/2+1/4+1/8+…)<2amn=O(mn) de tiempo. El espacio necesario es el mismo que el de LS_DL (nótese que se han cambiado los parámetros de este algoritmo). Del análisis de tiempo, se deduce que el número de pérdidas de caché es aproximadamente el doble que para LS_DL cuando se invoca con cadenas de tamaño m y n. Por lo tanto, el recuento aproximado de pérdidas de caché para LSDL_TRACE es 2mn(1+3/w).

Notamos que se puede conseguir cierta reducción en el tiempo de ejecución real cambiando A y B cuando A es más corto que B, asegurando así que la cadena más corta se divide en cada nivel de recursión. Esto nos permite conseguir que la recursión termine más rápido.

El algoritmo Strip_TRACE S t r i p_T R A C E

Este algoritmo difiere de LSDL_TRACE en que utiliza una versión modificada de Strip_DL en lugar de una versión modificada de LS_DL. La versión modificada de Strip_DL devuelve las matrices strip y V calculadas por Strip_DL. En consecuencia, Strip_TRACE utiliza Vtop y Vbot en lugar de Ttop y Tbot. La complejidad temporal asintótica de Strip_TRACE es también O(mn) y ocupa la misma cantidad de espacio que Strip_DL (nótese que los parámetros de Strip_DL se cambian respecto a los de Strip_TRACE). El número de pérdidas de caché es aproximadamente el doble que para Strip_DL.

Algoritmos multinúcleo

En esta sección, describimos nuestras paralelizaciones del algoritmo DL y los cuatro algoritmos de un solo núcleo de la sección anterior. Estas paralelizaciones suponen que el número de procesadores es pequeño en relación con la longitud de la cadena. La convención de nomenclatura que adoptamos para las versiones paralelas es añadir PP_ como prefijo al nombre del algoritmo de núcleo único.

El algoritmo P P_D L

Nuestra versión paralela del algoritmo DL, PP_DL, calcula los elementos en el mismo orden que DL. Sin embargo, comienza el cálculo de una fila antes de que se complete el cálculo de su fila anterior. A cada procesador se le asigna una única fila a computar y la computa de izquierda a derecha. Sea p el número de procesadores. El procesador z se asigna inicialmente para hacer el cálculo del bucle exterior para i=z, 1≤i≤p. El procesador z comienza después de un tiempo de retraso adecuado en relación con el inicio del procesador z-1 para que los datos que necesita para su cálculo ya han sido calculados por el procesador z-1. En nuestro código, el desfase entre el inicio del cálculo de dos filas consecutivas es el tiempo necesario para calcular n/p elementos. Al finalizar el cálculo de su iteración i, el procesador pasa a la iteración i+p del bucle exterior. La complejidad temporal de PP_DL es O(mn/p).

El algoritmo P P_L S_D L

Aunque la estrategia general de paralelización de PP_LS_DL es la misma que la utilizada en PP_DL, es necesario un cuidado extra para asegurar un cálculo idéntico al de LS_DL. La divergencia en los resultados es posible cuando dos o más procesadores están calculando simultáneamente diferentes filas de H utilizando la misma memoria. Esto ocurre, por ejemplo, cuando A=aaabc⋯ y p≥3. Comenzamos con el procesador i asignado a computar la fila i de H, 1≤i≤p. Supongamos que U=x y T=y inicialmente (nótese que x e y son direcciones en memoria). Debido a la sentencia swap(T],U) en LS_DL, el procesador 1 comienza a calcular la fila 1 de H utilizando la memoria que comienza en la dirección y. Si el procesador 2 comienza con un retraso adecuado como en PP_DL, calculará la fila 2 de H utilizando la memoria que comienza en la dirección x. Con otro retraso, el procesador 3 empezará a calcular la fila 3 de H de nuevo utilizando la memoria que empieza en la dirección y. Ahora, tanto el procesador 1 como el 3 están utilizando la misma memoria para calcular diferentes filas de H, por lo que corremos el riesgo de sobrescribir valores de H que pueden ser necesarios para cálculos posteriores. Como otro ejemplo, consideremos A=ababa⋯ y p≥4. Supongamos que U=x y T= inicialmente. El procesador 1 comienza a calcular la fila 1 utilizando la memoria y, luego, con un retraso, el procesador 2 comienza a calcular la fila 2 utilizando la memoria z, luego el procesador 3 comienza a calcular la fila 3 utilizando la memoria x. A continuación, el procesador 4 comienza a calcular la fila 4 utilizando la memoria y. En este momento el procesador 1 está computando la fila 1 con A=a y el procesador 4 está computando la fila 4 con A=b y ambos procesadores están usando la misma memoria de fila y.

Sea p1 y p2 dos procesadores que están usando la misma memoria para computar las filas r1<r2 de H y que ningún procesador está usando esta memoria para computar una fila entre r1 y r2. Del esquema de asignación de intercambios utilizado en LS_DL, se deduce que p1 está calculando la fila \(r_{1} = lastA-1\phantom {\dot {i}\}). ¡Los valores H de esta fila son necesarios para calcular las filas r1+1 a r2 como \phantom(\phantom {\dot {i}\!}r_{1} = lastA r_{1} < i \le r_{2}\). Estos valores no son necesarios para las filas i>r2 ya que para estas filas \(\phantom {\dot {i}!}lastA = r_{2} > r_{1} + 1 = últimoA). Sea j1 tal que \fantom {{punto}}}b_{j} = a_{r_{2}} = a_{r_{1} + 1}}. Entonces, para j>j1, \(\phantom {\dot {i}!}lastB \ge j_{1}\). Por lo tanto, para j>j1 las columnas 1 a j1-2 de la fila r1 no son necesarias para calcular una H en las filas entre r1 y r2.

Nuestro código paralelo utiliza un esquema de sincronización que se basa en las observaciones del párrafo anterior para retrasar la sobreescritura de los valores que se necesitan para cálculos posteriores y asegurar un cálculo correcto de la distancia DL. Nuestro esquema de sincronización emplea otra matriz W que se inicializa a 1. Supongamos que un procesador está calculando la fila i de H y que A=a. Cuando este procesador encuentra por primera vez una a en B, digamos en la posición j1, incrementa W. Cuando se encuentra la siguiente a, digamos en j2, incrementa W en 1. Cuando el procesador termina su cálculo de la fila i, las posiciones restantes de W se incrementan en 1. El procesador asignado para calcular la fila q de H puede calcular U si W=q. De nuestras observaciones anteriores, se deduce que cuando W=q, los valores antiguos en las posiciones de memoria U pueden sobrescribirse, ya que no son necesarios para futuros cálculos.

La complejidad temporal de este algoritmo de p-procesadores PP_LS_DL depende de los conjuntos de datos, ya que el retardo de sincronización depende de los datos. Sin embargo, esperamos un rendimiento en tiempo de ejecución de aproximadamente O(mn/p) cuando los caracteres de B están distribuidos de forma aproximadamente uniforme.

El algoritmo P P_S t r i p_D L

En la versión paralela PP_Strip_DL de Strip_DL, el procesador i se asigna inicialmente para calcular la tira i, 1≤i≤p. Una vez completada la tira j que tiene asignada, el procesador procede a calcular la tira j+p. Se utiliza una señal de matriz con fines de sincronización. Al calcular una fila r en su tira asignada s, un procesador necesita esperar hasta que signal=s. signal se establece en s por el procesador que trabaja en la tira s-1 cuando los valores a la izquierda de la tira s necesarios en el cálculo de la fila r de la tira s se han calculado y no hay riesgo de que los cálculos para la fila r de la tira s sobrescriban los valores V que necesitan otros procesadores. signal funciona de forma muy parecida a W en PP_LS_DL.

Nótese que cuando trabajamos con p tiras, necesitamos p copias de las matrices U y T utilizadas por Strip_DL.

La complejidad temporal de PP_Strip_DL depende del retardo de sincronización y se espera que se aproxime a O(mn/p).

El algoritmo P P_D L_T R A C E

Este algoritmo utiliza primero PP_DL para calcular H. A continuación, un único procesador realiza un traceback para construir el trace óptimo. Para valores razonables de p, el tiempo de ejecución está dominado por PP_DL y, por tanto, la complejidad de PP_DL_TRACE es también O(mn/p).

Los algoritmos P P_L S D L_T R A C E y P_S t r i p_T R A C E

En LSDL_TRACE (Strip_TRACE), dividimos repetidamente el problema en dos y aplicamos LS_DL (Strip_DL) a cada partición. La versión paralela PP_LSDL_TRACE (PP_Strip_TRACE) emplea la siguiente estrategia de paralelización:

  • Cada subproblema se resuelve utilizando PP_LS_DL (PP_Strip_DL) cuando el número de subproblemas independientes es pequeño; todos los p procesadores se asignan a la solución paralela de un único subproblema. Es decir, los subproblemas se resuelven de forma secuencial.

  • Los p subproblemas se resuelven en paralelo utilizando LS_DL (Strip_DL) para resolver cada subproblema en serie cuando el número de subproblemas independientes es grande,

    • La complejidad temporal de PP_LSDL_TRACE y PP_Strip_TRACE es O(mn/p).

  • .

Deja una respuesta

Tu dirección de correo electrónico no será publicada.