請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/33944
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 呂學一(Hsueh-I Lu) | |
dc.contributor.author | Chia-Chi Yeh | en |
dc.contributor.author | 葉家齊 | zh_TW |
dc.date.accessioned | 2021-06-13T05:49:39Z | - |
dc.date.available | 2006-07-17 | |
dc.date.copyright | 2006-07-17 | |
dc.date.issued | 2006 | |
dc.date.submitted | 2006-07-06 | |
dc.identifier.citation | [1] R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics. Addison-Wesley, 1989.
[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. [3] R. C.-N. Chuang, A. Garg, X. He, M.-Y. Kao, and H.-I. Lu, “Compact encodings of planar graphs via canonical ordering and multiple parentheses,” in Proceedings of the 25th International Colloquium on Automata, Languages, and Programming (K. G. Larsen, S. Skyum, and G. Winskel, eds.), Lecture Notes in Computer Science 1443, (Aalborg, Denmark), pp. 118–129, Springer-Verlag, 1998. [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. [6] J. I. Munro and S. S. Rao, “Succinct representations of functions,” in Proceedings of the 31st International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science 3142, (Turku, Finland), pp. 1006–1015, Springer-Verlag, 2004. [7] G. Jacobson, “Space-ef cient static trees and graphs,” in Proceedings of the 30th Annual Symposium on Foundations of Computer Science, (Research Triangle Park, North Carolina), pp. 549–554, IEEE, 30 Oct.–1 Nov. 1989. [8] D. Benoit, E. D. Demaine, J. I. Munro, R. Raman, V. Raman, and S. S. Rao, “Representing trees of higher degree,” Algorithmica, to appear. [9] D. R. Clark, Compact PAT Trees. PhD thesis, University of Waterloo, 1996. [10] D. R. Clark and J. I. Munro, “Ef cient suf x trees on secondary storage,” in Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, (Atlanta, Georgia), pp. 383–391, 23–30 Jan. 1996. [11] J. I. Munro, “Tables,” in Proceedings of the 16th Conference on Foundations of Software Technology and Theoretical Computer Science, Lecture Notes in Computer Science 1180, (Hyderabad, India), pp. 37–42, Springer-Verlag, 1996. [12] Y.-T. Chiang, C.-C. Lin, and H.-I. Lu, “Orderly spanning trees with applications to graph drawing and graph encoding,” in Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, (Washington, DC), pp. 506–515, 7–9 Jan. 2001. [13] R. F. Geary, R. Raman, and V. Raman, “Succinct ordinal trees with level-ancestor queries.,” in Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (J. I. Munro, ed.), (New Orleans, Louisiana, USA), pp. 1–10, SIAM, 2004. [14] R. F. Geary, N. Rahman, R. Raman, and V. Raman, “A simple optimal representation for balanced parentheses,” in Proceedings of the 15th Annual Symposium on Combinatorial Pattern Matching (S. C. Sahinalp, S. Muthukrishnan, and U. Dogrusぴoz, eds.), Lecture Notes in Computer Science 3109, (Istanbul,Turkey), pp. 159–172, Springer-Verlag, 2004. [15] J. I. Munro, V. Raman, and S. S. Rao, “Space effcient suffix trees,” Journal of Algorithms, vol. 39, no. 2, pp. 205–222, 2001. [16] P. van Emde Boas, “Machine models and simulations,” in Handbook of Theoretical Computer Science (J. van Leeuwen, ed.), vol. A, ch. 1, pp. 1–60, Amsterdam: Elsevier, 1990. [17] T. C. Bell, J. G. Cleary, and I. H. Witten, Text Compression. Englewood Cliffs, NJ: Prentice-Hall, 1990. [18] P. Elias, “Universal codeword sets and representations of the integers,” IEEE Transactions on Information Theory, vol. IT-21, pp. 194–203, 1975. [19] H. N. Gabow, J. L. Bentley, and R. E. Tarjan, “Scaling and related techniques for geometry problems,” in Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing, (New York, NY, USA), pp. 135–143, ACM Press, 1984. [20] M. A. Bender and M. Farach-Colton, “The LCA problem revisited,” in Proceedings of the 4th Latin American Symposium on Theoretical Informatics (G. H. Gonnet, D. Panario, and A. Viola, eds.), Lecture Notes in Computer Science 1776, (Punta del Este, Uruguay), pp. 88–94, Springer, 2000. [21] K. Sadakane, “Succinct representations of lcp information and improvements in the compressed suffix arrays,” in Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, (San Francisco), pp. 225–232, ACM and SIAM, 6–8 Jan. 2002. [22] R. Raman, V. Raman, and S. S. Rao, “Succinct dynamic data structures,” in Proceedings of the 7th International Workshop on Algorithms and Data Structures (F. K. H. A. Dehne, J.-R. Sack, and R. Tamassia, eds.), Lecture Notes in Computer Science 2125, (Providence, RI, USA), pp. 426–437, Springer-Verlag, 2001. [23] W.-K. Hon, K. Sadakane, andW.-K. Sung, “Succinct data structures for searchable partial sums,” in Proceedings of the 14th Symposium on Algorithms and Computation (T. Ibaraki, N. Katoh, and H. Ono, eds.), Lecture Notes in Computer Science 2906, (Kyoto, Japan), pp. 505–516, Springer-Verlag, 2003. [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. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/33944 | - |
dc.description.abstract | 有根樹是一種非常基本且重要的資料結構,而如何有效率地將它儲存起來並提供快速地查詢是一個被廣泛地探討的問題。
目前已知最好的結果是由 Geary、Raman 和 Raman 所提出的表示法 [SODA 2004, 第 1-10 頁]。 給定一棵 n 個節點的有根樹 T,他們的表示法在空間上需要 2n + o(n) 位元,其最高項已經達到資訊理論上的最佳解。 此外,他們的表示法在常數時間內對於 T 支援多種查詢。 在本篇論文中,我們基於 2n 個括號的平衡字串,對於 T 提出了改良的 2n + o(n) 位元表示法。我們的成果可以分成兩方面: 其一,我們的表示法在常數時間內所能支援的查詢,為 Geary、Raman 和 Raman 的表示法所支援的超集合; 其二,在我們使用的表示法中,可以很容易地藉著加入新的輔助字串來支援新的查詢。 | zh_TW |
dc.description.abstract | 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. | en |
dc.description.provenance | Made available in DSpace on 2021-06-13T05:49:39Z (GMT). No. of bitstreams: 1 ntu-95-R93922048-1.pdf: 435963 bytes, checksum: dd033f46a8c563850c3617aa438876a0 (MD5) Previous issue date: 2006 | en |
dc.description.tableofcontents | Chinese Abstract . . . . . . . . . . . . . . . . . . . . . ii
English Abstract . . . . . . . . . . . . . . . . . . . . . iii Acknowledgements . . . . . . . . . . . . . . . . . . . . . iv Contents . . . . . . . . . . . . . . . . . . . . . . . . . v List of Tables . . . . . . . . . . . . . . . . . . . . . . vi List of Figures . . . . . . . . . . . . . . . . . . . . . vii 1 Introduction . . . . . . . . . . . . . . . . . . . . . . 1 2 Preliminaries . . . . . . . . . . . . . . . . . . . . . 5 3 Distance, Subtree Height, and Lowest Common Ancestor . . 7 4 Rank and Select for Children . . . . . . . . . . . . . . 11 4.1 Child Rank . . . . . . . . . . . . . . . . . . . . . . 12 4.2 Child Select . . . . . . . . . . . . . . . . . . . . . 14 5 Concluding Remarks . . . . . . . . . . . . . . . . . . . 20 Bibliography . . . . . . . . . . . . . . . . . . . . . . . 21 | |
dc.language.iso | en | |
dc.title | 平衡括號大反撲 | zh_TW |
dc.title | Balanced Parentheses Strike Back | en |
dc.type | Thesis | |
dc.date.schoolyear | 94-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 趙坤茂,顏嗣鈞,游森棚 | |
dc.subject.keyword | 有根樹,資料結構,平衡括號, | zh_TW |
dc.subject.keyword | rooted tree,succinct data structure,balanced parentheses, | en |
dc.relation.page | 24 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2006-07-07 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-95-1.pdf 目前未授權公開取用 | 425.75 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。