作者
Francisco Claude, Patrick K Nicholson, Diego Seco
发表日期
2011
研讨会论文
String Processing and Information Retrieval: 18th International Symposium, SPIRE 2011, Pisa, Italy, October 17-21, 2011. Proceedings 18
页码范围
185-196
出版商
Springer Berlin Heidelberg
简介
Wavelet trees are one of the main building blocks in many space efficient data structures. In this paper, we present new algorithms for constructing wavelet trees, based on in-place sorting, that use virtually no extra space. Furthermore, we implement and confirm that these algorithms are practical by comparing them to a known construction algorithm. This represents a step forward for practical space-efficient data structures, by allowing their construction on more massive data sets.
学术搜索中的文章
F Claude, PK Nicholson, D Seco - String Processing and Information Retrieval: 18th …, 2011