情報処理学会研究報告
IPSJ SIG Technical Report

非線形項木パターンに対するマッチングアルゴリズムと頻出 1 変数項木パターン枚挙への応用
片山 悠1

鈴木 祐介2,a)

内田 智之2,b)

宮原 哲浩2,c)

概要：順序木とは辺ラベルを持ち，順序付けられた子を持つ根付き木である．項木パターンとは順序木に
構造的変数を導入した順序木パターンであり，構造的変数には任意の順序木を代入できる．項木パターン
中の全ての変数が異なるとき線形項木パターンといい，線形でない項木パターンを非線形項木パターンという．項木パターン中の全ての変数が同一のとき 1 変数項木パターンという．本研究では，項木パターン
中に複数種類の変数が存在するがその中の１種類の変数の繰り返しを許す非線形項木パターンのマッチン
グアルゴリズムを提案する．さらに，提案したマッチングアルゴリズムを用いて，頻出 1 変数項木パター
ンの枚挙アルゴリズムの高速化を行う．
キーワード：グラフアルゴリズム，機械学習，データマイニング

A Matching Algorithm for Non-Linear Term Tree Patterns
and its Application for Enumeration ofFrequent One-Variable Term Tree Patterns
Yu Katayama1

Yusuke Suzuki2,a)Tomoyuki Uchida2,b)Tetsuhiro Miyahara2,c)Abstract: Ordered trees are rooted trees with edge labels and ordered children. Term tree patterns arerooted ordered tree patterns having structured variables. A variable can be replaced with any rooted ordered
tree. A term tree pattern is linear if all variables in the term tree pattern have mutually distinct variable
labels. A term tree pattern is non-linear if the term tree pattern is not linear. A one-variable term tree pattern is a term tree pattern all of whose variable labels are the same. In this paper, we propose a polynomial
time matching algorithm for a kind of non-linear term tree patterns, and propose an enumeration algorithm
for frequent one-variable term tree patterns using proposed matching algorithm.
Keywords: graph algorithm, machine learning, data mining

1. はじめに

フや木構造データに拡張し，グラフのデータベースに対して頻出なグラフ構造を発見する問題とそれを解くアルゴリ

頻出アイテム集合発見問題は，データマイニングにおけズムが数多く提案されている [3], [6], [10]．本研究では，木る基本的な問題である．頻出アイテム集合発見問題をグラ

構造データに頻出な木構造パターンを発見する問題を解く

1

2

a)
b)
c)

広島市立大学情報科学部
Faculty of Information Sciences, Hiroshima City University,Japan
広島市立大学大学院情報科学研究科
Graduate School of Information Sciences, Hiroshima City
University, Japany-suzuki@hiroshima-cu.ac.jp
uchida@hiroshima-cu.ac.jp
miyares23@hiroshima-cu.ac.jp

c 2023 Information Processing Society of Japan⃝

枚挙アルゴリズムの高速化を行う．
本研究で扱う木構造データは，辺ラベルを持ち，各内部頂点が順序付けされた子を持つ根付き木として表される．
このような根付き木を順序木とよぶ．順序木に共通する木構造の表現方法として，項木パターンを用いる [8]．項木
パターンとは，順序木の内部に構造的変数の存在を認めた

1

情報処理学会研究報告
IPSJ SIG Technical Report

a
c

b
a
b

b

c

a

c

a
b

b

b
c

a

a
c

c

b

順序木 T1

順序木 T2

c

a

c

b

b

b

a

x

b

c

z

x

b

c

x

x

b

c

x

a
c b

c

順序木 T3y

線形項木パターン t1x1 変数項木パターン t2

y1rep項木パターン t3

図 1 項木パターンと頻出項木パターン枚挙問題の例

もので，構造的変数には任意の順序木を代入することがで中に複数の変数ラベルの変数が存在するが，ある 1 種類のきる．これ以降，構造的変数を単に変数とよぶ．変数は，変数ラベルを持つ変数のみ繰り返し出現することを許す非辺と同様に頂点の組とラベル（変数ラベル）から構成され線形な項木パターンを考える．このような項木パターンをる．変数への代入の際に各変数は変数ラベルによって区別

1rep項木パターン（または，1 種類の変数ラベルの繰り返され，同一の変数ラベルを持つ変数には，同一の順序木をしを許す非線形項木パターン）とよぶ．

代入しなければならない．項木パターン t と順序木 T が与本論文で扱う 1rep項木パターンと順序木に対するマッえられたとき，t の各変数に適当な順序木を代入することチング問題とは，1rep項木パターン t と順序木 T が与えらで順序木 T と同型になるならば，項木パターン t は順序木

れたときに，t と T がマッチするか判定する問題である．

T とマッチするという．項木パターン中の全ての変数が互

本論文では，1rep項木パターンと順序木に対するマッチン

いに異なる変数ラベルを持つとき，その項木パターンを線グ問題を多項式時間で解くマッチングアルゴリズムを提案

形な項木パターン，または線形項木パターンとよぶ．線形する．

でない項木パターンを非線形項木パターンとよぶ．

さらに，田中ら [10] の提案した頻出 1 変数項木パターン

項木パターンと順序木に対するマッチング問題とは，項の枚挙アルゴリズムを発展させ，提案したマッチングアル

木パターン t と順序木 T が入力として与えられたときに，ゴリズムを用いることで田中らの手法より高速な頻出 1 変

t と T がマッチするか否かを判定する問題である．頻出項

数項木パターンの枚挙アルゴリズムの提案を行う．提案し木パターン枚挙問題とは，与えられた順序木のデータベー

