DEIM Forum 2014 D7-5

テキストおよび構造の類似度に基づいた XML データに対する効率的な類似検索
涼介†

小柳

天笠

俊之††

北川 博之††† 筑波大学情報学群情報科学類 〒 305–8573 茨城県つくば市天王台 1 丁目 1-1†† 筑波大学システム情報系情報工学域 〒 305–8573 茨城県つくば市天王台 1 丁目 1-1
E-mail: †rkoya@kde.cs.tsukuba.ac.jp, ††{amagasa,kitagawa}@cs.tsukuba.ac.jp
あらまし XML は構造データや半構造データを記述するためのデータフォーマットであり，今日では広く用いられるようになっている．現在 Web 上には膨大な XML データが存在するが，中には内容が大きく類似している情報も多数存在している． 膨大な情報からある文書との類似度を効率的に計算することができれば，類似部分の検出を行うことができ， 引用，盗用の検出や重複除去等様々な用途に活用できると考えられる．XML データにはテキスト情報に加えて文書の構造情報を持つという特徴がある．このため，類似した XML データを検索するには，テキスト上の類似度と構造上の類似度を考慮した手法が必要である．本研究では，XML の木構造とテキストノードのラベルの情報を利用して類似度を計算し与えられた XML データの重複部分を検出する手法を提案する．
キーワード

XML, 部分木マッチング, 類似検索, 木編集距離

1. 序

似度として適用するという手法である．キーワード類似度とし論ては TF-IDF 等を用いてキーワードベクトルを構成しベクトル間のコサイン類似度を適用する手法や，キーワード集合間の1. 1 XML と類似検出（注 1）

Extensible Markup Language (XML)は拡張可能なマー

Jaccard 係数を適用する手法が使用されている．

クアップ言語の一つであり，利用者の目的に応じたタグを定義

1. 3 類似部分木探索問題

することで，文書やデータの構造や意味を汎用的に表現するこXML の類似検出に関する問題の中でも特に，与えられたとができる．その汎用性を受け，XML は 1998 年に W3C によXML データ（クエリ XML）に対して，予め用意しておいた

り策定，勧告されてから現在にかけて広く普及し，様々な用途

XML データ（対象 XML）に含まれるすべての類似した部分木に使われている．

を列挙する問題を類似部分木探索問題と呼ぶ．

しかし広く使われていることに伴い，内容が類似している情類似部分木探索問題を対象とした研究として Augsten らの提報の散在がしばしば見かけられる．このような類似した複数の案する TASM [5] や Cohen らの提案する Structure Search [6]

情報を見つけ出すことができれば，情報の相互補完，重複部分がある．[5], [6] はどちらも類似度として木編集距離 [2] を使用しの除去，コピーの検出等，様々な用途に活用できる．

ており，計算手法に木編集距離の算出回数を低減する工夫を取1. 2 XML における類似度の種類

り入れることで高速化を達成している．

XML は半構造データであり，テキスト情報に加えて，デー

TASM では，Top-k 類似部分木探索問題（類似部分木の上位

タ自体が木構造に基づく構造を持つ．テキストデータの比較や

k 個の検出）を解く手法について提案している．クエリ XML

構造情報など XML の持つ様々な情報を利用した類似度の計算のノード数に基づき探索対象の部分木のノード数に上限を設けについて多くの手法が研究されている [1]．

ることで処理の効率化を実現している．

XML データの構造を考慮した類似度計算手法として代表的Structure Search では，前述の Top-k に加えて「類似度を表なものに，XML データを図 1 のように木構造とみなしその木

す木編集距離が m 以下である部分木」という条件を加え，条構造の木編集距離 [2] をベースとして類似度を計算する手法が件を満たす部分木を求める手法について提案している．さらに，ある．しかし一般に木編集距離の計算は時間計算量が高コスト

この手法では対象 XML が持つ部分木全ての構造を調べ，予めであるため，巨大な XML ファイルを対象とした場合，効率的同一の構造を持つ部分木を特定しておき，クエリを処理する時な計算手法が必要不可欠となる．

にこの情報を使い類似度の再利用を行っている．加えて，必要XML データの内容を考慮した類似度計算手法として代表的な情報を予めインデックス付けしておくことで情報の参照の高なものに，情報検索の技術をベースとする方法がある [3], [4]．

速化を図り，TASM よりも効率的な計算手法を提案している．

これは類似度を測りたい二つの XML から単語や q-gram を抽しかしながら，TASM や Structure Search では類似度とし出し，それらの類似度（キーワード類似度）を求め XML の類て木編集距離のみを考慮しており，これにはいくつかの問題点が存在する．XML データにおいて，図 2 の例のように XML（注 1）：http://www.w3.org/XML/

データ中の構造がある程度規則性を持つ場合が少なくない．こarticles
articleauthor“John”

articlearticlecategoryauthorcategoryauthorcategory“DB”“John”“DB”“Peter”“Mining”

