Mostrar código-fonte de Arranjo de sufixos

{{Mais notas|data=julho de 2021}}

{| class="infobox" style="width: 22em"
! colspan="3" style="font-size: 125%; text-align: center;" | Array de sufixos
|-
! [[Lista de estrutura de dados|Tipe]]
| colspan="2" | [[Array]]
|-
! Inventado por
{{!}} colspan="2" {{!}}  {{harvtxt|Manber|Myers|1990}}
|-
! colspan="3" class="navbox-abovebelow" | [[Complexidade de tempo]]<br />em Notação [[Grande-O]]
|-
|
| Média
| Pior caso
|-
! Espaço
| <math>\mathcal{O}(n)</math>
| <math>\mathcal{O}(n)</math>
|-
! Construção
| <math>\mathcal{O}(n)</math>
| <math>\mathcal{O}(n)</math>
|}

Em [[ciência da computação]], um '''array de sufixos''' é um [[array]] ordenado de todos os [[subcadeia de caracteres#sufixo|sufixos]] de uma [[cadeia de caracteres]]. É uma [[estrutura de dados]] simples, porém poderosa que é usada, dentre outras, em índices de textos inteiros, algoritmos de [[compressão de dados]] e dentro do campo da [[bioinformática]].{{sfn|Abouelhoda|Kurtz|Ohlebusch|2002}}

Arrays de sufixos foram introduzidos por {{harvtxt|Manber|Myers|1990}} como uma alternativa simples e eficiente em termos de espaço a [[árvore de sufixos]]. Eles foram descobertos independentemente por {{harvtxt|Gonnet|Baeza-Yates|Snider|1992}} sob o noe ''array PAT''.

== Definição ==
Seja <math>S=s_1,s_2, ..., s_n</math> uma cadeia de caracteres e seja <math>S[i,j]</math> a [[subcadeia de caracteres|subcadeia]] de <math>S</math> que vai de <math>i</math> até <math>j</math>.

O array de sufixos <math>A</math> de <math>S</math> é definido como sendo um array de inteiros que proveem as posições iniciais dos [[subcadeia de caracteres#sufixo|sufixos]] de <math>S</math> em [[ordem lexicográfica]]. Isto significa que uma entrada <math>A[i]</math> contem a posição inicial do <math>i</math>-ésimo menor sufixo em <math>S</math> e, da mesma forma, para todo  <math>1 < i \leq n</math>: <math>S[A[i-1],n] < S[A[i],n]</math>.

== Exemplo ==

Considere o texto {{mvar|S}}=<code>banana$</code> a ser indexado:
{| class="wikitable"
|-
| i
| 1 || 2 || 3 || 4 || 5 || 6 || 7
|-
| S[i]
| b || a || n || a || n || a || $
|}

O texto termina com a letra sentinela especial <code>$</code>, que é único e lexicograficamente menor do que qualquer outro caractere. O texto possui os seguintes sufixos:

{|   class="wikitable"
!  align="left" | Suffix !!  align="left" | i
|-  class="odd"
|  align="left" | banana$ ||  align="left" | 1
|-  class="even"
|  align="left" | anana$ ||  align="left" | 2
|-  class="odd"
|  align="left" | nana$ ||  align="left" | 3
|-  class="even"
|  align="left" | ana$ ||  align="left" | 4
|-  class="odd"
|  align="left" | na$ ||  align="left" | 5
|-  class="even"
|  align="left" | a$ ||  align="left" | 6
|-  class="odd"
|  align="left" | $ ||  align="left" | 7
|}

Estes sufixos podem ser ordenados:

{|   class="wikitable"
!  align="left" | Suffix !!  align="left" | i
|-  class="odd"
|  align="left" | $ ||  align="left" | 7
|-  class="even"
|  align="left" | a$ ||  align="left" | 6
|-  class="odd"
|  align="left" | ana$ ||  align="left" | 4
|-  class="even"
|  align="left" | anana$ ||  align="left" | 2
|-  class="odd"
|  align="left" | banana$ ||  align="left" | 1
|-  class="even"
|  align="left" | na$ ||  align="left" | 5
|-  class="odd"
|  align="left" | nana$ ||  align="left" | 3
|}

O array de sufixos {{mvar|A}} contém a posição inicial destes sufixos ordenados:

{| class="wikitable"
| i
| 1 || 2 || 3 || 4 || 5 || 6 || 7
|-
| A[i]
| 7 || 6 || 4 || 2 || 1 || 5 || 3
|}

Array completo com os próprios sufixos:

{| class="wikitable"
| i
| 1 || 2 || 3 || 4 || 5 || 6 || 7
|-
| A[i]
| 7 || 6 || 4 || 2 || 1 || 5 || 3
|-
| 1
| $ || a || a || a || b || n || n
|-
| 2
|   || $ || n || n || a || a || a
|-
| 3
|   ||   || a || a || n || $ || n
|-
| 4
|   ||   || $ || n || a ||  || a
|-
| 5
|   ||   ||  || a || n ||  || $
|-
| 6
|   ||   ||  || $ || a ||  ||
|-
| 7
|   ||   ||  ||  || $ ||  ||

|}

Então por exemplo, <code>A[3]</code> contém o valor 4, e por isso, se refere ao sufixo iniciando na posição 4 dentro de {{mvar|S}}, que é o sufixo <code>ana$</code>.

== Notas ==
{{Reflist}}

== Referências ==
* {{citar periódico|ref=harv
 | doi=10.1016/S1570-8667(03)00065-0
 |título=Replacing suffix trees with enhanced suffix arrays
 |ano=2004
 |último1 =Abouelhoda |primeiro1 =Mohamed Ibrahim
 |último2 =Kurtz |primeiro2 =Stefan
 |último3 =Ohlebusch |primeiro3 =Enno
 |periódico=Journal of Discrete Algorithms
 | volume=2
 |páginas=53}}
* {{citar conferência|ref=harv
 |título= Suffix arrays: a new method for on-line string searches
 |ano= 1990
 |conferencia= First Annual ACM-SIAM Symposium on Discrete Algorithms
 |páginas= 319–327
 | url = http://dl.acm.org/citation.cfm?id=320176.320218
 |último1 = Manber	 |primeiro1 =  Udi |autorlink1 = Udi_Manber
 |último2 = Myers	 |primeiro2 =  Gene |autorlink2 = Gene_Myers
}}
* {{citar periódico|ref=harv
 |título= Suffix arrays: a new method for on-line string searches
 |ano= 1993
 |periódico= SIAM Journal on Computing
 | volume = 22
 |páginas= 935-948
 | doi = 10.1137/0222058
 | url = http://dl.acm.org/citation.cfm?id=320176.320218
 |último1 = Manber	 |primeiro1 =  Udi |autorlink1 = Udi_Manber
 |último2 = Myers	 |primeiro2 =  Gene |autorlink2 = Gene_Myers
}}
* {{citar periódico|ref=harv
 |título= New indices for text: PAT trees and PAT arrays
 |ano= 1992
 |periódico= Information retrieval: data structures and algorithms
 |último1 = Gonnet	 |primeiro1 =  G.H
 |último2 =  Baeza-Yates	 |primeiro2 =  R.A
 |último3 = Snider        |primeiro3 = T
}}
* {{citar periódico|ref=harv
 |título= Reducing the space requirement of suffix trees
 |ano= 1999
 |periódico= Software-Practice and Experience
 | volume = 29
 |número= 13
 |último1 = Kurtz |primeiro1 =  S
 | doi=10.1002/(SICI)1097-024X(199911)29:13<1149::AID-SPE274>3.0.CO;2-O
 |páginas=1149
}}
* {{citar periódico|ref=harv
 | doi = 10.1007/3-540-45784-4_35|capítulo=The Enhanced Suffix Array and Its Applications to Genome Analysis|título=Algorithms in Bioinformatics|series=Lecture Notes in Computer Science|ano=2002|último1 =Abouelhoda|primeiro1 =Mohamed Ibrahim|último2 =Kurtz|primeiro2 =Stefan|último3 =Ohlebusch|primeiro3 =Enno|isbn=978-3-540-44211-0|volume=2452|páginas=449
}}
* {{citar periódico|ref=harv
 | doi = 10.1145/1242471.1242472|título=A taxonomy of suffix array construction algorithms|ano=2007|último1 =Puglisi|primeiro1 =Simon J.|último2 =Smyth|primeiro2 =W. F.|último3 =Turpin|primeiro3 =Andrew H.|periódico=ACM Computing Surveys|volume=39|número=2|páginas=4
}}
* {{citar periódico|ref=harv
 | doi = 10.1109/DCC.2009.42|capítulo=Linear Suffix Array Construction by Almost Pure Induced-Sorting|título=2009 Data Compression Conference|ano=2009|último1 =Nong|primeiro1 =Ge|último2 =Zhang|primeiro2 =Sen|último3 =Chan|primeiro3 =Wai Hong|isbn=978-0-7695-3592-0|páginas=193
}}
* {{citar periódico|ref=harv
 | doi = 10.1007/978-3-642-22300-6_32|capítulo=Inducing the LCP-Array|título=Algorithms and Data Structures|series=Lecture Notes in Computer Science|ano=2011|último1 =Fischer|primeiro1 =Johannes|isbn=978-3-642-22299-3|volume=6844|páginas=374
}}
* {{citar periódico|ref=harv
 | doi = 10.1016/j.jda.2009.02.007|título=Dynamic extended suffix arrays|ano=2010|último1 =Salson|primeiro1 =M.|último2 =Lecroq|primeiro2 =T.|último3 =Léonard|primeiro3 =M.|último4 =Mouchard|primeiro4 =L.|periódico=Journal of Discrete Algorithms|volume=8|número=2|páginas=241
}}
* {{citar periódico|ref=harv
  | doi = 10.1007/3-540-44888-8_5|capítulo=Fast Lightweight Suffix Array Construction and Checking|título=Combinatorial Pattern Matching|series=Lecture Notes in Computer Science|ano=2003|último1 =Burkhardt|primeiro1 =Stefan|último2 =Kärkkäinen|primeiro2 =Juha|isbn=978-3-540-40311-1|volume=2676|páginas=55
}}
* {{citar periódico|ref=harv
  | doi = 10.1145/800152.804905|capítulo=Rapid identification of repeated patterns in strings, trees and arrays|título=Proceedings of the fourth annual ACM symposium on Theory of computing  - STOC '72|ano=1972|último1 =Karp|primeiro1 =Richard M.|último2 =Miller|primeiro2 =Raymond E.|último3 =Rosenberg|primeiro3 =Arnold L.|páginas=125
}}
* {{citar periódico|ref=harv
  | doi = 10.1109/SFCS.1997.646102|capítulo=Optimal suffix tree construction with large alphabets|título=Proceedings 38th Annual Symposium on Foundations of Computer Science|ano=1997|último1 =Farach|primeiro1 =M.|isbn=0-8186-8197-7|páginas=137
}}
* {{citar periódico|ref=harv
  | doi = 10.1007/3-540-45061-0_73|capítulo=Simple Linear Work Suffix Array Construction|título=Automata, Languages and Programming|series=Lecture Notes in Computer Science|ano=2003|último1 =Kärkkäinen|primeiro1 =Juha|último2 =Sanders|primeiro2 =Peter|isbn=978-3-540-40493-4|volume=2719|páginas=943
}}
* {{citar periódico|ref=harv
  | doi = 10.1145/1227161.1402296|título=Better external memory suffix array construction|ano=2008|último1 =Dementiev|primeiro1 =Roman|último2 =Kärkkäinen|primeiro2 =Juha|último3 =Mehnert|primeiro3 =Jens|último4 =Sanders|primeiro4 =Peter|periódico=Journal of Experimental Algorithmics|volume=12|páginas=1
}}
* {{citar periódico|ref=harv
  | doi = 10.1016/j.parco.2007.06.004|título=Scalable parallel suffix array construction|ano=2007|último1 =Kulla|primeiro1 =Fabian|último2 =Sanders|primeiro2 =Peter|periódico=Parallel Computing|volume=33|número=9|páginas=605
}}

[[Categoria:Estruturas de dados]]