Inspiriert von diesen beiden Fragen: String-Manipulation: Berechnen Sie die “Ähnlichkeit eines Strings mit seinen Suffixen” und die Programmausführung variiert, wenn die I/P-Größe in C über 5 steigt, habe ich den folgenden Algorithmus entwickelt.
Die Fragen werden
- Ist das richtig oder habe ich einen Denkfehler gemacht?
- Was ist die Worst-Case-Komplexität des Algorithmus?
Ein bisschen Kontext zuerst. Definieren Sie für zwei Zeichenfolgen ihre Ähnlichkeit als die Länge des längsten gemeinsamen Präfixes der beiden. Die totale Selbstähnlichkeit einer Zeichenfolge s ist die Summe der Ähnlichkeiten von s mit all seinen Suffixen. Also zum Beispiel die totale Selbstähnlichkeit von abacab ist 6 + 0 + 1 + 0 + 2 + 0 = 9 und die totale Selbstähnlichkeit von a wiederholt n mal ist n*(n+1)/2.
Beschreibung des Algorithmus: Der Algorithmus basiert auf dem Knuth-Morris-Pratt-String-Suchalgorithmus, indem die Grenzen der Präfixe der Zeichenfolge spielen die zentrale Rolle.
Zur Wiederholung: a Grenze einer Saite s ist ein echter Teilstring b von s was gleichzeitig ein Präfix und ein Suffix von ist s.
Bemerkung: Wenn b und c sind Grenzen von s mit b kürzer als cdann b ist auch eine Grenze von cund umgekehrt jede Grenze von c ist auch eine Grenze von s.
Lassen s eine lange Kette sein n und p ein Präfix von sein s mit Länge ich. Wir nennen eine Grenze b mit Breite k von p nicht erweiterbar wenn entweder i == n oder s[i] != s[k]andernfalls ist es erweiterbar (die length k+1 Präfix von s ist dann eine Grenze der Länge i+1 Präfix von s).
Wenn nun das längste gemeinsame Präfix von s und das Suffix beginnend mit s[i], i > 0hat Länge kdie Länge k Präfix von s ist eine nicht dehnbare Grenze der Länge ich+k Präfix von s. Es ist eine Grenze, weil es ein gemeinsames Präfix von ist s und s[i .. n-1]und wenn es erweiterbar wäre, wäre es nicht das längste gemeinsame Präfix.
Umgekehrt ist jede nicht erweiterbare Grenze (der Länge k) der Länge ich Präfix von s ist das längste gemeinsame Präfix von s und das Suffix beginnend mit s[i-k].
So können wir die Gesamtselbstähnlichkeit von berechnen s durch Summieren der Längen aller nicht dehnbaren Grenzen der Länge ich Präfixe von s, 1 <= i <= n. Das zu tun
- Berechnen Sie die Breite der breitesten Ränder der Präfixe durch den standardmäßigen KMP-Vorverarbeitungsschritt.
- Berechnen Sie die Breite der breitesten nicht dehnbaren Ränder der Präfixe.
- Für jeden ich,
1 <= i <= nwennp = s[0 .. i-1]hat eine nicht leere, nicht erweiterbare Grenze, let b die breiteste von diesen sein, addieren Sie die Breite von b und für alle nicht leeren Grenzen c von bwenn es sich um eine nicht erweiterbare Grenze von handelt paddiere seine Länge. - Fügen Sie die Länge hinzu n von sda das oben nicht abgedeckt ist.
Kode (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;
}
Also, ist das richtig? Ich wäre eher überrascht, wenn nicht, aber ich habe mich schon einmal geirrt.
Was ist die Worst-Case-Komplexität des Algorithmus?
Ich denke, es ist O (n), aber ich habe noch keinen Beweis dafür gefunden, dass die Anzahl der erweiterbaren Grenzen, die ein Präfix in seiner breitesten nicht erweiterbaren Grenze enthalten kann, begrenzt ist (oder vielmehr, dass die Gesamtzahl solcher Vorkommen O ist (n)).
Ich interessiere mich am meisten für scharfe Grenzen, aber wenn Sie beweisen können, dass es zB O(n*log n) oder O(n^(1+x)) für klein ist x, das ist schon gut. (Es ist offensichtlich im schlimmsten Fall quadratisch, daher ist eine Antwort von “Es ist O (n ^ 2)” nur interessant, wenn sie von einem Beispiel für quadratisches oder nahezu quadratisches Verhalten begleitet wird.)
de.wikipedia.org/wiki/…
– Hans Passant
19. Dezember 2011 um 15:34 Uhr
@HansPassant Ich mache etwas anderes mit der Borders-Tabelle, ich sehe nicht, wie die Argumentation für den KMP-Algorithmus darauf angewendet werden könnte. Können Sie das näher erläutern?
– Daniel Fischer
19. Dezember 2011 um 15:46 Uhr
Haben Sie versucht, das Programm mehrmals mit zufälligen Eingabedaten auszuführen und die Laufzeiten aufzuzeichnen? Ich sage natürlich nicht, dass dies eine vollständige und korrekte Antwort auf Ihre Frage geben würde, aber es würde wahrscheinlich eine allgemeine Vorstellung davon geben, wie sich die Laufzeit in Reataion zur Größe der Eingabe ändert.
– Benutzer500944
19. Dezember 2011 um 18:24 Uhr
@SaeedAmiri Bisher habe ich nichts gefunden, was auf nichtlineares Verhalten hinweist, aber ich hätte gerne einen Beweis oder ein Gegenbeispiel.
– Daniel Fischer
19. Dezember 2011 um 18:28 Uhr
@Grigry Die zufällige Eingabe ist linear, die einzige Möglichkeit für nichtlineares Verhalten ist die Eingabe mit speziellen regelmäßigen Mustern. Ich versuche herauszufinden, ob es solche Muster gibt oder nicht.
– Daniel Fischer
19. Dezember 2011 um 18:32 Uhr