修士論文 要旨

Space-Eﬃcient Representations for Algebraic Structures(代数的構造の省メモリ表現)
柳田 達也

数理情報学専攻 48-216232

定兼 邦彦 教授

指導教員

1 はじめに数時間で行う. 長さ N のビットベクトルは N + o(N )ビットで表現される. ストリング [4] は 1, 2, . . . , K のア

本発表では, 半順序集合と束を保持する空間効率の良ルファベットの列で, 同じくランダムアクセスと rank

いデータ構造について述べる. 半順序集合のデータ構造を O(log log K) 時間, select を O(1) 時間でサポートすの応用先として, 仮想通貨や NFT の取引の記録に用いる. 長さ N のとき, 空間計算量は N log K +o(N log K)られるブロックチェーンが挙げられる. また, 束のデービットである.

タ構造の応用先としては, データベース検索やプログラミング言語の継承関係の処理等が例として挙げられる.

3 半順序集合のデータ構造
要素数 n のラベル付き半順序集合を格納するのに2 準備2必要な空間の情報理論的下限は, n4 + 23 n + O(log n)

反射律, 反対称律, 推移律を満たす (P, ≤) を半順序集ビットであることが知られている [5]. また, 幅 w のラ合と言う. 記法として a <: b は, a < b であり, かつベル付き半順序集合に関しては n log n + 2n(w − 1) −a < c < b となる c が存在しないことを言う.

Θ(w2 log n) ビットよりも情報理論的下限が大きい [6].

半順序集合 P のトポロジカルラベリングとは, 全単射トポロジカルラベリングの半順序集合の情報理論的下

写像 l : P → {1, 2, . . . , |P |} であって, a ≤ b ⇒ l(a) ≤限は 2n(w − 1) − Θ(w 2 log n) ビットよりも大きい [7].

l(b) を満たすものである.

2

先行研究として, Munro と Nicholson [8] による n4 +半順序集合 P の Transitive Closure Graph は, 頂o(n2 ) ビットのデータ構造, Farzan と Fischer [9] によ

点集合 P と辺の集合 EC = {(a, b) ∈ P 2 ; a < b} のる (1 + ε)n log n + 2nw + o(nw) ビットのデータ構造がペア GC = (P, EC ) で定義される. また, Transitive知られている. ここで, ε ∈ (0, 1] は任意の定数である.

Reduction Graph は, 頂点集合 P と辺の集合 ER =これらはともにラベル付きの半順序集合を格納する.

{(a, b) ∈ P ; a <: b} のペア GR = (P, ER ) である.
2

本発表ではトポロジカルラベリングの半順序集合を格半 順 序 集 合 (P, ≤) の チ ェ ー ン 分 解 と は, P =納するデータ構造を 3 つ提案する. これは SWAT 2022

i=1 Ci かつ各 Ci が ≤ に関して全順序となるような {Ci }ki=1 である. k として取り得る値の最小値をで発表された内容である [7]. {Cp }w
p=1 を最小のチェー

Dilworth の幅 [1], 若しくは単に幅と呼ぶ.

かつ cp,i < cp,i+1 (i = 1, 2, . . . , |Cp | − 1) と定義する.

⨿kン分解とし, 各 Cp に対し Cp = {cp,1 , cp,2 , . . . , cp,|Cp | }可換律, 結合律, 吸収律を満たす (L, ∨, ∧) を束と言

1 つ目のデータ構造は Farzan と Fischer のデータう. ∨ を結び (join), ∧ を交わり (meet) という. 束は構造をトポロジカルラベリングの半順序集合へ応a ∨ b = a ⇔ b ≤ a と順序関係を定義することで半順序用 し た も の で あ る.

集合となる.

ベ ク ト ル Bp,q で 構 成 さ れ る.

これはストリング S とビット

S は S[x] = p ⇔本発表では有限要素数の束のみを考える. この時, 束x ∈ Cp というように定義される. Bp,q は Bp,q =は上で定めた順序関係において最大の元と最小の元を0d1,p,q 10d2,p,q 1 · · · 10d|Cp |,p,q 10dr,p,q と表される. ここで持つ. これらをそれぞれ ⊤, ⊥ と表記する.
束 L における結び既約元とは, x ̸= ⊥ かつ (a ∨ b ⇒0d は 0 が d 個並んだもの, di,p,q = |{x ∈ Cq ; x ≤∑i−1∑|C |cp,i }| − j=1 dj,p,q , dr,p,q = |Cq | − i=1p di,p,q であa = x または b = x) となる x ∈ L を指す. 交わり既約る. これは合計で 2n(w − 1) + o(nw) ビットを要する.

元とは, x ̸= ⊤ かつ (a ∧ b ⇒ a = x または b = x) を満

2 つ目のデータ構造はストリング S とビットベクトたす x である.

ル Ip,q , Op,q からなる. S は上と全く同じように定義

ビットベクトル [2, 3] は 0 または 1 のビット列であされる. また各ビットベクトルは Ip,q [i] = 1 ⇔ ∃x ∈り, ランダムアクセスと rank, select という操作を定Cq , x <: cp,i 及び, Op,q [i] = 1 ⇔ ∃x ∈ Cq , cp,i <: xSpace-Eﬃcient Representations for Algebraic Structures(代数的構造の省メモリ表現) (柳田 達也)となるように格納される. 空間計算量は合計で 2nw +o(nw) ビットとなる.

