 |
This article contains too much jargon and may need simplification or further explanation. Please discuss this issue on the talk page, and/or remove or explain jargon terms used in the article. Editing help is available. (March 2009) |
In computer science, a succinct data structure for a given data type is a representation of the underlying combinatorial object that uses an amount of space “close” to the information theoretic lower bound together with efficient algorithms for navigation, search, insertion and deletion operations.
A natural example is the representation of a binary tree: an arbitrary binary tree on n nodes can be represented in 2n + o(n) bits while supporting a variety of operations on any node, which includes finding its parent, its left and right child, and returning the size of its subtree, each in constant time. The number of different binary trees on n nodes is 
. For large n, this is about 4n; thus we need at least about log2(4n) = 2n bits to encode it. A succinct binary tree therefore would occupy only 2 bits per node.
The concept was introduced by Jacobson [1], to encode bit vectors, (unlabeled) trees and planar graphs in space essentially equal to the information-theoretic lower bound, while supporting navigation on it efficiently.
External links
- C++ and Java implementations of succinct data structures
- Developing for Developers : Succinct data structures
References
- ^ Jacobson, Guy, Space-Efficient Static Trees and Graphs, doi:, ISBN 0-8186-1982-1
This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)
