平衡括號大反撲

Balanced Parentheses Strike Back

葉家齊(Chia-Chi Yeh)

指導教授 ： 呂學一

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2006年)

https://doi.org/10.6342/NTU.2006.00150

摘要

有根樹是一種非常基本且重要的資料結構，而如何有效率地將它儲存起來並提供快速地查詢是一個被廣泛地探討的問題。
目前已知最好的結果是由 Geary、Raman 和 Raman 所提出的表示法 [SODA 2004, 第 1-10 頁]。
給定一棵 n 個節點的有根樹 T，他們的表示法在空間上需要 2n + o(n) 位元，其最高項已經達到資訊理論上的最佳解。
此外，他們的表示法在常數時間內對於 T 支援多種查詢。
在本篇論文中，我們基於 2n 個括號的平衡字串，對於 T 提出了改良的 2n + o(n) 位元表示法。我們的成果可以分成兩方面：
其一，我們的表示法在常數時間內所能支援的查詢，為 Geary、Raman 和 Raman 的表示法所支援的超集合；
其二，在我們使用的表示法中，可以很容易地藉著加入新的輔助字串來支援新的查詢。

關鍵字

有根樹 ； 資料結構 ； 平衡括號

並列摘要

Succinct representations for trees with efficient query support have been extensively studied. The best previously known result is due to Geary, Raman, and Raman [SODA 2004, pages 1-10]. The number of bits required by their representation for an n-node tree T is 2n + o(n), whose first-order term is information-theoretically optimal. Their representation supports a large set of O(1)-time queries on T. Based upon a balanced string of 2n parentheses, we give an improved 2n + o(n)-bit representation for T. Our improvement is two fold: Firstly, the set of O(1)-time queries supported by our representation is a proper superset of that supported by the representation of Geary, Raman, and Raman. Secondly, it is also much easier for our representation to support new queries by simply adding new auxiliary strings.

並列關鍵字

rooted tree ； succinct data structure ； balanced parentheses

參考文獻

[2] J. I. Munro and V. Raman, “Succinct representation of balanced parentheses, static trees and planar graphs,” SIAM Journal on Computing, vol. 31, no. 3, pp. 762–776, 2001.

[4] X. He, M.-Y. Kao, and H.-I. Lu, “Linear-time succinct encodings of planar graphs via canonical orderings,” SIAM Journal on Discrete Mathematics, vol. 12, no. 3, pp. 317– 325, 1999.

[5] Y.-T. Chiang, C.-C. Lin, and H.-I. Lu, “Orderly spanning trees with applications,” SIAM Journal on Computing, vol. 34, no. 4, pp. 924–945, 2005.

[24] N. Bonichon, C. Gavoille, and N. Hanusse, “Canonical decomposition of outerplanar maps and application to enumeration, coding and generation.,” J. Graph Algorithms Appl., vol. 9, no. 2, pp. 185–204, 2005.

[1] R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics. Addison-Wesley, 1989.