Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Compressed suffix array
open-in-new
<h2 id="open-source-implementations">Open source implementations</h2> <p>There are several open source implementations of compressed suffix arrays available (see External Links below). Bowtie and Bowtie2 are open-source compressed suffix array implementations of <a href="/facts/Sequence_alignment/p8GQfF7b">read alignment</a> for use in <a href="/facts/Bioinformatics/D5x2L8ee">bioinformatics</a>. The Succinct Data Structure Library (SDSL) is a library containing a variety of compressed data structures including compressed suffix arrays. FEMTO is an implementation of compressed suffix arrays for external memory. In addition, a variety of implementations, including the original <a href="/facts/FM-index/USSL4YMU">FM-index</a> implementations, are available from the Pizza & Chili Website (see external links). </p> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/FM-index/USSL4YMU">FM-index</a></li> <li><a href="/facts/Suffix_Array/Q87p7bYH">Suffix Array</a></li></ul> <h2 id="external-links">External links</h2> <p>Implementations: </p> <ul><li><a href="http://bowtie-bio.sourceforge.net/index.shtml">Bowtie</a> and <a href="http://bowtie-bio.sourceforge.net/bowtie2/index.shtml">Bowtie2</a></li> <li><a href="https://github.com/simongog/sdsl-lite">Succinct Data Structure Library (SDSL)</a></li> <li><a href="https://github.com/femto-dev/femto">FEMTO</a></li> <li><a href="https://web.archive.org/web/20120329222807/http://pizzachili.di.unipi.it/indexes.html">Pizza&Chili website</a>.</li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>R. Grossi and J. S. Vitter, Compressed Suffix Arrays and Suffix Trees, with Applications to Text Indexing and String Matching, SIAM Journal on Computing, 35(2), 2005, 378–407. An earlier version appeared in Proceedings of the 32nd ACM Symposium on Theory of Computing, May 2000, 397–406. <a href="https://dl.acm.org/doi/pdf/10.1145/335305.335351" target="_blank">https://dl.acm.org/doi/pdf/10.1145/335305.335351</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Paolo Ferragina and Giovanni Manzini (2000). "Opportunistic Data Structures with Applications". Proceedings of the 41st Annual Symposium on Foundations of Computer Science. p.390. <a href="http://eprints.adm.unipi.it/2028/1/TR-00-03.ps.gz" target="_blank">http://eprints.adm.unipi.it/2028/1/TR-00-03.ps.gz</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>R. Grossi, A. Gupta, and J. S. Vitter, High-Order Entropy-Compressed Text Indexes, Proceedings of the 14th Annual SIAM/ACM Symposium on Discrete Algorithms, January 2003, 841–850. <a href="https://kuscholarworks.ku.edu/bitstream/handle/1808/7192/vitter_2003.pdf?sequence=1" target="_blank">https://kuscholarworks.ku.edu/bitstream/handle/1808/7192/vitter_2003.pdf?sequence=1</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>R. Grossi and J. S. Vitter, Compressed Suffix Arrays and Suffix Trees, with Applications to Text Indexing and String Matching, SIAM Journal on Computing, 35(2), 2005, 378–407. An earlier version appeared in Proceedings of the 32nd ACM Symposium on Theory of Computing, May 2000, 397–406. <a href="https://dl.acm.org/doi/pdf/10.1145/335305.335351" target="_blank">https://dl.acm.org/doi/pdf/10.1145/335305.335351</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Paolo Ferragina and Giovanni Manzini (2000). "Opportunistic Data Structures with Applications". Proceedings of the 41st Annual Symposium on Foundations of Computer Science. p.390. <a href="http://eprints.adm.unipi.it/2028/1/TR-00-03.ps.gz" target="_blank">http://eprints.adm.unipi.it/2028/1/TR-00-03.ps.gz</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>R. Grossi and J. S. Vitter, Compressed Suffix Arrays and Suffix Trees, with Applications to Text Indexing and String Matching, SIAM Journal on Computing, 35(2), 2005, 378–407. An earlier version appeared in Proceedings of the 32nd ACM Symposium on Theory of Computing, May 2000, 397–406. <a href="https://dl.acm.org/doi/pdf/10.1145/335305.335351" target="_blank">https://dl.acm.org/doi/pdf/10.1145/335305.335351</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>K. Sadakane, Compressed Text Databases with Efficient Query Algorithms Based on the Compressed Suffix Arrays, Proceedings of the International Symposium on Algorithms and Computation, Lecture Notes in Computer Science, vol. 1969, Springer, December 2000, 410–421. <a href="https://www.academia.edu/download/49863657/Compressed_Text_Databases_with_Efficient20161025-5703-7wn9v5.pdf" target="_blank">https://www.academia.edu/download/49863657/Compressed_Text_Databases_with_Efficient20161025-5703-7wn9v5.pdf</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>R. Grossi, A. Gupta, and J. S. Vitter, High-Order Entropy-Compressed Text Indexes, Proceedings of the 14th Annual SIAM/ACM Symposium on Discrete Algorithms, January 2003, 841–850. <a href="https://kuscholarworks.ku.edu/bitstream/handle/1808/7192/vitter_2003.pdf?sequence=1" target="_blank">https://kuscholarworks.ku.edu/bitstream/handle/1808/7192/vitter_2003.pdf?sequence=1</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>L. Foschini, R. Grossi, A. Gupta, and J. S. Vitter, Indexing Equals Compression: Experiments on Suffix Arrays and Trees, ACM Transactions on Algorithms, 2(4), 2006, 611–639. <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>W.-K. Hon, R. Shah, S. V. Thankachan, and J. S. Vitter, On Entropy-Compressed Text Indexing in External Memory, Proceedings of the Conference on String Processing and Information Retrieval, August 2009. <a href="http://ndl.ethernet.edu.et/bitstream/123456789/47838/1/Jussi%20Karlgren_2009.pdf#page=85" target="_blank">http://ndl.ethernet.edu.et/bitstream/123456789/47838/1/Jussi%20Karlgren_2009.pdf#page=85</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> <li id="fn:11"><p>M. P. Ferguson, FEMTO: fast search of large sequence collections, Proceedings of the 23rd Annual Conference on Combinatorial Pattern Matching, July 2012 <a href="https://link.springer.com/chapter/10.1007/978-3-642-31265-6_17" target="_blank">https://link.springer.com/chapter/10.1007/978-3-642-31265-6_17</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li> </ol>