DEIM Forum 2014 D7-5 XML XML Web XML XML XML XML

(1)

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. 序

論

1. 1 XMLと類似検出

Extensible Markup Language (XML)（注 1）は拡張可能なマークアップ言語の一つであり，利用者の目的に応じたタグを定義することで，文書やデータの構造や意味を汎用的に表現することができる．その汎用性を受け，XMLは1998年にW3Cにより策定，勧告されてから現在にかけて広く普及し，様々な用途に使われている．しかし広く使われていることに伴い，内容が類似している情報の散在がしばしば見かけられる．このような類似した複数の情報を見つけ出すことができれば，情報の相互補完，重複部分の除去，コピーの検出等，様々な用途に活用できる． 1. 2 XMLにおける類似度の種類 XMLは半構造データであり，テキスト情報に加えて，データ自体が木構造に基づく構造を持つ．テキストデータの比較や構造情報などXMLの持つ様々な情報を利用した類似度の計算について多くの手法が研究されている[1]． XMLデータの構造を考慮した類似度計算手法として代表的なものに，XMLデータを図1のように木構造とみなしその木構造の木編集距離[2]をベースとして類似度を計算する手法がある．しかし一般に木編集距離の計算は時間計算量が高コストであるため，巨大なXMLファイルを対象とした場合，効率的な計算手法が必要不可欠となる． XMLデータの内容を考慮した類似度計算手法として代表的なものに，情報検索の技術をベースとする方法がある[3], [4]．これは類似度を測りたい二つのXMLから単語やq-gramを抽出し，それらの類似度（キーワード類似度）を求めXMLの類（注1）：http://www.w3.org/XML/ 似度として適用するという手法である．キーワード類似度としてはTF-IDF等を用いてキーワードベクトルを構成しベクトル間のコサイン類似度を適用する手法や，キーワード集合間の Jaccard係数を適用する手法が使用されている． 1. 3 類似部分木探索問題 XMLの類似検出に関する問題の中でも特に，与えられた XMLデータ（クエリXML）に対して，予め用意しておいた XMLデータ（対象XML）に含まれるすべての類似した部分木を列挙する問題を類似部分木探索問題と呼ぶ．類似部分木探索問題を対象とした研究としてAugstenらの提案するTASM [5]やCohenらの提案するStructure Search [6]

がある．[5], [6]はどちらも類似度として木編集距離[2]を使用しており，計算手法に木編集距離の算出回数を低減する工夫を取り入れることで高速化を達成している． TASMでは，Top-k類似部分木探索問題（類似部分木の上位 k個の検出）を解く手法について提案している．クエリXML のノード数に基づき探索対象の部分木のノード数に上限を設けることで処理の効率化を実現している．

Structure Searchでは，前述のTop-kに加えて「類似度を表

す木編集距離がm以下である部分木」という条件を加え，条件を満たす部分木を求める手法について提案している．さらに，この手法では対象XMLが持つ部分木全ての構造を調べ，予め同一の構造を持つ部分木を特定しておき，クエリを処理する時にこの情報を使い類似度の再利用を行っている．加えて，必要な情報を予めインデックス付けしておくことで情報の参照の高速化を図り，TASMよりも効率的な計算手法を提案している．

しかしながら，TASMやStructure Searchでは類似度として木編集距離のみを考慮しており，これにはいくつかの問題点が存在する．XMLデータにおいて，図2の例のようにXML

(2)