3

A



B

3

C

X

B

C

DocumentQuery

図 1 XML と木構造

D

E

D

F

1
articlesarticleauthor“John”

F

articlearticlecategoryauthorcategoryauthorcategory“DB”“John”“DB”“Peter”“Mining”

図2

図3

Document

Query

G
2

木編集距離の計算例

テキストノードとエレメントノード

2. 関 連 研 究
れは，データを中心に扱ういわゆるデータ指向の XML データによく見られる．この場合，要素のラベルや木自体の構造はほぼ同一であるため，二つの部分木の類似性を判定する場合には，
テキストノードの内容に関する類似性を評価したほうが，より期待する結果が得られると考えられる．TASM や Structure

Search では，テキストノードについて，値の完全一致だけを評価しているため，テキストの類似性を考慮した評価は行っていない．

1. 4 本研究の目的
本稿では，類似部分木探索問題に対して前述の問題点を解決するためにテキスト類似度を導入し，XML の構造と内容の両面を考慮した類似部分木検出を行う．部分木同士の木編集距
離に基づいた構造類似度，テキストノードが持つ単語集合のJaccard 係数に基づくテキスト類似度の両方を考慮した類似度について考え，各類似度に対して任意のパラメータで重み付けをすることで柔軟な類似条件の設定を実現する．テキスト類似度を導入することで，既存研究よりも柔軟な類似判定を実現し，さらに処理の効率化にも活用する事を目的とする．また，全てのデータがメモリに乗り切らないような巨大な XML データに対して類似度の計算を行う事を想定し，そのようなデータの処理に耐え得る効率的な類似度計算アルゴリズムを提案する．
加えて，実際に手法の実装を行い，実際の巨大な XML ファ
イルに対して本手法を適用し，巨大な XML データに対しても適用可能な性能かどうか，既存手法との実行時間の違いを確認
する．

1. 5 本論文の構成
本論文の構成は以下のとおりである．第 2. 章で関連する研究について述べ，前提知識について触れる．第 3. 章で本研究の提案手法について述べる．本手法において効率性の向上のために使用した工夫点と，それを取り入れたアルゴリズムの全体像について説明する．そして第 4. 章で評価実験の結果について述べ，本手法の効率性の確認と既存手法との比較を行う．第5. 章で本稿のまとめと今後の課題を述べる．

XML 類似度に関する研究は大きく以下の 3 つに分けられる．
（ 1 ） 与えられた 2 つの XML の木全体の類似度を求める
研究（ 2 ） 与えられた XML 全体と類似した別の XML の部分木を求める研究（類似部分木探索問題）（ 3 ） 与えられた 2 つの XML の類似した極大部分木ペアを求める研究（類似極大部分木探索問題）
まず 2. 1 節では本研究で使用している木編集距離の計算手法について紹介する．その後 XML の類似度に関する研究として

2. 2 節で 1，2. 3 節で 2，2. 4 節で 3 に関する研究を紹介し，本研究との関係や相違点を説明する．

2. 1 木編集距離の計算手法
XML データ同士の比較において，木編集距離 [2] がよく用いられる．木編集距離は木構造に対する距離の指標の一種で，ある一方の木に対しノードの追加，削除，改名などの操作を行い，もう一方の木と同じ構造に変形させるのに必要な操作のコストをその二つの木の距離とする手法である．各操作におけるコス
トには予め適当な値を設定しておく必要がある（本手法では全ての操作のコストを 1 と設定する．
）
例として図 3 の T1 , T2 間の木編集距離を考える．T1 を T2に変形させるためには（ 1 ） ノード E を削除（ 2 ） ノード G を追加（ 3 ） ノード A をノード X に改名の 3 つの操作が必要となる．よってこれらの操作のコストの合計である 3 が T1 , T2 間の木編集距離となる．
木編集距離の計算手法については様々な研究が存在するが，Zhang らの提案している手法 [7] は動的計画法を用いて 時間計
算量 O(n2 m2 ) ，空間計算量 O(nm) （ここでそれぞれ n, m は比較している木のノード数）を達成している．
本研究では構造類似度の計算に使用する木編集距離の計算手法として [7] を使用する．なお，木に対する操作としてはノードの追加，削除，改名のみを許し，各操作にかかるコストは全

て 1 とする．

2. 2 木全体の類似度計算手法に関する研究

速化が確認されている．
これらの手法はどちらも類似度として木編集距離のみを使用

木全体と木全体の類似度計算手法として Apichaya らの提案しており，類似部分木の上位 k 個を求める事を目的としていする KLAX と LAX & KEY [3] や，Luis Leitao らの提案する．本研究の提案手法では，木編集距離に加えてテキスト類似る [4] がある．

度も考慮しており，さらに Top-k を検出するのではなく類似度

