operaciones - programacion lineal entera teoria

¿Este algoritmo es lineal?

Question

Inspirado por estas dos preguntas: Manipulación de la cadena: calcule la "similitud de una cadena con sus sufijos" y la ejecución del programa varía a medida que el tamaño de I / P aumenta más allá de 5 en C.

Las preguntas serán

1. ¿Es correcto o cometí 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 auto-similitud 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 una repetición de n veces es n*(n+1)/2 .

Descripción del algoritmo: el algoritmo se basa en el algoritmo de búsqueda de cadenas Knuth-Morris-Pratt, en el que los bordes de los prefijos de la cadena juegan el papel central.

Para recapitular: un borde de una cadena s es una subcadena adecuada b de s, que es a la vez un prefijo y un sufijo de s .

Observación: si byc son bordes de s con b más cortos que c , entonces b también es un borde de c , y por el contrario, cada borde de c es también un borde de s .

Sea s una cadena de longitud n y p sea ​​un prefijo de s con longitud i . Llamamos un borde b con ancho k de p no extensible si i == n o s[i] != s[k] , de lo contrario es extensible (la longitud k+1 prefijo de s es entonces un borde de la longitud i+1 prefijo de s ).

Ahora, si el prefijo común más largo de sy el sufijo que comienza con s[i], i > 0 , tiene una longitud k , el prefijo de longitud k de s es un borde no extensible del prefijo i + k de longitud 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.

Por el contrario, cada borde no extensible (de longitud k ) de la longitud i prefijo de s es el prefijo común más largo de sy el sufijo comienza con s[ik] .

Por lo tanto, podemos calcular la auto-similitud total de s sumando las longitudes de todos los bordes no extensibles de la longitud i prefijos de s , 1 <= i <= n . Para hacer eso

1. Calcule el ancho de los bordes más anchos de los prefijos mediante el paso de preprocesamiento estándar de KMP.
2. Calcule el ancho de los bordes no extensibles más anchos de los prefijos.
3. Para cada i , 1 <= i <= n , si p = s[0 .. i-1] tiene un borde no extensible no vacío, b sea ​​el más ancho de estos, agregue el ancho de by para todos los bordes 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.

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;
}

Entonces, ¿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 esté limitado (o más bien, que el número total de tales ocurrencias sea O (norte)).

Estoy muy interesado en los límites agudos, pero si puedes probar que es, por ejemplo, O (n * log n) o O (n ^ (1 + x)) para x pequeña, eso ya es bueno. (Obviamente, es en el peor de los casos cuadrático, por lo que una respuesta de "Es O (n ^ 2)" solo es interesante si va acompañada de un ejemplo de comportamiento cuadrático o casi cuadrático).

Answer 1

Es posible que desee echar un vistazo al algoritmo Z, que es probablemente lineal:

s es una cuerda en C 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 la similitud es solo la suma de las entradas de Z.

Answer 2

Esto parece una idea realmente buena, pero lamentablemente creo que el comportamiento del caso más desfavorable es O (n ^ 2).

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

Considere 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, bordes [j] = j-1

3) el ciclo final en tu algoritmo irá al ciclo interno con j == K para 2K + 1 valores de i

4) el ciclo interno iterará K veces para reducir j a 0

5) Esto hace que el algoritmo necesite más de N * N / 8 operaciones para hacer una cadena de peor caso de longitud N.

Por ejemplo, para K = 4 gira alrededor del bucle 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, da la vuelta al ciclo interno 10,111,503 veces.

Tal vez hay una manera de arreglar el algoritmo para este caso?