Suffix array: Difference between revisions

Revision as of 21:49, 11 August 2020

Revision as of 20:55, 12 September 2020

Line 29:

{{harvtxt|Li|Li|Huo|2016}} gave the first in-place <math>\mathcal{O}(n)</math> time suffix array construction algorithm that is optimal both in time and space, where ''in-place'' means that the algorithm only needs <math>\mathcal{O}(1)</math> additional space beyond the input string and the output suffix array.

[[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|lastlast1=Abouelhoda|firstfirst1=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|lastlast1=Kärkkäinen|firstfirst1=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|lastlast1=Gawrychowski|firstfirst1=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 246:

| url = http://dl.acm.org/citation.cfm?id=320176.320218

| last1 = Manber | first1 = Udi | author1-link = Udi_Manber

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

}}

* {{cite conference |last2=Li|first2=Jian|last3=Huo|first3=Hongwei

Line 298 ⟶ 299:

* {{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

Line 321 ⟶ 322:

}}

* {{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=11–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