1 Search Results for "da Silva, Israel B. F."

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-dev.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}
}
  • Refine by Author
  • 1 da Fonseca, Paulo G. S.
  • 1 da Silva, Israel B. F.

  • Refine by Classification

  • Refine by Keyword
  • 1 Online construction
  • 1 Wavelet tree

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2017

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact