¿Es este algoritmo lineal?

Question

Inspirado por estas dos preguntas: String manipulation: calculate the "similarity of a string with its suffixes" y Program execution varies as the I/P size increases beyond 5 in C, se me ocurrió el siguiente algoritmo.

Las preguntas serán

1. Es correcto, o que han cometido un error en mi razonamiento?
2. ¿Cuál es la peor complejidad del algoritmo?

Un poco de contexto primero. Para dos cadenas, defina su similitud como la longitud del prefijo común más largo de los dos. La autosimilitud total de una cadena s es la suma de las similitudes de s con todos sus sufijos. Entonces, por ejemplo, la auto-similitud total de abacab es 6 + 0 + 1 + 0 + 2 + 0 = 9 y la auto-similitud total de a repite n veces es n*(n+1)/2.

Descripción del algoritmo: El algoritmo se basa en la cadena de Knuth-Morris-Pratt algoritmo de búsqueda, en el que las fronteras de prefijos de la cadena juegan un papel central.

Para recapitular: a frontera de una cadena s es una subcadena adecuada b de s que es simultáneamente un prefijo y un sufijo de s.

Observación: Si b y c son fronteras de s con b más corto que c, entonces b es también un borde de c, y por el contrario, todas las fronteras de c es también un borde de s.

Deje s ser una cadena de longitud n y p ser un prefijo de s con longitud i. Llamamos a una frontera b con anchura k de pno extensible si cualquiera i == n o s[i] != s[k], de lo contrario es extensible (la longitud de prefijo k+1 de s es entonces un borde de la longitud de prefijo i+1 de s).

Ahora, si el prefijo común más larga de s y el sufijo comenzando con s[i], i > 0, tiene longitud k, la longitud k prefijo de s es una frontera no extensible de la longitud i + k prefijo de s. Es un borde porque es un prefijo común de s y s[i .. n-1], y si fuera extensible, no sería el prefijo común más largo.

el contrario, todas las fronteras no extensible (de longitud k) de la longitud i prefijo de s es el prefijo común más larga de s y el sufijo comenzando con s[i-k].

Así podemos calcular la auto-similitud total de s sumando las longitudes de todas las fronteras no extensibles de la longitud i prefijos de s, 1 <= i <= n. Para hacerlo

1. Calcule el ancho de los bordes más anchos de los prefijos mediante el paso de preprocesamiento de KMP estándar.
2. Calcule el ancho de los bordes más amplios no extensibles de los prefijos.
3. Para cada i, 1 <= i <= n, si p = s[0 .. i-1] tiene un borde no vacío no extensible, dejar b ser la más amplia de estos, añadir la anchura de b y para todas las fronteras no vacíos c de b, si es un borde no extensible de p, agregue su longitud.
4. Agregue la longitud n de s, ya que eso no está cubierto por lo anterior.

de código (C):

#include <stdlib.h> 
#include <stdio.h> 
#include <string.h> 

/* 
* Overflow and NULL checks omitted to not clutter the algorithm. 
*/ 

int similarity(char *text){ 
    int *borders, *ne_borders, len = strlen(text), i, j, sim; 
    borders = malloc((len+1)*sizeof(*borders)); 
    ne_borders = malloc((len+1)*sizeof(*ne_borders)); 
    i = 0; 
    j = -1; 
    borders[i] = j; 
    ne_borders[i] = j; 
    /* 
    * Find the length of the widest borders of prefixes of text, 
    * standard KMP way, O(len). 
    */ 
    while(i < len){ 
     while(j >= 0 && text[i] != text[j]){ 
      j = borders[j]; 
     } 
     ++i, ++j; 
     borders[i] = j; 
    } 
    /* 
    * For each prefix, find the length of its widest non-extensible 
    * border, this part is also O(len). 
    */ 
    for(i = 1; i <= len; ++i){ 
     j = borders[i]; 
     /* 
     * If the widest border of the i-prefix has width j and is 
     * extensible (text[i] == text[j]), the widest non-extensible 
     * border of the i-prefix is the widest non-extensible border 
     * of the j-prefix. 
     */ 
     if (text[i] == text[j]){ 
      j = ne_borders[j]; 
     } 
     ne_borders[i] = j; 
    } 
    /* The longest common prefix of text and text is text. */ 
    sim = len; 
    for(i = len; i > 0; --i){ 
     /* 
     * If a longest common prefix of text and one of its suffixes 
     * ends right before text[i], it is a non-extensible border of 
     * the i-prefix of text, and conversely, every non-extensible 
     * border of the i-prefix is a longest common prefix of text 
     * and one of its suffixes. 
     * 
     * So, if the i-prefix has any non-extensible border, we must 
     * sum the lengths of all these. Starting from the widest 
     * non-extensible border, we must check all of its non-empty 
     * borders for extendibility. 
     * 
     * Can this introduce nonlinearity? How many extensible borders 
     * shorter than the widest non-extensible border can a prefix have? 
     */ 
     if ((j = ne_borders[i]) > 0){ 
      sim += j; 
      while(j > 0){ 
       j = borders[j]; 
       if (text[i] != text[j]){ 
        sim += j; 
       } 
      } 
     } 
    } 
    free(borders); 
    free(ne_borders); 
    return sim; 
} 