article author category “John” “John” “DB”“DB” article author category “Peter” “Mining” articles article author category “John” “DB” Query Document 図 1 XML と木構造 article author category “John” “John” “DB”“DB” article author category “Peter” “Mining” articles article author category “John” “DB” Query Document 図 2 テキストノードとエレメントノードれは，データを中心に扱ういわゆるデータ指向のXMLデータによく見られる．この場合，要素のラベルや木自体の構造はほぼ同一であるため，二つの部分木の類似性を判定する場合には，テキストノードの内容に関する類似性を評価したほうが，より期待する結果が得られると考えられる．TASMやStructure Searchでは，テキストノードについて，値の完全一致だけを評価しているため，テキストの類似性を考慮した評価は行っていない． 1. 4 本研究の目的本稿では，類似部分木探索問題に対して前述の問題点を解決するためにテキスト類似度を導入し，XMLの構造と内容の両面を考慮した類似部分木検出を行う．部分木同士の木編集距離に基づいた構造類似度，テキストノードが持つ単語集合の Jaccard係数に基づくテキスト類似度の両方を考慮した類似度について考え，各類似度に対して任意のパラメータで重み付けをすることで柔軟な類似条件の設定を実現する．テキスト類似度を導入することで，既存研究よりも柔軟な類似判定を実現し，さらに処理の効率化にも活用する事を目的とする．また，全てのデータがメモリに乗り切らないような巨大なXMLデータに対して類似度の計算を行う事を想定し，そのようなデータの処理に耐え得る効率的な類似度計算アルゴリズムを提案する．加えて，実際に手法の実装を行い，実際の巨大なXMLファイルに対して本手法を適用し，巨大なXMLデータに対しても適用可能な性能かどうか，既存手法との実行時間の違いを確認する． 1. 5 本論文の構成本論文の構成は以下のとおりである．第2. 章で関連する研究について述べ，前提知識について触れる．第3. 章で本研究の提案手法について述べる．本手法において効率性の向上のために使用した工夫点と，それを取り入れたアルゴリズムの全体像について説明する．そして第4. 章で評価実験の結果について述べ，本手法の効率性の確認と既存手法との比較を行う．第 5. 章で本稿のまとめと今後の課題を述べる．

A

B

C

D

E

F

X

B

C

D

F

G

1 2 3 3 図 3 木編集距離の計算例

2.

3. 提案手法

3. 1 諸定義本論文における記号の定義は表1のとおりである．これ以外の記号については，その都度定義していく．表 1 本論文における記号の定義記号定義 D 対象 XML di D の後行順番号が i であるノード Di diを根とする部分木 Q クエリ XML |D|, |Q|, |Di| それぞれの木のノード数 W ordsDi, W ordsQ それぞれの木が持つ単語集合 |W ordsDi|, |W ordsQ| 各集合に含まれる単語数 T ED(Di, Q) Di, Q 間の木編集距離 J accard(A, B) 集合 A, B 間の Jaccard 係数 Sim(Di, Q) Di, Q 間の類似度 Simt(Di, Q) Di, Q 間のテキスト類似度 Sims(Di, Q) Di, Q 間の構造類似度 θ 類似度閾値 α 各類似度の重みパラメータ depth(T ) 木 T の深さ Jaccard係数とは二つの集合間の要素の共起の度合いを表す値であり，以下の式により表される． J accard(A, B) = |A

∩

B| |A

∪

B| (1) また，木のノードにおける後行順番号とは，木を後行順に走

(4)

6

2

5

3

1

0

4

図 4 後行順番号の例査した時に何番目にそのノード訪れるかを表す数字であり，図 4のようにしてつけられる． 3. 2 問題定義本手法では，対象XMLに含まれる任意の部分木とクエリ XML間の構造類似度，テキスト類似度を以下のように定める． Sims(Di, Q) = 1− T ED(Di, Q) |Di| + |Q| (2)

Simt(Di, Q) = J accard(W ordsDi, W ordsQ) (3)

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

Sim(Di, Q) = αSims(Di, Q) + (1− α)Simt(Di, Q) (4)

