数理解析研究所講究録
1489 巻 2006 年 216-222

216

繰返し構造をもつラベル付順序木の簡潔な表現法
斉藤智哉 (Tomoya Saito), 中村篤祥 (Atsuyoshi Nakamura), 工藤峰– (Mineichi Kudo)
北海道大学 (Hokkaido University)

ABSTRACTを自動的に生成する手法 [4] を提案した。 Liu ら

本論文では、構造把握を目的とした、 ラベル付

順序木の繰返し構造を明示的に表す簡潔な表現である繰返し表現木を提案する。 また、 この表現のうち節点数が最も少ないものを求めるという問題
を考え、節点数$n$の木に対してその問題を $O(n^{3})$時間で解くアルゴリズムを示す。

1.

はじめに
インターネットの普及と発展に伴い、 WWW 上には大量かつ多様な情報が Web ページという形で蓄積されている。 これら膨大な情報を効率良くは、 タグの入れ子構造から得られる tag tree というラベル付順序木に現れる繰返し構造を発見することで、 data record と呼ばれる情報の単位構造を抽出する手法 [5] を提案した。 これらが部分的な情報の切り出しを行うのに対し、 南野らは、 タグ
列の繰返し構造を階層的に発見することで、Web
ページ全体の構造化を行う手法 [6] を提案した。
これらの手法は Web ページに関する経験則などを用いて繰返し構造の把握を行っており、 アプ
リケーションに電化した手法となっている。
本研究では、 ラベル付順序木の繰返し構造を明示的に表す簡潔な表現である繰返し表現木を提案
し、節点数最小の繰返し表現木を求めることにより繰返し構造を把握する手法を提案する。 繰返し

扱うために計算機による処理が必要となる。 しかし、 これら HTML 文書には文書に含まれる情報の意味が記述されていないため、直接このような文書から計算機によって自動的に情報を得ることは困難である。

表現木は繰返し構造をコンパクトにまとめた表現であるため、節点数が少ないものほどより尤もら

そこで、 Web ページに含まれる情報の自動的なしい繰返し構造の解釈であると考えられる。本手

抽出や統合を目的とする研究が盛んに行われてい法は経験則を用いないため、 Web ページに限らずる[1-3]。

ラベル付順序木として表すことのできる他の対象

このような研究のアプローチの–つとして、HTMLにも広く適用することができる。本論文では、 この問題を木の節点数 に対して時間計算量 $O(n^{3})$

文書に現れる繰返し構造に着目した手法がある[4-6]。たとえば、図 1 では、製品ひとつに対応する情報が記述された構造が 3 回繰返されている。
このような HTML 文書の繰返し構造を把握する$d^{l}$$nw\epsilon_{\mathrm{m}\mathrm{n}}\mathrm{g}\epsilon\iota \mathrm{g}\mathrm{o}*$$u\mathfrak{g}.\tau \mathrm{r}.-$l’.<\mbox{\boldmath $\lambda$}J イ‘$1\dot{\#}$

9.300

竃価オー’ ン$\mathrm{t}\mathrm{U}lV|^{\dot{\prime}\vee}\cdot$.

ru$\mathrm{R}-\emptyset$$-\sim$$\text{、}$

.

}

”rz

$B$

$\underline{\iota\not\in}$,) $l$$\mathrm{t}7^{\sim}/\mathit{9}v*T*\mathrm{S}$$n\infty$$\mathrm{E}$$\text{ス}\wedge^{\frac{-}{}}\text{ニ}\vee---J$$*\beta::.\cdot.l2l$$\cdot$$\mathfrak{m}.\uparrow \mathrm{w}ml\sigma_{\nu}7\cuparrow$$’\alpha \mathrm{z}\sim \mathrm{A}\mathrm{Z}7\text{イ}\lambda^{\gamma}i\circ \mathrm{g}.;\Rightarrow$$\mathrm{r}$

s&

$n$

で解くアルゴリズムを示す。実験によると、実際の HTML 文書に対して本手法を適用することで、ブラウザ上での目視により繰返し構造と解釈された部分のうち約 80%が把握できた。

$\ovalbox{\tt\small REJECT} \mathrm{P}-\angle:1^{arrow}=$

2.

問題設定

21.

繰返し表現木

根付き木で、 同じ親をもつすべての子の節点間$’..\mathrm{v}arrow R$$\mathrm{r}-|\cdot.\mathrm{K}22l.300(\mathrm{u}_{\dot{\lambda}^{\underline{\lambda}}})$Er オー\acute ン mn$\#..\mathrm{t}l:|\cdot \mathrm{V}209.\theta 00\mathrm{t}\ \dot{)}.\backslash )\mathrm{t}’\cdot\backslash \hslash$$\mathrm{r}\hslash$$\mathrm{m}rightarrow\circ$オージン$a\alpha$$\mathrm{R}rightarrow \mathrm{O}$に全順序が与えられた木を順序木という。木を図