/* The naive algorithm for comparison */ 
int common_prefix(char *text, char *suffix){ 
    int c = 0; 
    while(*suffix && *suffix++ == *text++) ++c; 
    return c; 
} 

int naive_similarity(char *text){ 
    int len = (int)strlen(text); 
    int i, sim = 0; 
    for(i = 0; i < len; ++i){ 
     sim += common_prefix(text,text+i); 
    } 
    return sim; 
} 

int main(int argc, char *argv[]){ 
    int i; 
    for(i = 1; i < argc; ++i){ 
     printf("%d\n",similarity(argv[i])); 
    } 
    for(i = 1; i < argc; ++i){ 
     printf("%d\n",naive_similarity(argv[i])); 
    } 
    return EXIT_SUCCESS; 
} 

Por lo tanto, es esto correcto? Estaría bastante sorprendido si no, pero he estado equivocado antes.

¿Cuál es la peor complejidad del algoritmo?

Creo que es O (n), pero todavía no he encontrado una prueba de que el número de bordes extensibles que un prefijo puede contener en su borde más amplio no extensible sea acotado (o más bien, que el número total de tales ocurrencias es O (n)).

Lo que más me interesan no tienen límites definidos, pero si puedes demostrar que es válido, por ejemplo. O (n * log n) o O (n^(1 + x)) para el pequeño x, eso ya está bien. (Obviamente, es en el peor de los casos cuadrático, por lo que una respuesta de "Es O (n^2)" solo es interesante si se acompaña de un ejemplo de comportamiento cuadrático o casi cuadrático.)

Answer 1

Esto parece una idea muy clara, pero, por desgracia, creo que el peor de los casos es O (n^2).

Aquí está mi intento de contraejemplo. (No soy un matemático así que por favor perdona mi uso de Python en lugar de ecuaciones para expresar mis ideas!)

Considerar la cadena con 4k + 1 símbolos

s = 'a'*K+'X'+'a'*3*K 

Esto tendrá

borders[1:] = range(K)*2+[K]*(2*K+1) 

ne_borders[1:] = [-1]*(K-1)+[K-1]+[-1]*K+[K]*(2*K+1) 

Tenga en cuenta que:

1) ne_borders [i] será igual a K para (2K + 1) valores de i.

2) para 0 < = j < = K, fronteras [j] = j-1

3) el bucle final en su algoritmo voy a entrar en el bucle interior con j == K para 2K + 1 valores de i

4) el bucle interno se iterar K veces para reducir j a 0

5) Esto da como resultado el algoritmo necesita más de N * N/8 operaciones para hacer una cadena del peor caso de longitud N

Por ejemplo, para K = 4 da la vuelta al ciclo interno 39 veces

s = 'aaaaXaaaaaaaaaaaa' 
borders[1:] = [0, 1, 2, 3, 0, 1, 2, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4] 
ne_borders[1:] = [-1, -1, -1, 3, -1, -1, -1, -1, 4, 4, 4, 4, 4, 4, 4, 4, 4] 

Para K = 2,248 va alrededor del lazo interno 10,111,503 veces!

¿Quizás hay una manera de arreglar el algoritmo para este caso?

Answer 2

Es posible que desee echar un vistazo a la Z-algoritmo, eso es demostrable lineal:

s es un C-secuencia de longitud N

Z[0] = N; 
int a = 0, b = 0; 
for (int i = 1; i < N; ++i) 
{ 
    int k = i < b ? min(b - i, Z[i - a]) : 0; 
    while (i + k < N && s[i + k] == s[k]) ++k; 
    Z[i] = k; 
    if (i + k > b) { a = i; b = i + k; } 
} 

Ahora similitud es simplemente la suma de las entradas de Z.