束におけるクエリとして, 順序関係を調べる lessthan,結びを返す join, 交わりを返す meet の 3 つが挙げられ

3 つ目のデータ構造はストリング S とビットベクトる. それぞれにかかる計算量は表 2 の通りである. なお,ル Bp,q , Tx で構成される. S と Bp,q は 1 つ目のものと2 つ目のデータ構造に関してはこれらのクエリをサポー同じである. Tx は Tx [p] = 1 ⇔ ∃y ∈ Cp , y <: x となトしない.

るように定義される.
半順序集合に関するクエリとして, adjGC , succGC ,predGC , adjGR , succGR , predGR の 6 つを考える. それぞれ, GC における隣接関係, 入力頂点, 出力頂点, GR

表 2. 束の各データ構造の時間/空間計算量の比較.

Space [bits]
lessthan(x, y)における隣接関係, 入力頂点, 出力頂点を求める. 表 1

join(x, y)にそれぞれの計算量を記す.

meet(x, y)

Proposal 1()nJ
O nwJ log w
J)(nJ
O wJ log log w
J()nJ
O wJ log n log log w
J()nJO wJ log log w
J

Proposal 2()nJ
O nM wJ log w
J-表 1. 半順序集合の各データ構造の時間/空間計算量

参考文献の比較.
Proposal 1

Proposal 2

Proposal 3Space [bits]

2n(w − 1) + o(nw)3nw − 2n + o(nk)adjGC (x, y)O (log log w)

predGC (x)O (w + t)

succGC (x)O (w + t)

2nw + o(nw)( )O w2()
O w2 + t)( 2O w +t

adjGR (x, y)

O (w)
( )
O w2
( )
O w2

predGR (x)succGR (x)O (log log w)
O (w + t)O (w + t)

O (log log w)

O (log log w)

O (w)O (log log w + t)

O (w)

O (w)

4 束のデータ構造
要素数 n の束の情報理論的下限は Θ(n1.5 ) ビットであることが知られている [10, 11]. また先行研究として,

Munro ら [12] による O(n1.5 log n) ビットのデータ構造が提案されている. 本発表においては 2 つの新しいデータ構造を提案する.

J, M をそれぞれ結び既約元, 交わり既約元の集合,nJ = |J|, nM = |M | とする. また, J は半順序集合であるから幅が定義できて, それを wJ と表す. J の最J
小のチェーン分解を {Cp }w
p=1 , x ∈ J に対して p(x) =q ⇔ x ∈ Cq とする. また, 適当な変数 a1 , a2 , . . . , awJを導入する.
この時, 束の元 x ∈ L を Enc(x) =∏y∈J, y≤x ap(y)という単項式としてエンコードする. これは既知 [13]の埋め込み L →∏ wJ

p=1 Ci と本質的に等しい.

これを全ての元に関して, 保持することで束を表現できる. 具
体的には, ストリング Sp を用いて, Sp [x] が Enc(x) 内の ap の次数を保持する. これが 1 つ目のデータ構造である.

2 つ目のデータ構造では, 交わり既約元のみのエンコードを保持することで束を表現する. これは交わり既約元のみから全ての元を復元できる [14] ことに由来する.

[1] R.P. Dilworth, A Decomposition Theorem for Partially Ordered Sets, Annals of Mathematics, 51(1),1950.
[2] G.J. Jacobson, Succinct Static Data Structures,
Ph.D Thesis, Carnegie Mellon University, 1988.
[3] A. Brodnik, J.I. Munro, Membership in ConstantTime and Almost-Minimum Space, SIAM Journal
on Computing, 28(5), 1999.
[4] A. Golynski, R. Raman, S. S. Rao, On the Redundancy of Succinct Data Structures, In Proceedingsof 11th Scandinavian Workshops on Algorithm Theory, 2008.
[5] D.J. Kleitman, B.L. Rothschild, Asymptotic Enumeration of Partial Orders on a Finite Set, Transactions of the American Mathematical Society, 205,
1975.
[6] G. Brightwell, S. Goodall, The Number of Partial
Orders of Fixed Width, Order, 13, 1996.
[7] T. Yanagita, S. Chakraborty, K. Sadakane, S.R.
Satti, Space-Eﬃcient Data Structures for Posetswith Applications, In Proceedings of 18th Scandinavian Symposium and Workshops on Algorithm
Theory, 2022.
[8] J.I. Munro, P.K. Nicholson, Succinct Posets, Algorithmica, 76, 2016.
[9] A. Farzan, J. Fischer, Compact Representation ofPosets, In Proceeding of the 22nd International
Symposium on Algorithms and Computation, 2011.
[10] W. Klotz, L. Lucht, Endliche Verbände, Journal
Für die Reine und Angewandte Mathematik, 247,1971.
[11] D.J. Kleitman, K.J. Winston,
The Asymptotic
Number of Lattices, Annals of Discrete Mathematics, 6, 1980.
[12] J.I. Munro, B. Sandlund, C. Sinnamon,
SpaceEﬃcient Data Structure for Lattices, In Proceedingsof 17th Scandinavian Symposium and Workshops on
Algorithm Theory, 2020.
[13] M. Siggers, On the Representations of Finite Distributive Lattices, arXiv:1412.0011v2, 2016.
[14] G. Birkhoﬀ, O. Frink, Representations of Lattices
by Sets, Transactions of the American Mathematical Society, 1948.