Revision as of 02:59, 24 December 2021 edit Giraffedata (talk \| contribs) Extended confirmed users, Pending changes reviewers 101,279 edits comprised of ← Previous edit		Revision as of 18:38, 31 December 2021 edit undo ExplodingCabbage (talk \| contribs) Extended confirmed users 840 edits Updated citation for definition of a "sparse suffix array". The previous citation did not contain any mention of the term "sparse suffix array" at all. Do note that Tomohiro I's surname really is "I" per his webpage at http://www.donald.ai.kyutech.ac.jp/~tomohiro/index_e.html - it's not short for "the first" like in the name of a king! Next edit →
Line 27: [[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.{{sfn\|Abouelhoda\|Kurtz\|Ohlebusch\|2004}} The suffix array for a subset of all suffixes of a string is called [[sparse suffix array]].{{sfn\|I\|Kärkkäinen\|~~Ukkonen~~Kempa\|~~1996~~2014}} Multiple probabilistic algorithms have been developed to minimize the additional memory usage including an optimal time and memory algorithm.{{sfn\|Gawrychowski\|Kociumaka\|2017}} == Definition == Line 360: \| 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 }} * {{cite conference\|last1=~~Kärkkäinen~~I\|first1=~~Juha~~Tomohiro\|last2=~~Ukkonen~~Kärkkäinen\|first2=~~Esko~~Juha\|last3=Kempa\|first3=Dominik\|title=Faster Sparse ~~suffix~~Suffix ~~trees~~Sorting \|date=~~1996~~2014\|series=~~Lecture~~Leibniz ~~Notes~~International Proceedings in ~~Computer~~Informatics ~~Science~~(LIPIcs) \|volume=~~1090~~25 \|pages=~~219–230~~386-396 \|publisher=~~Springer~~Schloss ~~Berlin~~Dagstuhl ~~Heidelberg~~– Leibniz-Zentrum fuer Informatik \|doi=10.~~1007~~4230/~~3-540-61332-3_155~~LIPIcs.STACS.2014.386 \|isbn=978-3-~~540~~939897-~~61332~~65-~~9}}~~1 }} * {{cite conference \| 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

Suffix array: Difference between revisions