Landau-Vishkin
El algoritmo de landau-vishkin es una solución para el problema de string-matching con k-diferencias. Este consiste en encontrar todas las ocurrencias de un patrón P en un texto T con a lo más k-diferencias
Tipos de diferencias
Para este algoritmo se definen tres tipos de diferencia, Discrepancia (Mismatch), inserción, y eliminación.
- Discrepancia (Mismatching): Un elemento del patrón corresponde a un carácter diferente en el texto
- Inserción: Un elemento del patrón no corresponde a ningún carácter en el texto
- Eliminación: Un carácter del texto no corresponde a ningún carácter en el patrón
Ejemplo
Dado el patrón P="bxdyegh", el texto T="abcdefghi"" y k=3, existe una ocurrencia con tres diferencias que empieza en la segunda posición en el texto
De izquierda a derecha la primera diferencia es una discrepancia, la segunda una inserción, y la última es una eliminación.
Definición
Este algoritmo se divide en dos etapas principales, el análisis del patrón y el análisis del texto, además existe una versión simple del algoritmo (trabaja con una matriz) y otra versión compleja (usando un suffix tree)
Análisis del patrón
El input de este algoritmo es solo el patrón P como un arreglo de caracteres.
En la versión simple de esta etapa se computa una matriz de dos dimensiones MAX-LENGTH(0,...,m-1;0,...,m-1) (donde m es el tamaño del patrón). MAX-LENGTH(i,j) = f significa que la subcadena \(a_{i+1},...,a_{i+f} = a_{j+1},...,a_{j+f}\), y además que \(a_{i+f+1} \neq a_{j+f+1}\).
#include <vector>
#include <string>
using namespace std;
vector<vector<int>> patternAnalysis(const string& pattern) {
int m = pattern.size();
vector<vector<int>> maxLen(m, vector<int>(m, 0));
for (int i = m - 2; i >= 0; --i)
for (int j = m - 1; j > i; --j)
if (pattern[i] == pattern[j])
maxLen[i][j] = 1 + ((i + 1 < m && j + 1 < m) ? maxLen[i + 1][j + 1] : 0);
return maxLen;
}
El número de operaciones realizadas por el algoritmo para cada diagonal es proporcional al número de pares en la diagonal, por lo tanto, el número total de operaciones realizadas por el algoritmo para todas las diagonales es proporcional al número total de pares que es \(O(m^2)\)
Para la versión compleja de esta etapa primero vemos que el podemos reducir el problema de encontrar f con la matriz MAX-LENGTH al problema Longest Common Ancestor (LCA), así vemos que MAX-LENGTH(i,j) \(=\) Length(\(LCA_{i,j}\)) de esta forma solo queda computar el suffix tree para encontrar el LCA en tiempo constante.
Análisis del texto
Para el análisis del texto se itera sobre todo el texto desde \(i\) hasta \(n-m+k\) donde en cada iteración se aplica el procedimiento CHECK. Existen diversas versiones de CHECK:
- CHECK 1 (Sankoff y Kruskal) y CHECK-2 (Ukkonen) están basados en programación dinámica y no usan el análisis del patrón precomputado.
- CHECK 3 (Landau y Vishkin) usa la matriz MAX-LENGTH precomputada
- CHECK 4 (Landau y Vishkin) usa el Suffix tree precomputado.
El algoritmo CHECK-1 computa una matriz \(D\) de tamaño (\(m + k + 1\);\(m+1\)). La entrada \(D_{l,j}\) representa el número mínimo de diferencias entre el prefijo del patrón \(a_{1}...a_{l}\) y la subcadena del texto \(t_{i+1}...t_{i+j}\).
\(D_{l,j}\) se calcula como el mínimo de sus tres predecesores, más la penalización por diferencia: \(\(D_{l,j} = \min \begin{cases} D_{l-1, j} + 1 & \text{ (Inserción)} \\ D_{l, j-1} + 1 & \text{ (Eliminación)} \\ D_{l-1, j-1} + (\text{si } a_{l} \neq t_{i+j} \text{ entonces } 1 \text{ sino } 0) & \text{ (Desajuste o Match)} \end{cases}\)\) Cada aplicación de CHECK-1 toma tiempo \(O(m^2)\).Esto resulta en un tiempo total de análisis del texto de \(O(nm^2)\). El espacio requerido es \(O(m^2)\) o puede reducirse a \(O(m)\).
El algoritmo CHECK-2 (basado en el trabajo de Ukkonen) es una modificación de la programación dinámica que mejora la eficiencia al concentrarse solo en las entradas relevantes de la matriz \(D\)
En lugar de calcular toda la matriz \(D\), CHECK-2 se centra en la cantidad \(L_{d,e}\), que denota la fila más larga \(l\) que se puede alcanzar en la diagonal \(d = j-l\) con exactamente \(e\) diferencias. Solo se necesita computar \(L_{d,e}\) para \(e \le k\) y \(|d| \le e\).
Debido a que el número de diagonales a calcular es \(O(k)\) y el avance puede tomar hasta \(O(m)\) pasos por diagonal, cada aplicación de CHECK-2 toma \(O(mk)\). Esto resulta en un tiempo total de análisis del texto de \(O(nmk)\).
El algoritmo CHECK-3 optimiza el paso más lento del algoritmo anterior, avanzar con la coincidencia exacta, este algoritmo en lugar de avanzar carácter por carácter, utiliza la matriz MAX-LENGTH precomputada. Esta matriz permite determinar en tiempo \(O(1)\) la longitud máxima de coincidencia exacta que se extiende desde una determinada posición.
La aplicación de CHECK-3 toma tiempo \(O(k^2)\). Esto resulta en un tiempo total de análisis del texto de \(O(nk^2)\). Sin embargo, se requiere el tiempo de preprocesamiento de \(O(m^2)\) y espacio \(O(m^2)\) para la matriz.
El algoritmo CHECK-4 es una optimización del CHECK-3 que mantiene la eficiencia en la fase de análisis del texto (\(O(nk^2)\)), pero mejora la eficiencia de la fase de análisis del patrón.
La complejidad total del algoritmo se convierte en \(O(m \log m + nk^2)\) y el espacio requerido es solo \(O(m)\). Esta es la versión asintóticamente más eficiente de Landau-Vishkin.
Implementación
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
int check3(const string& text, const string& pattern, const vector<vector<int>>& maxLen, int k, int iter) {
int n = text.size(), m = pattern.size();
vector<vector<int>> L(2 * k + 1, vector<int>(k + 1, -1));
for (int e = 0; e <= k; ++e) {
for (int d = -e; d <= e; ++d) {
int idx = d + k;
int best = -1;
if (e == 0) {
while (best + 1 < m && iter + best + 1 + d < n &&
iter + best + 1 + d >= 0 &&
pattern[best + 1] == text[iter + best + 1 + d])
++best;
L[idx][e] = best;
continue;
}
int bestPrev = -1;
if (d > -e + 1) bestPrev = max(bestPrev, L[idx - 1][e - 1] + 1); // insertion
if (d < e - 1) bestPrev = max(bestPrev, L[idx + 1][e - 1]); // deletion
bestPrev = max(bestPrev, L[idx][e - 1] + 1); // mismatch
// Version simplificada, no usa la matriz maxlen
while (bestPrev + 1 < m &&
iter + bestPrev + 1 + d < n && iter + bestPrev + 1 + d >= 0 &&
pattern[bestPrev + 1] == text[iter + bestPrev + 1 + d])
++bestPrev;
L[idx][e] = bestPrev;
}
for (int d = -e; d <= e; ++d)
if (L[d + k][e] >= m - 1) return iter;
}
return -1;
}
// Landau-Vishkin [1988] simple implementation (Ukkonen-like), time O(m^2 + nkm), space O(m^2 + k^2)
vector<int> landau_vishkin(const string& text, const string& pattern, const vector<vector<int>>& maxlen ,int k){
int n = text.size();
vector<int> occs;
for (int i = 0; i < n; i++) {
int occ = check3(text, pattern, maxlen, k, i);
if (occ > -1) occs.push_back(occ);
}
return occs;
}
Resumen general de complejidades
| Procedimiento | Preprocesamiento | Análisis del Texto | Tiempo Total | Espacio |
|---|---|---|---|---|
| CHECK-1 (Sankoff/Kruskal) | N/A | \(O(nm^2)\) | \(O(nm^2)\) | \(O(m)\) o \(O(m^2)\) |
| CHECK-2 (Ukkonen) | N/A | \(O(nmk)\) | \(O(nmk)\) | \(O(m)\) |
| CHECK-3 (LV) | \(O(m^2)\) (Matriz) | \(O(nk2)\) | \(O(m^2+nk^2)\) | \(O(m^2)\) |
| CHECK-4 (LV) | \(O(mlogm)\) (Suffix Tree) | \(O(nk^2)\) | \(O(mlogm+nk^2\)) | \(O(m)\) |
Ejemplos de uso
A continuación, se mostrará como se construye la matriz L paso a paso para el texto="abracadabra", el patrón="baced", y k=2. Se mostrará la matriz de la iteración para el índice 1 del texto (que es donde se da una ocurrencia del patrón)
Primero se construye una matriz de \((2k+1)\) x \((k+1)\) (ósea 5 filas y 3 columnas para el ejemplo), iniciando con todos los valores en un valor invalido (-1 en este caso)
En la matriz:
- \(e\) representa la cantidad de errores permitidos
- \(d\) representa la diferencia de desplazamiento entre el índice del texto y del patrón.
- Los valores donde \(e < |d|\) se omiten o se mantienen en \(-1\) por ser inválidos
La matriz se arma siguiendo principios de programación dinámica usando la siguiente formula:
Finalmente, la matriz L para la primera ocurrencia es la siguiente:
Como \(L[d = 1][e = 2] = 4\) se dice que se encontró una ocurrencia del patrón con 2 errores, ya que 4 es el índice en el que termina el patrón.
Referencias
-
LANDAU, G. M. AND VISHKIN, U. Fast String Matching with k Differences. Journal of Computer and System Sciences, 37, 63–78.. 1988.
-
D. SANKOFF AND J. B. KRUSKAL (Eds.), “Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison”, Addison-Wesley, Reading, MA, 1983.
-
E. UKKONEN, On approximate string matching, in “Proc. Int. Conf. Found. Comp. Theor.,” Lecture Notes in Computer Science 158, pp. 487495, Springer-Verlag, Berlin/New York, 1983.