Literature

Abouelhoda, Mohamed Ibrahim, Stefan Kurtz, and Enno Ohlebusch. 2004. “Replacing suffix trees with enhanced suffix arrays.” Journal of Discrete Algorithms 2 (1): 53–86.

Beller, Timo, Simon Gog, Enno Ohlebusch, and Thomas Schnattinger. 2011. “Computing the Longest Common Prefix Array Based on the Burrows-Wheeler Transform.” In Proceedings of String Processing and Information Retrieval, 18th International Symposium, (SPIRE 2011), 197–208.

———. 2013. “Computing the Longest Common Prefix Array Based on the Burrows-Wheeler Transform.” Journal of Discrete Algorithms 18 (0) (January): 22–31. doi:10.1016/j.jda.2012.07.007. http://dx.doi.org/10.1016/j.jda.2012.07.007.

Bender, Michael A., and Martin Farach-Colton. 2000. “The LCA Problem Revisited.” In Proceedings of the 4th Latin American Symposium on Theoretical Informatics (LATIN 2000), 88–94.

Brisaboa, Nieves R., Susana Ladra, and Gonzalo Navarro. 2009. “Directly Addressable Variable-Length Codes.” In Proceedings of String Processing and Information Retrieval, 16th International Symposium, (SPIRE 2009), 122–130.

Clark, David. 1996. “Compact Pat Trees.” Department of Computer Science, University of Waterloo.

Claude, Francisco, and Gonzalo Navarro. 2008. “Practical Rank/Select Queries over Arbitrary Sequences.” In Proceedings of String Processing and Information Retrieval, 15th International Symposium, (SPIRE 2008), 176–187.

Culpepper, J. Shane, Gonzalo Navarro, Simon J. Puglisi, and Andrew Turpin. 2010. “Top-k Ranked Document Search in General Text Databases.” In Proceedings Part II of the 18th Annual European Symposium on Algorithms (ESA 2010), 194–205.

Elias, Peter. 1974. “Efficient Storage and Retrieval by Content and Address of Static Files.” Journal of the ACM 21 (2) (April): 246–260. doi:10.1145/321812.321820. http://doi.acm.org/10.1145/321812.321820.

Fano, Robert Mario. 1971. On the Number of Bits Required to Implement an Associative Memory. Computation Structures Group Memo. Massachusetts Institute of Technology, Project MAC.

Ferragina, Paolo, Jouni Sirén, and Rossano Venturini. 2011. “Distribution-Aware Compressed Full-Text Indexes.” In Proceedings of the 19th Annual European Symposium on Algorithms (ESA 2011), 760–771.

Ferragina, Paolo, and Giovanni Manzini. 2000. “Opportunistic Data Structures with Applications.” In Proceedings of the 41st Annual Symposium on Foundations of Computer Science, (FOCS 2000), 390–398.

Fischer, Johannes. 2010. “Optimal Succinctness for Range Minimum Queries.” In Proceedings of the 9th Latin American Symposium on Theoretical Informatics (LATIN 2010), 158–169.

Gagie, Travis, Gonzalo Navarro, and Simon J. Puglisi. 2012. “New algorithms on wavelet trees and applications to information retrieval.” Theoretical Computer Science 426: 25–41.

Geary, Richard F., Naila Rahman, Rajeev Raman, and Venkatesh Raman. 2004. “A Simple Optimal Representation for Balanced Parentheses.” In Proceedings of the 15th Annual Symposium on Combinatorial Pattern Matching, (CPM 2004), 159–172.

———. 2006. “A simple optimal representation for balanced parentheses.” Theoretical Computer Science 368 (3): 231–246.

Gog, Simon, and Johannes Fischer. 2010. “Advantages of Shared Data Structures for Sequences of Balanced Parentheses.” In Proceedings of 2010 Data Compression Conference (DCC 2010), 406–415.

Gog, Simon, and Enno Ohlebusch. 2010. “Lightweight LCP-Array Construction in Linear Time.” CoRR abs/1012.4263.

———. 2011. “Fast and Lightweight LCP-Array Construction Algorithms.” In Proceedings of the 13th Workshop on Algorithm Engineering and Experiments, (ALENEX 2011), 25–34.