まざまな応用が期待できる。
Chang らは、 HTML 文書からタグ列の繰返し示するとき、子は左から右に順序付けされているとする。 本論文では、 全ての節点にラベルが与えられたラベル付順序木を考える。
連続的な繰返し構造をもつラベル付順序木をコンパクトに表現するために、繰返し情輻節点というものが導入されたラベル付順序木を考える。繰
とは、繰返し回数 (2 以上) で
返し情報節点パターンを発見し、情報を切り出すためのルール

ラベル付けされた節点であり、.*膨納\sim :u$4l**\mathrm{P}’.\hslash \mathfrak{l}=1\mathrm{f}\Re$

U2W1 納 1\check \rightarrow \sim

図 1 Web ページの例

ことができれば、情報抽出や情報統合などへのさ$r$$v_{1}$$v_{1}$の順序付けされ217された木を表現しているものとする (図 2 参照)。

, 無の場合、それらを表す節点数最小のラベル付順序木はそれぞである。 このとき節点数はそれぞ
れを、 それを用いずにそれが表現れ、 $9arrow 5,5arrow 4,7arrow 5$ というように減っておたすべての子$v_{1}$の親$P$$c_{1},$ $c_{2},$$\ldots,$$c_{k}$を根とする部分木列がの子を根とする部分柱列として

繰返し情報節点

$v$

$r$

回繰返

例 2 図 3 のラベル付順序木$T_{1},$ $T_{2}$$R_{12},$ $R_{2},$ $R_{3}$り、 よりコンパクトな表現になっている。

注意 1 節点数最小の繰返し表現木は–意に定まはとらない場合がある。例えば、下図のを表現する節点数最小
共にラベル付き順序血の繰返し表現木である。 このように節点数最小の$R_{42}$$R_{41}$$T_{4}$

繰返し表現木が複数存在する場合には、それらの図 2 繰返し情報節点とその展開している木に変換する操作を$v$の展開といい、その逆の操作を縮約という。根と葉以外の節点として繰返し情報節点を$0$個以上もつ木を繰返し表現木という。繰返し表現木 $R$ に含まれるすべての繰

返し情報節点を展開すると、繰返し情報節点を 1
つも含まない普通のラベル付順序木 $T$ が得られ3.2. 節で説明するように、最小繰返し表現木算
出問題は、以下のように定義される「高さ 1 のラる。 このとき、「繰返し表現木 $R$ は、 ラベル付き

ベル付順序木に対する節点重み和最小の繰返し表
現木算出問題」 を繰返し解く問題に帰着できる。

順序木

$T$

を表現する」 という。

問題 2(高さ 1 のラベル付順序木に対する節点重み和最小の繰返し表現木算出問題) ラベルの集合の各要素 には実数重み $w(l)$ が与上のラベル付
えられているものとする。 $T$ をを$\Sigma$とし、$l$$\Sigma$$\Sigma$

順序木で高さ 1 の任意の木であるとする。 このとき、 を表現する節点重み和最小の繰返し表現木$R$ を求めよ。 ただし、繰返し情報節点の重みは 1
$T$

とする。

3.

アルゴリズム
この節では、 まず、高さ 1 のラベル付順序木に

図 3 繰返し表現木の例

例1図3の$T_{1},$ $T_{2}$, 聡は–般的なラベル付順序木

であり、それ自身を表現する繰返し表現木でもある。 $R_{11}$ と $R_{12}$ は

を、

は乃を、
を表現する繰返し表現木である。

22.

$T_{1}$$R_{2}$$R_{3}$

は$T_{3}$

最小繰返し表現木算出問題

本論文では、 以下のような問題を扱う。

問題 1(節点数最小繰返し表現木算出問題) 与え

対する節点重み和最小の繰返し表現木算出問題を解くアルゴリズムを示し、その後、そのアルゴリズムを使った節点数最小繰返し表現木算出問題を解くアルゴリズムを示す。

31.

高さ 1 のラベル付順序木に対する節点重み和最小の繰返し表現木算出問題を解くア
ルゴリズム

まず、記述を簡略化するため、以下のような表記法を導入する。高さが 1 で葉の数が のラベル$n$付き順序木 $T$ に対し、 $T$ の子を 番目から 番目までに限った木を $T[i,j]$ で表す。 同じラベル の$i$られたラベル付順序木 $T$ を表現する節点数最小の繰返し表現木 $R$ を求めよ。
ただし、 ここでいう節点数とは、繰返し情報節

点を含めたすべての節点の数のことである。

$j$

$l$

根をもつ木

$R_{1}$と$R_{2}$

に対し、 $R_{1}+R_{2}$ は$R_{1}$を前 (左) にして 2 つの木の根を重ねてできる木と218する。 つまり、 木 $R_{1}+R_{2}$ は、点を根とする部分木列の後に$R_{1}$$R_{2}$の深さ 1 の節の深さ 1 の節点を根とする部分木地を加えたものを、 深さ 1 の節

点を根とする部分木の列としてもつ木である (図任意の自然数 と繰4 右から 2 番目の木参照)

