Veuillez Baidu pour certains concepts de base de tableaux de suffixes. Autrement dit, le tableau de suffixe est une collection de toutes les tailles de suffixe d'une chaîne. Ensuite, nous pouvons répondre à divers besoins en fonction de certaines propriétés du tableau du suffixe.
classe publique MySuffixArraytest {public char [] suffixe; // chaîne originale public int n; // string longueur public int [] rang; // classement du suffixe [i] dans tout suffixe public int [] sa; // suffixe [sa [1]] Rang) public int [] hauteur; // indique le suffixe [sa [i]] et le suffixe [sa [i - 1]], c'est-à-dire le plus long préfixe public de deux suffixes adjacents, le public int [] h; // est égal à la hauteur [Rank [i]], c'est-à-dire le plus long préfixe public du suffixe [i] et le suffixe de son précédent int [] ws; y; // deuxième mot-clé Array Public int [] x; // Classer le tableau auxiliaire}Les explications suivantes prennent la chaîne "Aabaaaab" comme exemple. Montons d'abord les résultats. Veuillez vous référer à ce résultat pour comprendre et analyser (j'ai copié l'image de quelqu'un d'autre de ce résultat. Veuillez indiquer 1 par défaut, car mon tableau commence par l'indice 0)
suffixe: le tableau de chaîne d'origine suppose que la chaîne d'origine est "Aabaaaab", alors la valeur correspondante de ce tableau doit être {'a', 'a', 'b', 'a', 'a', 'a', 'b'}
n: longueur de chaîne ici n est 8
Rang: Le tableau de classement du tableau du suffixe est équivalent au classement correspondant au I-Thu suffixe. Par exemple, Rank [0] fait référence au classement du suffixe "Aabaaaab" Rank [1] fait référence au classement du suffixe "Abaaaab"
SA: Il s'agit d'un tableau qui est inverse au tableau de rang. Le nœud X stockait-il le suffixe? Ou pour donner un exemple pour illustrer que SA [0] fait référence au tableau de suffixe de premier rang, c'est-à-dire, 3. Si vous comprenez la relation entre SA et Rank, vous devez également la comprendre.
Hauteur: la hauteur [i] est la longueur du plus grand préfixe commun du réseau de suffixes sa [i] et la hauteur du tableau de suffixe SA [i-1] se réfère aux deuxième et premiers préfixes communs SA [1] et SA [0] qui est la plus grande hauteur [1] = 3 à un regard "AAAB" et "aaaab".
H: H [i] fait référence au suffixe du i-th et le plus grand préfixe public de la précédente H [0] se réfère au premier tableau de suffixe, à savoir "AABAAAAB" et le plus grand préfixe public de la hauteur précédente [3] = 3 C'est un peu difficile à comprendre. Vous ne pouvez pas comprendre pour le moment et continuer à lire.
WS: Rien à dire, comptez le tri du tableau auxiliaire
Y: Le deuxième tri des mots clés est le tableau SA avec le deuxième mot clé trié équivalent au deuxième mot clé
X: Vous pouvez le comprendre comme une sauvegarde du tableau de rang. Il utilise initialement la sauvegarde du tableau de rang, puis enregistre le tableau de rang après chaque boucle
Tout d'abord, examinons le code du code SA. J'expliquerai la fonction du code un par un et joignez le code total à ce qui suit
rang = new int [n]; sa = new int [n]; ws = new int [255]; y = new int [n]; x = new int [n]; // Loucle la chaîne d'origine pour convertir la valeur int en tableau de rang pour (int i = 0; i <n; i ++) {rank [i] = (int) suffixe [i]; }La fonction du code ci-dessus consiste à initialiser le tableau et à effectuer le premier comptage et le tri. La première boucle consiste à attribuer la valeur initiale au tableau de rang. Après l'exécution, la valeur correspondante du tableau de rang est {97, 97, 98, 97, 97, 97, 97, 98}. Vous devriez voir que la valeur initiale du tableau de rang est le code ASCII correspondant à la lettre.
Les trois cycles suivants sont le premier tri de comptage. Si vous ne comprenez pas le comptage du tri, veuillez Baidu. Permettez-moi de parler du processus de ces trois cycles
pour (int i = 0; i <n; i ++) {ws [rang [i]] ++; x [i] = rang [i]; } pour (int i = 1; i <ws.length; i ++) {ws [i] + = ws [i - 1]; }Ce que font ces deux boucles, c'est compter toutes les valeurs d'occurrence et sauvegarder le tableau de rang vers le tableau X. Une fois la première boucle exécutée, ws [97] = 6, ws [98] = 2, et après l'exécution de la deuxième boucle, ws [97] = 6, ws [98] = 8
for (int i = n - 1; i> = 0; i--) {sa [- ws [rang [i]]] = i; }Le paragraphe ci-dessus est le code spécifique pour compter et tri pour trouver le tableau SA. Tout le monde doit avoir mal compris la première fois qu'ils l'ont lu. Pourquoi ont-ils trouvé le SA? J'étais également confus pour la première fois, mais soyez patient et comprenez attentivement ce code. Vous souvenez-vous encore de la formule mentionnée ci-dessus sa [rang [i]] = i par exemple, pour le suffixe "b", nous demandons à son sa, c'est-à-dire sa [rang [7]] = SA [98] = 7. De toute évidence, SA [98] n'existe pas, mais nous avons enregistré le nombre de fois que 98 apparaît dans le tableau WS, donc WS [98] devrait être le classement correspondant de "B". N'oubliez pas de soustraire 1 pour devenir SA [- ws [rang [i]]] = i. Quant à la raison pour laquelle vous devez traverser de l'arrière en avant, vous devez le comprendre attentivement ici, sinon vous serez certainement complètement aveuglé par la façon dont vous le triez en fonction du deuxième mot-clé. Comment le triez-vous s'il y a deux valeurs de rang qui sont les mêmes? Il doit apparaître d'abord devant le tableau SA. Si vous pensez à cette boucle et aux modifications de la valeur du tableau WS, vous comprendrez que l'ordre de la boucle FOR représente en fait l'ordre d'arrangement lorsque la valeur de rang est la même. La traversée de l'arrière en avant signifie que le classement du suffixe est également inférieur lorsque la valeur de rang est la même.
Ce qui précède n'est que le premier tri de comptage, ce qui équivaut à ne comparer que la première lettre de chaque tableau de suffixe pour trouver une SA. Le résultat correspondant est comme indiqué dans la figure ci-dessous.
// Loop Combination Sort pour (int j = 1, p = 0; j <= n; j = j << 1) {// Si vous avez besoin de le remplir, ajoutez le tableau de tri First YP = 0; for (int i = n - j; i <n; i ++) {y [p ++] = i; } // Rangez le deuxième mot clé en fonction du premier mot-clé sa pour (int i = 0; i <n; i ++) {if (sa [i]> = j) {y [p ++] = sa [i] - j; }} // tri les deux mots clés pour (int i = 0; i <ws.length; i ++) {ws [i] = 0; } pour (int i: x) {ws [i] ++; } pour (int i: x) {ws [i] ++; } pour (int i = 1; i <ws.length; i ++) {ws [i] + = ws [i - 1]; } pour (int i = n - 1; i> = 0; i--) {sa [- ws [x [y [i]]] = y [i]; y [i] = 0; } // Calculez le tableau de rang à partir de sa int xb [] = new int [n]; // x sauvegarde du tableau pour (int i = 0; i <n; i ++) {xb [i] = x [i]; } int numéro = 1; x [sa [0]] = 1; for (int i = 1; i <n; i ++) {if (xb [sa [i]]! = xb [sa [i - 1]]) {x [sa [i]] = ++ nombre; } else if (sa [i] + j> = n && sa [i - 1] + j> = n) {x [sa [i]] = nombre; } else if (sa [i] + j <n && sa [i - 1] + j> = n) {x [sa [i]] = ++ numéro; } else if (xb [sa [i] + j]! = xb [sa [i - 1] + j]) {x [sa [i]] = ++ nombre; } else {x [sa [i]] = nombre; } if (nombre> = n) Break; }}C'est le morceau de code le plus difficile à comprendre lors de la recherche du tableau SA. Tout d'abord, vous devez comprendre l'idée de l'algorithme de multiplication. Après le premier ordre de comptage, connaissons-nous déjà le tri de la première lettre initiale de tous les tableaux de suffixes? Puisque nous savons que le tri de la première lettre initiale équivaut à l'ordre de sa deuxième lettre (notez la différence entre le tri et l'ordre. Le tri est que nous savons dans lequel il est fixé. L'ordre est que nous ne connaissons que l'ordre dans lequel il apparaît, mais nous ne savons pas lequel il est spécifiquement classé). C'est bien sûr, car ils sont originaires d'une chaîne, et pour chaque suffixe, il peut également être utilisé comme suffixe pour son suffixe précédent. En parlant, par exemple, pour "baaaab", l'ordre de sa première lettre correspond au deuxième ordre clé de "Abaaaab". Avec l'ordre du premier mot-clé et le type du deuxième mot-clé, nous pouvons trouver le type combiné des deux mots clés. Selon le résultat du tri de combinaison, nous pouvons toujours utiliser l'idée précédente. Après la première combinaison de "baaaab", nous trierons l'ordre des deux premières lettres "BA", afin qu'il puisse également utiliser l'ordre du deuxième mot-clé de "Aabaaaab". La logique de tout le type est référencée ci-dessous
Ensuite, nous analyserons le code en segments
for (int i = n - j; i <n; i ++) {y [p ++] = i; } // Sélectionnez le deuxième mot clé en fonction du premier mot-clé sa pour (int i = 0; i <n; i ++) {if (sa [i]> = j) {y [p ++] = sa [i] - j; }}Le code ci-dessus est de trouver le SA, c'est-à-dire le tableau Y du deuxième mot-clé, la valeur initiale de P étant 0, et la première boucle consiste à classer le suffixe qui doit être rempli à l'avant du tableau.
Vous devez comprendre la logique de la deuxième boucle en combinaison avec le diagramme logique précédent. Nous traversons le résultat de tri du premier mot-clé SA. If (sa [i]> = j) détermine si le suffixe peut être utilisé comme deuxième mot-clé pour d'autres suffixes. Prenant la première boucle j = 1 comme exemple, lorsque sa [i] = 0 représente le tableau de suffixe "aabaaaab", il ne peut évidemment pas être utilisé comme deuxième mot-clé pour d'autres suffixes. Pour le deuxième mot clé qui peut être utilisé comme d'autres suffixes, l'ordre de son SA est le deuxième mot clé correspondant. Sa [i] - J trouve le suffixe de son deuxième mot clé et le met dans le tableau Y et P ++. Vous devez comprendre lentement ici.
// fusionner le type de deux mots clés pour (int i = 0; i <ws.length; i ++) {ws [i] = 0; } pour (int i: x) {ws [i] ++; } pour (int i = 1; i <ws.length; i ++) {ws [i] + = ws [i - 1]; } pour (int i = n - 1; i> = 0; i--) {sa [- ws [x [y [i]]]] = y [i]; y [i] = 0; }Ce qui précède consiste à trouver le tri combiné basé sur le premier tri de mots clés SA et le deuxième tri des mots clés Y. Ce code est assez obscur. Nous pouvons d'abord ne pas comprendre le code, mais comprendre une idée. Pour le tri de deux mots clés, les règles réelles sont similaires au tri de deux nombres. Par exemple, 11 et 12 comparent la taille, 10 bits sont le premier mot-clé et les bits uniques sont le deuxième mot-clé. Après avoir comparé 10 bits, nous trouvons 11 = 12, puis comparons les bits simples, nous savons que 11 <12. Si les 10 bits sont les mêmes, l'ordre des bits uniques est l'ordre de taille. J'ai dit que la première fois que je compte le tri ci-dessus que l'ordre du tri de comptage pour la boucle représente en fait l'ordre de disposition lorsque les valeurs de rang sont les mêmes. Alors, comment pouvons-nous trouver la commande après que les deux mots clés sont fusionnés en un seul compte? Laissez-moi vous dire ma compréhension. Un rythme de nombre contient en fait deux types, l'un est le type de valeurs numériques, et l'autre est le type d'ordre d'occurrence. Les règles sont équivalentes à l'exemple précédent de comparaison de 11 et 12. Le type de valeurs numériques est de 10 bits, et le type d'ordre d'occurrence est un bits. À ce stade, nous avons une idée. Le tri des valeurs est trié par le premier mot-clé, et le tri des occurrences est trié par le deuxième mot-clé, afin que nous puissions compter et trier à la fois pour trouver le tri après la combinaison des deux mots clés. Le code ci-dessus est l'implémentation de cette idée. Le tableau X est le tableau de rang du premier mot-clé, et nous le comptons.
for (int i = n - 1; i> = 0; i--) {sa [- ws [x [y [i]]]] = y [i]; y [i] = 0; }Cette boucle est la mise en œuvre de toutes les idées ci-dessus. Nous traversons le deuxième tableau des mots clés Y de l'arrière. Pour y [i], nous calculons le classement de comptage de son premier mot-clé. Ce classement de comptage est le classement de y [i], et le décompte final est réduit de 1. Le type de mots clés fusionné a été trouvé avec succès.
Je crois que si vous comprenez tous les codes ci-dessus, vous serez certainement étonné. J'étais également excité quand j'ai pensé à ce code encore et encore, et j'étais tout simplement convaincu. Ceci est le charme des algorithmes.
Avec le tableau SA, nous pouvons trouver le tableau de rang. Ce n'est pas difficile, donc nous ne l'expliquerons pas. Tous les codes de recherche de SA sont attachés ci-dessous.
public static void main (String [] args) {String str = "aaBaaaaab"; MySuffixArrayTest arraytest = new mySuffixArrayTest (str.toString ()); arraytest.initsa (); // trouver SA array} public void initsa () {rank = new int [n]; sa = new int [n]; ws = new int [255]; y = new int [n]; x = new int [n]; // Loucle la chaîne d'origine pour convertir la valeur int en tableau de rang pour (int i = 0; i <n; i ++) {rank [i] = (int) suffixe [i]; } // premier compte pour (int i = 0; i <n; i ++) {ws [rang [i]] ++; x [i] = rang [i]; } pour (int i = 1; i <ws.length; i ++) {ws [i] + = ws [i - 1]; } pour (int i = n - 1; i> = 0; i--) {sa [- ws [rang [i]]] = i; } // Loop Combination Sort for (int j = 1, p = 0; j <= n; j = j << 1) {// Si vous devez remplir, ajoutez le tableau trié d'abord yp = 0; for (int i = n - j; i <n; i ++) {y [p ++] = i; } // Rangez le deuxième mot clé en fonction du premier mot-clé sa pour (int i = 0; i <n; i ++) {if (sa [i]> = j) {y [p ++] = sa [i] - j; }} // tri les deux mots clés pour (int i = 0; i <ws.length; i ++) {ws [i] = 0; } pour (int i: x) {ws [i] ++; } pour (int i = 1; i <ws.length; i ++) {ws [i] + = ws [i - 1]; } pour (int i = n - 1; i> = 0; i--) {sa [- ws [x [y [i]]] = y [i]; y [i] = 0; } // Calculez le tableau de rang basé sur SA int xb [] = new int [n]; // x sauvegarde du tableau pour (int i = 0; i <n; i ++) {xb [i] = x [i]; } int numéro = 1; x [sa [0]] = 1; for (int i = 1; i <n; i ++) {if (xb [sa [i]]! = xb [sa [i - 1]]) {x [sa [i]] = ++ nombre; } else if (sa [i] + j> = n && sa [i - 1] + j> = n) {x [sa [i]] = nombre; } else if (sa [i] + j <n && sa [i - 1] + j> = n) {x [sa [i]] = ++ numéro; } else if (xb [sa [i] + j]! = xb [sa [i - 1] + j]) {x [sa [i]] = ++ nombre; } else {x [sa [i]] = nombre; } if (nombre> = n) Break; }}}}Résumer
Ce qui précède est l'exemple de code pour les tableaux de sac de tableaux de suffixes java qui vous sont présentés. J'espère que cela vous sera utile. Si vous avez des questions, veuillez me laisser un message et l'éditeur vous répondra à temps. Merci beaucoup pour votre soutien au site Web Wulin.com!