DROPS

Document

DOI: 10.4230/LIPIcs.SEA.2017.16

Online Construction of Wavelet Trees

Authors: Paulo G. S. da Fonseca and Israel B. F. da Silva

Published in: LIPIcs, Volume 75, 16th International Symposium on Experimental Algorithms (SEA 2017)

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.

Cite as

Paulo G. S. da Fonseca and Israel B. F. da Silva. Online Construction of Wavelet Trees. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 16:1-16:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{dafonseca_et_al:LIPIcs.SEA.2017.16,
  author =	{da Fonseca, Paulo G. S. and da Silva, Israel B. F.},
  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 =	{Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.16},
  URN =		{urn:nbn:de:0030-drops-76135},
  doi =		{10.4230/LIPIcs.SEA.2017.16},
  annote =	{Keywords: Wavelet tree, Online construction}
}

Search Results

Documents authored by da Fonseca, Paulo G. S.

Online Construction of Wavelet Trees

Abstract

Cite as

Thanks for your feedback!

Could not send message