本研究における類似部分木探索問題は，対象XML D および与えられた問合せQ，閾値θ ，パラメータαに対して，以下の条件を満たすD 中の全ての部分木Di を列挙する問題である． Sim(Di, Q) > θ (5) 3. 3 ナイーブアルゴリズム 3. 2節で定義した問題をナイーブに解くことを考えた場合（1）与えられたθ, α, Qを受け取りXMLデータDを読み込む（2） Dの全ての部分木DiとQ間のテキスト類似度（ Jac-card係数），構造類似度（木編集距離）を求める（3）類似条件を満たす部分木を全て出力するというような処理が考えられる．しかし，巨大なXMLデータを対象XMLとして想定した場合にこのようなアルゴリズムでは膨大な計算コストおよび空間コストが必要になるという問題があり，現実的でない．本研究ではこれらの問題点に対して，閾値による枝刈り(3. 4節)とPost-order Queueによるストリーム処理(3. 5節)を取り入れることで解決する． 3. 4 閾値による枝刈りまず最初に，DiのサイズとQ のサイズが著しく異なっている場合類似度も小さくなることが自明に分かる．ここで，式 (5)より，類似度の下限が決まっており_|Q|が固定されていることから，予め類似条件を満たしうるような|Di|の範囲を求められる．これにより，得られる結果を損なうことなく過剰に大きい（過剰に小さい）部分木についての計算を無視することができる．類似条件の式より，類似条件を満たしている時の構造類似度の下限値θs とテキスト類似度の下限値θtは以下の式により求まる． θs= θ− (1 − α) α (<= Sims(Di, Q)) (6) θt= θ− α 1− α (<= Simt(Di, Q)) (7) また，Jaccard係数と木編集距離の特性から，以下の式が成り立つ． Sims(Di, Q) <_{= 1 −} abs(|D i| − |Q|) |Di| + |Q| (8) Simt(Di, Q) <₌ |W ords Q| |W ordsDi| (9) 式6，8 を|Di|について解くことで定理1 を，式7，9 を |W ordsDi|について解くことで定理2を示すことができる．［定理1］ Di, Qが類似条件を満たすならば |Q| θs 2− θs < = |Di| <_{= |Q|} 2− θs θs ［定理2］ Di, Qが類似条件を満たすならば

|W ordsQ|θt<_{= |W ords}Di| <= |W ordsQ|

1 θt これらの定理により，ノード数か単語数が範囲外である部分木については類似条件を満たし得ないので類似度の計算を省く事ができる． 3. 5 Post-order Queue によるストリーム処理木に含まれるノードをPost-order（後行順）で並べた時，任意の部分木は根ノードを末尾とする連続したノードのみによって構成される．よって，全てのノードの後行順番号とそのノードを根とした部分木に含まれるノードのうち最も後行順番号が小さいノード（最左ノード）の後行順番号のペアを保持しておくことで木構造を表現できる．また，定理1より類似度を計算しなければいけない部分木のノード数の上限が_{⌊|Q|(2 − θ}s)/θs⌋(= maxDnとする) 個と決まっていることから，対象となる部分木の類似度の計算のために保持しておかなければならないノードは最新maxDn個で充分である事が分かる．maxDnはクエリXMLサイズと閾値のみに依存するので，対象XMLに対し後行順で読み込み処理を行うことにより，メモリに乗り切らないような巨大なXML データを対象XMLとした場合でも一度のディスクへのシーケンシャルアクセスで類似度の計算処理が可能となる． 3. 6 データ構造本手法では，Post-order Queueにより扱うデータは，各ノードdi において • posID（diの後行順番号） • left（Diに含まれる最左ノード） • wsize（Diが持つ単語数） • nodetype（テキストノードかエレメントノードか）

(5)

• label（diのラベル） • words（diの単語集合）の情報から構成される．図 1のXMLデータでの例を表2に示す．ノードのラベルには文字列に対応した数字（連番やハッシュ等）を割り当てることで値の保持や比較の簡単化を行う．