たマッチングアルゴリズムおよび枚挙アルゴリズムを計算

スと，閾値 σ に対して，データベース中の順序木でマッチ機上に実装し，評価実験を行った結果を報告する．

するものの割合が σ 以上である項木パターンを全て枚挙す

図 1 に線形項木パターン，1 変数項木パターン，1rep項

る問題である．宮原ら [6] はタグ木パターンという線形項木パターンと頻出項木パターン枚挙問題の例を示す．項木

木パターンを拡張したパターンを提案し，頻出線形項木パパターンの変数は，2 つの頂点の組と変数ラベルで構成さターン枚挙問題を解く枚挙アルゴリズムを提案した．

れる．図では変数を頂点の組をつなぐ線と線上の四角で表Angluin[1] は正例から推論可能な言語族としてパターン

す．四角内のラベルは，その変数の変数ラベルを表す．順

言語を導入した．さらに，パターン中に 1 種類の変数しか序木集合 {T1 , T2 , T3 } を順序木のデータベースとする．線現れない 1 変数パターンを提案した [2]．1 変数項木パター

形項木パターン t1 は順序木 T1 , T2 , T3 とマッチし，1 変数

ンとは，1 変数パターンの概念を項木パターンに拡張した

項木パターン t2 は順序木 T1 とマッチし，1rep項木パター

もので，項木パターン中の全ての変数が同一の変数ラベルン t3 は順序木 T1 , T2 とマッチする．このとき閾値 σ = 0.5を持つものである．舛井ら [5] は，1 変数項木パターンととすると，t1 , t3 は {T1 , T2 , T3 } に対して頻出な項木パター

3

頂点数 N の順序木に対するマッチング問題を O(N ) 時間で解くマッチングアルゴリズムを提案した．酒井ら [7] は，
舛井らの研究を発展させ O(N 2 ) 時間のマッチングアルゴ
リズムを提案した．また，田中ら [10] は，宮原ら [6] の枚
挙アルゴリズムを発展させ，頻出 1 変数項木パターン枚挙
問題を解く枚挙アルゴリズムの提案と実装を行った．

ンである．

2. 準備
本節では，項木パターン，線形項木パターン [8] および

1 変数項木パターン [5] に関する諸定義を行う．
順序木とは，根を持ち，任意の葉以外の頂点に対して，変数の種類や出現回数に制限がない非線形項木パターン

その頂点の子の集合に順序が定義されている木である．Λ

と順序木に対するマッチング問題は NP 完全な問題と知らを辺ラベルの集合，X を Λ ∩ X = ∅ を満たす変数ラベルのれている [9]．しかし非線形な項木パターンであっても，1集合とする．T = (V, E) を Λ ∪ X 上の順序木とする．こ変数項木パターンのような変数ラベルの種類数に制限があこで，V を頂点集合，E ⊆ V × (Λ ∪ X) × V を辺集合とするような項木パターンと順序木に対するマッチング問題はる．Λ の要素 a でラベル付けされている頂点 u, v 間の辺を多項式時間で計算可能である．本研究では，項木パターン

e = (u, a, v) で表し，辺 e の辺ラベルを Λ(e) で表す．X のc 2023 Information Processing Society of Japan⃝2

情報処理学会研究報告
IPSJ SIG Technical Report

要素 x でラベル付けされている頂点 u, v 間の辺を変数と呼u1

び，h = [u, x, v] で表し，変数 h の変数ラベルを X(h) で表c

す．2 つの頂点 u, v ∈ V に対して，辺 e = (u, a, v) ∈ E ま

a

b
u3

u2

u4

y

たは変数 h = [u, x, v] ∈ E であるとき，u は v の親である

a

x

b

a

といい，v は u の子であるという．順序木 T の頂点 u と，

u5

u6

u7

u8

u の 2 つの子 u′ , u′′ に対して，u′ <Tu u′′ は u の子の順序において u′ が u′′ より小さいことを表す．
定義 1

Λ ∪ X 上の順序木 T = (V, E) に対し，V ′ = V ，

E 中の変数全体の集合を H ′ ，E ′ = E − H ′ とするとき，3

c

x

u10

u11

u9

b

c

a

c

a

u12

w13

u14

u15

u16

1rep項木パターン f

つ組 t = (V ′ , E ′ , H ′ ) を Λ ∪ X 上の項木パターン，または

v1

単に項木パターンという．

w1

a

b c

b

v2

v3

w2

v4

項木パターン g = (Vg , Eg , Hg ) に対し，Hg = ∅ のとき，

a

b

a

a

b

つまり変数を持たない項木パターンを Λ 上の順序木，また

v5

v6

v7

w3

w4

は単に順序木とよぶ．

順序木 g1

項木パターン f = (Vf , Ef , Hf ), g = (Vg , Eg , Hg ) に対し，f と g が同型であるとは，下記の (1)–(4) の 4 つの条 件 を 満 た す 全 単 射 φ : Vf → Vg が 存 在 す る と き をいう．このとき f ∼= g と書く．(1)(u, a, v) ∈ Ef のとき，その時に限り (φ(u), a, φ(v)) ∈ Eg である．(2) あるx ∈ X に対して [u, x, v] ∈ Hf のとき，その時に限り，あるy ∈ X に対して [φ(u), y, φ(v)] ∈ Hg である．(3)2 つの変数

c
u2

u3

a

a

b c

b

a

v2

v3

u7

u8

v4