KLAX は XML 木を複数の木に分解し各部分木のリーフノー
ドのキーワード類似度を求めた後に分割統治法を用いて XMLに閾値を設けることで検出の条件を設定している．この点がこれらの関連研究と異なる点である．

木全体の類似度を求める手法である．LAX & KEY はリーフ

2. 4 類似極大部分木探索問題に関する研究

ノードのキーワード類似度とリーフノードの持つラベルが完全

2 つの XML に含まれる部分木と部分木の組み合わせの内，一致している割合を重み付けして統合し類似度とする手法であ最大の類似部分木組み合わせを検出する研究として寺島らの [9]る．これら二つの手法はどちらもキーワード類似度としてテキがある．

ストを単語単位で分割し名詞以外を取り除いたもののコサイン類似度を使っている．

寺島らの手法では，各部分木間の類似度を子部分木同士の類似度を利用し再帰的に求めることで効率的なアルゴリズムを実この研究では Oﬃce Open XML File Format を対象とした現している．この研究では本研究と同じく類似度に対し構造類

Oﬃce ファイル間の類似度を XML 類似度に基づき求める実験

似度とテキスト類似度の両方を考慮した類似度を採用しているを行い，従来の XML 類似度計算手法である LAX+ [8] を使用

が，構造類似度として非順序木に対する木編集距離を使用してした場合よりも良い精度が得られている．LAX+では，リーフ

おり，本研究では順序木に対する木編集距離を使用している．

ノードのテキストの完全一致のみを評価しており，この研究にこの手法では 1MB 程度の大きさの XML ファイルを対象とよって XML におけるテキスト類似度の重要性の一端が示されし，二つの XML データの部分木と部分木のマッチングを行っている．

ているが，本手法では，さらに大きなサイズの XML の部分木

[4] では，複数の文書から重複文書を検出するという問題を対象にし，XML データのおおまかなクラスタリングと厳密な類似度計算の二段階の処理に分け効率化を図っている．クラス
タリングには XML データ間のキーワード類似度を適用し，そとクエリ XML の木全体のマッチングを行っているという点で異なる．

3. 提 案 手 法の後各クラスタに含まれる文書間において木構造に基づく帰納

3. 1 諸 定 義的計算手法を使用した類似度の計算を行い厳密な類似度を求め本論文における記号の定義は表 1 のとおりである．これ以外て重複検出を行っている．また，同時にクラスタリング等に必の記号については，その都度定義していく．

要な各パラメータの最適な値の決定方法に機械学習を使用する手法も提案しており，高速化を実現している．
本研究は，類似部分木探索問題を扱っているため，これらの研究とは対象としている問題が異なる．

表 1 本論文における記号の定義
記号

定義

D

対象 XMLdi

D の後行順番号が i であるノード

2. 3 類似部分木探索問題に関する研究

Di

di を根とする部分木与えられた XML データ（クエリ XML）に対して，予め用Q

クエリ XML意しておいた XML データ（対象 XML）に含まれる全ての類|D|, |Q|, |Di |それぞれの木のノード数

似した部分木を列挙する問題を類似部分木探索問題と呼び，こW ordsDi , W ordsQそれぞれの木が持つ単語集合

れは本研究が対象としている問題である．類似部分木探索問題|W ordsDi |, |W ordsQ | 各集合に含まれる単語数
T ED(Di , Q)

Di , Q 間の木編集距離

Jaccard(A, B)

集合 A, B 間の Jaccard 係数

Sim(Di , Q)

Di , Q 間の類似度

Simt (Di , Q)

Di , Q 間のテキスト類似度ていき，子部分木の計算結果を親部分木の計算に用いることで，Sims (Di , Q)

Di , Q 間の構造類似度

計算量の削減を図っている．さらに，類似部分木候補となりう

θ

類似度閾値

る部分木の大きさと深さの上限値をクエリ XML の大きさから

α

各類似度の重みパラメータ

求めておき，上限値に収まらない部分木の木編集距離の計算を

depth(T )木 T の深さを対象とした研究として Augsten らの提案する TASM [5] やCohen らの提案する Structure Search [6] がある．
TASM [5] は部分木の編集距離を葉から根に向かって計算し省くという手法で効率化を行い巨大な XML データに対しての適用を実現している．

StructureSearch [6] では，対象となる巨大な XML データの全部分木の構造と頻出しているラベルに着目し，予めインデッ
クス付けを行い同じ構造を持つ部分木をひとまとめにして扱うことで木編集距離の計算結果を再利用し，計算時間の削減を実現している．前述の TASM との比較実験では，5〜63 倍の高Jaccard 係数とは二つの集合間の要素の共起の度合いを表す
値であり，以下の式により表される．

∩

|A B|
∪
Jaccard(A, B) =
|A B|

(1)

また，木のノードにおける後行順番号とは，木を後行順に走類似条件の式より，類似条件を満たしている時の構造類似度の下限値 θs とテキスト類似度の下限値 θt は以下の式により求