D のPost-order Queueによる処理時にJaccard係数を計算するための単語集合wordsは，リーフノードについてのみ単語集合をディスクに保存しておき，読み込んだノードがリーフノードでない場合は子ノードの単語集合の和集合を取ることで動的に単語集合を構成していく．また，予めXMLファイルをパースして各ノードの情報を後行順にバイナリファイルとして保存しておくことで，類似度計算時にパース処理に時間をかけなくてすむようにしておく． Post-order Queue から取り出したノードデータを保持するバッファとしてリングバッファを使用する．リングバッファとは任意の大きさのバッファの始端と終端を擬似的に接続し環状にすることで先頭と末尾への要素の挿入と削除，要素へのランダムアクセスを定数時間で実行可能にしたデータ構造である．リングバッファを使用することで，時間的コストを消費せずに空間計算量を抑えることが可能となる． 3. 7 アルゴリズムこれらのアイデアを取り入れたアルゴリズムをAlgorithm1 に示す．アルゴリズムの概要を以下に示す．（1）パラメータとクエリXMLを受け取り初期化処理を行う(1-4行) （2） D のPost-order Queueから1ノード分バッファに読み込む(5-6行) （3）読み込んだノードを根とする部分木Diのノード数と単語数が上限値以上なら次のノードへ進む(7-9行) （4）読み込んだノードを根とする部分木についての単語集合を構成し，テキスト類似度を求める(10-17行) （5）テキスト類似度が類似条件を満たす必要条件を満たしているなら構造類似度を求める(18-22行) （6）類似条件を満たしているなら部分木は類似しているとみなし結果リストに追加する(23-25行) （7） Post-order Queueが空になるまで以上の処理を繰り返す 3. 8 計算量この節では提案手法を木編集距離計算とJaccard係数計算の表 2 ノードデータの例

posID left wsize nodetype label words

0 0 1 text 0 (John) {0} 1 0 1 element 1 (author) {} 2 2 1 text 2 (DB) {2} 3 2 1 element 3 (category) {} 4 0 2 element 4 (article) {} 5 5 1 text 5 (peter) {5} 6 5 1 element 1 (author) {} Algorithm 1 EnumrateSimilarSubtree Require: D, Q, α, θ

Ensure: all subtrees fulfill Similarity Condition

1: Calculate maxDn(upper bound of nodes),

2: maxDw(upper bound of words)

3: Doc⇐ new RingBuﬀer(maxDn)

4: P Q⇐ Post-order Queue of D 5: Result⇐ Empty List of subtrees 6: for di: P Q do

7: Doc[i % maxDn]⇐ di

8: if |Di| > maxDnor|W ordsDi| > maxDw then

9: goto N EXT

10: end if

11: if diis not leaf node then

12: 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

19: Simt⇐ Doc[i % maxDn].words.getJ accard()

20: if α(1−abs(|Di|−|Q|) |Di|+|Q| ) + (1− α)Simt< θ then 21: goto N EXT 22: end if 23: Sims⇐ 1 −T ED(D_|D i,Q) i|+|Q|

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

25: Result.add(Di) 26: end if 27: N EXT : 28: end for 29: return Result 部分に分け，それぞれの計算量について述べる．まず木編集距離の計算部は[7] の手法から時間計算量

O(|Di||Q|depth(Di)depth(Q))空間計算量O(|Di||Q|)となる．

ここで，depth(Di)はそれぞれ木の深さを表しており，最悪で Di,平均でlog2(|Di|)となる．また，|Di| の最大値maxDn はQ, θ, αにより決まるので，時間計算量 O(|Q|2 log22|Q|)空間計算量O(|Q|2 )となる．さらに，木編集距離計算は類似部分木候補の数だけ実行されるため，最終的に全ての処理に対する時間計算量はO(C|Q|2_log2 2|Q|) (CはDに含まれる類似部分木候補の数)となる．次にJaccard係数の計算部について考える．まず，一単語を W ordsDiに挿入する時にそれがW ordsQとの共通要素なのかを調べるために二分探索を行っているためO(log2|W ordsQ|) が必要である．さらに，単語を単語集合に挿入する回数は最大でO(|W ordsD| log2|W ordsD|) となる．これは，一単語に関して一度挿入が行われる度にその単語を含んでいる集合の要素数が2 倍以上に増えていくと考えると，一単

(6)

語が挿入される回数は高々 log2|W ordsD| 回になることから分かる．ここで，_{|W ords}D|, |W ordsQ| はそれぞれ D, Q に比例していると考えると，すべての処理に対する時間

計算量は O(D log2(D) log2(Q)) となる．空間計算量に関し