り (φ(u), b, φ(v)) ∈ Eg または [φ(u), y, φ(v)] ∈ Hg である．
項木パターンに対する代入について定義する．f, g を 2
つ以上の頂点を持つ項木パターンとする．h = [v0 , x, v1 ] を

f の変数，σ = [u0 , u1 ] を g の異なる頂点のリストとする，
ここで u0 は g の根であり，u1 は g の葉である．このとき

x := [g, [u0 , u1 ]] を変数ラベル x に対する束縛という．束縛 x := [g, [u0 , u1 ]] を f に次のように適用して新しい項木
パターン f ′ を得る．変数ラベル x を持つ変数 h に対して，

f の変数の集合 Hf から変数 h を削除し，頂点 v0 と g の頂点 u0 を，頂点 v1 と g の頂点 u1 をそれぞれ同一視する．
′

u9

b

a

a

b c

a b

v5

v6

u6

v2

v3

u9

(=v7)

c a
u10

2 つの子 u′ , u′′ において，u′ <fu u′′ のとき，そのときに(5)(u, a, v) ∈ Ef または [u, x, v] ∈ Hf のとき，その時に限

b
(=v1)

a

に対し，y ̸= y ′ (y, y ′ ∈ X) である．(4)f の頂点 u とそのき，f と g が辺と変数ラベルを無視して同型であるという．

(=w1)

u4

u5

その時に限り [φ(u), y, φ(v)] ∈ Hg , [φ(u′ ), y ′ , φ(v ′ )] ∈ Hg

次の条件 (5) を満たす全単射 φ : Vf → Vg が存在すると

a

b

(=v1)

[u, x, v], [u′ , x′ , v ′ ] ∈ Hf に対し，x ̸= x′ (x, x′ ∈ X) ならば限り，φ(u′ ) <gφ(u) φ(u′′ ) である．また上記の条件 (4) と順序木 g2
u1

v5

v4

b

a

v6

u11

w4

(=w3)

(=v7)

b

c

a

c

a

u12

u13

u14

u15

u16

順序木 f {x := [g1 , [v1 , v7 ]], y := [g2 , [w1 , w3 ]]}図 2 1rep項木パターン f への代入と 2-port 対応部分木の例．

を代入とよぶ．ここで x1 , . . . , xn は X に含まれる互いに異なる変数ラベルである．また g1 , . . . , gn 中の変数は，変数ラベルとして x1 , . . . , xn を持たない．代入 θ に含まれる束縛を項木パターン f に全て適用して得られる新しい項木
パターンを f θ と書く．
定義 2

Λ∪X 上の項木パターン t に対し，t の項木パター
ン言語を L(t) = { 順序木 T | ある代入 θ に対し T ∼= tθ}と定義する．
順序木 T と項木パターン t に対し，T ∈ L(t) ならば t は

T とマッチするという．
T を順序木とする．T の部分グラフ S に対し，S が順序新しい項木パターン f の 2 つ以上の子を持つ頂点 v の子

木であり，S の各頂点の親子関係と兄弟関係の順序関係がの順序を次のように定める．v ′ , v ′′ を v の 2 つの子とする．

T と等しいならば，S を T の部分木という．T の部分木 S′(1) v, v , v ∈ Vg であり，v <gv v ′′ ならば，v ′ <fv v ′′ であ′る．(2) v, v ′ , v ′′ ∈ Vf であり，v ′ <fv v ′′ ならば，v ′ <fv v ′′である．(3) v = v0 ，v ′ ∈ Vf ，v ′′ ∈ Vg であり，v ′ <fv v1′
ならば，v ′ <fv v ′′ である．(4) v = v0 ，v ′ ∈ Vf ，v ′′ ∈ Vg′
であり，v1 <fv v ′ ならば，v ′′ <fv v ′ である．

′

′′

′

束縛の有限集合 θ = {x1 := [g1 , σ1 ], . . . , xn := [gn , σn ]}c 2023 Information Processing Society of Japan⃝と，S の頂点の組 (u, v) が次の 3 つの条件を満たすとき，S を (u, v) に関する T の 2-port 対応部分木（または単にT の 2-port 対応部分木）とよび，S(u, v) と表す．(1) u
は S の根，v は S の葉である．(2) S の任意の 2 つの頂点

w1 , w2 に対し，S 上で w1 のすぐ隣の兄弟が w2 であるな
ら，T 上でも w1 のすぐ隣の兄弟が w2 である．(3) u, v を3

情報処理学会研究報告
IPSJ SIG Technical Report

除く S の全ての頂点の次数は，T における各頂点の次数問題： t と T がマッチするか否かを判定せよと等しい．条件 (3) より，(u, v) に関する T の 2-port 対応

Suzuki ら [9] は頂点数 n の線形項木パターンと頂点数

部分木 S(u, v) に対して，v を除く S(u, v) の全ての葉は T

N の順序木に対するマッチング問題を O(nN ) 時間で解の葉である．順序木 T に対し，(u, v) に関する T の 2-port

くマッチングアルゴリズム Matching を提案した．舛井

対応部分木 S(u, v) は，S(u, v) の根 u， S(u, v) において u

ら [5] は頂点数 n の１変数項木パターンと頂点数 N の順序の子の先頭となる頂点，S(u, v) において u の子の末尾と木に対するマッチング問題を O(N 3 ) 時間で解くマッチンなる頂点，S(u, v) の葉 v の 4 つの頂点を T から選ぶこと

グアルゴリズム OneMatching を提案した．本論文では，で定めることができる．よって T の全ての 2-port 対応部

