License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2017.16
URN: urn:nbn:de:0030-drops-76135
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7613/
Go to the corresponding LIPIcs Volume Portal

da Fonseca, Paulo G. S. ; da Silva, Israel B. F.

Online Construction of Wavelet Trees

pdf-format:
LIPIcs-SEA-2017-16.pdf (0.6 MB)

Abstract

The wavelet tree (WT) is a flexible and efficient data structure for representing character strings in succinct space, while allowing for fast generalised rank, select and access operations. As such, they play an important role in modern text indexing methods. However, despite their popularity, not many algorithms have been published concerning their construction. In particular, while the WT is capable of representing a sequence of length n over an alphabet of size m in n\lg m+o(n\lg m) bits, much more space is typically used for its construction. Here we propose an O(n\lg m)-time online method for the construction of the WT, requiring no prior knowledge about the input alphabet. The proposed algorithm is conceptually simpler than other state-of-the-art methods, while having comparable time performance and being more space-efficient in practice, since it performs just one pass over the input text and uses little extra space other than for the structure itself, as shown both theoretically and empirically.

BibTeX - Entry

@InProceedings{dafonseca_et_al:LIPIcs:2017:7613,
  author =	{Paulo G. S. da Fonseca and Israel B. F. da Silva},
  title =	{{Online Construction of Wavelet Trees}},
  booktitle =	{16th International Symposium on Experimental Algorithms (SEA 2017)},
  pages =	{16:1--16:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-036-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{75},
  editor =	{Costas S. Iliopoulos and Solon P. Pissis and Simon J. Puglisi and Rajeev Raman},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7613},
  URN =		{urn:nbn:de:0030-drops-76135},
  doi =		{10.4230/LIPIcs.SEA.2017.16},
  annote =	{Keywords: Wavelet tree, Online construction}
}

Keywords: Wavelet tree, Online construction
Collection: 16th International Symposium on Experimental Algorithms (SEA 2017)
Issue Date: 2017
Date of publication: 07.08.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI