簡潔データ構造
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/04/03 04:35 UTC 版)
簡潔データ構造 (かんけつデータこうぞう、英: succinct data structure) とは計算機科学の用語で、情報理論的下界に「近い」領域量だけを使いつつ、（他の圧縮形式とは異なり）効率的に質問を受け付けることができるデータ構造を指す。その概念は最初 Jacobson [1] によってビット配列、木、平面的グラフを符号化するために導入された。通常のロスなしデータ圧縮アルゴリズムとは異なり、簡潔データ構造は事前の展開操作をせずに使用することができる。圧縮データ構造は関連する考え方に基づいているが、圧縮データ構造ではデータ構造のサイズは表現しようとする特定のデータに依存する。
- ^ Jacobson, G. J (1988). Succinct static data structures.
- ^ a b Raman, R.; Raman, V.; Rao, S.S. (2002). "Succinct indexable dictionaries with applications to encoding k-ary trees and multisets" (PDF). Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms. pp. 233–242. ISBN 089871513X。
- ^ Sadakane, K.; Grossi, R. (2006). "Squeezing succinct data structures into entropy bounds" (PDF). Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm. pp. 1230–1239. ISBN 0898716055。
- ^ Jacobson, G. (1989). Space-efficient static trees and graphs.
- ^ González, R.; Grabowski, S.; Mäkinen, V.; Navarro, G. (2005). "Practical implementation of rank and select queries" (PDF). Poster Proceedings Volume of 4th Workshop on Efficient and Experimental Algorithms (WEA). pp. 27–38.
- ^ Clark, D. (1998). Compact pat trees.
- ^ Vigna, S. (2008). “Broadword implementation of rank/select queries”. Experimental Algorithms: 154–168.
- ^ Brodnik, A.; J. I Munro (1999). “Membership in constant time and almost-minimum space”. SIAM J. Comput. 28 (5): 1627–1640. doi:10.1137/S0097539795294165.
- ^ Patrascu, M. (2008). "Succincter" (PDF). Foundations of Computer Science, 2008. FOCS'08. IEEE 49th Annual IEEE Symposium on. pp. 305–313.
- ^ Belazzougui, Djamal. “Hash, displace, and compress”. 2011年12月30日閲覧。
[続きの解説]
「簡潔データ構造」の続きの解説一覧
- 1 簡潔データ構造とは
- 2 簡潔データ構造の概要
- 3 推奨文献
- 簡潔データ構造のページへのリンク