6

まる．

2
0

5
1

図4

3

4

θs =

θ − (1 − α)
α

θt =

θ−α
1−α

(<
= Simt (Di , Q))

3. 2 問 題 定 義

Sims (Di , Q) <=1−
Simt (Di , Q) <=本手法では，対象 XML に含まれる任意の部分木とクエリ

XML 間の構造類似度，テキスト類似度を以下のように定める．

Simt (Di , Q) = Jaccard(W ordsDi , W ordsQ )

(7)

り立つ．

4 のようにしてつけられる．

T ED(Di , Q)
|Di | + |Q|(6)

また，Jaccard 係数と木編集距離の特性から，以下の式が成後行順番号の例

査した時に何番目にそのノード訪れるかを表す数字であり，図Sims (Di , Q) = 1 −(<= Sims (Di , Q))

(2)

(8)

|W ordsQ ||W ordsDi |(9)

式 6，8 を |Di | について解くことで定理 1 を，式 7，9 を|W ordsDi | について解くことで定理 2 を示すことができる．
［定理 1］Di , Q が類似条件を満たすならばθs <2 − θs|Q||Di | <
= |Q| θ2 − θs =s(3)

これらの値を以下の式により，パラメータ α で重み付けをし統合した値を XML データ Di , Q 間の類似度とする．

abs(|Di | − |Q|)
|Di | + |Q|［定理 2］Sim(Di , Q) = αSims (Di , Q) + (1 − α)Simt (Di , Q) (4)Di , Q が類似条件を満たすならば本研究における類似部分木探索問題は，対象 XML D およ

|W ordsQ |θt <= |W ordsDi | <= |W ordsQ |1
θtび与えられた問合せ Q ，閾値 θ ，パラメータ α に対して，以これらの定理により，ノード数か単語数が範囲外である部分木

下の条件を満たす D 中の全ての部分木 Di を列挙する問題でについては類似条件を満たし得ないので類似度の計算を省く事

ある．

ができる．

Sim(Di , Q) > θ(5)

3. 5 Post-order Queue によるストリーム処理
木に含まれるノードを Post-order（後行順）で並べた時，任3. 3 ナイーブアルゴリズム

意の部分木は根ノードを末尾とする連続したノードのみによっ

3. 2 節で定義した問題をナイーブに解くことを考えた場合て構成される．よって，全てのノードの後行順番号とそのノー（ 1 ） 与えられた θ, α, Q を受け取り XML データ D を読みドを根とした部分木に含まれるノードのうち最も後行順番号が込む

小さいノード（最左ノード）の後行順番号のペアを保持してお（ 2 ） D の全ての部分木 Di と Q 間のテキスト類似度（Jac-くことで木構造を表現できる．

card 係数），構造類似度（木編集距離）を求める

また，定理 1 より類似度を計算しなければいけない部分木の（ 3 ） 類似条件を満たす部分木を全て出力する

ノード数の上限が ⌊|Q|(2 − θs )/θs ⌋(= maxDn とする) 個と決というような処理が考えられる．しかし，巨大な XML データ

まっていることから，対象となる部分木の類似度の計算のためを対象 XML として想定した場合にこのようなアルゴリズムに保持しておかなければならないノードは最新 maxDn 個ででは膨大な計算コストおよび空間コストが必要になるという充分である事が分かる．maxDn はクエリ XML サイズと閾値問題があり，現実的でない．本研究ではこれらの問題点に対しのみに依存するので，対象 XML に対し後行順で読み込み処理て，閾値による枝刈り (3. 4 節) と Post-order Queue によるスを行うことにより，メモリに乗り切らないような巨大な XML

トリーム処理 (3. 5 節) を取り入れることで解決する．

データを対象 XML とした場合でも一度のディスクへのシーケ

3. 4 閾値による枝刈り
まず最初に，Di のサイズと Q のサイズが著しく異なっている場合類似度も小さくなることが自明に分かる．ここで，式(5) より，類似度の下限が決まっており |Q| が固定されている

ンシャルアクセスで類似度の計算処理が可能となる．

3. 6 データ構造
本手法では，Post-order Queue により扱うデータは，各ノード di においてことから，予め類似条件を満たしうるような |Di | の範囲を求•

posID（di の後行順番号）められる．これにより，得られる結果を損なうことなく過剰に•left（Di に含まれる最左ノード）

大きい（過剰に小さい）部分木についての計算を無視すること•

wsize（Di が持つ単語数）

ができる．

•

nodetype（テキストノードかエレメントノードか）•label（di のラベル）

Algorithm 1 EnumrateSimilarSubtree•

words（di の単語集合）

Require: D, Q, α, θの情報から構成される．図 1 の XML データでの例を表 2 に

Ensure: all subtrees fulfill Similarity Condition示す．

1: Calculate maxDn (upper bound of nodes),

