Cet algorithme est-il linéaire?

Inspiré par ces deux questions: Manipulation des chaînes: calculez la “similarité d’une chaîne avec ses suffixes” et l’exécution du programme varie lorsque la taille de l’I / P dépasse 5 en C , j’ai développé l’algorithme ci-dessous.

Les questions seront

  1. Est-ce correct ou ai-je commis une erreur dans mon raisonnement?
  2. Quelle est la pire complexité de l’algorithme?

Un peu de contexte d’abord. Pour deux chaînes, définissez leur similarité comme la longueur du préfixe commun le plus long des deux. L’auto-similarité totale d’une chaîne s est la sum des similitudes de s avec tous ses suffixes. Ainsi, par exemple, l’auto-similarité totale d’ abacab est 6 + 0 + 1 + 0 + 2 + 0 = 9 et l’auto-similitude totale d’ une répétition n fois est n*(n+1)/2 .

Description de l’algorithme: L’algorithme est basé sur l’algorithme de recherche de chaîne Knuth-Morris-Pratt, en ce sens que les bordures des préfixes de la chaîne jouent un rôle central.

En résumé: une bordure d’une chaîne s est une sous-chaîne appropriée b de s qui est simultanément un préfixe et un suffixe de s .

Remarque: Si b et c sont des frontières de s avec b plus courtes que c , alors b est aussi une frontière de c et, inversement, chaque frontière de c est aussi une frontière de s .

Soit s une chaîne de longueur n et p un préfixe de s de longueur i . Nous appelons une bordure b de largeur k de p non extensible si i == n ou s[i] != s[k] , sinon elle est extensible (la longueur k+1 préfixe de s est alors une bordure de la longueur i+1 préfixe de s ).

Maintenant, si le préfixe commun le plus long de s et le suffixe commençant par s[i], i > 0 , a une longueur k , le préfixe de longueur k de s est une bordure non extensible de préfixe de longueur i + k de s . C’est une frontière parce que c’est un préfixe commun de s et s[i .. n-1] , et si elle était extensible, ce ne serait pas le plus long préfixe commun.

Inversement, chaque bordure non extensible (de longueur k ) du préfixe de longueur i de s est le préfixe commun le plus long de s et le suffixe commençant par s[ik] .

Nous pouvons donc calculer l’auto-similarité totale de s en additionnant les longueurs de toutes les frontières non extensibles des préfixes de longueur i de s , 1 <= i <= n . Pour faire ça

  1. Calculez la largeur des limites les plus larges des préfixes à l’étape de pré-traitement KMP standard.
  2. Calculez la largeur des limites non extensibles les plus larges des préfixes.
  3. Pour chaque i , 1 <= i <= n , si p = s[0 .. i-1] a une bordure non extensible non vide, soit b le plus large de ceux-ci, ajoutez la largeur de b et pour tout les bordures non vides c de b , s’il s’agit d’une bordure non extensible de p , ajoutez sa longueur.
  4. Ajoutez la longueur n de s , car elle n’est pas couverte par ce qui précède.

Code (C):

 #include  #include  #include  /* * 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 = 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  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; } 

Alors, est-ce correct? Je serais plutôt surpris sinon, mais je me suis trompé avant.

Quelle est la pire complexité de l’algorithme?

Je pense que c’est O (n), mais je n’ai pas encore trouvé la preuve que le nombre de bordures extensibles qu’un préfixe peut avoir dans sa plus large bordure non extensible est limité (ou plutôt que le nombre total de telles occurrences est O (n)).

Ce qui m’intéresse le plus, ce sont les limites nettes, mais si vous pouvez prouver que c’est par exemple O (n * log n) ou O (n ^ (1 + x)) pour un petit x , c’est déjà bon. (C’est évidemment au pire quadratique, donc une réponse de “c’est O (n ^ 2)” n’a d’intérêt que si elle est accompagnée d’un exemple de comportement quadratique ou quasi-quadratique.)

Cela semble être une très bonne idée, mais malheureusement, je pense que le pire comportement est O (n ^ 2).

Voici ma tentative de contre-exemple. (Je ne suis pas mathématicien, alors pardonnez-moi d’utiliser Python au lieu d’équations pour exprimer mes idées!)

Considérons la chaîne avec 4K + 1 symboles

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

Cela aura

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

Notez que:

1) ne_borders [i] sera égal à K pour (2K + 1) les valeurs de i.

2) pour 0 <= j <= K, les frontières [j] = j-1

3) la boucle finale de votre algorithme ira dans la boucle intérieure avec j == K pour 2K + 1 valeurs de i

4) la boucle interne itérera K fois pour réduire j à 0

5) Il en résulte que l’algorithme a besoin de plus de N * N / 8 opérations pour effectuer la chaîne la plus défavorable de longueur N.

Par exemple, pour K = 4, il contourne la boucle interne 39 fois.

 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] 

Pour K = 2 248, il contourne la boucle intérieure 10 111 503 fois!

Peut-être qu’il y a un moyen de réparer l’algorithme pour ce cas?

Vous voudrez peut-être jeter un coup d’œil à l’algorithme Z, qui est manifestement linéaire:

s est un C-ssortingng de longueur 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; } } 

Maintenant, la similarité est simplement la sum des entrées de Z.