返し表現木 $R$ に対し、1 の節点列の間にラベル$h$$(l_{n}, m_{n})$ :入力 : 根節点のラベ)、 $(l_{1}, m_{1}),$ $(l_{2}, m_{2}),$
高さ 1 の木 $T$ の葉の (ラベル, 重み) の列
出力 $(N_{Rm_{R}},):T$ を表現する節点重み和最小の繰返とその節点重み和 $m_{R}$し表現木 $R$ の根節点
$l$$\ldots,$$N_{R}$$h$。

$h\mathrm{x}R$% [Minimize Height-One Tree]$\mathrm{M}\mathrm{i}\mathrm{n}\mathrm{H}\mathrm{l}\mathrm{T}\mathrm{r}\mathrm{e}\mathrm{e}$は、 $R$ の根と深さの繰返し情報節点を挿

1: $m[i, i]arrow m_{i}$ for $i=1,2,$
2: $m[i,j]arrow\infty$
for $i=1,2,$ $n,j=1,2,$
3: for $k=2$ to do
4:
for $i=1$ to $n-k$ do
5:
for $j=0$ to $k-2$ do$\ldots,$$\ldots,$

入した形の木を表すものとする。 つまり、は、深さ 1 の節点としてラベル$h$$h\mathrm{x}R$の繰返し情報節点のみをもち、 $R$ の深さ 1 の節点を根とする部分

木列を, 深さ 2 の節点を根とする部分木列としてもつ木である (図 4 右端の木参照)$n$$\ldots,$$n,i<j$$n$

if $m[i,i+j]+m[i+j+1,i+k-1]$$<m[i, i+k-1]$ then6:$m[i,i+k-1]arrow m[i,i+j]$7:$+m[i+j+1,i+k-1]$

。

8:
9:
10:
11:
12:
13:

$\mathrm{t}\mathrm{y}\mathrm{p}\mathrm{e}[i,i+k-1]arrow(2,j)$

end ifend for$larrow 1$

while $i+lk+k-1\leq n$ do
if
then
break
end ifif $m[i,i+k-1]+1<m[i,i+lk+k-1]$
then$m[i,i+lk+k-1]arrow m[i,i+k-1]+1$$(\iota_{i+1k},\iota_{:+lk+1},$$\iota_{:+1\mathrm{k}+\mathrm{k}-1)}$$\ldots,$$\neq(\iota_{:}, \iota_{:+1}, \ldots, \iota_{:+k-1})$

図 4 根のラベルが等しい 2 つの繰返し表現木の足し算と繰返し表現木のスカラー倍
命題 1 繰返し表現木 $R$ が、高さ 1 で葉の数が $n\geq$のラベル付き順序体 $T$ を表現する節点重み和最$2$小繰返し表現木であれば、 以下の Case 1 またはCase 2 のどちらかが成り立つ。ただし、 $R[i,j]$ は$T[i,j]$ を表現する節点重み和最小繰返し表現木とする。

Case 1 $kh=n$ を満たすある自然数

$k$

と

$h$

が存

在し、 $R=h\mathrm{x}R[1, k]$ を満たす。

Case $21\leq k<n$ を満たすある

$k$

14:
15:
16:

17:

:
end if19:$larrow l+1$
20:
end while
21:
22:
end for23: end for
24: $m_{R}arrow m[1,n]$25:
26: return $(m_{R}+1, N_{R})$$18$$\mathrm{t}\mathrm{y}\mathrm{p}\mathrm{e}[i,i+lk+k-1]arrow(1, k)$$N_{R}arrow \mathrm{C}\mathrm{o}\mathrm{o}\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{c}\mathrm{t}\mathrm{M}\mathrm{i}\mathrm{n}\mathrm{h}\mathrm{e}\mathrm{e}$($l,l_{1},$$l_{n}$$\ldots,$, type)が存在し、$R=R[1, k]+R[k+1, n]$ を満たす。
(証明) $R$ の深さ 1 の節点が 1 つの節点 のみの場合は、 展開したときに葉が 2 つ以上になるという仮定から は繰返し情報節点でなければならない。 したがって $kh=n$ を満たすある自然数 とが存在し、 $T[1, k]$ を表現するある繰返し表現木$R’$ が存在して $R=h\mathrm{x}R’$ と書ける。 $R$ は節点重み和最小であるので $R’$ は $T[1, k]$ を表す節点重み

図 5 アルゴリズム MinHlbee

$v$

$v$

$k$

$h$

表現木、

$R_{2}$

は $T[k+1, n]$ を表現する繰返し表現木であり、 $R=R_{1}+R_{2}$ と書ける。 $R$ は節点重み和最小なので、$R_{1},$ $R_{2}$はそれぞれ $T[1, k],$ $T[k+1, n]$を表現する節点重み和最小の繰返し表現木でなければならない。 よってこのとき、 Case 2 が成り立っている。

口

和最小の繰返し表現木でなければならない。 したがってこのとき、 Case 1 が成り立っている。