ノードのラベルには文字列に対応した数字（連番やハッシュ等）を割り当てることで値の保持や比較の簡単化を行う．

D の Post-order Queue による処理時に Jaccard 係数を計算

maxDw (upper bound of words)

2:

3: Doc ⇐ new RingBuﬀer(maxDn )4: P Q ⇐ Post-order Queue of D
5: Result ⇐ Empty List of subtrees

するための単語集合 words は，リーフノードについてのみ単

6: for di : P Q do

語集合をディスクに保存しておき，読み込んだノードがリーフ

7:

Doc[i % maxDn ] ⇐ di

ノードでない場合は子ノードの単語集合の和集合を取ることで8:

if |Di | > maxDn or |W ordsDi | > maxDw then

動的に単語集合を構成していく．

9:

また，予め XML ファイルをパースして各ノードの情報を後行順にバイナリファイルとして保存しておくことで，類似度計
算時にパース処理に時間をかけなくてすむようにしておく．

Post-order Queue から取り出したノードデータを保持する

goto N EXT

10:

end if11:

if di is not leaf node then12:child ⇐ di .posID − 1

13:Doc[i % maxDn ].words ⇐ Doc[child % maxDn ].words

14:

while Doc[i % maxDn ].lef t =|バッファとしてリングバッファを使用する．リングバッファとDoc[child % maxDn ].lef t do

は任意の大きさのバッファの始端と終端を擬似的に接続し環状

15:

child ⇐ Doc[child % maxDn ].lef t − 1にすることで先頭と末尾への要素の挿入と削除，要素へのラン

16:

Doc[i % maxDn ].words ⇐merge(Doc[i % maxDn ].words,

ダムアクセスを定数時間で実行可能にしたデータ構造である．
リングバッファを使用することで，時間的コストを消費せずに
空間計算量を抑えることが可能となる．

Doc[child % maxDn ].words)
17:

end while

18:

end if

3. 7 アルゴリズム

19:

Simt ⇐ Doc[i % maxDn ].words.getJaccard()

これらのアイデアを取り入れたアルゴリズムを Algorithm120:

if α(1 −に示す．アルゴリズムの概要を以下に示す．

21:（ 1 ） パラメータとクエリ XML を受け取り初期化処理を行う (1-4 行)（ 2 ） D の Post-order Queue から 1 ノード分バッファに読み込む (5-6 行)（ 3 ） 読み込んだノードを根とする部分木 Di のノード数と単語数が上限値以上なら次のノードへ進む (7-9 行)（ 4 ） 読み込んだノードを根とする部分木についての単語集

abs(|Di |−|Q|)) + (1 − α)Simt < θ then
|Di |+|Q|goto N EXT

22:

end if23:

Sims ⇐ 1 −24:

if αSims + (1 − α)Simt >= θ then25:

T ED(Di ,Q)|Di |+|Q|

Result.add(Di )26:

end if

27:

N EXT :

28: end for
29: return Result

合を構成し，テキスト類似度を求める (10-17 行)（ 5 ） テキスト類似度が類似条件を満たす必要条件を満たしているなら構造類似度を求める (18-22 行)

部分に分け，それぞれの計算量について述べる．
ま ず 木 編 集 距 離 の 計 算 部 は [7] の 手 法 か ら 時 間 計 算 量（ 6 ） 類似条件を満たしているなら部分木は類似しているとO(|Di ||Q|depth(Di )depth(Q)) 空間計算量 O(|Di ||Q|) となる．

みなし結果リストに追加する (23-25 行)

ここで，depth(Di ) はそれぞれ木の深さを表しており，最悪で（ 7 ） Post-order Queue が空になるまで以上の処理を繰りDi , 平均で log2 (|Di |) となる．また，|Di | の最大値 maxDn

返す

は Q, θ, α により決まるので，時間計算量 O(|Q|2 log22 |Q|) 空

3. 8 計 算 量

間計算量 O(|Q|2 ) となる．さらに，木編集距離計算は類似部分

この節では提案手法を木編集距離計算と Jaccard 係数計算の木候補の数だけ実行されるため，最終的に全ての処理に対する時間計算量は O(C|Q|2 log22 |Q|) (C は D に含まれる類似部分

表 2 ノードデータの例

posID left wsize nodetype label

木候補の数) となる．
words

次に Jaccard 係数の計算部について考える．まず，一単語を00

1 text0 (John)

{0}

1

0

1 element

1 (author)

{}

2

2

1 text2 (DB){2}3

2

1 element

3 (category) {}が必要である．さらに，単語を単語集合に挿入する回数は

4

0

2 element

4 (article){}

最 大 で O(|W ordsD | log2 |W ordsD |) と な る ．こ れ は ，一 単

5

5

1 text5 (peter){5}

語に関して一度挿入が行われる度にその単語を含んでいる

6

5

1 element

1 (author){}