ては，ノードデータが O(maxDn) ≃ O(Q)，単語集合が

O(maxDnmaxDw) ≃ O(|Q|2) であるため，全体でO(|Q|2)

となる．

4. 評価実験

4. 1 実験の目的および実験環境実際にXMLファイルを入力とし，θやD, Qの大きさ，類似部分木の含有率の違いによる実行時間，消費メモリ，検出部分木数の変化を調べた．加えて，既存手法との実行時間，木編集距離の計算回数の比較を行った．また，本実験において実行時間のうち木編集距離計算にかかった時間を計算時間，それ以外の時間を探索時間と表記する． D として人工データであるXMarkベンチマーク（注 2）_と実データであるdblp（注 3）, SwissProt（注 4）を使用した．dblp, Swis-sProtのXMLファイルはXML Data Repository（注 5）の物を利用した．QにはDから抽出した適当なサイズの部分木を使用した．使用したデータセットを表3に示す．なお，ここでの語彙数とはデータセット内に存在するユニークな単語の総数であり，構造数とはテキストノードと属性値のテキストを全て無視(木構造とエレメントノードのラベルのみを考慮)した時のユニークな部分木の数である．

実験は全て64bit Windows7, Intel Core i7 @ 3.20GHz CPU,

8GB RAM で構成されたPC上で行った．提案手法と既存手

