文脈自由文法による構文木の集合を表現する
決定グラフの高速な構築
Efficient Construction of Decision Diagrams Representing the Set of
All Parse Trees of a Context-free Grammar
網井 圭
1∗西野 正彬
2山本 章博
1Kei Amii
1Masaaki Nishino
2Akihiro Yamamoto
11
京都大学大学院情報学研究科
1
Graduate School of Informatics, Kyoto University
2
NTT コミュニケーション科学基礎研究所
2
NTT Communication Science Laboratories
Abstract: In this paper, we propose an algorithm for constructing decision diagrams (DD) representing the set of all parse trees of a context-free grammar (CFG). CFG is widely used in the field of natural language processing and bioinformatics to estimate the hidden structures of sequence data. A DD is a data structure that represents a Boolean function in a concise form. We propose an efficient method to construct ZSDDs, one of DD variants, representing the set of all parse trees based on CYK (Cocke-Younger-Kasami) algorithm. This method runs with a small number of binary operations. We show that the method can construct such ZSDDs much faster than naive method based on compiling a Boolean function by experiments.
1
はじめに
文脈自由文法は記号列の構造を決定するモデルとし て幅広く使用されている．代表的な使用例として，自 然言語処理における文章の係り受け構造の解析 [1] や， 生命情報学における RNA の二次構造の解析 [2] が挙げ られる． ある記号列が与えられた文脈自由文法からどのよう に生成されるか，すなわちどのような構文木が得られる かを求める手法として CYK(Cocke-Younger-Kasami) アルゴリズムが知られている．CYK アルゴリズムでは， 記号列の長さを n，文法に含まれる規則の数を|P | と すると，動的計画法によって O(|P |n3) の計算時間で構 文木の集合を生成できる．一方で，何らかの追加の制 約条件を満たすような構文木の集合を求めたい場合に は，CYK アルゴリズムを適用することができない．こ こで追加の制約条件とは，ある生成規則の使用回数に 制限をつけたり，特定の規則の組が同時に使われない といった条件のことである．このような制約条件を考 慮できると，問題分野特有の背景知識を加味した解析 が容易に行える．例えば自然言語処理においては，あ ∗連絡先：京都大学大学院情報学研究科 〒 606-8501 京都市左京区吉田本町 E-mail: [email protected] る品詞の出現回数が制限される，特定の部分の品詞が 同じであるといった背景知識を加味した構文解析を行 うことができる．同様に，生命情報学においては結合 位置間の距離など構造に関する背景知識が既知の場合 にそれを考慮できる． 筆者らは，文献 [3] において決定グラフを用いること で様々な制約が課されたうえで文脈自由文法による解 析を行う方法を示した．決定グラフとはブール関数を 表現するデータ構造であり，ブール関数に対する様々 な演算をグラフの大きさに比例した時間で実行できる． 文脈自由文法において，どの部分記号列がどの生成規 則により生成されたかを命題変数で表すことにより，あ る記号列に対する構文木集合はブール関数を用いて表 現することができる．そのため構文木集合を決定グラ フで表現することができ，制約を追加するなどの演算 や，制約を満たす最適な構文木の探索などを高速に実 行することができる．決定グラフを用いたブール関数 操作の計算時間は，ブール関数を表現する決定グラフ の大きさに比例することが知られている．決定グラフ には二分決定図 (Binary Decision Diagram, BDD)[4]， ゼロサプレス型二分決定図 (Zero-suppressed Binary Decision Diagram, ZDD)[5]，項分岐決定図 (Sentential Decision Diagram, SDD)[6]，ゼロサプレス型項分岐決 定図 (Zero-suppressed Sentential Decision Diagram,人工知能学会研究会資料 SIG-FPAI-B508-02
ZSDD)[7] といったいくつかの種類がある．あるブール 関数を表現する際にどの決定グラフを用いると大きさ が最小になるかは表現するブール関数に依存するが，構 文木集合を表現する場合には ZSDD が最小になること が実験的に示されている [3]． 先行研究では決定グラフの大きさについての議論が された一方で，効率的な構築法については言及されて いなかった．実際に決定グラフを用いて解析を行うた めには構築にかかる時間が重要である．そこで本稿で は効率的な構築方法について述べる．論理式が与えら れたとき，ZSDD 間の Apply 演算によってボトムアッ プに構築することができる．構文木の集合を表す論理 式をまず求めたのちに，それに対応する ZSDD を構築 する場合，O(|P |2n4) 回の演算が必要となる．本稿で は CYK アルゴリズムに沿った演算を行うことにより， O(|P |n3) 回の演算で効率的に ZSDD を構築する方法 を提案する．この提案法により大幅な高速化が達成で きることを実験により示す． 本稿は以下のように構成される．第 2 章では準備と して文脈自由文法と決定グラフについて解説し，第 3 章では決定グラフの構築法について述べる．第 4 章で は実験により 2 種類の構築法での決定グラフの構築時 間を比較し，CYK アルゴリズムに沿った構築法が高速 に動作することを示す．最後に第 5 章ではまとめと今 後の展望を述べる．
2
準備
2.1
文脈自由文法
定義 2.1 文脈自由文法 (context-free grammar, CFG) は，非終端記号の有限集合 V ，終端記号の有限集合 Σ， 生成規則の有限集合 P ，開始記号 S を指定することに より規定される文法 G = (V, Σ, P, S) (1) のうち，生成規則が次の形式となっているものである． A→ α (A ∈ V, α ∈ (Σ ∪ V )∗) (2) S から生成規則の適用を繰り返し w ∈ Σ∗が生成さ れるとき，記号列 w は文法 G により導出されるという．2.2
(X, Y)-分解
紙面の都合上，以下では決定グラフのうち ZSDD を 紹介する．なお，ZSDD は集合族を表現する決定グラ フとして導入されたが，集合族とブール関数は等価で あるため，ZSDD はブール関数を表現するためにも使 える． 3 1 5 B 0 A 2 D 4 C 6 (a) A vtree 1 B A 3 ε B ±C ε 5 D C (b) A ZSDD図 1: (a) vtree の例, (b) (a) の vtree を参照し，集合 族 {{A, B}, {B}, {B, C}, {C, D}} を表現する ZSDD (X, Y)-分解は与えられた集合族を小さな集合族に分 割する手法であり，決定グラフを構成する重要な技術 である．f を集合族，X, Y をそれぞれ要素の集合であ り，全体集合の分割となっているとする．集合族 f は， X, Y を全体集合とする集合族 pi(X), si(Y) によって， f = [p1(X)⊔ s1(Y)]∪ · · · ∪ [pn(X)⊔ sn(Y)], として表現される．記号∪, ⊔ は集合族に対する union， join 演算を表し，それぞれ f∪g = {a | a ∈ f または a ∈ g}, f ⊔ g = {a ∪ b | a ∈ f かつ b ∈ g} として定義され る．p1, . . . , pnを (X, Y)-分解における主部，p1, . . . , pn を副部と呼ぶ．もし主部が排他的 (すべての i̸= j につ いて pi∩ pj =∅) かつ網羅的 ( ∪n i=1pi) かつ無矛盾 (す べての i について pi̸= ∅) であるならば，その (X, Y)-分解を (X, Y)-分割と呼び，(p1, s1), . . . , (pn, sn) とし て表現する．さらに，すべての i̸= j について si̸= sj を満たすならば (X, Y)-分割は圧縮されていると呼ぶ． 例えば，集合族{{A, B}, {B}, {B, C}, {C, D}} の X = {A, B}, Y = {C, D} としたときの (X, Y)-分割は [{{A, B}}⊔{∅}]∪[{{B}}⊔{∅, {C}}]∪[{∅}⊔{{C, D}}], である．ここで {{A, B}}, {{B}}, {∅} が主部であり， {∅}, {∅, {C}}, {{C, D}} が副部である．
2.3
vtree
(X, Y)-分割と並んで ZSDD を構成する重要な概念 である vtree を導入する．ZSDD は集合族に対して再 起的に (X, Y)-分割を適用することで有向非巡回グラフ の形に集合族を分解して表現する手法である．すなわ ち，与えられた集合族を，(X, Y)-分割によって X, Y を 全体集合とする集合族 p1, . . . , pn, s1, . . . , snに分解し， さらにそれらを (X, Y)-分割によって部分集合族に分割 する…という手続きを表現したものが ZSDD である． vtree は再起的な (X, Y)-分割の順序を与えるものであ り，ある vtree に沿った (X, Y)-分割を表現する ZSDD を作成すると，一意な ZSDD を構成できる．vtree は各節が必ず 2 つの子を持つような根付き二分木であり， vtree の各葉が全体集合に含まれる各要素に対応してい る．図 1(a) に vtree の例を示す．図中の葉は対応する 変数を表現しており，節の数字は ID を表している．各 節には一意な ID が付与されている． vtree の節は，全体集合に含まれる要素を，左側の子 を根とする木に含まれる要素の集合と右側の子を根と する木に含まれる要素の集合の 2 つの集合に分割してい るとみなすことができる．図中の根 v3は，X ={A, B} かつ Y であるような (X, Y)-分割を表している．同様 に v3の左側の子 v1も，v1を根とする部分木において X ={B} かつ Y = {A} であるような (X, Y)-分割を 表している．以下では vl, vrがそれぞれ v の左側の子， 右側の子を表しているものとする．また，それぞれの 頂点の根とする部分木を表すためにも vl, vrを用いる． もし vlが葉であるとき，v をシャノンノードと呼び， そうでない場合に分解ノードと呼ぶ．図 1(a) の根は分 解ノードであり，その子はどちらもシャノンノードで ある．また，全ての頂点がシャノンノードであるとき， その vtree を right-linear-vtree と呼ぶ． なお，以下では入力グラフ，vtree，ZSDD の 3 種類 のグラフを扱うため，混乱を避けるために vtree の頂 点を vnode と呼び，v, vl, vr, v 1, v2, . . . などと表す．同 様に，入力グラフの頂点は gnode と呼び，u, u1, u2, . . . などと表す．後述する ZSDD の頂点は znode と呼び， z1, . . . , znなどと表す．
2.4
ゼロサプレス型項分岐決定図 (ZSDD)
ZSDD とは集合族をグラフとして表現するデータ構 造であり，多数の要素からなる集合族を圧縮して表現で きる．ZSDD を以下のように再帰的に定義する．なお， α を ZSDD とし，α が表現する集合族を⟨α⟩ とする． 定義 2.2 α は以下のいずれかの条件を満たすとき，vn-ode v を参照する ZSDD と呼ぶ． • α = ϵ または α = ⊥．(解釈: それぞれ ⟨ϵ⟩ = {∅}， ⟨⊥⟩ = ∅) • α = X または α = ±X かつ v が要素 X に対応 する vtree の葉．(解釈: それぞれ⟨X⟩ = {{X}}， ⟨±X⟩ = {{X}, ∅}) • α = {(p1, s1), . . . , (pn, sn)}，v は vnode，(p1, . . . pn) がそれぞれ部分 vnode vlを参照する ZSDD，s 1, . . . sn が vnode vrを参照する ZSDD，かつ⟨p 1⟩, . . . ⟨pn⟩ が (X, Y)-分割の条件を満たす集合族に対応して いる．(解釈: ⟨α⟩ =∪n i=1⟨pi⟩ ⊔ ⟨si⟩) ここで，ϵ,⊥, X, ±X を終端 ZSDD と呼ぶ．終端 ZSDD でない ZSDD は，vnode v によって表されている (X, Y)-分割 {(p1, s1), . . . , (pn, sn)} を表しており，決定ノー ドと呼ぶ．図 1(b) は図 1 の vtree を参照し，集合族 {{A, B}, {B}, {B, C}, {C, D}} を表す ZSDD である． 図中の円ノードと，その子ノードである四角いノード とあわせて決定ノードを表現している．円ノード中の 数字はその決定ノードが参照している vnode の ID で ある．四角い子ノードは (X, Y)-分割に含まれる主部， 副部のペアを表現しており，左側が主部，右側が副部 である． ZSDD の特徴的な機能として Apply 演算がある．Ap-ply 演算は 2 つの ZSDD に対してそれぞれが表現する集 合族間の二項演算を実行し，結果の ZSDD を生成する 演算である．例えば集合族の和集合は f∪ g = {a | a ∈ f または a∈ g} として定義されるが，f と g とのそれ ぞれを表す ZSDD を入力として Apply 演算を実行する ことで，集合族の和 h = f∪ g を表す ZSDD を得るこ とができる．なお，以下では和のほかにも集合族の直 積を計算する演算 f⊔ g = {a ∪ b | a ∈ f かつ b ∈ g} も 用いる．3
ZSDD
の効率的な構築法
3.1
ブール関数による表現
構文木の集合は，適切な命題変数を導入することに よってブール関数として表現することができる．構文 木での生成規則の出現に対して命題変数 bijlを導入す る．終端記号の系列の i 文字目から j 文字目までから なる部分系列を αijとしたとき，αijが l 番目の生成規 則 qlから生成される場合に bijl= 1 となる．構文木集 合を現す集合族は，あるブール関数を満たすモデルと して定義することができる． それぞれの記号列 αijは高々1 つの生成規則により導 出される．そのため各命題変数 bij∗のうち，二つ以上 が同時に真にならない制約が必要となり，その制約を Hij = ∧ bijk,bijl:j̸=k ¬bijk∨ ¬bijl (3) と表す．次に，αijに対する非終端記号 X を開始記号 とする導出において，最初に利用された生成規則のイ ンデックスの集合を S(X) ij とする．各集合 S (X) ij の規則 のうちいずれかが真となる制約は， Fij(X)= ∨ k∈S(X)ij bijk (4) となる．また，qk= (X → Y Z) に対して， Dijk=¬bijk∨ (j−1 ∨ l=i Fi,l(Y )∧ Fl+1,j(Z) ) (5)Time flies like an arrow like an arrow 前置詞 冠詞 名詞 前置詞句 名詞句 Time 名詞 (a) CYK テーブル
Time
flies
like
an
arrow
like an arrow
前置詞 冠詞 名詞
前置詞句
名詞句
Time
名詞
(b) Z 11名詞Time
flies
like
an
arrow
like an arrow
前置詞 冠詞 名詞 前置詞句 名詞句Time
名詞 (c) Z35前置詞句図 2: 記号列 Time flies like an arrow に対する CYK テーブルと部分記号列に対する構文木の例．通常，それぞ れのセルは部分記号列を生成し得る非終端記号を表す．本研究ではセル中の各非終端記号が一つの ZSDD を表す ものとする． とする．最後に，i < k ≤ j < l であるような全ての bijs, bkltに対して， C = ∧ bijs,bklt:i<k≤j<l ¬bijs∨ ¬bklt (6) とする．これらの式を用いると，正しい導出に対応す る規則の集合が与えられた時に真を返すブール関数は， ∧ i,j:1≤i<j≤n Hij ∧ ∧ bijk Dijk ∧ C (7) として表現することができる．
3.2
素朴な構築方法
式 (7) に従って決定グラフを素朴な方法で構築する ことができる．それぞれのリテラルについての決定グ ラフを構築し，式中の∧, ∨ に従い Apply 演算を繰り 返すことでボトムアップに構築できる．ここで，必要 な演算の回数は式中の演算子の個数に一致する．式 (6) において全ての規則と位置の組み合わせについて演算 を行う必要があるので，その回数は O(|P |2n4) となる． 次節では，CYK アルゴリズムに従い O(|P |n3) 回の 演算で決定グラフを構築する方法を述べる．なお，一 度の Apply 演算に必要な計算量は入力となる 2 つの決 定グラフの大きさに依存するため，単純に演算の回数 だけで計算量を比較することはできない．そのため，構 築にかかる時間については第 4 章で実験的に比較する．3.3
CYK アルゴリズムに沿った構築方法
CYK アルゴリズムは，与えられた記号列と文法に 対して，記号列がどのように文法から生成されるかを O(|P |n3) の計算時間で求めるアルゴリズムである．図 2(a) のような CYK テーブルを左下から順に埋めてい くことにより解析を行う．例えば最右列の上から 3 段 目のセルには動詞句と前置詞句が含まれているが，こ れは like an arrow という記号列が動詞句または前置詞 句から生成され得ることを表す．CYK アルゴリズムは チョムスキー標準形の文脈自由文法についてのみ解析 を行うことができるが，任意の文脈自由文法はチョム スキー標準形に変換することができる． この CYK アルゴリズムに沿って Apply 演算を行う ことで ZSDD を構築する．つまり，CYK テーブルにお いてセル中の各非終端記号が一つの ZSDD に対応する と考え，ボトムアップに構築を行う．ZijAを非終端記 号 A から i 番目から j 番目の終端記号列を生成するよ うな構文木集合を表す ZSDD とおく．一つの ZSDD は 2(b)(c) のように部分的な構文木を表す．i = j のとき， ⟨ZiiA⟩ = ∪ qk=(A→αi) {{biik}}. (i = j) (8) i < j のとき， ⟨ZijA⟩ = ∪ qk=(X→BC) s.t.X=A ( j∪−1 r=i (⟨ZirB⟩⊔⟨Zr+1jC⟩)⊔{{bijk}}) (9) が成り立つ． CYK アルゴリズムに沿って式 (8), (9) の ZSDD を 構築する具体的な方法を Alg.1 に示す． 終端記号 αiと規則 A→ αiがあるとき，ZiiAは 1-5 行目のように構築される．k 番目の規則が A → αiと いう形になっている場合{biik} は ⟨ZiiA⟩ の要素として 含まれる． ZijA (i < j) は A → BC という形の規則が存在す る場合に ZirB と Zr+1jC を結合して得ることができ る (i≤ r < j)．13 行目のように Apply 演算で 2 つの表 1: 長さ n の記号列に対し構文木を表す ZSDD の構築時間についての実験結果．各行は生成される ZSDD の大 きさ，CNF をコンパイルする素朴な方法での構築時間，CYK アルゴリズムに沿った方法での構築時間を表す．タ イムアウトは 1800 秒とした． (a)G1についての構築時間 n 3 4 5 6 7 8 9 10 11 12 ZSDDの大きさ 6 15 34 78 173 381 825 1772 3785 8067 CNFでの構築時間(秒) 0.740 0.779 0.937 1.162 1.492 2.932 19.592 633.668 - -CYKでの構築時間(秒) 0.301 0.332 0.348 0.321 0.344 0.322 0.349 0.359 0.378 0.396 n 13 14 15 16 17 18 19 20 ZSDDの大きさ 17153 36407 77171 163436 345865 731367 1545431 3263474 CNFでの構築時間(秒) - - - -CYKでの構築時間(秒) 0.560 0.658 1.286 2.797 5.746 12.649 29.351 72.04 (b)G2についての構築時間 n 2 4 6 8 10 12 ZSDDの大きさ(秒) 2 13 64 303 1398 5079 CNFでの構築時間(秒) 0.214 0.532 0.827 5.73 - -CYKでの構築時間(秒) 0.228 0.232 0.231 0.239 0.249 0.356 Algorithm 1 CYK アルゴリズムに沿った ZSDD の 構築 Input: 終端記号列 α1. . . αn と チョムスキー標準形 の文脈自由文法 G = (V, Σ, P, S) Output: 全構文木の集合を表す ZSDD 1: for i = 1 to n do 2: for A∈ V do 3: ZiiA← ∅ 4: for qk= A→ αi, qk∈ P do
5: ZiiA ← ZiiA∪ {biik}.
6: for t = 1 to n do 7: for i = 1 to n− t do 8: j← i + t. 9: for A∈ V do 10: ZijA← ∅. 11: for r = i to j− 1 do 12: for qk= A→ BC, qk ∈ P do
13: ZijA← ZijA∪(ZirB⊔Zr+1jC⊔{bijk}).
14: Return Z1nS. ZSDD の表す集合族の直積を求めることにより結合を行 う．集合族の直積 h = f⊔g = {a∪b | a ∈ f かつ b ∈ g} について，f 中の集合と g 中の集合の全組み合わせが h の要素に対応する．いま，ZSDD が表す集合族に含ま れるそれぞれの集合は一つの構文木に対応する．よっ て ZirB⊔ Zr+1jCは構文木の可能な全組み合わせを表 すことになり，それらを結合するための規則に対応す る変数 bijkを各集合に加えることで ZijAの要素が得 られる． 以上の操作により，全体の構文木を表す Z1nSを O(|P |n3) 回の演算で得ることができる．なお，SDD についても CYK アルゴリズムに沿った演算により構築することが できる．
4
実験
ブール関数を CNF に変換してコンパイルする素朴 な構築法1と，CYK アルゴリズムに沿った構築法の実 行時間を比較する．文法として以下の 3 種類を用いた． G1: A → AA, A → a G2: A → AA, A → AB, B → BA, A → a, B → b G3: S → aS | cS | gS | uS | Sa | Sc | Sg | Su S → aSu | uSa | cSg | gSc | SS | ϵ G1, G2によって単純で典型的な文法についての評価 を行う．また，G3は生命情報学の分野で使用されて いる文法であり [2]，実用的で規則や記号の数の多い文 法についても評価を行う．構文木を構築する記号列は， G1では aaaa のような a のみで構成された列，G2で は abab のように a と b が交互に出現する列，G3では RNA 配列のデータベースである RNAcentral[8] から抜 粋したものを使用した． ZSDD の構築に必要な vtree は以下のように構成する．各 (i, j) について，bij1, bij2, . . . , bij|P |の順に
right-linear-vtree を作り，それを Bij とする．次に right-linear-vtree の集合 Rh = {Bij|j − i + 1 = h} を作 る．Rhに含まれる vtree は各変数に対応する規則が h 文字を生成する．最後に Rn, Rn−1, . . . , R1の順に right-linear-vtree のように結合し，それを実験で用いる vtree 1CNF に変換せずに構築する方法でも実験を行ったが，CNF に 変換した場合の方が高速に構築できたため，CNF に変換した場合を ベースラインとする．
表 2: 中間 ZSDD の大きさの最大値についての実験結果．最終的に出力される ZSDD の大きさと，それぞれの方 法で構築途中に作られる中間 ZSDD の大きさの最大値を表す．タイムアウトは 1800 秒とした． (a)G1についての最大値 n 3 4 5 6 7 8 9 10 11 12 13 14 15 最終ZSDD 6 15 34 78 173 381 825 1772 3785 8067 17153 36407 77171 CNFでの最大値 19 71 218 1171 5659 74346 1884881 22303149 - - - - -CYKでの最大値 6 15 34 78 173 381 825 1772 3785 8067 17153 36407 77171 (b)G2についての最大値 n 2 4 6 8 10 12 最終ZSDD 2 13 64 303 1398 5079 CNFでの最大値 5 72 1287 93849 - -CYKでの最大値 2 13 64 303 1398 5079 とする．なお，この vtree を与えることにより ZSDD が小さくなることが実験的に示されている [3]． 表 1 に G1, G2それぞれについて CNF をコンパイル する素朴な方法と，CYK アルゴリズムに沿って演算を 行った場合の構築時間を示す．G3については n = 8, 20 の場合ともに CNF では 1800 秒以内に ZSDD を構築 できなかったが，CYK アルゴリズムによる方法では n = 8 のとき大きさ 864 で 0.690 秒，n = 20 のとき大 きさ 13579271 で 447 秒という結果が得られた．以上 より，CYK アルゴリズムによる方法が CNF に比べ高 速に ZSDD を構築できることがわかる． 高速に構築できた理由について考察する．ZSDD 間 の Apply 演算にかかる時間は入力される 2 つの ZSDD の大きさの積に比例するため，構築の途中に生成され る中間 ZSDD の大きさに依存する．構築の過程で生成 される中間 ZSDD の最大の大きさを表 2 に示す．CNF による方法では演算回数が大きくなることに加え，中間 ZSDD が非常に大きくなるため一度の演算にかかる時 間が大きくなる．また，今回検証した文法では CYK ア ルゴリズムに沿った構築での中間 ZSDD の最大の大き さが全て最終的に出力される ZSDD の大きさに等しい．
5
おわりに
本稿では，全構文木の集合を表現する決定グラフを CYK アルゴリズムに沿って効率的に構築する方法を与 え，素朴な方法に比べ高速に構築できることを実験に より示した．今後の課題として，他の vtree について も検討することや，構築された決定グラフに演算を適 用して実問題に応用すること等が挙げられる．参考文献
[1] C. D. Manning and H. Sch¨utze. Foundations of statistical natural language processing.
Cam-bridge: MIT press, 1999.
[2] R. Durbin, S. R. Eddy, A. Krogh, and G. Mitchi-son. Biological sequence analysis: probabilistic models of proteins and nucleic acids. 1998. [3] K. Amii, M. Nishino, and A. Yamamoto. On the
Sizes of Decision Diagrams Representing the Set of All Parse Trees of a Context-free Grammar.
Pro-ceedings of Advanced Methodologies for Bayesian Networks (AMBN), Vol. 73, pp. 153–164, 2017.
[4] R. E. Bryant. Graph-based algorithms for Boolean function manipulation. Computers, IEEE
Trans-actions, Vol. 100.8, pp. 677–691, 1986.
[5] S. Minato. Zero-suppressed BDDs for set manip-ulation in combinatorial problems. Proceedings of
the 30th international Design Automation Confer-ence (DAC). ACM, pp. 272–277, 1993.
[6] A. Darwiche. SDD: A new canonical represen-tation of propositional knowledge bases.
Proceed-ings of International Joint Conference on Artificial Intelligence (IJCAI), pp. 819–826, 2011.
[7] M. Nishino, N. Yasuda, S. Minato, and M. Na-gata. Zero-Suppressed Sentential Decision Dia-grams. Proceedings of the 30th Conference on
Ar-tificial Intelligence (AAAI), pp. 1058–1066, 2016.
[8] RNAcentral Consortium. Rnacentral: an interna-tional database of ncrna sequences. Nucleic acids