集 合 の 要 素 数 が 2 倍 以 上 に 増 え て い く と 考 え る と ，一 単

W ordsDi に挿入する時にそれが W ordsQ との共通要素なのかを調べるために二分探索を行っているため O(log2 |W ordsQ |)45

7

ら分かる．ここで，|W ordsD |, |W ordsQ | はそれぞれ D, Q

40
35

6

に 比 例 し て い る と 考 え る と ，す べ て の 処 理 に 対 す る 時 間
計算量は O(D log2 (D) log2 (Q)) となる．空間計算量に関し

30て は ，ノ ー ド デ ー タ が O(maxDn ) ≃ O(Q)，単 語 集 合 がO(maxDn maxDw ) ≃ O(|Q|2 ) であるため，全体で O(|Q|2 )となる．

4. 評 価 実 験

5
4

25
20
15

探索時間 [s]10計算時間 [s]5321

消費メモリ [MB]0

4. 1 実験の目的および実験環境

Memory [MB]Time [s]語が挿入される回数は高々 log2 |W ordsD | 回になることか

0

1000

3000

0
4000

実際に XML ファイルを入力とし，θ や D, Q の大きさ，類2000
File size [MB]似部分木の含有率の違いによる実行時間，消費メモリ，検出部

図 5 D の大きさの違いによる実行時間と消費メモリの変化

分木数の変化を調べた．加えて，既存手法との実行時間，木編
50
45
40
35
30
25
20
15
10
5
0

時間のうち木編集距離計算にかかった時間を計算時間，それ以D として人工データである XMark ベンチマーク （注 2） と実
データである dblp（注 3）, SwissProt（注 4）を使用した．dblp, Swis-sProt の XML ファイルは XML Data Repository（注 5） の物をTime [s]外の時間を探索時間と表記する．

利用した．Q には D から抽出した適当なサイズの部分木を使用した．使用したデータセットを表 3 に示す．なお，ここでの語彙数とはデータセット内に存在するユニークな単語の総数で

1400
1200
1000
800
探索時間 [s]計算時間 [s]
検出候補数
検出結果数

視 (木構造とエレメントノードのラベルのみを考慮) した時の

600
400
200
0

0.5

あり，構造数とはテキストノードと属性値のテキストを全て無Number of Subtree

集距離の計算回数の比較を行った．また，本実験において実行

0.6

0.7
0.8
Threshold

0.91

図 6 閾値の違いによる実行時間と検出部分木数の変化

ユニークな部分木の数である．
実験は全て 64bit Windows7, Intel Core i7 @ 3.20GHz CPU,

8GB RAM で構成された PC 上で行った．提案手法と既存手|Q| = 54, θ = 0.8, α = 0.5 として実行時間，使用メモリを計測法である TASM のプログラムは C++で記述し x86 64-w64-

した．

mingw32, gcc version 4.5.4 20111030 を使いコンパイルを行っ結果を図 5 に示す．探索時間はほぼ D の大きさに比例しておた．既存手法である SS は著者により提供された Java によるり，消費メモリと計算時間は文書サイズによらず一定であった．

プログラムを JRE 64bit version 1.7.0 45 上で実行し実験を

4. 3 閾値の違いによる実験閾値 θ を 0.55 から 0.95 まで変化させた時の実行時間と類行った．

4. 2 D の大きさの違いによる実験

似部分木の検出数を計測した．D には Xmark1800 を使用し，

D のファイルサイズを 100MB から 4000MB まで変化させ|Q| = 84, α = 0.5 として計測した．
結果を図 6 に示す．閾値 0.55 から 0.70 にかけて検出部分木
数が大きく変化しており，それに伴い木編集距離の計算時間も表 3 使用したデータセット
名前

サイズ

ノード数 単語数

語彙数

構造数

大きく変化した（2.94 秒から 0.11 秒）．θ >= 0.70 の時に検出

[MB]

[百万]

[百万]

[千]

[千]

候補数は検出結果数とほぼ等しくなっており，テキスト類似度

XMark100

114

3.6

11.2

163

82

を用いた候補の絞り込みが効果的に作用していると考えられる．

XMark200

227

7.2

22.6

231

112

XMark400

454

14.5

45.2

332

146

XMark900

1024

32.5

101.9

436

178

XMark1800

2048

65.1

203.7

564

204

XMark3600

4096

130.1

407.1

801

228

SwissProt

110

9.4

6.4

306

59

結果を図 7 に示す．計算時間，消費メモリともに Q が大き

dblp

128

7.2

6.7

733

10

くなるにつれて増えた．探索時間はほぼ一定であった．3. 8 節

4. 4 Q の大きさの違いによる実験
Q のノードサイズを変化させて実行時間，使用メモリを計測した．D には Xmark200 を使用し，全て θ = 0.8, α = 0.5 とした．

で示した各計算量の Q に関する部分を抜き出すと（注 2）：http://www.xml-benchmark.org/•

