第 7 章 まとめと今後の課題
7.2 今後の課題
はじめに,方形描画の符号に関する今後の課題について述べる.
本研究では, 底辺つき方形描画を5m/3 bit に符号化する方法を与えが, よりコ ンパクトな符号が存在するのかどうかについて考えてみよう.
底辺つき方形描画を高速に列挙するアルゴリズムが既に知られている[29, 30, 31].
k 個の面をもつ底辺つき方形描画の個数をNkとしよう. 我々は, 上記の列挙ア ルゴリズムを実装することにより, 底辺つき方形描画の個数の数え上げを行い,
N11 = 10948768という結果を得た. よって, 11個の面をもつ底辺つき方形描画に
対する符号の平均の長さは, 少なくとも24 > logN11 = 23.5 bitであるとわかる.
一方, 本文で提案した符号は, 5×11 = 55 bitである. これは, 11個の面をもつ底
7.2. 今後の課題 95
面数 本研究(bit) 少なくとも必要な
平均の符号長(bit)
1 5 0
2 10 1
3 15 3
4 20 5
5 25 7
6 30 10
7 35 12
8 40 15
9 45 18
10 50 21
11 55 24
12 60 27
13 65 30
表 7.1: 本研究で設計した底辺つき方形描画の符号と, 少なくとも必要な符号の平 均の長さ
辺つき方形描画に対するよりコンパクトな符号が存在することを意味している. 同 様に, k = 1から13個の面をもつ底辺つき方形描画に対して, 少なくとも必要な符 号の平均の長さを調べてみたところ表7.2のようになった.
表7.2は, 面数が1–13までの底辺つき方形描画に関しては,よりコンパクトな符 号が存在することを意味している. 底辺つき方形描画の一般の個数は現在のところ 知られていないため, 漸近的なふるまいは分からない. しかし,我々は, 表7.2に示 した結果から, よりコンパクトな符号が存在すると予想している. 本研究の今後の 課題はより短い符号を設計することである. さらには, より短く, かつ高速にクエ リの解を求めることができるような符号を設計することも今後の課題である. ま た, 一般に, f 面をもつ底辺つき方形描画の個数に対する数え上げを行うことも今 後の課題である. もし, その個数が分かったならば, 底辺つき方形描画の符号の長 さに対する下界を示せたことになる.
次に,極大平面グラフに関する今後の課題について述べる.
クエリを考慮した極大平面グラフの符号として現在最良の結果[2]は,高々(lgn)/4 個の点をもつ全ての極大平面グラフのカタログをo(n) bitの補助テーブルに保存 する. カタログを作成するために多くの計算時間を必要とし, それを保存するため に膨大な記憶領域を必要としてしまうため, 実装には不向きであると考えられる.
一方, 我々が与えた極大平面グラフに対する符号は簡単なので実装しやすい. 実際 に, プログラムとして我々の符号化手法を実装し,実験的に我々の符号の有用性を 検証することが今後の課題である. 極大平面グラフは応用範囲が広いグラフクラ スであるため実装がまたれている.
96 第7章 まとめと今後の課題 その他に, より実用的な補助テーブルを提案することも今後の課題である. 補題
4.2.1で示した通り, 長さが2nの符号に, サイズがo(n) bit の補助テーブルを追加
したならば,様々な命令をO(1)時間で計算できるという結果がある. この補助テー ブルのサイズは, 理論的にはo(n) bitであるが,隠された定数係数は比較的大きく, 例えば, 符号の長さが数ギガバイトのとき, 補助テーブルのサイズは非常に大きく なると予想されている. したがって,実用的な長さの符号に対してコンパクトな補 助テーブルを新たに設計することが, 今後の課題である. 現在, 我々はこれらの課 題に既に取り組んでいる.
97
謝辞
本研究を進めるにあたり, 多大なるご指導, ご鞭撻を賜りました群馬大学 工学部 情報工学科 中野眞一 教授に深く感謝いたします. 中野眞一 教授の懇切丁寧にご 指導する姿は,私にとって,教育者,研究者としての鏡でした. そのご指導のもとで 研究に励めたということは私の人生においてかけがえのないものです. 心から感 謝いたします.
また，本論文の副査をお引き受け頂いた群馬大学 工学部 情報工学科 柴田幸夫 教授, 横尾英俊 教授, 山崎浩一 准教授, 天野一幸 准教授には, 本論文を査読して 頂き貴重な助言を数多く賜りましたこと, ここに深く感謝, 御礼申し上げます. 天 野一幸 准教授にはリサーチプロポーザルをご指導いただき, 特筆して感謝いたし ます.
特別研修では, McGill University Computer Science, David Avis 教授にお世話 になりました. 研究面, 生活面ともに多大なる助けを頂き, 非常に有意義な時間を 過ごすことができました. ここに, David Avis教授に心からの感謝を意を表します.
さらに,日頃からお世話になっております情報数理工学講座 大澤新吾 助手, 鏑 木喜雄 技官, 情報数理工学講座第三研究室の方々,情報数理工学講座第二研究室の 方々に感謝いたします.
情報数理工学講座の先輩である津山工業高等専門学校 情報工学科菊地洋右 講師 には研究面でも生活面でも多くのご指導をしていただきました. 整数分割の符号 に関する結果は菊地洋右 講師のご指導によるものです. ここに, 菊地洋右 講師に 感謝の意を表します. 同じく, 情報数理工学講座の先輩である川野晋一郎 氏には, 多くの議論をともにして頂き,本研究の完成への大きな助けとなりました. とくに, 整数分割の符号に関する結果は川野晋一郎 氏のご指導によるものです. 川野晋一 郎氏に深く感謝いたします.
博士後期課程への進学や, カナダにおける特別研修が無事に終了したことなど, 多くのことを我が子のように喜び,祝っていただいた清水ご夫妻に感謝いたします.
情報数理工学講座の卒業生である吉井訓史 氏, 金子達也 氏, 千明大介 氏には, 学部, 博士前期課程時にとくにお世話になりました. 彼等との議論なくしては本研 究の完成は成し得なかったはずです. ちょうどn面をもつ方形描画の符号に関す る研究は, 吉井訓史 氏と千明大介 氏との共同研究です. 深く感謝いたします.
98 第7章 まとめと今後の課題 最後に, 長きにわたる学生生活を支え, 暖かく見守り続けてくれた両親と, ここ で名を挙げられなかった多くの方々に深く感謝します.
99
参考文献
[1] L.C. Aleardi, O. Devillers and G. Schaeffer, Succinct Representation of Trian-gulations with a Boundary, Proceeding of the 9th International Workshop on Algorithms and Data Structures, (WADS2005), Lecture Notes in Computer Science, vol.3608, pp.134–145, 2005.
[2] L.C. Aleardi, O. Devillers and G. Schaeffer, Optimal Succinct Representations of Planar Maps,Proceeding of the 22th Annual Symposium on Computational Geometry, (SCG2006), pp.309–318, 2006.
[3] D.A. Benoit, E.D. Demaine, J.I. Munro and V. Raman, Representing Trees of Higher Degree, Proceeding of the 6th International Workshop on Algo-rithms and Data Structures, (WADS1999), Lecture Notes in Computer Sci-ence, vol.1663, pp.169–180, 1999.
[4] D.A. Benoit, E.D. Demaine, J.I. Munro, R. Raman, V. Raman and S.S. Rao Representing Trees of Higher Degree,Algorithmica, vol.43, pp.275–292, 2005.
[5] A. Chanda and A. Garg, Compact Encodings of Planar Orthogonal Draw-ings, Proceeding of the 10th International Symposium on Graph Drawing, (GD2002), Lecture Notes in Computer Science, vol.2528, pp.174–186, 2002.
[6] Y.T. Chiang, C.C. Lin and H.I. Lu, Orderly Spanning Trees with Applications to Graph Encoding and Graph Drawing,Proceeding of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA2001), pp.506–515, 2001.
[7] Y.T. Chiang, C.C. Lin and H.I. Lu, Orderly Spanning Trees with Applica-tions, SIAM Journal on Computing vol.34, pp.924–945, 2005.
[8] M. Chrobak and S. Nakano, Minimum-width Grid Drawings of Plane Graphs, Computational Geometry, vol.11, pp.29–54, 1998.
100 第7章 まとめと今後の課題 [9] R.C.N. Chuang, A. Garg, X. He, M.Y. Kao and H.I. Lu, Compact Encodings of Planar Graphs via Canonical Orderings and Multiple Parentheses, Pro-ceeding of the 25th International Colloquium on Automata, Languages, and Programming, (ICALP1998), Lecture Notes in Computer Science vol.1443, pp.118–129, 1998.
[10] D. Clark, Compact Pat Trees, Ph. D, thesis, Department of Computer Sci-ence, University of Waterloo, 1998.
[11] R.R. Geary, R. Raman and V. Raman, Succinct Ordinal Trees with Level-Ancestor Queries,ACM Transactions on Algorithms, vol.2, no.4, pp.510–534, 2006.
[12] R.L. Graham, D.E. Knuth and O. Patashnik,Concrete Mathematics, 2nd ed., Addison-Wesley, 1994.
[13] F. Harary and E. Palmer,Graphical Enumeration, Academic Press, New York, 1973.
[14] X. He, On Floor-Plan of Plane Graph, SIAM Journal on Computing, vol.28, pp.2150–2167, 1999.
[15] X. He, M.Y. Kao and H.I. Lu, Linear-Time Succinct Encodings of Planar Graphs, SIAM Journal on Discrete Mathematics, vol.12, no.3, pp.317–325, 1999.
[16] X. He, M.Y. Kao and H.I. Lu, A Fast General Methodology for Information-Theoretically Optimal Encodings of Graphs, SIAM Journal on Computing, vol.30, pp.838–846, 2000.
[17] G. Jacobson, Space-efficient Static Trees and Graphs, Proceeding of the 30th IEEE Symposium on Foundations of Computer Science, (FOCS1989), pp.549–554, 1989.
[18] G. Jacobson, Succinct Static Data Structures,Ph. D, thesis, CMU-CS-89-112, Carnegie Mellon University, 1989.
[19] G. Kant, Drawing Planar Graphs Using the Canonical Ordering, Algorith-mica, vol.16, pp.4–32, 1996.
7.2. 今後の課題 101 [20] S. Kawano and S. Nakano, Constant Time Generation of Set Partitions,
IE-ICE Transaction on Fundamentals, vol.E88-A, no.4, pp.930–934, 2005.
[21] S. Kawano and S. Nakano, Generating All Series-parallel Graphs, IEICE Transaction on Fundamentals, vol.E88-A, no.5, pp.1129–1135, 2005.
[22] K. Keeler and J. Westbrook, Short Encodings of Planar Graphs and Maps, Discrete Applied Mathematics, vol.58, no.3, pp.239–252, 1995.
[23] Z. Li and S. Nakano, Efficient Generation of Plane Triangulations without Repetitions, Proceeding of the 28th International Colloquium on Automata, Languages, and Programming, (ICALP2001), Lecture Notes in Computer Sci-ence, vol.2076, pp.433–443, 2001.
[24] Z. Li and S. Nakano, Listing All Connected Plane Triangulations, IEICE Transaction on Fundamentals, vol.E86-A, no.7, pp.1807–1812, 2003.
[25] J.I. Munro and V. Raman, Succinct Representation of Balanced Parentheses, Static Trees and Planar Graphs, Proceeding of the 38th IEEE Symposium on Foundations of Computer Science, (FOCS1997), pp.118–126, 1997.
[26] J.I. Munro and V. Raman, Succinct Representation of Balanced Parentheses and Static Trees, SIAM Journal on Computing, vol.31, no.3, pp.762–776, 2001.
[27] J.I. Munro and S.S. Rao, Succinct Representations of Functions,Proceeding of the 31st International Colloquium on Automata, Languages and Computation, (ICALP2004), Lecture Notes in Computer Science, vol.3142, pp.1006–1015, 2004.
[28] M. Naor, Succinct Representations of General Unlabeled Graphs, Discrete Applied Mathematics, vol.28, pp.303–307, 1990.
[29] S. Nakano, Enumerating Floorplans with n Rooms, Proceeding of the 12th International Symposium on Symbolic and Algebraic Computation, (IS-SAC2001), Lecture Notes in Computer Science, vol.2223, pp.107–115, 2001.
[30] S. Nakano, Enumerating Floorplans with n Rooms, IEICE Transaction on Fundamentals, vol.E85-A, no.7, , pp.1746–1750, 2002.
102 第7章 まとめと今後の課題 [31] S. Nakano, Enumerating Floorplans with Some Properties, Interdisciplinary
Information Sciences, vol.8, no.2, pp.199–206, 2002.
[32] S. Nakano, Efficient Generation of Plane Trees, Information Processing Let-ters, vol.84, pp.167–172, 2002.
[33] S. Nakano, Efficient Generation of Triconnected Plane Triangulations, Com-putational Geometry Theory and Applications, vol.27, no.2, pp.109–122, 2004.
[34] S. Nakano and T. Uno, Constant Time Generation of Trees with Specified Diameter, Proceeding of the 30th Workshop on Graph-Theoretic Concepts in Computer Science, (WG2004), Lecture Notes in Computer Science, vol.3353, pp.33–45, 2004.
[35] S. Nakano and T. Uno, Generating Colored Trees, Proceeding of the 30th Workshop on Graph-Theoretic Concepts in Computer Science, (WG2005), Lecture Notes in Computer Science, vol.3787, pp.249–260, 2005.
[36] C. Papadimitriou and M. Yannakakis, A Note on Succinct Representations of Graphs, Information and Control, vol.71, pp.181–185, 1986.
[37] D. Poulalhon and G. Schaeffer, Optimal Coding and Sampling of Triangu-lations, Proceeding of the 30th International Colloquium on Automata, Lan-guages, and Programming, (ICALP2003), Lecture Notes in Computer Science, vol.2719 pp.1080–1094, 2003.
[38] D. Poulalhon and G. Schaeffer, Optimal Coding and Sampling of Triangula-tions, Algorithmica, vol.46, no.3, pp.505–527, 2006.
[39] K.H. Rosen (Eds.), Handbook of Discrete and Combinatorial Mathematics, CRC Press, Boca Raton, 2000.
[40] J. Rossignac, Edgebreaker: Connectivity Compression for Triangle Meshes, IEEE Transaction on Visualization and Computer Graphics, vol.5, pp.47–61, 1999.
[41] W. Schnyder, Embedding Planar Graphs on the Grid, Proceeding of the Annual 1st ACM-SIAM Symposium on Discrete Algorithms, (SODA1990), pp.138–147, 1990.
7.2. 今後の課題 103 [42] 高木正博, 中野眞一, いくつかの特徴をもつ方形描画の列挙, 電子情報通信学
会論文誌DI, vol.J86-DI, no.4, pp.208–216, 2003.
(英訳) Listing All Rectangular Drawings with Certain Properties, SYSTEMS and COMPUTERS in JAPAN, vol.35, no.4, pp.1–8, 2004.
[43] 高木正博, 中野眞一, L字形描画の列挙,電子情報通信学会論文誌DI, vol.J87-DI, no.1, pp.1–11, 2004.
[44] G. Turan, On The Succinct Representations of Graphs, Discrete Applied Mathematics, vol.8, pp.289–294, 1984.
[45] W. Tutte, A Census of Planar Triangulations, Canadian Journal of Mathe-matics, vol.14, pp.21–38, 1962.
[46] W. Tutte, A Census of Planar Maps, Canadian Journal of Mathematics, vol.15, pp.249–271, 1963.
[47] D.B West, Introduction to Graph Theory, 2nd edition. Prentice Hall, 1996.
[48] K. Yamanaka, S. Kawano, Y. Kikuchi, and S. Nakano, Constant Time Gener-ation of Integer Partitions, IEICE Transaction on Fundamentals, vol.E90-A, no.5, pp.888–895, 2007.
[49] 山中克久,中野眞一, リアライザの列挙,電子情報通信学会論文誌DI, vol.J87-DI, no.12, pp.1043–1053, 2004.
(Also in) K. Yamanaka and S. Nakano, Generating All Realizers, Electronics and Communication in Japan, Part2, vol.89, no.7, pp.40–47, 2006.
[50] K. Yamanaka and S. Nakano, Coding Floorplans with Fewer Bits, IEICE Transactions on Fundamentals, vol.E89-A, no. 5, pp.1181–1185, 2006.
[51] K. Yamanaka and S. Nakano, Compact Encoding of Plane Triangulations
with Efficient Query Support, 情報処理学会 第101回アルゴリズム研究会,
2005-AL-101-6, pp.35–42, 2005.
[52] K. Yamanaka and S. Nakano, A Compact Encoding of Rectangular Drawings with Efficient Query Supports, Proceeding of the 3rd International Confer-ence on Algorithmic Aspects in Information and Management, (AAIM2007), Lecture Notes in Computer Science, vol.4508, pp.68–81, 2007.
104 第7章 まとめと今後の課題 [53] S. Yoshii, D. Chigira, K. Yamanaka and S. Nakano, Constant Time Gener-ation of Rectangular Drawings with Exactly n Faces, IEICE Transaction on Fundamentals, vol.E89-A, no.9, pp.2445–2450, 2006.
[54] 吉井訓史,中野眞一,方形描画の数え上げ,電子情報通信学会論文誌A, vol.J88-A, no.8, pp.945–952, 2005.
105
付 録 A rank 命令
本節では, 2進符号Sに, o(n)ビットの補助テーブルSAを追加することにより, Sのrank(i)の値をO(1)時間で計算する方法を紹介する. 詳細は, [10, 17, 18]等を 参照されたい. 本節は, [10]で紹介された方法を説明する.
Sは‘0’と‘1’からなる符号する. 直感的に,rank(i)とは符号Sの先頭からi文字 目までに現れる‘1’の個数である. 形式的な定義は次のようになる. i文字目からj 文字目までのSの部分符号をS[i, j]と書く. このとき, rank(i)とはS[1, i]中の‘1’
の個数である. 例えば, S =((())(()(()))()())ならばrank(6) = 4である.
アルゴリズムの主なアイデアは次のようなものである.
‘0’と‘1’からなる2進符号Sとiが与えられたとする. Sの長さをnとする. 符 号Sをいくつかのブロックに分割する. iを含むブロックをBとする. このとき, rank(i)の値は
(1) Sの先頭からBの先頭までの‘1’の個数と, (2) Bの先頭からiまでの‘1’の個数
の和である. O(1)時間で(1)の値を得るために, 各ブロックに対して, Sの先頭か らそのブロックの先頭までの‘1’の個数をテーブルに保存しておく. このように前 処理しておくことで(1)の値を高速に得ることができる. 次に, (2)の値を求めるこ とを考えよう. (2)の値を高速に計算するために, ブロックBをより小さなブロッ クに分割する. 小さなブロックに関しても同様なテーブルを用意することにより, (2)の値を計算する. 実際のところ, (2)の値を計算するためには, ある長さの全て の符号に対して答えを保存しておくテーブル(ユニバーサルテーブルと呼ばれる) が利用される. 詳細については後述する. このように, Sをブロックに分割するこ とを2段階だけ行うことにより, rank(i)の値を分けて計算することが主なアイデ アである.
それでは, rank(i)を高速に計算する方法を詳細に説明する.
2進符号Sとiが与えられたとする. Sの長さをnとする. はじめに, Sを2段階 に分割することを考えよう.
符号Sを,長さdlgne2 bit のブロックに分ける. この長さのブロックを大ブロッ クと呼ぶことにする. 各大ブロックについて, Sの先頭から大ブロックの先頭のま