この命題より、 $T$ を表現する節点重み和最小のの深さ 1 の節点数が 2 以上の場合を考える。
を根と 1 番目の深さ 1 の節点のみからなる木
展開した木を [ , k]、根と 2 番目以降の深さ 1 の繰返し表現木を求めるには、 Case 1 か Case 2 を満たす候補木 $R$ の中から探せばよいことがわかを展開した木を $T[k+1, n]$

求まっていれば、 $R$ を求めることができる。 同は $T[1, k]$ を表現する繰返し

様に、 $j-i<k$ に対する $R[i,j]$ が求まっていれ$R$$R_{1}$$T$$1$

節点のみからなる木とする。このとき、$R_{2}$$R_{1}$る。したがって、 $j-i<n-1$ に対する $R[i,j]$ が

219

ば、 $j-i=k$ を満たす $R[i,j]$ を求めることがで$R$きる。 よって、 $R[i, i]=T[i, i]$ という事実を使っよって、 アルゴリズム MinHITree は与えられたて、動的計画法により節点重み付きラベル付き順序木 $T$ に対し、小の繰返し表現木$R$$T$を表現する節点重み和最を求めることができる。

の根節点を$N_{R}$

として $(m_{R}, N_{R})$ を出力する。

命題 2 アルゴリズム

リズム MinHlIree を示す。 このアルゴリズムで$O(n^{3})$

の

$i$

$k$

に対し、すべてに対する $T[i, i+k-1]$ を表現する節点重み和

最小の繰返し表現木 $R[i, i+k-1]$ の根節点を除いた節点重み和 $m[i,i+k-1]$ を $k=1,2,$$\ldots,$$n$の順番に求める。 $k=1$ の場合は、 $R[i, i]=T[i, i]$ なの
で $m[i, i]=m$ : となる (1 行目)。 $k\geq 2$ の場合は、

命題 1 の 2 つの Case を満たす候補木の中から節点重み和が最小となるものを探す。 Case 2 を満たすものは、 5 行目から 10 行目で探される。 Case
1 を満たすものは、 11 行目から 21 行目で探される。 11 行目から 21 行目では、 から 個単位の $h\geq 2$ 回の繰返しに対して $m[i, i+hk-1]$ を
$k$

$i$

計算しているが、 が小さい場合から計算してい$k$るので、 k=k。のときには、すでに$i$から $k<$ 緬を表

現する節点重み和最小の繰返し表現木 $R$ の節点

図 5 に、高さ 1 のラベル付順序木に対する節点
重み和最小の繰返し表現木算出問題を解くアルゴ
は、 $1\leq k\leq n-i+1$ を満たす

$T$

重み和

$m_{R}$と $R$ の根節点 $N_{R}$ の組を出力する。
$MinH\mathrm{J}$Tree の時間計算量はである。

(証明) 5 行目から 10 行目の for ループは$12$ 行目から 21 行目までの while) レープは $O(n)$であるので、 3 行目から 23 行目までのノレープは$O(n)_{\text{、}}$$O(n^{3})$である。 他の処理はすべて $O(n)$ であるから、 全体として $O(n^{3})$ で計算できる。

32.

口

最小繰返し面諭木算出問題を解くアルゴリ
ズム

この節では、 与えられたラベル付順序木 $T$ を表現する節点数が最小の繰返し表現木 $R$ を求めるアルゴリズム(図 6) を説明$\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{v}2\mathrm{M}\mathrm{i}\mathrm{n}\mathrm{R}\mathrm{R}\mathrm{B}\mathrm{e}\mathrm{e}$する。
[Convert to the Minimum Repetition Representation TYee]
入力: ラベル付順序平 $T$ の根節点$\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{v}2\mathrm{M}\mathrm{i}\mathrm{n}\mathrm{R}\mathrm{R}\mathrm{T}\mathrm{r}\propto\%$

個単位の繰返しに対して、 Case 1 を満たす候補木の探索は終っている。 $T[i,\dot{j}+k_{0}-1]$ に対してはCase 1 を満たす候補木は他にはないので、 $k=k_{0}$の処理に入った時点で $m[i, i+k_{0}-1]$ には、 Case
1 を満たす候補木の節点重み和の最小値が入っている。 したがって、 $k=k0+1$ の処理を行なう
ときにはすべての$i$に対し、 $m[i, i+k_{0}-1]$ には$R[i, i+k_{0}-1]$ の根節点を除いた節点重み和が設定されている。

$N_{T}$

出力 $(N_{R}, m_{R}):T$ を表現する節点数が最小のとその節点数 $m_{R}$繰返し表現木 $R$ の根節点
$N_{R}$

が子を持たない then
1: if
2: return $(N_{T}, 1)$
3: elseのラベルを \iota 、子の列を4:の STEP 1\sim 4 を順に実行.
5: STEPI.
$N_{T}$$N_{T}$$C_{1},$ $C_{2},$$C_{k}$$\ldots,$$(N_{i},m_{i})arrow \mathrm{C}\mathrm{o}\mathrm{n}\mathrm{v}2\mathrm{M}\mathrm{i}\mathrm{n}\mathrm{R}\mathrm{R}\mathrm{r}\mathrm{r}\mathrm{e}\mathrm{e}(C_{1})$