探索時間 O(log2 |Q|)

（注 3）：http://www.informatik.uni-trier.de/~ley/db/•

計算時間 O(|Q|2 log2 |Q|2 )•消費メモリ O(|Q|2 )（注 4）：http://web.expasy.org/docs/swiss-prot_guideline.html（注 5）：http://www.cs.washington.edu/research/xmldatasets/www/

repository.html

であり，Q の変化に対するそれぞれの実験結果は上記の理論

100

1000

1000

TASM
SS

10

10
0.1

100

提案手法

Time [s]1Memory [MB]Time [s]

100

10

探索時間
計算時間
メモリ消費

0.01

1
10

100
1000
Query node size

1

10000

Xmark100 XMark200 XMark1800 SwissProt

図 7 Q の大きさの違いによる実行時間と消費メモリの変化

図 9 既存手法との実行時間の比較

80

TASM

70

10,000,000

SS

60

1,000,000

提案手法

50

100,000

40
30

TED Computation

Time [s]dblpDocument name

探索時間 [s]20

計算時間 [s]1010,000

0
0

20
40
60
80
Content rate of similar subtree [%]

100
10
1

100

Xmark100 XMark200 XMark1800 SwissProt

Document name

図 10

図 8 類似部分木の含有率の違いによる実行時間の変化的な計算量に対応している事が確認できる．

1,000

dblp

既存手法との木編集距離の計算回数の比較

おり，実行時間も比較的長くなっている．これは，SwissProt

4. 5 類似部分木の含有率の違いによる実験の語彙数が少ないため，似た単語集合を持つ部分木が多く存在

D に含まれる Q の類似部分木の数を変化させて実行時間

し，テキスト類似度での絞り込みがうまく作用していないからを計測した．ノード数 32 の Q を作成した後，クエリ XML
を任意の割合で含んだ D （ノード数 3,200,000）を作成し，

θ = 0.8, α = 0.5 として計測を行った．
結果を図 8 に示す．探索時間は類似部分木の含有率によらず一定，計算時間は 3. 8 節で示した通り含有率に比例した．

であると考えられる．

4. 7 α, θ の違いによる検出部分木数の比較実験
テ キ ス ト 類 似 度 ，構 造 類 似 度 が XML デ ー タ の 類 似
度 に 対 し て ど の 程 度 寄 与 し て い る か を 調 べ る 為 に ，実
デ ー タ で あ る SwissProt と dblp を 対 象 XML と し ，α =4. 6 既存手法との比較実験

0.0(テキスト類似度のみ), α = 0.5, α = 1.0(構造類似度のみ)

人工データ，実データの両方に対して実行時間と木編集距離のにおいて閾値を変化させた時の，類似部分木として検出された

計算回数の計測を行い既存手法の TASM, StructureSearch (SS)

部分木の数を計測した．また，クエリ XML には 4. 6 節での実との比較を行った．提案手法では全て θ = 0.6, α = 0.5, |Q| = 64

験に用いたものと同じデータを使用した．結果を図 11，図 12で計測を行った．TASM, SS では k = 5 とし，類似度上位 5 個に示す．

の部分木の検出を行った．
結果を図 9，図 10 に示す．実行時間について全てのデータ

α = 0.5 でのテキストと構造を考慮した場合を見てみると，
dblp ではクエリ XML と類似している部分木がほぼ存在しなセットで TASM, SS の両方を上回る性能を確認することがで

いが，SwissProt では高い類似度を持つ部分木が多く存在してきた．TASM と比較すると 30〜75 倍，SS と比較すると 7〜13

いる事が分かる．また，テキストのみを考慮した場合と構造の倍の高速化が確認できた．木編集距離計算回数を見てみると，みを考慮した場合を比べた時，dblp では構造が似ている部分木

提案手法では既存手法に比べ木編集距離の計算回数が格段に少の数がテキストが類似している部分木の数に比べ非常に多く，ない事が分かる．これらの結果から，テキスト類似度を利用しSwissProt では構造が似ている部分木の数とテキストが似ていた枝刈りが実行時間の削減に大きく影響を与えていると考えらる部分木の数にあまり差がない事が分かる．さらに，表 3 に示れる．

す通り，dblp は SwissProt よりも語彙数が多く，SwissProt は提案手法による実データである SwissProt と dblp の木編集

dblp よりも構造数が多い事が分かる．これらの特徴は，dblp

距離計算回数を比べると，SwissProt の方が著しく多くなってはテキストを中心に扱ういわゆるデータ指向型な XML データ

本手法では対象とする XML がデータ指向型 XML であるほ10000000
α = 0.0 (テキストのみ)
α = 0.5
α = 1.0 (構造のみ)

Number of Subtree

1000000
100000

ど本手法は効率性を発揮できる事が確認できたが，反面，構造を中心に扱う XML を対象とした時にテキスト類似度での絞り込みがうまく作用しにくいという事が分かった．こういうケー

