Inspiré par ces deux questions : Manipulation des chaînes de caractères : calculez la "similarité d'une chaîne de caractères avec ses suffixes". y L'exécution du programme varie lorsque la taille de l'I/P augmente au-delà de 5 en C j'ai trouvé l'algorithme ci-dessous.
Les questions seront les suivantes
- Est-ce correct, ou ai-je fait une erreur dans mon raisonnement ?
- Quelle est la complexité de l'algorithme dans le pire des cas ?
Un peu de contexte d'abord. Pour deux chaînes de caractères, définissez leur similarité comme la longueur du plus long préfixe commun des deux. L'autosimilarité totale d'une chaîne s est la somme des similitudes de s avec tous ses suffixes. Ainsi, par exemple, l'autosimilarité totale de abacab est 6 + 0 + 1 + 0 + 2 + 0 = 9 et l'autosimilarité totale de a répétées n temps est n*(n+1)/2 .
Description de l'algorithme : L'algorithme est basé sur l'algorithme de recherche de chaînes de Knuth-Morris-Pratt, en ce sens que la chaîne de caractères de l'algorithme de Knuth-Morris-Pratt n'a pas été modifiée. frontières des préfixes de la chaîne jouent le rôle central.
Pour récapituler : a frontière d'une chaîne de caractères s est une sous-chaîne propre b de s qui est simultanément un préfixe et un suffixe de s .
Remarques : Si b y c sont des frontières de s con b plus court que c alors b est également une frontière de c et, inversement, toute frontière de c est également une frontière de s .
Soit s soit une chaîne de longueur n y p soit un préfixe de s avec la longueur i . Nous appelons une frontière b avec largeur k de p non-extensible si l'un ou l'autre i == n o s[i] != s[k] sinon elle est extensible (la longueur k+1 préfixe de s est alors une frontière de la longueur i+1 préfixe de s ).
Maintenant, si le plus long préfixe commun de s et le suffixe commençant par s[i], i > 0 , a une longueur k la longueur k préfixe de s est une bordure non extensible de la longueur i+k préfixe de s . C'est une frontière parce que c'est un préfixe commun de s y s[i .. n-1] et s'il était extensible, il ne serait pas le préfixe commun le plus long.
Inversement, toute bordure non extensible (de longueur k ) de la longueur i préfixe de s est le plus long préfixe commun de s et le suffixe commençant par s[i-k] .
Nous pouvons donc calculer l'autosimilarité totale de s en additionnant les longueurs de toutes les frontières non extensibles de la longueur i préfixes de s , 1 <= i <= n . Pour ce faire
- Calculer la largeur des bords les plus larges des préfixes par l'étape de prétraitement standard de KMP.
- Calculez la largeur des bords non extensibles les plus larges des préfixes.
- Pour chaque i ,
1 <= i <= nsip = s[0 .. i-1]a une bordure non vide et non extensible, soit b être le plus large, ajoutez la largeur de b et pour toutes les frontières non vides c de b si elle est une frontière non extensible de p ajoutez sa longueur. - Ajoutez la longueur n de s puisque cela n'est pas couvert par ce qui précède.
Code (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;
}Alors, c'est correct ? Je serais plutôt surpris si ce n'était pas le cas, mais j'ai déjà eu tort auparavant.
Quelle est la complexité de l'algorithme dans le pire des cas ?
Je pense que c'est O(n), mais je n'ai pas encore trouvé de preuve que le nombre de frontières extensibles qu'un préfixe peut avoir contenues dans sa plus large frontière non extensible est borné (ou plutôt, que le nombre total de ces occurrences est O(n)).
Je suis surtout intéressé par des limites nettes, mais si vous pouvez prouver que c'est par exemple O(n*log n) ou O(n^(1+x)) pour de petites valeurs x c'est déjà bien. (C'est évidemment au pire quadratique, donc une réponse de "C'est O(n^2)" n'est intéressante que si elle est accompagnée d'un exemple de comportement quadratique ou quasi-quadratique).