6:

STEP2.

7:

STEP3.

:STEP4.

forとする。 次$\mathrm{i}=1,2,\ldots,\mathrm{k}$$(l_{1},l_{2}, \ldots,l_{k})arrow \mathrm{L}\mathrm{a}\mathrm{b}\mathrm{e}\mathrm{l}\mathrm{i}\mathrm{n}\mathrm{g}(N_{1}, N_{2}, \ldots N_{k})$

したがって、 $m[1, n]$ には、 $k=n$ のとき、 $T$ に対する節点重み和最小の繰返し表現木 $R=R[1, n]$の、根を除いた節点重み和が設定される。 を表
す節点重み最小の繰返し表現木 $R$ は、それぞれの$m[i, i+k-1]$ を計算するときに Case 1 と Case 2
でどちらの方が小さくなるか、 またその Case においてどの単位で繰返したり、どの位置でわかれたりすれば最小となるのかをに記憶させているので、から最小になるよう$T$$\mathrm{t}\mathrm{y}\mathrm{p}\mathrm{e}[i, i+k-1]$$(N_{R},m_{R}\vdash \mathrm{M}\mathrm{i}\mathrm{n}\mathrm{H}1’\mathrm{R}\mathrm{o}\mathrm{e}(l,l_{1}, l_{2}, \ldots,l_{k},m_{1},m_{2}, \ldots,m_{k})$

$8$

根が
置換

$N_{R}$の木 $R$ の葉節点でラベルが,$l_{1}$の節点を$N_{1}$に9: end if
10: return $(N_{R}, m_{R})$図 6 アルゴリズム$\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{v}2\mathrm{M}\mathrm{i}\mathrm{n}\mathrm{B}\mathrm{R}\mathrm{n}\mathrm{e}\mathrm{e}$$\mathrm{t}\mathrm{y}\mathrm{p}\mathrm{e}[1, n]$$\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{v}2\mathrm{M}\mathrm{i}\mathrm{n}\mathrm{R}\mathrm{R}\mathrm{R}\mathrm{a}\mathrm{e}$に選ばれた繰返し単位や分割位置を辿ることにより節点重み和. $m[1, n]$ を達成する繰返し表現木 $R$

は、 $T$ の根節点が入力されを表現する最小節点数の繰返し表現木 $R$の組を出力する。
とその節点数の根節点根だけからなる高さが の木 $T$ が与えられた場
ると、

$T$

$N_{R}$

を $O(n)$ の時間で構成できる。 このようなアルゴ

リズムを CootructMinhee とする@ MinHlRee
は $m[1, n]$ を$m_{R^{\text{、}}}\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{s}\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{c}\mathrm{t}{\rm Min}^{r}\mathrm{b}\mathrm{e}\mathrm{e}$で求まった$m_{R}$$0$

合は、 $T$ を表現する繰返し表現木が $T$ そのものしかないため、 $(N_{T}, 1)$ を出力する。

220

高さ力 O 以上の木 $T$ の根節点
た場合は、
葉節点

$N_{T}$の子の列$L_{1},$ $L_{2},$$L_{k}$$\ldots,$$N_{T}$$C_{1},$ $C_{2},$$C_{k}$$\ldots,$が入力される。 $T$ の根節点 $N_{T}$ の子の列をに対応する

それらを根とするをもつ高さ 1 の漫

$T’$

で、そ

れぞれの葉節点が以下の条件 (1) を満たすラベルをもつものを求める。ただし、$l_{k}$$l_{2},$$l_{1},$$\ldots,$$C_{i}$

を根とする部分木を鶉とする。

$T$$C_{1},$ $C_{2},$の部分木をる。数学的帰納法の仮定より、の STEP 2 で求まる (Ni,$m_{i}$とし、$C_{k}$$\ldots,$$T_{1},$ $T_{2},$$\ldots$, 臨とす$\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{v}2\mathrm{M}\mathrm{i}\mathrm{n}\mathrm{R}\mathrm{R}\mathrm{h}\mathrm{e}\mathrm{e}$) は、乃を表現する節

点数最小の繰返し表現木鳥の根節点瓦とその節の組になっている。 を表現する節点数. 点数とする。 このと最小の繰返し表現木の 1 つを$T$

$m_{i}$$R^{*}$$l_{t}’=l_{j}\Leftrightarrow T_{i}=T_{j}$for $(i,j)\in\{1,2, \ldots, k\}^{2}$ (1)

このようなラベル付けを行なうのが図 6 の Label-ing 関数である (STEP 2)。図 6 のアルゴリズムでは、 Labeling 関数の引数として(STEP 1) で求めた鴎を表現する最小繰返し表現$\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{v}2\mathrm{M}\mathrm{i}\mathrm{n}\mathrm{R}\mathrm{R}\mathrm{h}\mathrm{e}\mathrm{e}$の根節点瓦の列を渡しているが、
RRTree は決定的アルゴリズムなので $T_{i}=T_{j}$ と島 $=R_{j}$ は等価となることに注意されたい。 の節点数は鶉の節点数以下であるため、 オーダー
的には差がでないが島で比較した方が効率がよい。 このようにして求めたラベルちの実数重み木$\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{v}2{\rm Min}$$R_{i}$$R_{i}$$w(l_{i})$を$R_{i}$の節点数

根節点のラベルは$m_{i}$$N_{T}$に設定する。 また、 $T’$ ののラベ\sim 嫁とし、 の実数重$l$

みは 1 と設定する。 $T$ からこのように構築された
高さ 1 の木 $T’$ とラベルの重み $w$ に対する 「高さ1 のラベル付順序木に対する節点重み和最小の繰返し表現木算出問題」 を関数 MinHITree で解き(STEP 3)、得られた T 宝対する節点重み和最小とその節点重み和の繰返し表現木 $R$ の根節点を得る。最後に $R$ の葉節点各々を、 ラベルが$N_{R}$$m_{R}$$l_{i}$

であれば鶉を表現する最小繰返し表現木亮のき、$R^{*}$

において、展開したときになる部分$R_{1}^{\mathrm{r}},$$R_{2}^{*},$$R_{k}^{*}$$\ldots,$$T_{1},$ $T_{2},$$T_{k}$$\ldots,$はそれぞれ$T_{1},T_{2},$ $\ldots,T_{k}$の節点数最小繰返し表現木になっている。 した
で置き換
を
がって
$R_{1}^{*},$ $R_{2}^{*},$えた木も$R^{**}$$R_{1},$ $R_{2},$$R_{k}^{*}$$\ldots,$$T$$R_{k}$$\ldots,$を表現する節点数最小の繰返し

表現木である。 この繰返し表現木$R^{**}$

において、の内部以外の繰返し情報節点をすべを縮約するとする。 これはて展開した木をが得ことによって節点数最小の繰返し表現木においてられることを意味する。
$R_{k}$$R_{1},$ $R_{2},$$\ldots,$

$Q$

$Q$

$R^{\mathrm{r}*}$

$Q$

をラベル

$\mathit{1}_{1}$,$R_{k}$$\ldots,$の葉節点に置き換えた木 $T’$$l_{k}$$l_{2},$$R_{1},$ $R_{2},$$\ldots,$

は、 明らかに MinHITree に入力される木に等し
い。

ベル

の節点数

$R_{k}$$R_{1},$ $R_{2},$$\ldots,$$l_{1},$ $l_{2},$$\ldots$$m_{1},$ $m_{2},$$\ldots,$$m_{k}$を、ラ, 砺の重みと考え、根節点のラベルの重みを 1 とみなせば、 $T’$ の節点重み和と $Q$ の節点数は等しい。 T 宝対する縮約と $Q$ に対する縮約は
1 対 1 に対応し、 $T’$ から縮約により出来る木 $T”$
からラベ)y ,の葉節点をに置き換えてできる木は、対応する の縮約によ$4\rangle$$\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{v}2\mathrm{M}\mathrm{i}\mathrm{n}\mathrm{R}\mathrm{R}\mathrm{h}\mathrm{e}\mathrm{e}$。

