Bitte Baidu für einige grundlegende Konzepte von Suffix -Arrays. Einfach ausgedrückt, das Suffix -Array ist eine Sammlung aller Suffixgrößen einer Zeichenfolge. Anschließend können wir verschiedene Bedürfnisse erfüllen, die auf einigen Eigenschaften des Suffix -Arrays basieren.
public class MySuffixArrayTest { public char[] suffix;//original string public int n;//string length public int[] rank;// Ranking of Suffix[i] in all suffix public int[] sa;// Suffix[SA[1]] < Suffix[SA[2]] … < Suffix[SA[Len]], that is, the suffix with ranking i is Suffix[SA[i]] // (It is an inverse operation with Rang) public int [] Höhe; // zeigt Suffix [sa [i]] und Suffix [sa [i - 1]] an, dh das längste öffentliche Präfix von zwei benachbarten Suffixen, öffentlich int [] h; // ist gleich groß [i]. y; // zweites Schlüsselwort Rang Array public int [] x; // Rang Auxiliary Array}}Die folgenden Erklärungen nehmen die Zeichenfolge "Aabaaaab" als Beispiel. Zeigen wir zuerst die Ergebnisse. Bitte beachten Sie dieses Ergebnis für das Verständnis und die Analyse (ich habe das Bild eines anderen von diesem Ergebnis kopiert. Bitte standardmäßig einreichen 1, da mein Array mit dem Index 0 beginnt.
Suffix: Das ursprüngliche String -Array geht davon aus
N: Stringlänge hier ist 8 ist 8
Rang: Das Ranking-Array des Suffix-Arrays entspricht der Rangliste, die dem I-Th-Suffix entspricht. Zum Beispiel bezieht sich Rang [0] auf die Rangliste des Suffix "Aabaaaab" Rang [1] auf die Rangliste des Suffix "Abaaaab".
SA: Dies ist ein Array, das dem Rang -Array umgekehrt ist. Speichert der X-Knoten das Suffix? Oder um ein Beispiel zu geben, um zu veranschaulichen, dass sich SA [0] auf das erstrangige Suffix-Array bezieht, dh 3.. Das entsprechende Rang [3] des Arrays beträgt 0. Bitte verstehen Sie die Formel SA [Rang [i]] = i. Wenn Sie die Beziehung zwischen SA und Rang verstehen, sollten Sie sie auch verstehen.
Höhe: Höhe [i] ist die Länge des größten häufigen Präfixes des SA [i] -Suffixarrays, und das SA-Suffix-Array-Höhe [1] bezieht sich auf die zweiten und ersten größten häufigen Präfixe SA [1] und SA [0], dh die größten gemeinsamen Präfixe von "aaab" und "aaaab" sehen die Höhe [1].
H: H [i] bezieht sich auf das I-Th-Suffix und das größte öffentliche Präfix des vorherigen H [0]. Sie können vorerst nicht verstehen und weiter lesen.
WS: Nichts zu sagen: Zählen
Y: Die zweite Schlüsselwort -Sortierung ist das SA -Array mit dem zweiten Schlüsselwort, das dem zweiten Schlüsselwort äquivalent sortiert ist
X: Sie können es als Backup von Rank Array verstehen. Es verwendet zunächst Rangarray -Sicherung und zeichnet dann das Rang -Array nach jeder Schleife auf
Schauen wir uns zunächst den Code für SA -Array an. Ich werde die Funktion des Codes eins nacheinander erläutern und den Gesamtcode an die folgenden anschließen
Rank = New int [n]; sa = new int [n]; WS = New int [255]; y = neu int [n]; x = new int [n]; // Die ursprüngliche Zeichenfolge schleifen, um den int -Wert in das Rang -Array für (int i = 0; i <n; i ++) {Rank [i] = (int) Suffix [i] umzuwandeln; }Die Funktion des obigen Codes besteht darin, das Array zu initialisieren und die erste Zählung und Sortierung durchzuführen. Die erste Schleife besteht darin, dem Rangarray den Anfangswert zuzuweisen. Nach der Ausführung beträgt der entsprechende Wert des Rangarrays {97, 97, 98, 97, 97, 97, 97, 98}. Sie sollten sehen, dass der Anfangswert des Rangarrays der ASCII -Code ist, der dem Buchstaben entspricht.
Die nächsten drei Zyklen sind die erste Zählsortierung. Wenn Sie das Zählensortieren nicht verstehen, bitte Baidu. Lassen Sie mich über den Prozess dieser drei Zyklen sprechen
für (int i = 0; i <n; i ++) {ws [Rang [i]] ++; x [i] = Rank [i]; } für (int i = 1; i <wslength; i ++) {ws [i]+= ws [i - 1]; }Diese beiden Schleifen zählen alle Vorkommenswerte und sichern das Rangarray auf das X -Array. Nach der ersten Schleife ist WS [97] = 6, WS [98] = 2 und nach der zweiten Schleife WS [97] = 6, WS [98] = 8
für (int i = n-1; i> = 0; i--) {sa [-ws [Rang [i]]] = i; }Der obige Absatz ist der spezifische Code für das Zählen und Sortieren, um das SA -Array zu finden. Jeder muss missverstanden haben, wenn er es zum ersten Mal gelesen hat. Warum fanden sie die SA? Ich war auch zum ersten Mal verwirrt, aber bitte sei geduldig und verstehe diesen Code sorgfältig. Erinnern Sie sich noch an die oben erwähnte Formel Sa [Rang [i]] = Ich zum Beispiel für das Suffix "B", wir fragen seine SA, dh SA [Rang [7]] = SA [98] = 7. Offensichtlich existiert SA [98] nicht, aber wir haben aufgezeichnet, wie oft 98 im WS -Array erscheint, sodass WS [98] das entsprechende Rang von "B" sein sollte. Bitte vergessen Sie nicht, 1 zu subtrahieren, um SA [-WS [Rang [i]]] = i. Was Sie von hinten nach vorne durchqueren müssen, müssen Sie es hier sorgfältig verstehen. Andernfalls werden Sie auf jeden Fall vollständig geblendet, wenn Sie es nach dem zweiten Keyword sortieren. Wie sortieren Sie es, wenn es zwei Rangwerte gibt, die gleich sind? Es muss zuerst vor dem SA -Array erscheinen. Wenn Sie über diese Schleife und die Änderungen im WS -Array -Wert nachdenken, werden Sie verstehen, dass die Reihenfolge der für die für die Schleife tatsächlich die Reihenfolge der Anordnung darstellt, wenn der Rangwert gleich ist. Die Durchführung von hinten nach vorne bedeutet, dass das Suffix -Ranking ebenfalls niedriger ist, wenn der Rangwert gleich ist.
Das obige ist nur die erste Zählsortierung, die nur dem Vergleich des ersten Buchstabens jedes Suffix -Arrays entspricht, um eine SA zu finden. Das entsprechende Ergebnis ist wie in der folgenden Abbildung dargestellt.
// Schleifenkombinationssortierung für (int j = 1, p = 0; j <= n; j = j << 1) {// Wenn Sie es füllen müssen, fügen Sie das Sortierarray zuerst hinzu yp = 0; für (int i = n - j; i <n; i ++) {y [p ++] = i; } // Das zweite Schlüsselwort nach dem ersten Schlüsselwort SA für (int i = 0; i <n; i ++) {if (sa [i]> = j) {y [p ++] = sa [i] - j; }} // Sortieren Sie die beiden Schlüsselwörter für (int i = 0; i <wsgth; i ++) {WS [i] = 0; } für (int i: x) {ws [i] ++; } für (int i: x) {ws [i] ++; } für (int i = 1; i <wslength; i ++) {ws [i]+= ws [i - 1]; } für (int i = n-1; i> = 0; i--) {sa [-ws [x [y [i]]] = y [i]; y [i] = 0; } // Berechnen Sie das Rangarray aus Sa int xb [] = new int [n]; // x Array -Sicherung für (int i = 0; i <n; i ++) {xb [i] = x [i]; } int nummer = 1; x [sa [0]] = 1; für (int i = 1; i <n; i ++) {if (xb [sa [i]]! = xb [sa [i - 1]]) {x [sa [i]] = ++ nummer; } else if (sa [i] + j> = n && sa [i - 1] + j> = n) {x [sa [i]] = nummer; } else if (sa [i] + j <n && sa [i - 1] + j> = n) {x [sa [i]] = ++ nummer; } else if (xb [sa [i] + j]! = xb [sa [i - 1] + j]) {x [sa [i]] = ++ nummer; } else {x [sa [i]] = nummer; } if (number> = n) brechen; }}Dies ist das schwierigste Code, um das SA -Array zu verstehen. Zunächst müssen Sie die Idee des Multiplikationsalgorithmus verstehen. Kennen wir nach dem ersten Zählbeschluss bereits die Sortierung des ersten ersten Briefes aller Suffix -Arrays? Da wir wissen, dass die Sortierung des ersten Anfangsbuchstabens der Reihenfolge seines zweiten Buchstabens entspricht (beachten Sie den Unterschied zwischen Sortierung und Ordnung. Die Sortierung ist, dass wir wissen, in welcher er festgelegt ist. Die Reihenfolge ist, dass wir nur die Reihenfolge kennen, in der er erscheint, aber wir nicht wissen, in welchem er ausdrücklich eingestuft wird). Dies ist natürlich, da sie ursprünglich aus einer Saite stammen und für jedes Suffix auch als Suffix für sein vorheriges Suffix verwendet werden kann. Apropos zum Beispiel für "Baaaab" Die Reihenfolge seines ersten Buchstabens entspricht der zweiten Schlüsselwortreihenfolge von "Abaaaab". Mit der Reihenfolge des ersten Schlüsselworts und der Art des zweiten Schlüsselworts finden wir die kombinierte Art der beiden Schlüsselwörter. Nach dem Ergebnis der Kombination können wir die vorherige Idee trotzdem verwenden. Nach der ersten Kombination "Baaaab" sortieren wir die Reihenfolge der ersten beiden Buchstaben "BA", damit er auch die Reihenfolge des zweiten Schlüsselworts von "Aabaaaab" verwenden kann. Die Logik der gesamten Sorte wird unten verwiesen
Dann werden wir den Code in Segmenten analysieren
für (int i = n - j; i <n; i ++) {y [p ++] = i; } // Wählen Sie das zweite Schlüsselwort gemäß dem ersten Schlüsselwort SA für (int i = 0; i <n; i ++) {if (sa [i]> = j) {y [p ++] = sa [i] - j; }}Der obige Code besteht darin, die SA zu finden, dh das y -Array des zweiten Schlüsselworts, wobei der Anfangswert von P 0 ist, und die erste Schleife besteht darin, das Suffix zu bewerten, das in der Vorderseite des Arrays gefüllt werden muss.
Sie müssen die Logik der zweiten Schleife in Kombination mit dem vorherigen Logikdiagramm verstehen. Wir durchqueren das Sortierergebnis des ersten Schlüsselworts SA. If (sa [i]> = j) bestimmt, ob das Suffix als zweites Schlüsselwort für andere Suffixe verwendet werden kann. Wenn Sie die erste Schleife J = 1 als Beispiel nehmen, wenn SA [i] = 0 das Suffix -Array "aabaaaab" darstellt, kann es offensichtlich nicht als zweites Schlüsselwort für andere Suffixe verwendet werden. Für das zweite Schlüsselwort, das als andere Suffixe verwendet werden kann, ist die Reihenfolge seiner SA das entsprechende zweite Schlüsselwort. SA [i] - J findet das Suffix seines als zweiten Schlüsselworts und stellt es in das Y -Array und P ++. Sie müssen hier langsam verstehen.
// Die Art von zwei Schlüsselwörtern für (int i = 0; i <wsgth; i ++) {ws [i] = 0 zusammenführen; } für (int i: x) {ws [i] ++; } für (int i = 1; i <wslength; i ++) {ws [i]+= ws [i - 1]; } für (int i = n-1; i> = 0; i--) {sa [-ws [x [y [i]]] = y [i]; y [i] = 0; }Das obige soll die Kombinationssortierung basierend auf der ersten Keyword -Sortierung SA und der zweiten Keyword -Sortierung y finden. Dieser Code ist ziemlich dunkel. Wir können den Code zuerst nicht verstehen, sondern eine Idee verstehen. Für die Sortierung von zwei Schlüsselwörtern ähneln die tatsächlichen Regeln der Sortierung von zwei Zahlen. Zum Beispiel sind 11 und 12 die Größe vergleichen, 10 Bit sind das erste Schlüsselwort und einzelne Bits sind das zweite Schlüsselwort. Nach dem Vergleich von 10 Bit finden wir 11 = 12 und vergleichen dann die einzelnen Bits, wir wissen, dass 11 <12. Wenn die 10 Bit gleich sind, ist die Reihenfolge der einzelnen Bits die Größenreihenfolge. Ich sagte, das erste Mal, dass ich die Sortierung darüber zähle, dass die Reihenfolge der Zählsortierung für Schleife tatsächlich die Reihenfolge der Anordnung darstellt, wenn die Rangwerte gleich sind. Wie finden wir die Bestellung, nachdem die beiden Schlüsselwörter in einer Zählung zusammengeführt wurden? Lassen Sie mich Ihnen mein Verständnis sagen. Eine Zählsart enthält tatsächlich zwei Sorten, eine ist die Art von numerischen Werten und die andere ist die Art von Auftrittsreihenfolge. Die Regeln entsprechen dem vorherigen Beispiel für den Vergleich von 11 und 12. Die Art der numerischen Werte beträgt 10 Bit, und die Art der Auftrittsreihenfolge beträgt ein Bit. Zu diesem Zeitpunkt haben wir eine Idee. Die Sortierung von Werten wird nach dem ersten Schlüsselwort sortiert, und die Sortierung von Vorkommen wird nach dem zweiten Schlüsselwort sortiert, sodass wir gleichzeitig zählen und sortieren können, um die Sortierung zu finden, nachdem die beiden Schlüsselwörter kombiniert wurden. Der obige Code ist die Implementierung dieser Idee. Das X -Array ist das Rangarray des ersten Schlüsselworts, und wir zählen es.
für (int i = n-1; i> = 0; i--) {sa [-ws [x [y [i]]]] = y [i]; y [i] = 0; }Diese Schleife ist die Implementierung aller oben genannten Ideen. Wir durchqueren das zweite Schlüsselwort -Array y von hinten. Für y [i] berechnen wir das Zählranking seines ersten Schlüsselworts. Dieses Zählranking ist das Ranking von y [i], und die endgültige Zählung wird um 1 reduziert. Die zusammengeführte Keyword -Sortierung wurde erfolgreich gefunden.
Ich glaube, wenn Sie alle oben genannten Codes verstehen, werden Sie definitiv erstaunt sein. Ich war auch aufgeregt, als ich immer wieder über diesen Code nachdachte, und ich war einfach überzeugt. Dies ist der Charme von Algorithmen.
Mit dem SA -Array finden wir das Rangarray. Das ist nicht schwierig, also werden wir es nicht erklären. Alle Codes zum Finden von SA sind unten angehängt.
public static void main (String [] args) {String str = "aabaaaab"; MySuffixArrayTest ArrayTest = new MySuffixArrayTest (Str.ToString ()); ArrayTest.inita (); // SA Array} public void initsa () {rank = new int [n]; sa = new int [n]; WS = New int [255]; y = neu int [n]; x = new int [n]; // Die ursprüngliche Zeichenfolge schleifen, um den int -Wert in das Rang -Array für (int i = 0; i <n; i ++) {Rank [i] = (int) Suffix [i] umzuwandeln; } // Erste Zählsart für (int i = 0; i <n; i ++) {WS [Rang [i]] ++; x [i] = Rank [i]; } für (int i = 1; i <wslength; i ++) {ws [i]+= ws [i - 1]; } für (int i = n-1; i> = 0; i--) {sa [-ws [Rang [i]]] = i; } // Schleifenkombinationssortierung für (int j = 1, p = 0; j <= n; j = j << 1) {// Wenn Sie füllen müssen, fügen Sie das sortierte Array zuerst yp = 0 hinzu; für (int i = n - j; i <n; i ++) {y [p ++] = i; } // Das zweite Schlüsselwort nach dem ersten Schlüsselwort SA für (int i = 0; i <n; i ++) {if (sa [i]> = j) {y [p ++] = sa [i] - j; }} // Sortieren Sie die beiden Schlüsselwörter für (int i = 0; i <wsgth; i ++) {WS [i] = 0; } für (int i: x) {ws [i] ++; } für (int i = 1; i <wslength; i ++) {ws [i]+= ws [i - 1]; } für (int i = n-1; i> = 0; i--) {sa [-ws [x [y [i]]] = y [i]; y [i] = 0; } // Berechnen Sie das Rangarray basierend auf SA int xb [] = new int [n]; // x Array -Sicherung für (int i = 0; i <n; i ++) {xb [i] = x [i]; } int nummer = 1; x [sa [0]] = 1; für (int i = 1; i <n; i ++) {if (xb [sa [i]]! = xb [sa [i - 1]]) {x [sa [i]] = ++ nummer; } else if (sa [i] + j> = n && sa [i - 1] + j> = n) {x [sa [i]] = nummer; } else if (sa [i] + j <n && sa [i - 1] + j> = n) {x [sa [i]] = ++ nummer; } else if (xb [sa [i] + j]! = xb [sa [i - 1] + j]) {x [sa [i]] = ++ nummer; } else {x [sa [i]] = nummer; } if (number> = n) brechen; }}}}Zusammenfassen
Das obige ist der Beispielcode für SAC -Arrays von Java -Suffix -Arrays, die Ihnen vorgestellt wurden. Ich hoffe, es wird Ihnen hilfreich sein. Wenn Sie Fragen haben, hinterlassen Sie mir bitte eine Nachricht und der Editor wird Ihnen rechtzeitig antworten. Vielen Dank für Ihre Unterstützung auf der Wulin.com -Website!