Erklärung des minimalen zyklischen Verschiebungsalgorithmus

Question

Ich bin vor kurzem auf diesen Code gestoßen, der keinen Kommentar enthält. Er findet die minimale zyklische Verschiebung eines Wortes (dieser Code gibt speziell seinen Index in der Zeichenkette zurück) und heißt Duval-Algorithmus. Nur Infos Ich habe eine Beschreibung des Algorithmus in wenigen Worten und einen saubereren Code gefunden. Ich würde jede Hilfe zum Verständnis dieses Algorithmus zu schätzen wissen. Ich habe immer gefunden, Text-Algorithmen ziemlich schwierig und ziemlich schwer zu verstehen.

int minLexCyc(const char *x) {
    int i = 0, j = 1, k = 1, p = 1, a, b, l = strlen(x);
    while(j+k <= (l<<1)) {
        if ((a=x[(i+k-1)%l])>(b=x[(j+k-1)%l])) {
            i=j++;
            k=p=1;
        } else if (a<b) {
            j+=k; 
            k=1; 
            p=j-i;
        } else if (a==b && k!=p) {
            k++;
        } else {
            j+=p; 
            k=1;
        }
    }
    return i;
}

Answer 1

Erstens glaube ich, dass Ihr Code einen Fehler enthält. Die letzte Zeile sollte lauten return p; . Ich glaube, dass i den Index der lexikografisch kleinsten zyklischen Verschiebung und p die kleinste passende Verschiebung enthält. Ich denke auch, dass Ihre Abbruchbedingung zu schwach ist, d.h. Sie überprüfen zu viel, nachdem Sie eine Übereinstimmung gefunden haben, aber ich bin mir nicht sicher, was genau es sein sollte.

Wir suchen eine Zeichenkette, die mit der bei i beginnenden Zeichenkette übereinstimmt, und wir versuchen, sie mit einer Zeichenkette zu vergleichen, die bei j beginnt. Wir tun dies, indem wir das k-te Zeichen jeder Zeichenkette vergleichen und dabei k erhöhen (solange sie übereinstimmen). Beachten Sie, dass wir i nur dann ändern, wenn wir feststellen, dass die mit j beginnende Zeichenkette lexikografisch kleiner ist als die mit j beginnende Zeichenkette, dann setzen wir i auf j und setzen k und p auf ihre Anfangswerte zurück.

Ich habe keine Zeit für eine detaillierte Analyse, aber es sieht so aus

1. i = der Beginn der lexikografisch kleinsten zyklischen Verschiebung
2. j = der Beginn der zyklischen Schicht, die wir mit der bei i beginnenden Schicht abgleichen
3. k = das aktuell betrachtete Zeichen in den Zeichenketten i und j (die Zeichenketten stimmen an den Positionen 1 bis k-1 überein)
4. p = die betreffende zyklische Schicht (ich glaube, p steht für Präfix)

Editer Weiter gehend

dieser Abschnitt des Kodex

    if ((a=x[(i+k-1)%l])>(b=x[(j+k-1)%l])) {
        i=j++;
        k=p=1;

Verschiebt den Beginn des Vergleichs auf eine lexikografisch frühere Zeichenkette, wenn wir eine finden, und reinitialisiert alles andere.

dieser Abschnitt

   } else if (a<b) {
        j+=k; 
        k=1; 
        p=j-i;

ist der schwierige Teil. Wir haben eine Fehlanpassung gefunden, die lexikografisch nach unserer Referenzzeichenkette liegt, also springen wir an das Ende des bisher gefundenen Textes und beginnen mit dem Abgleich von dort. Außerdem erhöhen wir p (unsere Schrittweite). Warum können wir alle Anfangspunkte zwischen j und j + k überspringen? Das liegt daran, dass die Zeichenkette, die mit i beginnt, die lexikografisch kleinste ist, und wenn das Ende der aktuellen j-Zeichenkette größer ist als die Zeichenkette bei i, dann wird jedes Suffix der Zeichenkette bei j größer sein als die Zeichenkette bei i.

Endlich

    } else if (a==b && k!=p) {
        k++;
    } else {
        j+=p; 
        k=1;

prüft lediglich, ob sich die mit i beginnende Zeichenkette der Länge p wiederholt.

**weiter bearbeiten* Wir tun dies, indem wir k inkrementieren, bis k == p und prüft, ob das k-te Zeichen der mit i beginnenden Zeichenkette mit dem k-ten Zeichen der mit j beginnenden Zeichenkette übereinstimmt. Sobald k den Wert p erreicht hat, beginnt die Suche beim nächsten vermuteten Vorkommen der Zeichenkette von neuem.

Noch weiter bearbeiten zu versuchen, die Fragen von Jethro zu beantworten.

Erstens: die k != p en else if (a==b && k!=p) Hier haben wir eine Übereinstimmung, da das k-te und alle vorherigen Zeichen in den Zeichenfolgen, die mit i und j beginnen, gleich sind. Die Variable p steht für die Länge, die wir für die sich wiederholende Zeichenfolge halten. Wenn k != p eigentlich k < p Wir stellen also sicher, dass die p Zeichen der mit i beginnenden Zeichenkette die gleichen sind wie die p Zeichen der mit j beginnenden Zeichenkette. k == p (das letzte else) sollten wir an einem Punkt sein, an dem die Zeichenkette mit j + k sieht genauso aus wie die Zeichenkette, die mit j beginnt, also erhöhen wir j um p und setzen k wieder auf 1 und vergleichen die beiden Zeichenketten erneut.

Zweitens: Ja, ich glaube, Sie haben recht, es sollte i zurückgeben. Ich habe die Bedeutung von "Minimum Cyclic Shift" missverstanden.

Answer 2

Es könnte sich um den gleichen Algorithmus handeln, dessen Erklärung Sie hier finden können ici :

int ComputeMaxSufPos(string w)
{
    int i = 0, n = w.Length;
    for (int j = 1; j < n; ++j)
    {
        int c, k = 0;
        while ((c = w[(i + k) % n].CompareTo(w[(j + k) % n])) == 0 && k != n)
        { k++; }
        j += c > 0 ? k / (j - i) * (j - i) : k;
        i = c > 0 ? j : i;
    }
    return i;
}