これらのアルゴリズムをもとに，1rep項木パターンと順序

分木の数は高々 O(N 4 ) である．ここで N は T の頂点数で木に対するマッチング問題を解くマッチングアルゴリズム

ある．

xMatching1，xMatching2 を提案する．

項木パターン中の変数が互いに異なる変数ラベルを持つ

提案したマッチングアルゴリズム xMatching1 を Al-とき，その項木パターンを線形な項木パターン，または線

gorithm 1 に示す．入力として頂点数 n の 1rep項木パター

形項木パターンとよぶ．線形でない項木パターンを非線形

ン t と，頂点数 N の順序木 T が与えられたときのアルゴ

項木パターンとよぶ．項木パターン中の変数ラベルの数がリズム xMatching1 の動作を説明する．x を 1rep項木パ

1 のとき，つまり，全ての変数が同一の変数ラベルを持つ

ターン中に繰り返し出現することを許す変数ラベルとす

とき，その項木パターンを 1 変数項木パターンとよぶ．本る．xMatching1 は順序木 T の全ての 2-port 対応部分

論文では，項木パターン中に複数の変数ラベルの変数が存木を列挙する．そして列挙した各 2-port 対応部分木を t

在するが，ある１種類の変数ラベルを持つ変数のみ繰り返の変数ラベル x の変数に代入し，線形項木パターン t′ をし出現することを許す非線形な項木パターンを考える．こ得る．そして t′ と T がマッチするか否かをアルゴリズムのような項木パターンを 1rep項木パターン （または，1Macthing を用いて判定する．もし t′ と T がマッチする種類の変数ラベルの繰り返しを許す非線形項木パターン）

ような 2-port 対応部分木が存在すれば，その時点で 2-portとよぶ．1rep項木パターンのクラスは線形項木パターンの対応部分木の列挙を終了し，xMatching1 は “yes” を返クラスおよび１変数項木パターンのクラスを包含する．本す．全ての 2-port 対応部分木を列挙しても t′ と T がマッ

論文では，簡単のために 1rep項木パターンと 1 変数項木パ

チしなければ，xMatching1 は “no” を返す．順序木 T のターンにおいて変数ラベル x を持つ変数のみ繰り返し出現

全ての 2-port 対応部分木は O(N 4 ) 個存在する．t′ と T がするものとする．

マッチするか否かを判定するのに O(N 2 ) 時間かかるため，

項木パターンに対する代入の例と 2-port 対応部分木の例を図 2 に示す．1rep項木パターン f の変数ラベル x を持つ変xMatching1 は 1rep項木パターンと順序木に対するマッチング問題を O(N 6 ) 時間で計算する．

数に対し順序木 g1 を，変数ラベル y を持つ変数に対し順序木t を 1rep項木パターンとする．t を幅優先探索したとき

g2 を代入し，順序木 f {x := [g1 , [v1 , v7 ]], y := [g2 , [w1 , w3 ]]}に t 中の変数で変数ラベル x を持つ変数が最初に出現すを得る．順序木 f {x := [g1 , [v1 , v7 ]], y := [g2 , [w1 , w3 ]]} 中

るならば，そのような t を bf s1rep項木パターン とよの 2-port 対応部分木 g1 (v1 , v7 ) を赤色の破線の枠で，2-port

ぶ．bf s1rep項木パターンと順序木に対するマッチング問

対応部分木 g2 (w1 , w3 ) を緑色の破線の枠で示す．

題を解くマッチングアルゴリズム xMatching2 を Algo-

D = {T1 , T2 , . . . , Tm } を空でない順序木の有限集合，trithm 2 に示す．xMatching2 は xMatching1 よりも高を項木パターンとする．matchD (t) を，t とマッチする

速にマッチング問題を解くことが可能である．頂点数 nTi ∈ D (1 ≤ i ≤ m) の個数と定義し，D に対する t の支持の bf s1rep項木パターン t と，頂点数 N の順序木 T が与率 suppD (t) を suppD (t) = matchD (t)/m と定義する．実えられたときのアルゴリズム xMatching2 の動作を説明

数 σ (0 < σ ≤ 1) に対して，suppD (t) ≥ σ ならば，項木パ

する．xMatching2 は xMatching1 と同様に，順序木 T

ターン t は D に対して σ 頻出であるという．実数 σ は，頻の 2-port 対応部分木を列挙し，Matching を用いてマッ出と判断するために閾値としてユーザが与える値であり，チするか否かを判定する．この時に T の全ての 2-port 対最小支持率とよばれる．

応部分木を列挙するわけではなく，t 中の変数ラベル x の

3. 1rep項木パターンのマッチングアルゴリ
ズム
1rep項木パターンに対するマッチング問題を次のように変数の出現位置に基づき高々 N 2 個の 2-port 対応部分木を列挙する．よって xMathing2 は bf s1rep項木パターンと順序木に対するマッチング問題を O(N 4 ) 時間で計算する．
補題 1

t を 項 木 パ タ ー ン ，T を 順 序 木 と す る ．

定義する．

x1 , . . . , xn を t 中 に 出 現 す る 変 数 ラ ベ ル と す る ．項 木

1rep項木パターンに対するマッチング問題

パ タ ー ン t と 順 序 木 T が マ ッ チ す る な ら ば ，そ の 時