は、 こうしてできた $R$ の根節点 $N_{R}$ と節点重み和$m_{R}$の組を出力する。

命題 3 ラベル付順序木 $T$ に対し、 $Conv\mathit{2}MinRRToee$の出力が $(N_{R}, m_{R})$ であったとする。 このとき、$N_{R}$を根とする繰返し表現木 $R$ は $T$ を表現する

節点数最小の繰返し表現木であり、その節点数は$m_{R}$$R_{k}$$R_{1},$ $R_{2},$$l_{k}$$l_{2},$$\mathit{1}_{1}$$\ldots,$$\ldots,$$Q$

りできる木 $Q’$ に–致し、$T”$ の節点重み和と $Q’$ の節点数は常に等しい。したがって $T’$ に対する節点

重み和最小の繰返し表現木 $R’$ のラベ) 嫁 1, , ...,に置き換えて出来る木の葉節点を$R$ は、 $Q$ を縮約して出来る繰返し表現木の中で節$l_{2}$

根節点に置換する (STEPに$R_{1},$ $R_{2},$$l_{k}$$R_{k}$$\ldots,$

点数最小のものであり、その節点数は $R’$ の節点
重み和に等しい。 STEP 3, 4 ではそのような $R$ に対する根節点$N_{R}$

及び節点数

よって、 $T$ の高さが$k$

$m_{R}$を求めている。

の場合も命題が成り立つ。
口

である。

(証明)

$T$

が高さ

$0$

の場合は、

$T$

は根節点

$N_{T}$

のみからなり、 この場合 $(N_{R}, m_{R})=(N_{T}, 1)$ である o

命題 4 節点数 の任意のラベル付き順序木に対し、 アルゴリズム COnv2MinRR 伽 e の時間計算

このとき、 $T$ を表現する節点数最小繰返し表現木

量は

も根節点

$N_{T}$

のみからなる木であり、その節点数は 1 である。よって $T$ の高さが$0$の場合、命題は成り立つ。
高さが $k-1$ 以下のラベル付順序木に対して命題が成り立っているとする。 を高さが の木とす
$T$

$k$

$n$

$O(n^{\theta})$である。

(証明) 入力木$T$の高さんに関する数学的帰納法で証明する。
$h=0$ のとき、 2 行目でリターンするので、 明

らかに $O(1)$ である。

$\Gamma$

221

ん $\geq 1$ のとき、 h<h。を満たす高さ

対する$\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{v}2\mathrm{M}\mathrm{i}\mathrm{n}\mathrm{R}\mathrm{R}\mathrm{R}\mathrm{e}\mathrm{e}$が、 ある定数

$c$

$h$

の木

$\tau*$に$\sum_{i=1}^{k}n_{i}^{3}+nk+k^{3}+k\leq n^{3}$より (後述).

の計算時間丁 ime(T*)

に対してTime $(T)\leq cn^{3}$Time

よって、 $T$ の高さがん $=h_{0}$ のときも成り立つの$(T^{*})\leq cn^{3}$

で、$C\mathrm{o}\mathrm{n}\mathrm{v}2\mathrm{M}\mathrm{i}\mathrm{n}\mathrm{R}\mathrm{R}\mathrm{R}\mathrm{e}\mathrm{e}$の計算量は $O(n^{3})$ である。

であると仮定する。 $T$ の高さを h=h。とする。 $T$の深さ 1 の節点を根とする木をる。 また、

とする。

仮定より、

$\ldots$とす$T_{k}$$\ldots,$, 寡の節点数を, 乃は高さが妬より小さいので、$T_{1},$ $T_{2},$$T_{1},$ $T_{2},$$T_{1},$ $T_{2},$$n_{1},$ $n_{2},$$\ldots$$T_{1}(1\leq i\leq k)$に対し$\ldots,$$n_{k}$$\mathrm{t}\mathrm{i}\mathrm{m}\mathrm{e}_{1}$$n= \sum_{1=1}^{k}.n_{i}+1$

を示す。

より、

$\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{v}2\mathrm{M}\mathrm{i}\mathrm{n}\mathrm{R}\mathrm{R}\mathrm{b}\mathrm{e}\mathrm{e}$の計算時間は高々cn3i 時間である。 よって、 Step
1 にかかる時間$\sum_{i=1}^{k}n_{i}^{3}+nk+k^{3}+k\leq n^{3}$

右辺 $=n^{3}=( \sum_{i=1}^{k}n:+1)^{3}$は$=( \sum_{i=1}^{k}n_{1})^{3}+3(_{:=1}\sum^{k}n:)^{2}+3\sum_{i=1}^{k}n:+1$$\mathrm{t}\mathrm{i}\mathrm{m}\mathrm{e}_{1}=\sum_{i=1}^{k}Time(T_{i})\leq\sum_{i=1}^{k}cn_{i}^{3}$.

$= \sum_{2=1}^{k}n_{1}^{3}+(_{:=1}\sum^{k}n:)^{3}-\sum_{i=1}^{k}n_{1}^{3}$である。

Step 2 の Labeling 関数では、丁 1,$T_{2},$$T_{k}$$\ldots,$にの全ての対する最小繰返し表現木
組合せに関して比較を行い、 同じ木には同じラベ$R_{1},$ $R_{2},$$+3(_{i=1} \sum^{k}n:)^{2}+3\sum_{2=1}^{k}$$ni+1$$R_{k}$$\ldots,$

ルを、異なる木には異なるラベルを付ける。

節点数は高々n’ であり、数

$c_{2}$$R_{i}$と$R_{j}$$R_{i}$のの比較はある定に対して高々 $c_{2} \min\{n_{i}, n_{j}\}$ 時間でできる。

したがって、 Step 2 にかかる時間$\mathrm{t}\mathrm{i}\mathrm{m}\mathrm{e}_{2}$ここで、 n’ は全て 1 以上なので、$( \sum_{1=1}^{k}.n:)^{3}-\sum_{i=1}^{k}n_{i}^{3}\geq k^{3}-k$が成り立つ.

よって、は$n^{3} \geq\sum_{:=1}^{k}n_{1}^{3}+k^{3}-k+3(\sum_{:=1}^{k}n_{i})^{2}+3\sum_{i=1}^{k}n:+1$

time2$\leq c_{2}\sum_{i=1}^{k}\sum_{j=:+1}^{k}\min\{n_{i}, n_{j}\}\leq c_{2}nk$

また、 $k \leq n-1=\sum_{i=1}^{k}n$ : であるから、である。

Step 3 にかかる時間
定数$c_{3}$$\mathrm{t}\mathrm{i}\mathrm{m}\mathrm{e}_{3}$は、命題 2 よりある$n^{3} \geq\sum_{i=1}^{k}n_{i}^{3}+k^{3}+3(\sum_{:=1}^{k}n_{i})^{2}+2.\sum_{*=1}^{k}n_{i}+1$に対して
方,$\mathrm{t}\mathrm{i}\mathrm{m}\mathrm{e}_{3}\leq c_{3}k^{3}$$E_{\mathrm{J}} \text{、}\mathrm{Z}=\sum_{i=1}^{k}n_{i}^{3}+k^{3}+nk+k$である。

Step4 にかかる時間 time4 は、 ある定数 c4 に対して$\leq\sum_{i=1}^{k}n_{1}^{8}+k^{8}+(_{i=1}\sum^{k}n:)^{2}+2\sum_{:=1}^{k}$

time4

ni

$\leq c_{4}k$である。したがって、 Time $(T)$ に対して次式が成よって左辺$\leq$

右辺が成り立つ。

口

り立つ。

Time

. $+c_{2}nk+c_{3}k^{3}+c_{4}k$4.

実験$(T) \leq c\sum_{i=1}^{k}n_{1}^{3}$$c\geq c_{2},$ $c_{3},c_{4}$とするとHTML 文書の tag troe を最小繰返し表現木に変換した際、 どれほど繰返し構造を把握できるか$\backslash$Time $(T) \leq c\sum_{i=1}^{k}n_{i}^{3}+cnk+ck^{3}+ck$を評価する実験を行った。

222

41.

方法

5.

まとめ

データとして、 商品の情報が掲載されている

本稿では、 ラベル付順序木の繰返し構造を簡潔

Web ページを 6 ページ、検索エンジンの検索結果ページを 3 ページ用いた。各 HTML 文書は Tidy
[7] を用いて整形したのち、 tag tree の最小繰返し

かつ明示的に表す表現を提案した。 また、 その表

表現木を求め、 元の木の節点数と比較した。 また各ページのうち、 Web ブラウザ上での目視によっ則を用いた既存法 [4-6] では類似した構造の繰返て繰返し構造とみなせる部分に着目し、 最小繰返
し表現木においてその部分が繰返しとして縮約できているかを調べた。 なお、 節点のラベルが同出できないという問題点がある。情報抽出の観点であるかの比較にはタグの種類のみを用い、 タグに付加される属性は用いなかった。 また、 テキス

ト部分はその内容によらず同じラベルの節点とみ
なした。

4.2.

考察

節点数は平均して 451% に減少した。また、繰
返し構造と判断された部分のうち 786% が繰返し構造として縮約された。楽天を例にとると、繰返し構造とみなした部分がすべて繰返し構造として縮約されており、 目視による解釈と–致した構造把握が行えたと言える。 また節点数も比較的少な
くなり、 多くの繰返し構造が縮約されていると考えられる。 -方、Yahoo!検索結果では、繰返し構造とみなした部分のうち、繰返し単位を構成する
要素数の異なりによって縮約できなかった部分が多かった。

現のうち節点数が最小のものを節点数 に対して $O(n^{3})$ で求めるアルゴリズムを示した。 経験$n$

しも抽出可能であるが、今回提案した表現では抽からは類似した繰返し構造の把握も必要であり、そのための手法の検討が今後の課題として挙げら
れる。

参考文献
, A. Silva and J.
[1] A. Laender, B.
Teixeira, A Brief Survey of Web Data Extraction Tools, $ACM$ SIGMOD Record, 31,
2(2002), 84-93.
[2] 山田泰寛池田大輔坂本比呂志有村博紀,$\mathrm{R}\mathrm{i}\mathrm{b}\mathrm{e}\mathrm{i}\mathrm{r}\triangleright \mathrm{N}\mathrm{e}\mathrm{t}$WWW からの情報抽出: ウェブラッパーの自動構築, 人工知能学会論文誌. 19, 3(2004), 302310.
[3] N. Kushmerick, Wrapper Induction for Inforthesis, University ofmation Extraction.
Washington, 1997.
[4] C-H. Chang and S-C. Lui, IEPAD: Information
Based on Pattern Discovery.
$Pmceed\iota’ngs$tof ん e JOth Intemationd Conference on t ん e World Wide Web, 2001, 681688.
[5] B. Liu, R. Grossman and Y. Zhai, Mining
Data Records in Web Pages. Proceedings of$\mathrm{P}\mathrm{h}\mathrm{D}$$\mathrm{E}\mathrm{x}\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{c}\mathrm{t}\mathrm{i}\dot{\mathrm{o}}\mathrm{n}$the 9th $ACM$ SIGKDD International Con-

ference on Knowledge Discovery and Data
Mining, 2003, 601-606.
[6] 南野朋之, 繰返し構造に基づいた Web ページの構造化, 情報処理学会論文誌, 45, 9(2004),

2157-2167.
[7] Tidy, http:$//\mathrm{w}\mathrm{w}\mathrm{w}.\mathrm{w}3.\mathrm{o}\mathrm{r}\mathrm{g}/\mathrm{P}\bm{\mathrm{m}}\mathrm{p}\mathrm{l}\mathrm{e}/\mathrm{R}\mathrm{a}\mathrm{g}\mathrm{g}\mathrm{e}\mathrm{t}\mathrm{t}/\mathrm{t}\mathrm{i}\mathrm{d}\mathrm{y}/$