Por favor, Baidu para alguns conceitos básicos de matrizes de sufixo. Simplificando, a matriz do sufixo é uma coleção de todos os tamanhos de sufixo de uma corda. Em seguida, podemos atingir várias necessidades com base em algumas propriedades da matriz de sufixo.
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 Rank) int [] altura; // indica sufixo [SA [i]] e sufixo [SA [i - 1]], ou seja, o prefixo público mais longo de dois sufixos adjacentes, o público de Int [] h; // é igual à altura [rank [i]], que é o mais longo prefixo público do sufixo [i] e o sfix de seu sfix anterior y; // Segunda palavra -chave Rank ARAY Public int [] x; // classificar array auxiliar}As seguintes explicações tomam a string "aabaaaab" como exemplo. Vamos primeiro mostrar os resultados. Consulte este resultado para entender e análise (copiei a imagem de outra pessoa desse resultado. Por favor, subscrito 1 por padrão, porque minha matriz começa com o subscrito 0)
Sufixo: A matriz de string original assume que a string original é "aabaaaab", então o valor correspondente dessa matriz deve ser {'a', 'a', 'b', 'a', 'a', 'a', 'b'}
n: comprimento da corda aqui n é 8
Classificação: A matriz de classificação da matriz do sufixo é equivalente ao ranking correspondente ao sufixo i-Th. Por exemplo, a classificação [0] refere -se ao ranking do sufixo "AABAAAAB".
SA: Esta é uma matriz inversa à matriz de classificação. O nó X armazena o sufixo? Ou para dar um exemplo para ilustrar que SA [0] se refere à matriz de sufixo do primeiro classificada, ou seja, 3. Ou seja, a classificação correspondente [3] da matriz é 0. Certifique-se de entender a fórmula SA [Rank [i]] = i. Se você entender o relacionamento entre SA e Rank, também deve entender.
Altura: altura [i] é a duração do maior prefixo comum da matriz de sufixo SA [i] e a altura do array do sufixo SA [I-1] [1] refere-se ao segundo e dos primeiros maiores prefixos comuns SA [1] e SA [0], que são os maiores prefixos comuns de "aaab aaab e" aaaab ", veja naturalmente [1]
H: H [i] refere-se ao sufixo i-Th e ao maior prefixo público do anterior H [0] refere-se à primeira matriz de sufixo, a saber, "Aabaaaab" e o maior prefixo público do anterior, a saber, aBS, ou seja, a altura [0]] = altura [3] = 3 é um pouco difícil. Você não consegue entender por enquanto e continuar lendo.
WS: Nada a dizer, Conte classificando a matriz auxiliar
Y: A segunda palavra -chave é a matriz SA com a segunda palavra -chave classificada equivalente à segunda palavra -chave
X: Você pode entendê -lo como um backup da matriz de classificação. Inicialmente, ele usa o backup da matriz de classificação e depois registra a matriz de classificação após cada loop
Primeiro, vejamos o código da matriz SA. Vou explicar a função do código um por um e anexar o código total ao seguinte
rank = new int [n]; SA = novo int [n]; ws = novo int [255]; y = new int [n]; x = novo int [n]; // loop a string original para converter o valor int na matriz de classificação para (int i = 0; i <n; i ++) {rank [i] = (int) sufixo [i]; }A função do código acima é inicializar a matriz e executar a primeira contagem e classificação. O primeiro loop é atribuir o valor inicial à matriz de classificação. Após a execução, o valor correspondente da matriz de classificação é {97, 97, 98, 97, 97, 97, 97, 98}. Você deve ver que o valor inicial da matriz de classificação é o código ASCII correspondente à letra.
Os próximos três ciclos são a primeira classificação de contagem. Se você não entende a contagem de classificação, por favor, Baidu. Deixe -me falar sobre o processo desses três ciclos
for (int i = 0; i <n; i ++) {ws [classificação [i]] ++; x [i] = classificação [i]; } para (int i = 1; i <ws.length; i ++) {ws [i]+= ws [i - 1]; }O que esses dois loops fazem é contar todos os valores de ocorrência e fazer backup da matriz de classificação para a matriz X. Após a execução do primeiro loop, WS [97] = 6, WS [98] = 2, e após o segundo loop ser executado, WS [97] = 6, WS [98] = 8
for (int i = n-1; i> = 0; i-) {sa [-ws [rank [i]]] = i; }O parágrafo acima é o código específico para contar e classificar para encontrar a matriz SA. Todos devem ter entendido mal a primeira vez que lêem. Por que eles encontraram o SA? Também fiquei confuso pela primeira vez, mas seja paciente e entenda esse código com cuidado. Você ainda se lembra da fórmula mencionada acima SA [Rank [i]] = I, por exemplo, para o sufixo "B", perguntamos ao seu SA, isto é, SA [Rank [7]] = SA [98] = 7. Obviamente, o SA [98] não existe, mas registramos o número de vezes que 98 aparece na matriz WS, então o WS [98] deve ser o ranking correspondente de "B". Por favor, não se esqueça de subtrair 1 para se tornar SA [-WS [rank [i]]] = i. Quanto ao motivo pelo qual você precisa atravessar de volta para a frente, você precisa entendê -lo com cuidado aqui, caso contrário, você definitivamente ficará completamente cego pela maneira como a classifica de acordo com a segunda palavra -chave. Como você classifica se houver dois valores de classificação que são iguais? Deve aparecer primeiro em frente à matriz SA. Se você pensar sobre esse loop e as alterações no valor da matriz WS, entenderá que a ordem do loop for realmente representa a ordem de arranjo quando o valor da classificação for o mesmo. A travessia de trás para frente significa que a classificação do sufixo também é menor quando o valor da classificação é o mesmo.
O exposto acima é apenas a primeira classificação de contagem, que é equivalente a comparar apenas a primeira letra de cada matriz de sufixo para encontrar um SA. O resultado correspondente é como mostrado na figura abaixo.
// Classificação de combinação de loop para (int j = 1, p = 0; j <= n; j = j << 1) {// Se você precisar preenchê -lo, adicione a matriz de classificação primeiro yp = 0; for (int i = n - j; i <n; i ++) {y [p ++] = i; } // varia a segunda palavra -chave de acordo com a primeira palavra -chave SA para (int i = 0; i <n; i ++) {if (sa [i]> = j) {y [p ++] = sa [i] - j; }} // classificando as duas palavras -chave para (int i = 0; i <ws.length; i ++) {ws [i] = 0; } para (int i: x) {ws [i] ++; } para (int i: x) {ws [i] ++; } para (int i = 1; i <ws.length; i ++) {ws [i]+= ws [i - 1]; } para (int i = n-1; i> = 0; i-) {sa [-ws [x [y [i]]] = y [i]; y [i] = 0; } // Calcule a matriz de classificação de SA int xb [] = new int [n]; // x Backup de matriz para (int i = 0; i <n; i ++) {xb [i] = x [i]; } int número = 1; x [SA [0]] = 1; for (int i = 1; i <n; i ++) {if (xb [sa [i]]! = xb [sa [i - 1]]) {x [sa [i]] = ++ número; } else if (sa [i] + j> = n && sa [i - 1] + j> = n) {x [sa [i]] = número; } else if (sa [i] + j <n && sa [i - 1] + j> = n) {x [sa [i]] = ++ número; } else if (xb [sa [i] + j]! = xb [sa [i - 1] + j]) {x [sa [i]] = ++ número; } else {x [sa [i]] = número; } if (número> = n) quebra; }}Este é o código mais difícil de entender ao encontrar a matriz SA. Primeiro de tudo, você precisa entender a idéia do algoritmo de multiplicação. Após a primeira ordem de contagem, já sabemos a classificação da primeira letra inicial de todas as matrizes de sufixo? Como sabemos a classificação da primeira letra inicial, é equivalente à ordem de sua segunda letra (observe a diferença entre classificação e ordem. A classificação é que sabemos em qual ele está fixado. A ordem é que só sabemos a ordem em que ele aparece, mas não sabemos em qual ele está especificamente classificado). É claro que isso é originalmente de uma corda e, para cada sufixo, também pode ser usado como sufixo para seu sufixo anterior. Falando nisso, por exemplo, para "Baaaab", a ordem de sua primeira letra corresponde à segunda ordem de palavra -chave de "Abaaaab". Com a ordem da primeira palavra -chave e o tipo de segunda palavra -chave, podemos encontrar o tipo combinado das duas palavras -chave. De acordo com o resultado do tipo de combinação, ainda podemos usar a ideia anterior. Após a primeira combinação "Baaaab", resolvemos a ordem das duas primeiras letras "BA", para que ele também possa usar a ordem da segunda palavra -chave de "Aabaaaab". A lógica de todo o tipo é mencionada abaixo
Em seguida, analisaremos o código nos segmentos
for (int i = n - j; i <n; i ++) {y [p ++] = i; } // Selecione a segunda palavra -chave de acordo com a primeira palavra -chave SA para (int i = 0; i <n; i ++) {if (sa [i]> = j) {y [p ++] = sa [i] - j; }}O código acima é encontrar o SA, ou seja, a matriz Y da segunda palavra -chave, com o valor inicial de p sendo 0, e o primeiro loop é classificar o sufixo que precisa ser preenchido na frente da matriz.
Você precisa entender a lógica do segundo loop em combinação com o diagrama lógico anterior. Atravessamos o resultado de classificação da primeira palavra -chave SA. Se (SA [i]> = j) determinar se o sufixo pode ser usado como a segunda palavra -chave para outros sufixos. Tomando o primeiro loop j = 1 como exemplo, quando SA [i] = 0 representa a matriz de sufixo "aabaaaab", obviamente não pode ser usada como a segunda palavra -chave para outros sufixos. Para a segunda palavra -chave que pode ser usada como outros sufixos, a ordem de seu SA é a segunda palavra -chave correspondente. SA [i] - J encontra o sufixo dele como a segunda palavra -chave e a coloca na matriz Y e p ++. Você precisa entender aqui lentamente.
// mescla o tipo de duas palavras -chave para (int i = 0; i <ws.length; i ++) {ws [i] = 0; } para (int i: x) {ws [i] ++; } para (int i = 1; i <ws.length; i ++) {ws [i]+= ws [i - 1]; } para (int i = n-1; i> = 0; i-) {sa [-ws [x [y [i]]] = y [i]; y [i] = 0; }O acima é encontrar a combinação de classificação com base na primeira palavra -chave SA e na segunda palavra -chave classificando y. Este código é bastante obscuro. Primeiro, não podemos entender o código, mas entender uma ideia. Para a classificação de duas palavras -chave, as regras reais são semelhantes à classificação de dois números. Por exemplo, 11 e 12 comparam o tamanho, 10 bits são a primeira palavra -chave e os bits únicos são a segunda palavra -chave. Depois de comparar 10 bits, encontramos 11 = 12 e, em seguida, comparamos os bits únicos, sabemos que 11 <12. Se os 10 bits forem iguais, a ordem dos bits únicos é a ordem de tamanho. Eu disse na primeira vez que conto a classificação acima de que a ordem da classificação da contagem para o loop realmente representa a ordem de arranjo quando os valores de classificação são iguais. Então, como encontramos o pedido depois que as duas palavras -chave são mescladas em uma classificação de uma contagem? Deixe -me dizer meu entendimento. Na verdade, um tipo de contagem contém dois tipos, um é o tipo de valores numéricos, e o outro é o tipo de ordem de ocorrência. As regras são equivalentes ao exemplo anterior de comparação de 11 e 12. O tipo de valores numéricos é de 10 bits e o tipo de ordem de ocorrência é um bits. Neste ponto, temos uma ideia. A classificação dos valores é classificada pela primeira palavra -chave e a classificação de ocorrências é classificada pela segunda palavra -chave, para que possamos contar e classificar um momento para encontrar a classificação após a combinação das duas palavras -chave. O código acima é a implementação dessa ideia. A matriz X é a matriz de classificação da primeira palavra -chave, e nós a contamos.
for (int i = n-1; i> = 0; i-) {sa [-ws [x [y [i]]] = y [i]; y [i] = 0; }Esse loop é a implementação de todas as idéias acima. Atravessamos a segunda palavra -chave da parte traseira. Para Y [i], calculamos a classificação da contagem de sua primeira palavra -chave. Essa classificação de contagem é o ranking de Y [i], e a contagem final é reduzida em 1. O tipo de palavra -chave mesclada foi encontrada com sucesso.
Acredito que, se você entender todos os códigos acima, você definitivamente ficará surpreso. Também fiquei empolgado quando pensei nesse código repetidamente e estava simplesmente convencido. Este é o charme dos algoritmos.
Com a matriz SA, podemos encontrar a matriz de classificação. Isso não é difícil, então não explicaremos. Todos os códigos para encontrar SA estão anexados abaixo.
public static void main (string [] args) {string str = "aabaaaab"; MySuffixArrayTest ArrayTest = new MySuffixArrayTest (str.toString ()); Arraytest.initsa (); // Encontre SA Array} public void initsa () {rank = new int [n]; SA = novo int [n]; ws = novo int [255]; y = new int [n]; x = novo int [n]; // loop a string original para converter o valor int na matriz de classificação para (int i = 0; i <n; i ++) {rank [i] = (int) sufixo [i]; } // primeira contagem de contagem para (int i = 0; i <n; i ++) {ws [rank [i]] ++; x [i] = classificação [i]; } para (int i = 1; i <ws.length; i ++) {ws [i]+= ws [i - 1]; } para (int i = n-1; i> = 0; i--) {sa [-ws [rank [i]]] = i; } // Classificação de combinação de loop para (int j = 1, p = 0; j <= n; j = j << 1) {// Se você precisar preencher, adicione a matriz classificada primeiro yp = 0; for (int i = n - j; i <n; i ++) {y [p ++] = i; } // varia a segunda palavra -chave de acordo com a primeira palavra -chave SA para (int i = 0; i <n; i ++) {if (sa [i]> = j) {y [p ++] = sa [i] - j; }} // classificando as duas palavras -chave para (int i = 0; i <ws.length; i ++) {ws [i] = 0; } para (int i: x) {ws [i] ++; } para (int i = 1; i <ws.length; i ++) {ws [i]+= ws [i - 1]; } para (int i = n-1; i> = 0; i-) {sa [-ws [x [y [i]]] = y [i]; y [i] = 0; } // Calcule a matriz de classificação com base em sa int xb [] = new int [n]; // x Backup de matriz para (int i = 0; i <n; i ++) {xb [i] = x [i]; } int número = 1; x [SA [0]] = 1; for (int i = 1; i <n; i ++) {if (xb [sa [i]]! = xb [sa [i - 1]]) {x [sa [i]] = ++ número; } else if (sa [i] + j> = n && sa [i - 1] + j> = n) {x [sa [i]] = número; } else if (sa [i] + j <n && sa [i - 1] + j> = n) {x [sa [i]] = ++ número; } else if (xb [sa [i] + j]! = xb [sa [i - 1] + j]) {x [sa [i]] = ++ número; } else {x [sa [i]] = número; } if (número> = n) quebra; }}}}Resumir
O exposto acima é o código de exemplo para matrizes SAC de matrizes de sufixo Java apresentadas a você. Espero que seja útil para você. Se você tiver alguma dúvida, deixe -me uma mensagem e o editor responderá a você a tempo. Muito obrigado pelo seu apoio ao site wulin.com!