Suffix array: Difference between revisions

Revision as of 20:55, 12 September 2020

Revision as of 16:22, 7 December 2020

Line 30:

[[Enhanced suffix arrays]] (ESAs) are suffix arrays with additional tables that reproduce the full functionality of suffix trees preserving the same time and memory complexity.<ref>{{Cite journal|last1=Abouelhoda|first1=Mohamed Ibrahim|last2=Kurtz|first2=Stefan|last3=Ohlebusch|first3=Enno|date=March 2004|title=Replacing suffix trees with enhanced suffix arrays|journal=Journal of Discrete Algorithms|volume=2|issue=1|pages=53–86|doi=10.1016/s1570-8667(03)00065-0|issn=1570-8667|doi-access=free}}</ref>

The suffix array for a subset of all suffixes of a string is called [[sparse suffix array]].<ref>{{Citation|last1=Kärkkäinen|first1=Juha|title=Sparse suffix trees|date=1996|work=Lecture Notes in Computer Science|pages=219–230|publisher=Springer Berlin Heidelberg|doi=10.1007/3-540-61332-3_155|isbn=9783540613329|last2=Ukkonen|first2=Esko}}</ref> Multiple probabilistic algorithms have been developed to minimize the additional memory usage including an optimal time and memory algorithm.<ref>{{Cite journal|last1=Gawrychowski|first1=Paweł|last2=Kociumaka|first2=Tomasz|date=January 2017|title=Sparse Suffix Tree Construction in Optimal Time and Space|journal=Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms|___location=Philadelphia, PA|publisher=Society for Industrial and Applied Mathematics|volume=|pages=425–439|isbn=9781611974782|arxiv=1608.00865|doi=10.1137/1.9781611974782.27|s2cid=6608776}}</ref>

== Definition ==

Line 227:

== References ==

* {{cite conference|ref=harv

| title = Suffix arrays: a new method for on-line string searches

| year = 1990

Line 236:

| last2 = Myers | first2 = Gene | author2-link = Gene_Myers

}}

* {{cite journal|ref=harv

| title = Suffix arrays: a new method for on-line string searches

| year = 1993

Line 260:

|volume = 11147

|pages = 268–284

|ref = harv |last1=Li|first1=Zhize}}

* {{cite journal|ref=harv

| doi=10.1016/S1570-8667(03)00065-0

| title=Replacing suffix trees with enhanced suffix arrays

Line 273:

| pages=53–86| doi-access=free

}}

* {{cite journal|ref=harv

| title = New indices for text: PAT trees and PAT arrays

| year = 1992

Line 282:

| url = http://orion.lcg.ufrj.br/Dr.Dobbs/books/book5/chap05.htm

}}

* {{cite journal|ref=harv

| title = Reducing the space requirement of suffix trees

| year = 1999

Line 294:

| hdl-access = free

}}

* {{cite conference|ref=harv

| doi = 10.1007/3-540-45784-4_35|title=The Enhanced Suffix Array and Its Applications to Genome Analysis|conference=Algorithms in Bioinformatics|series=[[Lecture Notes in Computer Science]]|year=2002|last1=Abouelhoda|first1=Mohamed Ibrahim|last2=Kurtz|first2=Stefan|last3=Ohlebusch|first3=Enno|isbn=978-3-540-44211-0|volume=2452|pages=449

}}

* {{cite journal|ref=harv

| doi = 10.1145/1242471.1242472|title=A taxonomy of suffix array construction algorithms|year=2007|last1=Puglisi|first1=Simon J.|last2=Smyth|first2=W. F.|last3=Turpin|first3=Andrew H.|journal=ACM Computing Surveys|volume=39|issue=2|pages=4

| s2cid = 2653529| url = http://researchrepository.murdoch.edu.au/id/eprint/27889/}}

* {{cite conference|ref=harv

| doi = 10.1109/DCC.2009.42|title=Linear Suffix Array Construction by Almost Pure Induced-Sorting|conference=2009 Data Compression Conference|year=2009|last1=Nong|first1=Ge|last2=Zhang|first2=Sen|last3=Chan|first3=Wai Hong|isbn=978-0-7695-3592-0|pages=193

}}

* {{cite conference|ref=harv

| doi = 10.1007/978-3-642-22300-6_32|title=Inducing the LCP-Array|conference=Algorithms and Data Structures|series=Lecture Notes in Computer Science|year=2011|last1=Fischer|first1=Johannes|isbn=978-3-642-22299-3|volume=6844|pages=374

|arxiv=1101.3448}}

* {{cite journal|ref=harv

| doi = 10.1016/j.jda.2009.02.007|title=Dynamic extended suffix arrays|year=2010|last1=Salson|first1=M.|last2=Lecroq|first2=T.|last3=Léonard|first3=M.|last4=Mouchard|first4=L.|journal=Journal of Discrete Algorithms|volume=8|issue=2|pages=241

|doi-access=free}}

* {{cite conference|ref=harv

| doi = 10.1007/3-540-44888-8_5|title=Fast Lightweight Suffix Array Construction and Checking|conference=Combinatorial Pattern Matching|series=Lecture Notes in Computer Science|year=2003|last1=Burkhardt|first1=Stefan|last2=Kärkkäinen|first2=Juha|isbn=978-3-540-40311-1|volume=2676|pages=55

}}

* {{cite conference|ref=harv

| doi = 10.1145/800152.804905|title=Rapid identification of repeated patterns in strings, trees and arrays|conference=Proceedings of the fourth annual ACM symposium on Theory of computing - STOC '72|year=1972|last1=Karp|first1=Richard M.|last2=Miller|first2=Raymond E.|last3=Rosenberg|first3=Arnold L.|pages=125

}}

* {{cite conference|ref=harv

| doi = 10.1109/SFCS.1997.646102|title=Optimal suffix tree construction with large alphabets|conference=Proceedings 38th Annual Symposium on Foundations of Computer Science|year=1997|last1=Farach|first1=M.|isbn=0-8186-8197-7|pages=137

}}

* {{cite conference|ref=harv

| doi = 10.1007/3-540-45061-0_73|title=Simple Linear Work Suffix Array Construction|conference=Automata, Languages and Programming|series=Lecture Notes in Computer Science|year=2003|last1=Kärkkäinen|first1=Juha|last2=Sanders|first2=Peter|author2-link=Peter Sanders (computer scientist)|isbn=978-3-540-40493-4|volume=2719|pages=943

}}

* {{cite journal|ref=harv

| doi = 10.1145/1227161.1402296|title=Better external memory suffix array construction|year=2008|last1=Dementiev|first1=Roman|last2=Kärkkäinen|first2=Juha|last3=Mehnert|first3=Jens|last4=Sanders|first4=Peter|author4-link=Peter Sanders (computer scientist)|journal=Journal of Experimental Algorithmics|volume=12|pages=1–24

| s2cid = 12296500| url = https://publikationen.bibliothek.kit.edu/1000009446}}

* {{cite journal|ref=harv

| doi = 10.1016/j.parco.2007.06.004|title=Scalable parallel suffix array construction|year=2007|last1=Kulla|first1=Fabian|last2=Sanders|first2=Peter|author2-link=Peter Sanders (computer scientist)|journal=Parallel Computing|volume=33|issue=9|pages=605

}}