Grossi, Roberto, Ankur Gupta, and Jeffrey Scott Vitter. 2003. “High-order entropy-compressed text indexes.” In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2003), 841–850.

Kasai, Toru, Gunho Lee, Hiroki Arimura, Setsuo Arikawa, and Kunsoo Park. 2001. “Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications.” In Proceedings of the 12th Annual Symposium on Combinatorial Pattern Matching, (CPM 2001), 181–192.

Kärkkäinen, Juha, Giovanni Manzini, and Simon J. Puglisi. 2009. “Permuted Longest-Common-Prefix Array.” In Proceedings of the 20th Annual Symposium on Combinatorial Pattern Matching, (CPM 2009), 181–192.

Larsson, N. Jesper, and Kunihiko Sadakane. 2007. “Faster suffix sorting.” Theoretical Computer Science 387 (3): 258–272.

Mäkinen, Veli, and Gonzalo Navarro. 2005. “Succinct Suffix Arrays Based on Run-Length Encoding.” In Proceedings of the 16th Annual Symposium on Combinatorial Pattern Matching, (CPM 2005), 45–56.

Navarro, Gonzalo, and Eliana Providel. 2012. “Fast, Small, Simple Rank/Select on Bitmaps.” In Proceedings of the 11th International Symposium on Experimental Algorithms (SEA 2013), 295–306.

Ohlebusch, Enno, Johannes Fischer, and Simon Gog. 2010. “CST++.” In Proceedings of String Processing and Information Retrieval, 17th International Symposium, (SPIRE 2010), 322–333.

Ohlebusch, Enno, and Simon Gog. 2009. “A Compressed Enhanced Suffix Array Supporting Fast String Matching.” In Proceedings of String Processing and Information Retrieval, 16th International Symposium, (SPIRE 2009), 51–62.

Okanohara, Daisuke, and Kunihiko Sadakane. 2007. “Practical Entropy-Compressed Rank/Select Dictionary.” In Proceedings of the 9th Workshop on Algorithm Engineering and Experiments (ALENEX 2007).

Pagh, Rasmus. “Low Redundancy in Static Dictionaries with O(1) Worst Case Lookup Time.” In Proceedings of the 26th International Colloquium on Automata, Languages and Programming (ICALP 1999)year, 595–604.

Raman, Rajeev, Venkatesh Raman, and S. Srinivasa Rao. 2002. “Succinct indexable dictionaries with applications to encoding k-ary trees and multisets.” In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2002), 233–242.

Sadakane, Kunihiko. 2002. “Succinct representations of LCP information and improvements in the compressed suffix arrays.” In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2002), 225–232.

———. 2003. “New text indexing functionalities of the compressed suffix arrays.” Journal of Algorithms 48 (2): 294–313.

———. 2007a. “Compressed Suffix Trees with Full Functionality.” Theory of Computing Systems 41 (4): 589–607.

———. 2007b. “Succinct data structures for flexible text retrieval systems.” Journal of Discrete Algorithms 5 (1) (March): 12–22. doi:10.1016/j.jda.2006.03.011. http://dx.doi.org/10.1016/j.jda.2006.03.011.

———. 2008. The Ultimate Balanced Parentheses.

Schnattinger, Thomas, Enno Ohlebusch, and Simon Gog. 2012. “Bidirectional search in a string with wavelet trees and bidirectional matching statistics.” Information and Computation 213: 13–22.

Transier, Frederik, and Peter Sanders. 2010. “Engineering Basic Algorithms of an In-Memory Text Search Engine.” ACM Transactions on Information Systems 29 (1) (December): 2–1. doi:10.1145/1877766.1877768. http://doi.acm.org/10.1145/1877766.1877768.

Vigna, Sebastiano. 2008. “Broadword Implementation of Rank/Select Queries.” In Proceedings of the 7th Workshop on Experimental Algorithms, WEA (2008 WEA), 154–168.

Williams, Hugh E., and Justin Zobel. 1999. “Compressing Integers for Fast File Access.” The Computer Journalvolume (3): 193–201. doi:10.1093/comjnl/42.3.193. http://comjnl.oxfordjournals.org/content/42/3/193.abstract.