Suffix array: Difference between revisions

Revision as of 08:21, 19 April 2025

Latest revision as of 03:37, 11 August 2025

(3 intermediate revisions by one other user not shown)

Line 28:

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}}

TheA suffixsorted array forof aonly subsetsome of(rather than all) suffixes of a string is called a [[sparse suffix array]].{{sfn|I|Kärkkäinen|Kempa|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 288:

| author2-link = Gene Myers

}}

* {{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|pages=425–439|isbn=9781611974782|arxiv=1608.00865|doi=10.1137/1.9781611974782.27 |s2cid=6608776}}

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

|doi = 10.1007/978-3-030-00479-8_22

Line 377 ⟶ 376:

* [http://code.google.com/p/compression-code/downloads/list Suffix sorting module for BWT in C code]

* [http://www.codeodor.com/index.cfm/2007/12/24/The-Suffix-Array/1845 Suffix Array Implementation in Ruby]

* [httphttps://sary.sourceforge.net/index.html.en Suffix array library and tools]

* [http://pizzachili.dcc.uchile.cl/ Project containing various Suffix Array c/c++ Implementations with a unified interface]

* [https://github.com/y-256/libdivsufsort A fast, lightweight, and robust C API library to construct the suffix array]