入力： 1rep項木パターン t，順序木 Tに 限 り ，tθ = t{x1 := [S1 (u1 , v1 ), [u1 , v1 ]], . . . , xn :=c 2023 Information Processing Society of Japan⃝4

情報処理学会研究報告
IPSJ SIG Technical Report

Algorithm 1 XMatching1(t, T )2 つの頂点 c1 , c2 の間に頂点が挿入されることはないため，

Input: 1rep項木パターン t, 順序木 T
Output: “yes” or “no”
1: for each T の頂点 u do
2:
c1 , . . . , ck を u の全ての子とする
3:
for i := 1 to k do4:
for j := i to k do
5:
subT を u と，ci . . . , cj とその子孫全体からなる T の部分木とする6:
for each subT の頂点 v do
7:
S を subT から v の子孫全体を除いた T の部分木とする （v は S に含まれる）
8:t′ := t{x := [S, [u, v]]} とする
9:
if Matching(t′ , T )[9] = “yes” then10:
return “yes”
11:
end if
12:
end for13:
end for14:
end for
15: end for
16: return “no”

Si 上で ξi (c1 ) のすぐ隣の兄弟が ξi (c2 ) であるなら，T 上でも ξi (c1 ) のすぐ隣の兄弟が ξi (c2 ) である．よって部分木 Siと頂点の組 (ξi (wi1 ), ξi (wi2 )) は T の 2-port 対応部分木であ る ．こ の と き ，t{x1 := [Q1 , [w11 , w12 ]], . . . , xn :=∼ T な の で ，tθ = t{x1 :=[Qn , [wn1 , wn2 ]]} =[S1 (ξ1 (w11 ), ξ1 (w12 )), [ξ1 (w11 ), ξ1 (w12 )]], . . . , xn:=∼
[Sn (ξn (wn1 ), ξn (wn2 )), [ξn (wn1 ), ξn (wn2 )]]} = T が 成 り
立つ．

(⇐=)

マ ッ チ の 定 義 よ り ，T の あ る 2-port 対 応 部 分

木の列 S1 (u1 , v1 ), . . . , Sn (un , vn ) に対し，tθ = t{x1 :=[S1 (u1 , v1 ), [u1 , v1 ]], . . . , xn := [Sn (un , vn ), [un , vn ]]} ∼= Tを満たすならば，t と T がマッチする．
定理 1□

アルゴリズム xMathing1 は 1rep項木パターンと頂点数 N の順序木に対するマッチング問題を O(N 6 ) 時
間で正しく解く．
証明： t と T がマッチするので，tθ ∼= T を満たす代入 θ が存在する．ここで補題１より代入 θ = {x := [S, [u, v]], x1 :=Algorithm 2 XMatching2(t, T )Input: bf s1rep項木パターン t, 順序木 T
Output: “yes” or “no”
1: h を幅優先探索して最初に到達する t の変数ラベル x の変数，u′を変数 h の親ポート，f をその順番とする
2: u を幅優先探索で f 番目の T の頂点とする
3: c1 , . . . , ck を u の全ての子とする
4: i を u の子の順番で変数 h の子ポートの順番とする
5: for j := i to k do
6:
subT を u と，ci . . . , cj とその子孫全体からなる T の部分木とする
7:for each subT の頂点 v do
8:
S を subT から v の子孫全体を除いた T の部分木とする（v は S に含まれる）
9:t′ := t{x := [S, [u, v]]} とする
10:
if Matching(t′ , T )[9] = “yes” then11:
return “yes”
12:
end if13:
end for
14: end for
15: return “no”

[S1 (u1 , v1 ), [u1 , v1 ]], . . . , xn := [Sn (un , vn ), [un , vn ]]} とする．x を 1rep項木パターンに繰り返し出現する変数ラベルとする．代入 θ を変数ラベル x に対する束縛からなる代入

θ′ = {x := [S, [u, v]} とそれ以外の変数ラベルに対する束縛からなる代入 θ′′ = {x1 := [S1 (u1 , v1 ), [u1 , v1 ]], . . . , xn :=[Sn (un , vn ), [un , vn ]]} に わ け て 考 え る ．こ の と き tθ =t(θ′ θ′′ ) = (tθ′ )θ′′ ∼= T である．θ′ は変数ラベル x に対する束縛からなる代入なので，tθ′ は線形項木パターンであ∼Tる．線形項木パターン tθ′ と順序木 T に対して，(tθ′ )θ′′ =となる代入 θ′′ が存在するか否か，つまり tθ′ と T がマッチするか否かはアルゴリズム Matching(tθ′ , T ) によって判定できる．これにより，x 以外の変数ラベルに対して補題 1 の条件を満たす 2-port 対応部分木の列が存在するか否かを判定できる．よって T の全ての 2-port 対応部分木

S(u, v) に対して，代入 θ′ = {x := [S, [u, v]} を作成し，tθ′と T がマッチするか判定すれば，全ての変数ラベルに対して，補題 1 の条件を満たすような 2-port 対応部分木の列が[Sn (un , vn ), [un , vn ]]} ∼= T を満たす T の 2-port 対応部

存在するか否かを確かめることができる．よって，アルゴ

分木の列 S1 (u1 , v1 ), . . . , Sn (un , vn ) が存在する．

リズム xMathing1 は 1rep項木パターンと順序木に対す

証明： (=⇒) t と T がマッチするので，マッチの定義より，
t{x1 := [Q1 , [w11 , w12 ]], . . . , xn := [Qn , [wn1 , wn2 ]]} ∼= Tるマッチング問題を正しく解く．

を満たす順序木の列 Q1 , . . . , Qn が存在する．ここで wi1

る時間は O(N 4 ) 時間である．変数ラベル x の変数に代入

は Qi の根，wi2 は Qi のある葉である (1 ≤ i ≤ n)．代入の後の線形項木パターン tθ′ の最大サイズは N である．よっ

定義より，Qi の親子関係と兄弟の順序関係は代入後の T にて，線形項木パターン tθ′ と順序木 T がマッチするか否か

おいても保たれる．よって Qi と同型な T の部分木 Si が存の判定にかかる時間は高々 O(N 2 ) 時間である．これより，在する．VQi を Qi の頂点集合，VSi を Si の頂点集合とし，アルゴリズム XMatching1 は，1rep項木パターンに対す

ξi を VQi から VSi への同型写像とする．wi1 , wi2 以外の Qi

るマッチング問題を O(N 6 ) 時間で正しく解く．

T の 2-port 対応部分木は高々 N 4 個であり，列挙にかか□の頂点 w は，代入の前後で次数が変化しないため，Si の頂舛井ら [5] の定理 1 より，T の 2-port 対応部分木 S(u, v)

点 ξi (w) ∈ VSi \ {ξi (wi1 ), ξi (wi2 )} の Si における次数と Tの根 u と，S(u, v) において u の子の先頭となる頂点の 2 つにおける次数は等しい．また代入の前後で，Qi の連続するを一意に決めたとき，S(u, v) の数は高々 N 2 個しかない．

c 2023 Information Processing Society of Japan⃝5

情報処理学会研究報告
IPSJ SIG Technical Report

よって，定理 1 より次の定理が示せる．
定理 2

ア ル ゴ リ ズ ム xMathing2 は bf s1rep項 木 パ

ターンと頂点数 N の順序木に対するマッチング問題を
4O(N ) 時間で正しく解く．

4. 頻出 1 変数項木パターンの枚挙アルゴリズ
ムの高速化

Algorithm 3 Gen-F1TTPX
Input: 順序木の集合 D，最小支持率 σ (0 < σ ≤ 1)
Output: D に対して σ 頻出な 1 変数項木パターンの全集合 Π(σ)
1: Π1 (σ) :=enumFreq(D, σ) [10]2: Π(σ) :=replaceEdgeX(D, σ, Π1 (σ)) (Procedure 4)
3: return Π(σ)

頻出 1 変数項木パターン枚挙問題は次のような問題である [10]．
頻出 1 変数項木パターン枚挙問題
入 力：空 で な い 順 序 木 の 有 限 集 合 D，最 小 支 持 率 σ(0 < σ ≤ 1)
問題：D に対して σ 頻出な 1 変数項木パターンを全て枚挙せよ

D を空でない順序木の有限集合，実数 σ (0 < σ ≤ 1)
を最小支持率とする．田中ら [10] は，D に対して σ 頻出
な 1 変数項木パターンを全て枚挙するアルゴリズム Gen-F1TTP を提案した．本論文では，1 変数項木パターンの枚挙アルゴリズム Gen-F1TTP を発展させ，D に対して σ 頻出な 1 変数項木パターンを高速に全て枚挙する

Procedure 4 replaceEdgeX

Input: 順序木の集合 D，最小支持率 σ (0 < σ ≤ 1)，変数のみからなる線形項木パターンの集合 ΠinOutput: 1 変数項木パターンの集合 Πout
1: Πout := ∅2: pos := 1
3: for π ∈ Πin do4:
Πout := Πout ∪ replaceEdgeXSub(D, σ, π, pos) (Procedure 5)
5: end for
6: return Πout

アルゴリズム Gen-F1TTPX(Algorithm 3) を提案する．
アルゴリズム Gen-F1TTPX の動作を説明する．手続き

enumFreq はアルゴリズム Gen-F1TTP[10] 中で用いられた手続きと同一である．手続き enumFreq は，順序木の列挙手法である最右拡張 [3], [11] を用いて変数のみからなる線形項木パターンを枚挙する．これにより，D に対して σ 頻出な変数のみからなる線形項木パターンを全て枚挙する．本研究では，アルゴリズム Gen-F1TTP の

replaceEdge と replaceOneVariable をもとに，手続
き replaceEdgeX(Procedure 4) を提案する．x を 1rep
項木パターンと 1 変数項木パターンに繰り返し出現する
変数ラベルとする．手続き replaceEdgeX は，手続き

enumFreq の出力である変数のみからなる線形項木パターンに対して，brute-force method を用いて各変数に辺または変数ラベル x の変数を代入し，D に対して σ 頻出となるか調べていく．この手続きの途中で作成される項木パター
ンは bf s1rep項木パターンであるため，頻出か否かを判定するために前節で提案した xMatching2 を用いる．
田中ら [10] の補題 1 より，次の補題が示せる．
補題 2 項木パターン f, g に対し，f ∼= gθ となる代入 θが存在するならば L(f ) ⊆ L(g) である．
定理 3

アルゴリズム Gen-F1TTPX は，D に対して

σ 頻出な 1 変数項木パターンを過不足なく枚挙する．
証明： アルゴリズム Gen-F1TTPX の手続き enumFreq
は変数のみからなる σ 頻出な線形項木パターンを過不足なく枚挙する [10]．g を手続き enumFreq の出力である

Procedure 5 replaceEdgeXSub

Input: 順序木の集合 D，最小支持率 σ (0 < σ ≤ 1)，1rep項木パ
ターン π ，正数 pos
Output: 1rep項木パターンの集合 Πout
1: if pos > |Eπ ∪ Hπ | then2:
return {π}3: end if
4: Πtmp := ∅5: 変数 h を π の辺と変数の BFS 順で pos 番目の位置にある変数とする
6: for D に頻出な辺ラベル k do
7:πk を π の変数 h を k でラベル付けされた辺で置き換えた項
木パターンとする
8:if πk が D に対して σ 頻出である then9:
Πtmp := Πtmp ∪ {πk }10:
end if
11: end for
12: πx を π の変数 h を変数ラベル x の変数で置き換えた項木パター
ンとする
13: if πx が D に対して σ 頻出である then14:
Πtmp := Πtmp ∪ {πx }15: end if
16: Πout := ∅17: for π ′ ∈ Πtmp do18:
Πout := Πout ∪replaceEdgeXSub(D, σ, π ′ , pos + 1)
19: end for
20: return Πout

変数のみからなる線形項木パターンの一つとする．手続
き replaceEdgeX は，g に対し，brute-force method を

c 2023 Information Processing Society of Japan⃝6

情報処理学会研究報告
IPSJ SIG Technical Report

用いて各変数に辺または変数ラベル x を持つ変数を代入

は従来手法 Gen-F1TTP と同様であり，最小支持率が下する．これにより，g と辺と変数ラベルを無視して同型ながるに伴い途中で生成される項木パターンの数が増えるた

全ての 1 変数項木パターンを全て枚挙する．補題 1 より，
項木パターン f, g が，ある代入 θ が存在して f ∼= gθ となめであると考えられる．

るとき，D に対する f の支持率は g の支持率以下となる．

0.6 にかけては実行時間にほとんど差がないが，σ が 0.5 以

よって，項木パターン g の D に対する支持率が最小支持下の時は実行時間が削減できていることが確認できる．こ率 σ を下回ったならば，g に代入をして作成される全てのれは，従来手法に比べ提案手法では途中で生成される項木

項木パターンの支持率は必ず σ よりも小さくなる．この性

パターン数の削減が行われているためだと考えられる．

実データ集合 Dleu に対して，最小支持率 σ が 1.0 から質を用いて，手続き replaceEdgeX は，ある項木パター

また実データ集合 Dleu に対して，最小支持率 σ が 0.3 のンが最小支持率 σ を下回ったならば，その項木パターンにときに実行時間が削減できているが，それ以外ではあまり差代入して作成される項木パターンの作成を行わない．よっがないことが確認できる．これは，従来手法において頻出て，手続き replaceEdgeX は，σ 頻出な変数のみからなか否かの判定に用いるマッチングアルゴリズム Matching

る線形項木パターン g に対して，辺と変数ラベルを無視しと OneMatching に比べ，提案手法で頻出か否かの判定て同型な全ての σ 頻出な 1 変数項木パターンを過不足なくに用いるマッチングアルゴリズム xMatching2 が遅いた

枚挙する．

めだと考えられる．つまり，σ がある程度小さくなり途中

以上より，アルゴリズム Gen-F1TTPX は，D に対しで生成される項木パターン数の削減量が大きくならないて σ 頻出な 1 変数項木パターンを過不足なく枚挙する．□と，マッチングアルゴリズムの実行時間の差によって，総5. 評価実験
前節で提案した頻出 1 変数項木パターン枚挙問題を解く
枚挙アルゴリズム Gen-F1TTPX と田中ら [10] が提案した枚挙アルゴリズム Gen-F1TTP を主記憶メモリ:16.0GB，

CPU:11th Gen Intel(R) Core(TM) i7-1165G7@2.80GHz，

実行時間が速くならないと考えられる．この考察が正しいかどうか確認するために，途中で生成される項木パターン
数と，それらが頻出か否かの判定を行う回数を調べる必要があると考えられる．

6. おわりに

OS:Windows 10 の計算機上に開発環境:Eclipse，開発言本研究では，項木パターン中に複数の変数ラベルが存在

語:Java を用いて実装した．以降，枚挙アルゴリズム Gen-

するが，ある１種類の変数ラベルを持つ変数のみ繰り返

F1TTPX を提案手法，枚挙アルゴリズム Gen-F1TTP をし出現することを許す非線形な項木パターンを 1rep項木

従来手法とよぶ．評価実験では，田中ら [10] の実験と同様

パターンと定義した．そして，1rep項木パターンと順序木に実データ集合 Dleu と人工データ集合 Dsyn の 2 種類のに対するマッチング問題を解く多項式時間アルゴリズム

順序木集合を入力として用いた．

xMatching1 と xMatching2 を提案した．さらに，田中実データ集合 Dleu として，KEGG-GLYCAN データベーら [10] の提案した頻出 1 変数項木パターンの枚挙アルゴリ

ス [4] に登録されている白血病に関する糖鎖データ 177 個

ズムを発展させ，マッチングアルゴリズム xMatching2を順序木とみなして用いた．人工データ集合 Dsyn として，を用いることでより高速に枚挙を行う枚挙アルゴリズム

次の (1),(2) のように作成した頂点数 30 の順序木 100 個を

Gen-F1TTPX を提案した．提案したマッチングアルゴリ用いた．(1) ランダムに作成した頂点数 30 の順序木 10 個．

ズムおよび枚挙アルゴリズムを計算機上に実装し，実デー(2)1 変数項木パターン t1 , t2 , t3 を L(t3 ) ⊆ L(t2 ) ⊆ L(t1 )タ集合と人工データ集合を用いて評価実験を行った．

となるように作成し，t1 , t2 , t3 の変数にランダムに作成し項木パターン中に定数 k 個の変数ラベルが存在し，それた順序木を代入して得られた順序木をそれぞれ 30 個ずつ．

らが繰り返し出現することを許す非線形な項木パターン

評 価 実 験 と し て ，入 力 を (1) 実 デ ー タ 集 合 Dleu とを k 変数項木パターンとよぶ．k 変数項木パターンは 1 変(2) 人工データ集合 Dsyn の 2 通り，最小支持率 σ を，数項木パターンと比べ，データ中のいくつかの構造が繰りσ ∈ {1.0, 0.9, 0.8, 0.7, 0.6, 0.5, 0.4, 0.3} の 8 通りに対して，返し出現することを表現できるため，糖鎖データなどの実提案手法 Gen-F1TTPX と従来手法 Gen-F1TTP を実行

データの表現により適していると考えられる．また圧縮木

し実行時間を比較した．実データ集合 Dleu を入力としたという項木パターンを用いた順序木の可逆圧縮手法にも応ときの実行時間と頻出 1 変数項木パターンの数を表 1 に示用できると考えられる．今後の課題としては，本研究で提す．人工データ集合 Dsyn を入力としたときの実行時間と案した枚挙アルゴリズムを発展させ，頻出 k 変数項木パ

頻出 1 変数項木パターンの数を表 2 に示す．

ターンの枚挙アルゴリズムの開発を行うことが挙げられ

実データ集合 Dleu ，人工データ集合 Dsyn のいずれの入力に対しても，最小支持率が下がると提案手法 Gen-る．また，頻出 1 変数項木パターンの枚挙アルゴリズムの逐次出力も重要な課題である．

F1TTPX の実行時間が増加することが確認できる．これc 2023 Information Processing Society of Japan⃝7

情報処理学会研究報告
IPSJ SIG Technical Report
表 1

実データ集合 Dleu を入力としたときの実行結果

最小支持率 σ

1.0

0.9

0.8

0.7

0.6

0.5

0.4

0.3

σ 頻出な 1 変数項木パターンの数

1

1

1

4

10

10

12

35

従来手法 Gen-F1TTP の実行時間 (ms)

87

116

301

11,77622,153379,812523,240

3,043,844

提案手法 Gen-F1TTPX の実行時間 (ms)

26

94

400

15,036

21,683

149,938

194,767

597,817

表 2

人工データ集合 Dsyn を入力としたときの実行結果

最小支持率 σ

1.0

0.9

0.8

0.7

0.6

0.5

0.4

0.3

σ 頻出な 1 変数項木パターンの数

1

3

3

3

6

6

9

12

従来手法 Gen-F1TTP の実行時間 (ms)

201

2,591

8,789

23,927

77,853

247,645806,160

3,477,453

提案手法 Gen-F1TTPX の実行時間 (ms)

219

4,264

16,024

41,615125,993

329,385

873,499

2,573,719

謝辞
本 研 究 は JSPS 科 研 費 JP19K12102,JP19K12103,

JP21K12021 の助成を受けたものです．
参考文献
[1]

[2]

[3]

[4]
[5]

[6]

[7]

[8]

[9]

[10]

[11]

D. Angluin, Inductive inference of formal languages frompositive data, Information and Control, 45: 117–135,
1980.
D. Angluin, Finding patterns common to a set of string,
Journal of Computer and System Sciences, 21: 46–62,
1980.
T. Asai, K. Abe, S. Kawasoe, H. Sakamoto, H. Arimura,and S. Arikawa, Eﬃcient substructure discovery fromlarge semi-structured data, IEICE Trans. Inf. Syst.,
Vol. E87-D(12), 2754–2763, 2004.
KEGG GLYCAN Database,https://www.genome.jp/kegg/glycan/ (accessed 22 February 2022)
舛井 里帆, 池森 千尋, 鈴木 祐介, 内田 智之, 宮原 哲浩, 1
変数項木パターンに対する多項式時間マッチングアルゴ
リズム, 火の国情報シンポジウム 2020, C4-2, 2020.
T. Miyahara, Y. Suzuki, T. Shoudai, T. Uchida, andT. Kuboyama, Enumeration of Maximally Frequent Ordered Tree Patterns with Wildcards for Edge Labels,
IPSJ Trans. Math. Model. Appl.(TOM), Vol. 10(2), 59–
69, 2017.
酒井 笑理, 鈴木 祐介, 内田 智之, 宮原 哲浩, 1 変数項木パターンに対するマッチングアルゴリズムの改良, 第 182 回
アルゴリズム研究会, AL182-11, 2021.
Y. Suzuki, T. Shoudai, T. Uchida,T. Miyahara, Ordered
Term Tree Languages Which Are Polynomial Time Inductively Inferable from Positive Data, Theoretical Computer Science, 350(1): 63–90, 2006.
Y. Suzuki, T. Shoudai, T. Uchida,T. Miyahara, An Efﬁcient Pattern Matching Algorithm for Ordered Term
Tree Patterns, IEICE Trans. Inf. Syst., Vol. E98-A(6):1197–1211, 2015.
田中 知希, 鈴木 祐介, 内田 智之, 宮原 哲浩, 頻出 1 変数
項木パターンの枚挙アルゴリズム, 第 120 回人工知能基本問題研究会, SIG-FPAI-120, 24–29, 2022.
M. Zaki, Eﬃciently Mining Frequent Trees in a Forest:
Algorithms and Applications, IEEE Trans. Knowledge
and Data Engineering, Vol. 17(8), 1021–1035, 2005.

c 2023 Information Processing Society of Japan⃝

8