法であるTASMのプログラムはC++で記述しx86 64-w64-mingw32, gcc version 4.5.4 20111030を使いコンパイルを行った．既存手法であるSSは著者により提供されたJavaによるプログラムをJRE 64bit version 1.7.0 45 上で実行し実験を行った． 4. 2 D の大きさの違いによる実験 Dのファイルサイズを100MBから4000MBまで変化させ表 3 使用したデータセット名前サイズノード数単語数語彙数構造数 [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 dblp 128 7.2 6.7 733 10 （注2）：http://www.xml-benchmark.org/ （注3）：http://www.informatik.uni-trier.de/~ley/db/ （注4）：http://web.expasy.org/docs/swiss-prot_guideline.html （注5）：http://www.cs.washington.edu/research/xmldatasets/www/ repository.html 0 1 2 3 4 5 6 7 0 5 10 15 20 25 30 35 40 45 0 1000 2000 3000 4000 M emo ry [MB] Ti m e [s ] File size [MB] 探索時間[s] 計算時間[s] 消費メモリ[MB] 図 5 D の大きさの違いによる実行時間と消費メモリの変化 0 200 400 600 800 1000 1200 1400 0 5 10 15 20 25 30 35 40 45 50 0.5 0.6 0.7 0.8 0.9 1 N um be r o f Sub tr ee Ti me [s] Threshold 探索時間[s] 計算時間[s] 検出候補数検出結果数図 6 閾値の違いによる実行時間と検出部分木数の変化 |Q| = 54, θ = 0.8, α = 0.5として実行時間，使用メモリを計測した．結果を図5に示す．探索時間はほぼDの大きさに比例しており，消費メモリと計算時間は文書サイズによらず一定であった． 4. 3 閾値の違いによる実験閾値 θ を0.55から0.95まで変化させた時の実行時間と類似部分木の検出数を計測した．D にはXmark1800を使用し， |Q| = 84, α = 0.5として計測した．結果を図6に示す．閾値0.55から0.70にかけて検出部分木数が大きく変化しており，それに伴い木編集距離の計算時間も大きく変化した（2.94秒から0.11秒）．θ >_{= 0.70}の時に検出候補数は検出結果数とほぼ等しくなっており，テキスト類似度を用いた候補の絞り込みが効果的に作用していると考えられる． 4. 4 Q の大きさの違いによる実験 Qのノードサイズを変化させて実行時間，使用メモリを計測した．DにはXmark200を使用し，全て θ = 0.8, α = 0.5とした．結果を図7に示す．計算時間，消費メモリともに Qが大きくなるにつれて増えた．探索時間はほぼ一定であった．3. 8節で示した各計算量のQに関する部分を抜き出すと • 探索時間O(log2|Q|) • 計算時間_O(|Q|2 log2|Q| 2 ) • 消費メモリO(|Q|2₎ であり，Qの変化に対するそれぞれの実験結果は上記の理論

(7)

1 10 100 1000 0.01 0.1 1 10 100 10 100 1000 10000 Me mo ry [M B] Ti m e [s ]

Query node size

探索時間計算時間メモリ消費 図 7 Q の大きさの違いによる実行時間と消費メモリの変化 0 10 20 30 40 50 60 70 80 0 20 40 60 80 100 Ti m e [s ]

Content rate of similar subtree [%] 探索時間[s] 計算時間[s] 図 8 類似部分木の含有率の違いによる実行時間の変化的な計算量に対応している事が確認できる． 4. 5 類似部分木の含有率の違いによる実験 D に含まれるQ の類似部分木の数を変化させて実行時間を計測した．ノード数32の Qを作成した後，クエリXML を任意の割合で含んだ D（ノード数 3,200,000）を作成し， θ = 0.8, α = 0.5として計測を行った．結果を図8に示す．探索時間は類似部分木の含有率によらず一定，計算時間は3. 8節で示した通り含有率に比例した． 4. 6 既存手法との比較実験人工データ，実データの両方に対して実行時間と木編集距離の計算回数の計測を行い既存手法のTASM, StructureSearch (SS) との比較を行った．提案手法では全てθ = 0.6, α = 0.5,|Q| = 64 で計測を行った．TASM, SSではk = 5とし，類似度上位5個の部分木の検出を行った．結果を図9，図10に示す．実行時間について全てのデータセットでTASM, SSの両方を上回る性能を確認することができた．TASMと比較すると30∼75倍，SSと比較すると7∼13 倍の高速化が確認できた．木編集距離計算回数を見てみると，提案手法では既存手法に比べ木編集距離の計算回数が格段に少ない事が分かる．これらの結果から，テキスト類似度を利用した枝刈りが実行時間の削減に大きく影響を与えていると考えられる．提案手法による実データであるSwissProtとdblpの木編集距離計算回数を比べると，SwissProtの方が著しく多くなって 1 10 100 1000

Xmark100 XMark200 XMark1800 SwissProt dblp

Time [s ] Document name TASM SS 提案手法図 9 既存手法との実行時間の比較 1 10 100 1,000 10,000 100,000 1,000,000 10,000,000

Xmark100 XMark200 XMark1800 SwissProt dblp

TED Com pu ta tio n Document name TASM SS 提案手法図 10 既存手法との木編集距離の計算回数の比較おり，実行時間も比較的長くなっている．これは，SwissProt の語彙数が少ないため，似た単語集合を持つ部分木が多く存在し，テキスト類似度での絞り込みがうまく作用していないからであると考えられる． 4. 7 α, θ の違いによる検出部分木数の比較実験テキスト類似度，構造類似度が XML データの類似度に対してどの程度寄与しているかを調べる為に，実データであるSwissProtとdblp を対象XMLとし，α = 0.0(テキスト類似度のみ), α = 0.5, α = 1.0(構造類似度のみ) において閾値を変化させた時の，類似部分木として検出された部分木の数を計測した．また，クエリXMLには4. 6節での実験に用いたものと同じデータを使用した．結果を図11，図12 に示す． α = 0.5 でのテキストと構造を考慮した場合を見てみると， dblpではクエリXMLと類似している部分木がほぼ存在しないが，SwissProtでは高い類似度を持つ部分木が多く存在している事が分かる．また，テキストのみを考慮した場合と構造のみを考慮した場合を比べた時，dblpでは構造が似ている部分木の数がテキストが類似している部分木の数に比べ非常に多く， SwissProtでは構造が似ている部分木の数とテキストが似ている部分木の数にあまり差がない事が分かる．さらに，表3に示す通り，dblpはSwissProtよりも語彙数が多く，SwissProtは dblpよりも構造数が多い事が分かる．これらの特徴は，dblp はテキストを中心に扱ういわゆるデータ指向型なXMLデータ

(8)

1 10 100 1000 10000 100000 1000000 10000000 0 0.2 0.4 0.6 0.8 1 N umb er of S ub tr ee Threshold α = 0.0 (テキストのみ) α = 0.5 α = 1.0 (構造のみ) 図 11 SwissProt での α, θ による検出部分木数の比較 1 10 100 1000 10000 100000 1000000 10000000 0 0.2 0.4 0.6 0.8 1 N umb er o f Su btr ee Threshold α = 0.0 (テキストのみ) α = 0.5 α = 1.0 (構造のみ) 図 12 dblp での α, θ による検出部分木数の比較 であり，SwissProtは構造を中心に扱うXMLデータであることに起因する．さらに4. 6節での既存手法との比較実験の結果において，対象XMLがdblpの時，SwissProtの時に比べて速度と枝狩り効率が大きく向上している事と照らし合わせると，本手法はデータ指向型であるXMLデータを対象とした時により高い効率性を発揮できているということがわかる．

5. ま

と

め

本稿では，XMLにおける類似部分木探索問題を対象とし，テキストの類似度と構造の類似度の二面から類似度を求める手法を提案した．テキストノードに対する類似判定と木構造に対する類似判定を混ぜあわせることで既存手法に比べ高度な類似判定を実現した．また，提案手法に対し巨大なXMLファイルを対象とし，時間計算量，空間計算量の双方ともに効率的であるアルゴリズムを提案した．提案したアルゴリズムについて実際に実装，評価実験を行い巨大なXMLファイルに対しても適用可能な性能であることが確認できた．さらに既存手法(TASM, SS)との比較を行った結果，人工データ，実データともに既存手法よりも短い実行時間で実行可能であることが確認できた．この事から，テキスト類似度を利用した類似部分木候補の絞り込みが効果的に作用し，既存手法での冗長な木編集距離計算を削減できたと考えられる．本手法では対象とするXMLがデータ指向型XMLであるほど本手法は効率性を発揮できる事が確認できたが，反面，構造を中心に扱うXMLを対象とした時にテキスト類似度での絞り込みがうまく作用しにくいという事が分かった．こういうケースでは部分木が類似しているかどうかについて構造類似度の占める割合が多くなっていると考えられる．よって，構造を考慮した候補の絞り込みを取り入れることでこのようなXMLデータを対象とした時にも効率性を維持できることが期待される．さらに，対象XMLに含まれる語彙数や構造数をもとにその XMLデータが持つ特徴を予め調べておき，探索や枝刈りに活用するといった改良案が考えられる．これらの他に今後の課題として，木編集距離やJaccard係数以外の類似度指標を適用することによる幅広い類似条件設定の実現や，切り出した単語に対してストップワードを取り除く等のふるい分けや重み付けを行うことによる検出精度の向上，類似極大部分木検出への拡張等が挙げられる．加えて，さらなる高速化という点ではBloom Filterによるテキスト類似度計算回数の削減やインデックス作成によるディスクアクセス時間の削減，並列化への対応などが挙げられる．謝辞本研究の一部はJSPS科研費25330124の助成を受けたものである．また，実験を行うにあたり，ザルツブルグ大学の

Nikolaus Augsten教授，ヘブライ大学のSara Cohen教授に

プログラムコードを提供をしていただいた．

文献

[1] Joe Tekli, Richard Chbeir, and Kokou Yetongnon. Sur-vey: 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 prob-lems. Theor. Comput. Sci., Vol. 337, No. 1-3, pp. 217–239, June 2005.

[3] Apichaya Auvattanasombat, Yousuke Watanabe, and Haruo Yokota. An evaluation of similarity search meth-ods blending structures and keywords in XML documents. In IIWAS ’13, 2013.

[4] Lu´ıs Leitão and Pável Calado. Efficient XML duplicate de-tection using an adaptive two-level optimization. In Pro-ceedings 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 Knowl-edge 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 In-ternational 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 the editing 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 docu-ments. 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.

DEIM Forum 2014 D7-5 XML XML Web XML XML XML XML