algorithm - sobre - método levenshtein

¿Hay un algoritmo de distancia de edición escasa?

Question

Digamos que tienes dos cadenas de longitud 100.000 que contienen ceros y unos. Puede calcular su distancia de edición en aproximadamente 10 ^ 10 operaciones.

Si cada cadena solo tiene 100 unidades y el resto son ceros, entonces puedo representar cada cadena usando 100 enteros diciendo dónde están las.

¿Existe un algoritmo mucho más rápido para calcular la distancia de edición utilizando esta representación dispersa? Aún mejor sería un algoritmo que también usa 100 ^ 2 de espacio en lugar de 10 ^ 10 de espacio.

Para dar algo para probar, considera estas dos cadenas con 10 unas cada una. Los enteros dicen dónde están los en cada cadena.

[9959, 10271, 12571, 21699, 29220, 39972, 70600, 72783, 81449, 83262]

[9958, 10270, 12570, 29221, 34480, 37952, 39973, 83263, 88129, 94336]

En términos algorítmicos, si tenemos dos cadenas binarias dispersas de longitud n cada una representada por k enteros cada uno, ¿existe un algoritmo de distancia de edición de tiempo O(k^2) ?

Answer 1

¡Por supuesto! Hay tan pocas operaciones posibles con tantos 0s. Quiero decir, la respuesta es a lo sumo 200.

Echa un vistazo a

10001010000000001
vs       ||||||
10111010100000010

Mira todos los ceros con tuberías. ¿Importa cuál de esos acabas eliminando? No Esa es la clave.

Solución 1

Consideremos la solución normal de n * m:

dp(int i, int j) {
    // memo & base case
    if( str1[i-1] == str1[j-1] ) {
        return dp(i-1, j-1);
    }
    return 1 + min( dp(i-1, j), dp(i-1, j-1), dp(i, j-1) );
}

Si casi todos los personajes fueran un 0, ¿cuál sería la mayor cantidad de tiempo?

if( str1[i-1] == str1[j-1] ) { // They will be equal so many times, (99900)^2 times!
    return dp(i-1, j-1);
}

Podía imaginarme eso goteando por decenas de miles de recursiones. Todo lo que necesitas para la lógica son los ~ 200 puntos críticos. Puedes ignorar el resto. Una simple modificación sería

if( str1[i-1] == str1[j-1] ) {
    if( str1[i-1] == 1 )
        return dp(i-1, j-1); // Already hit a critical point

    // rightmost location of a 1 in str1 or str2, that is <= i-1
    best = binarySearch(CriticalPoints, i-1);
    return dp(best + 1, best + 1); // Use that critical point
    // Important! best+1 because we still want to compute the answer at best
    // Without it, we would skip over in a case where str1[best] is 1, and str2[best] is 0.
}

CriticalPoints sería la matriz que contiene el índice de cada 1 en str1 o str2. Asegúrese de que esté ordenado antes de la búsqueda binaria. Ten en cuenta esos gochya''s. Mi lógica era: bueno, necesito asegurarme de calcular la respuesta en el best índice, así que vamos con el best + 1 parámetro best + 1 . Pero, si es best == i - 1 , nos quedamos atascados en un bucle. Me encargaré de eso con una comprobación rápida de str1[i-1] == 1 . Hecho, Phew.

Puede hacer una comprobación rápida de la corrección observando que, en el peor de los casos, alcanzará todas las combinaciones 200 * 100000 de i y j que generan puntos críticos, y cuando esos puntos críticos llaman min(a, b, c) , solo hace tres Llamadas a funciones recursivas. Si alguna de esas funciones son puntos críticos, entonces es parte de las 200 * 100000 que ya contamos y podemos ignorarlas. Si no lo es, entonces en O (log (200)) cae en una sola llamada en otro punto crítico (ahora, es algo que sabemos que es parte de los 200 * 100000 que ya contamos). Por lo tanto, cada punto crítico lleva, en el peor 3*log(200) casos, 3*log(200) excluyendo las llamadas a otros puntos críticos. De manera similar, la primera llamada de función caerá en un punto crítico en el tiempo de log(200) . Por lo tanto, tenemos un límite superior de O (200 * 100000 * 3 * log (200) + log (200)).

Además, asegúrese de que su tabla de notas sea un hashmap, no una matriz. 10 ^ 10 de memoria no caben en su computadora.

Solucion 2

Usted sabe que la respuesta es a lo sumo 200, así que evite computar más que las operaciones en profundidad.

dp(int i, int j) { // O(100000 * 205), sounds good to me.
    if( abs(i - j) > 205 )
        return 205; // The answer in this case is at least 205, so it''s irrelevant to calculating the answer because when min is called, it wont be smallest.
    // memo & base case
    if( str1[i-1] == str1[j-1] ) {
        return dp(i-1, j-1);
    }
    return 1 + min( dp(i-1, j), dp(i-1, j-1), dp(i, j-1) );
}

Este es muy simple, pero lo dejo para la solución dos porque esta solución parece haber salido de la nada, en lugar de analizar el problema y averiguar dónde está la parte lenta y cómo optimizarla. Sin embargo, mantenga esto en su caja de herramientas, ya que debería estar codificando esta solución.

Solucion 3

Al igual que la Solución 2, podríamos haberlo hecho así:

dp(int i, int j, int threshold = 205) {
    if( threshold == 0 )
        return 205;
    // memo & base case
    if( str1[i-1] == str1[j-1] ) {
        return dp(i-1, j-1);
    }
    return 1 + min( dp(i-1, j, threshold - 1), dp(i-1, j-1, threshold - 1), dp(i, j-1, threshold - 1) );
}

Es posible que esté preocupado por la posibilidad de que dp (i-1, j-1) caiga, pero el umbral mantiene a i y j muy cerca, por lo que calcula un subconjunto de la Solución 2. Esto se debe a que el umbral disminuye cada vez que i y j se alejan. aparte. dp(i-1, j-1, threshold) lo haría idéntico a la Solución 2 (Por lo tanto, este es un poco más rápido).

Espacio

Estas soluciones le darán la respuesta muy rápidamente, pero si también desea una solución de optimización de espacio, sería fácil reemplazar str1[i] con (i in Str1CriticalPoints) ? 1 : 0 (i in Str1CriticalPoints) ? 1 : 0 , usando un hashmap. Esto daría una solución final que todavía es muy rápida (aunque será 10 veces más lenta), y también evita mantener las cadenas largas en la memoria (hasta el punto en que podría ejecutarse en un Arduino). Aunque no creo que esto sea necesario.

Tenga en cuenta que la solución original no utiliza 10 ^ 10 de espacio. Usted menciona "aún mejor, menos de 10 ^ 10 espacios", con la implicación de que 10 ^ 10 de espacio sería aceptable. Desafortunadamente, incluso con suficiente RAM, la iteración a pesar de que el espacio toma 10 ^ 10 veces, lo que definitivamente no es aceptable. Ninguna de mis soluciones usa 10 ^ 10 de espacio: solo 2 * 10 ^ 5 para sujetar las cuerdas, lo que puede evitarse como se explicó anteriormente. 10 ^ 10 bytes 10 GB para referencia.

EDITAR: Como señala Maniek, solo necesita verificar abs(i - j) > 105 , ya que las 100 inserciones restantes necesarias para igualar i y j obtendrán el número de operaciones por encima de 200.