10000

スでは部分木が類似しているかどうかについて構造類似度の占1000める割合が多くなっていると考えられる．よって，構造を考慮100した候補の絞り込みを取り入れることでこのような XML デー
タを対象とした時にも効率性を維持できることが期待される．

10

さらに，対象 XML に含まれる語彙数や構造数をもとにその

1
0

0.2

0.4

0.6

Threshold

0.8

1

XML データが持つ特徴を予め調べておき，探索や枝刈りに活用するといった改良案が考えられる．
これらの他に今後の課題として，木編集距離や Jaccard 係数

図 11 SwissProt での α, θ による検出部分木数の比較

以外の類似度指標を適用することによる幅広い類似条件設定の10000000
1000000

Number of Subtree

実現や，切り出した単語に対してストップワードを取り除く等

α = 0.0 (テキストのみ)
α = 0.5
α = 1.0 (構造のみ)

100000のふるい分けや重み付けを行うことによる検出精度の向上，類似極大部分木検出への拡張等が挙げられる．加えて，さらなる高速化という点では Bloom Filter によるテキスト類似度計算

10000

回数の削減やインデックス作成によるディスクアクセス時間の1000

削減，並列化への対応などが挙げられる．

100

謝

辞

10

本研究の一部は JSPS 科研費 25330124 の助成を受けたも1のである．また，実験を行うにあたり，ザルツブルグ大学の
0

0.2

0.4

0.6

Threshold

0.81

図 12 dblp での α, θ による検出部分木数の比較

であり，SwissProt は構造を中心に扱う XML データであることに起因する．
さらに 4. 6 節での既存手法との比較実験の結果において，対象 XML が dblp の時，SwissProt の時に比べて速度と枝狩り効率が大きく向上している事と照らし合わせると，本手法はデータ指向型である XML データを対象とした時により高い効率性を発揮できているということがわかる．

5. ま と め
本稿では，XML における類似部分木探索問題を対象とし，テキストの類似度と構造の類似度の二面から類似度を求める手法を提案した．テキストノードに対する類似判定と木構造に対する類似判定を混ぜあわせることで既存手法に比べ高度な類似判定を実現した．
また，提案手法に対し巨大な XML ファイルを対象とし，時間計算量，空間計算量の双方ともに効率的であるアルゴリズムを提案した．提案したアルゴリズムについて実際に実装，評価実験を行い巨大な XML ファイルに対しても適用可能な性能であることが確認できた．さらに既存手法 (TASM, SS) との比較を行った結果，人工データ，実データともに既存手法よりも短い実行時間で実行可能であることが確認できた．この事から，
テキスト類似度を利用した類似部分木候補の絞り込みが効果的に作用し，既存手法での冗長な木編集距離計算を削減できたと考えられる．

Nikolaus Augsten 教授，ヘブライ大学の Sara Cohen 教授にプログラムコードを提供をしていただいた．
文

献[1] Joe Tekli, Richard Chbeir, and Kokou Yetongnon. Survey: An overview on XML similarity: Background, current
trends and future directions. Comput. Sci. Rev., Vol. 3,
No. 3, pp. 151–173, August 2009.
[2] Philip Bille. A survey on tree edit distance and related problems. Theor. Comput. Sci., Vol. 337, No. 1-3, pp. 217–239,
June 2005.
[3] Apichaya Auvattanasombat, Yousuke Watanabe, andHaruo Yokota. An evaluation of similarity search methods blending structures and keywords in XML documents.
In IIWAS ’13, 2013.
[4] Luı́s Leitão and Pável Calado. Eﬃcient XML duplicate detection using an adaptive two-level optimization. In Proceedings of the 28th Annual ACM Symposium on Applied
Computing, SAC ’13, pp. 832–837, New York, NY, USA,
2013. ACM.
[5] Nikolaus Augsten, Denilson Barbosa, Michael M. Bohlen,
and Themis Palpanas. Eﬃcient top-k approximate subtree
matching in small memory. IEEE Transactions on Knowledge and Data Engineering, Vol. 23, No. 8, pp. 1123–1137,
2011.
[6] Sara Cohen. Indexing for subtree similarity-search using
edit distance. In Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, SIGMOD’13, pp. 49–60, New York, NY, USA, 2013. ACM.
[7] K. Zhang and D. Shasha. Simple fast algorithms for theediting distance between trees and related problems. SIAM
J. Comput., Vol. 18, No. 6, pp. 1245–1262, December 1989.
[8] Yousuke Watanabe, Hidetaka Kamigaito, and Haruo
Yokota. Style-based similarity search for oﬃce XML documents. In IIWAS ’12, pp. 138–146, New York, NY, USA,2012. ACM.
[9] Shintaro Terajima. A scheme for finding maximal similar
subtrees from XML data. In DEIM Forum 2011 E1-2, 2011.