論文 / 著書情報
Article / Book Information
論題

Office XML文書の部分木に着目した類似スタイルのファイル検索

Title

Style Search for Office XML Documents using XML Sub-tree Similarity

著者

上垣外英剛, 渡辺陽介, 横田治夫

Author

Hidetaka KAMIGAITO, Yousuke WATANABE, Haruo YOKOTA

掲載誌/書名

第4回データ工学と情報マネジメントに関するフォーラム(DEIM2012),, ,Journal/Book nameDEIM2012, , ,

発行日 / Issue date2012, 3

Powered by T2R2 (Science Tokyo Research Repository)DEIM Forum 2012 E11-2

Oﬃce XML 文書の部分木に着目した類似スタイルのファイル検索
上垣外英剛†

渡辺

陽介††

横田

治夫†††

† 東京工業大学 工学部 情報工学科†† 東京工業大学 学術国際情報センター††† 東京工業大学 大学院情報理工学研究科 計算工学専攻〒 152-8552 東京都目黒区大岡山 2-12-1
E-mail: †kamigaito.h.aa@m.titech.ac.jp, ††watanabe@de.cs.titech.ac.jp, †††yokota@cs.titech.ac.jp
あらまし

近年，Oﬃce 文書に代表されるような，フォント，配置，サイズ等の詳細なスタイル情報を含んだ複数のXML ファイルから構成されるアーカイブ形式の文書が増加している．しかし，既存のテキストベースの検索エンジ
ンは，本文の文字列やタグ情報などを検索対象とするのみで，スタイル情報を活用してはいない．スタイル情報まで踏み込んだ検索ができれば，本文の内容に依らずに体裁の類似した文書を探し出すなどの要求が実現できると考えられる．そこで本稿では，Oﬃce 文書内のスタイル情報の XML ファイルに着目した類似検索手法として SOS を提案す
る．SOS の内部処理における XML ファイル同士の類似度計算の精度向上のため，既存の XML ファイルの類似度計
算アルゴリズム LAX を改良した手法 LAX+を提案する．提案手法に対し，実際に docx，xlsx，pptx のファイルを用いて，スタイルの類似した文書を検索した際の適合率，再現率を評価する．
キーワード

Oﬃce Open XML, XML Similarity, 類似スタイル検索

Style Search for Oﬃce XML Documents using XML Sub-tree Similarity
Hidetaka KAMIGAITO† , Yousuke WATANABE†† , and Haruo YOKOTA†††† Department of Computer Science, Tokyo Institute of Technology†† Global Scientiﬁc Information and Computing Center, Tokyo Institute of Technology††† Department of Computer Science, Graduate School of Information Science and Engineering
Tokyo Institute of Technology
2-12-1 Ookayama, Meguro-ku, Tokyo, 152-8550 Japan
E-mail: †kamigaito.h.aa@m.titech.ac.jp, ††watanabe@de.cs.titech.ac.jp, †††yokota@cs.titech.ac.jp
Abstract Recently, the number of oﬃce documents represented by XML archive format is increasing. XML ﬁlesin oﬃce documents contain information about page structures and styles such as font, size and arrangement. But,
existing text-based search engines do not focus on these style information. If we utilize them, we can achieve similarity search for oﬃce documents based on structures and styles. We propose SOS, a similarity search method basedon structures and styles of oﬃce documents. To compute similarity between oﬃce documents, we have to compute
similarity of XML ﬁles in the oﬃce documents. We also propose an XML similarity algorithm LAX+ which is anextension of existing XML leaf node clustering algorithm LAX. In our experiments, we use docx, xlsx and pptx ﬁlesand evaluate SOS and LAX+ by precision and recall.
Key words Oﬃce Open XML, XML Similarity, Style Search

1. は じ め にXML ファイルに記録している．こうしたファイル数の増加に伴い，Oﬃce 文書の検索要求は高度化・多様化してきている．

近年，Microsoft Oﬃce に代表されるような XML 記述を用

しかしながら，既存のテキストベースの検索エンジンは，本いたアーカイブ形式の文書が増加している．これらの文書は文の文字列やタグ情報などを検索対象とするのみで，スタイル

内容と共に，フォント，テキストサイズ，配置，文字色，リス

情報を活用してはいない．スタイル情報まで踏み込んだ検索がトのマーカー等を始めとした多くの構造情報・スタイル情報をできれば，本文の内容に依らずに体裁の類似した文書を探し出図 2 OOXML の構造
図 1 類似スタイル Oﬃce 文書の検索システム

ズムで，精度が高いという特徴を持つ．しかし，TED は現在したり、テンプレートによる文書の管理を行うなどの要求が実最も計算量が少ない方法 [8] でも O(n3 ) であり，データ量が多現できると考えられる．

い XML ファイルや，多くの XML ファイルを比較する用途に

本研究では図 1 に示すような，ある Oﬃce 文書ファイルを与は向いていない．一方で計算量が少ないアルゴリズムとしてはえるとそれに類似したスタイルを持つ Oﬃce 文書をランキング

tag similarity [9]，entropy を用いた手法 [10] 等が存在する．いして返す検索システムの構築を目指す．そのための Oﬃce Open

ずれも計算量 O(n) と高速ではあるが，精度が低いという問題

XML 文書 (以下 OOXML 文書) を対象にしたスタイル類似度検点がある．精度が高く計算量も多くはないアルゴリズムとして索手法として，Structure-based Oﬃce Document Search (以は LAX [11] が存在する．LAX は部分木のリーフノードを比較

下 SOS) を提案する．SOS では，まず OOXML 文書内に含ますることで XML 文書の類似度を計算するアルゴリズムで，計れる複数 XML ファイル同士の類似度を計算し，そしてそれ

算量は O（n2 ）である．本研究では，OOXML 文書内の XMLらを集約して OOXML 文書間の類似度を求めている．よって，ファイルを対象に，LAX を改良した手法を提案する．

XML ファイル間の類似度を精度よくかつ効率的に計算するアルゴリズムが特に重要な役割を担う．本研究では XML ファイ

3. Oﬃce Open XML

ル間の類似度計算アルゴリズムとして，我々の研究グループ

Oﬃce Open XML ファイルフォーマット (以下 OOXML) は，が以前に提案したアルゴリズム LAX [11] を改良した LAX+を

Zip アーカイブとして保存されているため，解凍することで構提案している．本稿では提案手法 SOS, LAX+に対し，実際に造を展開できる．OOXML の構造を.docx を例として図 2 にdocx，xlsx，pptx のファイルを用いて，スタイルの類似した示した．OOXML の構造はいくつかの Markup Langauge(以文書を検索した際の適合率，再現率を評価する．

下 ML) によって定義されている [1]．主にパーツと，パーツ間

本稿の構成は以下の通りである．まず，2. 節で関連研究につの関係を記述したファイルで構成されていて，各パーツは 1 つ

いて述べ，3. 節で提案手法を理解するために必要な前提知識で以上の XML ファイルによって構成されている．この節ではス

ある OOXML の概要を説明する．次に 4. 節において SOS を

タイル情報を読み取る際に重要なパーツファイルについて説明

提案し，5. 節にて XML ファイル間の類似度計算アルゴリズム

する．

として，既存手法の LAX と今回改良を加えた LAX+を説明す•

Shared ML: WordProcessing ML，Spreadsheet ML，る．6. 節で提案手法 LAX+および SOS の評価を行い，最後にPresentation ML において共通して使用されるパーツを含

7. 節でまとめと今後の課題を述べる．

んでいる．これらのパーツはメタデータかユーザー定義に関

2. 関 連 研 究
Oﬃce 文書の本文の内容検索を実現した検索エンジンであ係する情報を含んでおり，スタイル情報を検索する際に重要である．

•

WordProcessing ML: 主に.docx 拡張子の文書に使用さればすでに多く存在する．ローカル環境を対象としたものはれている．WordProcessing ML では document.xml が多くの

Windows デスクトップサーチ [2], Mac OS X の Spotlight [3]パーツを参照しており，中心的な役割を果たしている．またが，Web 上では Google ﬁletype 検索 [4] 等がある．基本的にこ単一の document.xml でメインとなる内容を記録をしている．

れらの検索エンジンでは，本文の文字列やタグ情報などを検索重要な役割が document.xml に集約されているため WordPro-

対象とするのみで，スタイル情報を活用してはいない．Oﬃce

cessing ML は簡単な構造をしている．注釈に関するパーツが文書のスタイル情報は XML 構造を用いた記述がなされている

多いのも特徴である．

ため，文書の内容に重点を置いた文字列による検索では，直接スタイルを検索することは難しい．

•

Spreadsheet ML: 主に拡張子.xlsx のファイルに使用されている．Spreadsheet ML を構成するパーツファイルの数はXML ファイルの類似度計算には多くの方法が存在する [5]．

他の ML と比較して非常に多い．これはワークブック，ワーク

そのなかでも Tree Edit Distance(TED) [6] が最も有名である．

シート，セルのそれぞれの区分けで文書を管理しているからで

TED は一般的な文字列の比較に用いられているレーベンシュ

ある．実用上 xlsx は主にワークシートとそれらを取りまとめる

タイン距離 [7] を，木構造にも使えるように拡張したアルゴリ

ワークブックによって構成されているが，Spreadsheet ML の

構造もそれを踏まえた形となっている．複数のセルに関係する
トに関係するパーツは workbook.xml からそれぞれの rels ファ

れぞれ直接，もしくは間接的に presentaion.xml か slideN.xml
から参照されており，他のパーツと比べると重要性が高い．

OOXML はスタイル情報が 1 つ以上の XML によって構成される複数のパーツによって記述されているため，単一の XML
ファイルの比較では十分ではない．そのため全体的なスタイルの検索に必要な類似度計算を行うには，スタイル関連の情報を多く含む複数の XML ファイル間での比較を考慮する必要がある．次節では複数の XML ファイル間での類似度計算を行い，Oﬃce 文書に対するスタイル類似度検索を行う手法について説明する．

4. Structure-based Oﬃce document Search(2)

Spart (pqj , pij ) =smax(|Fqj |, |Fij |)(4)

片方の OOXML 文書にしか j 番目のパーツが存在しない場合
は Sparts (pqj , pij ) = 0 とする．sq→i と si→q を分けて求める
理由は，LAX が Sxml (fx , fy ) =| Sxml (fy , fx ) となる非対称な性質の類似度尺度であるためである．本研究で改良を行った

LAX+は対称な類似度尺度であるため，LAX+を用いて XML
ファイルの類似度を求めている場合は，2 回同じ計算を行う必
要はない．
（ 3 ） OOXML 文書同士の類似度計算:

OOXML 文書同士の類似度を，それらに含まれるパーツの類似度から計算する．OOXML 文書 oq , oi の類似度 Soo (oq , oi ) は，各文書に含まれるパーツの集合 Pq , Pi から以下の式で計算される．

Soo (oq , oi ) =∑pqj ∈Pq ,pij ∈Pi

wj( ∑|P |
q

l=1 wl× Spart (pqj , pij ))(5)

本 節 で は 提 案 手 法 Structure-based Oﬃce document

Search(以下 SOS) について説明する．
以下では，類似検索におけるクエリに相当する OOXML 文書
を oq ，検索対象となる OOXML 文書集合を O = {oi |1 <
=i<
= I}

(3)

i→q

Presentation ML: 主に拡張子.pptx のファイルに使用さのパーツの中でも slideMasterN.xml と slideLayoutN.xml はそSxml (fijk , fqjk )sq→i (|Fqj | > |Fij |)s =s(otherwise)

造になっている．

Presentation ML の中心的な役割を果たしている．また，その他(1)fqjk ∈Fqj ,fijk ∈Fij

するものであっても workbook.xml から間接的に参照される構(N = 1, 2, . . .) から参照されており，これら 2 つのパーツが∑si→q =

イルを通じて参照される．ただし変更履歴はワークシートに関れている．ほとんどのパーツが presentation.xml と slideN.xml

Sxml (fqjk , fijk )fqjk ∈Fqj ,fijk ∈Fij

パーツは worksheetN.xml (N = 1, 2, . . .)，複数のワークシー•∑

sq→i =

ただし，wj は j 番目のパーツに対する重みづけ変数を表わしている．
（ 4 ） OOXML 文書類似度に基づくランキング:と 表 記 す る ．前 述 の 通 り，各 OOXML 文 書 oi の 内 部 は 複文書集合 O = {oi |1 <=i<= I} の要素のうち，類似度 Soo (oq , oi )数 の パ ー ツ の 集 合 Pi = {pij |1 <= j <= Ji } に よって 構 成の値が閾値を超えた oi のみ，値の高い順にランキングする．なさ れ て お り，各 パ ー ツ pij も 複 数 の XML ファイ ル の 集 合お，閾値は 0 から 100 の範囲で指定可能である．

Fij = {fijk |1 <= k <= Kij } によって構成されている．その5. XML ファイル間の類似度計算ため，2 つの OOXML 文書 oq , oi 間の類似度 Soo (oq , oi ) を求めるには，下の階層から段階的に集約していく必要がある．まず

この節では本研究で提案する XML ファイルの類似度計算アパーツを構成している XML ファイルの類似度 Sxml を計算し，ルゴリズム LAX+について説明する．OOXML 文書は XML

その後パーツごとの類似度 Sparts を集計し，最後に OOXML

ファイルのリーフノードに主なスタイル情報が記録されている文書の類似度 Soo が決定される．

ため，OOXML 文書の検索を実現するためにはリーフノードに

SOS における OOXML 文書同士の類似度の大まかな計算手着目した XML 類似度計算手法を用いることが望ましいと考え順は以下のようになっている．

られる．また SOS では複数の XML ファイル間で比較を行う（ 1 ） XML ファイル同士の類似度計算:

ため，計算量が少ない手法でなければならない．そこで本研究oq と oi 中の j 番目のパーツ pqj , pij に含まれる XML ファイル

では，計算量が O（n2 ）と高速で精度も高くリーフノードに着のうち，ファイル名が対応するもののペア (fqjk , fijk ) の類似度目したアルゴリズムである LAX [11] に着目して，LAX に改良

Sxml (fqjk , fijk ) を計算する．この値は，5. 節で述べる LAX(従を加えた LAX+を SOS における XML 文書の類似度計算関数

来手法) または LAX+(提案手法) によって求められる．

とする．

（ 2 ） パーツ同士の類似度計算:

まず 5. 1 節で LAX の概要について述べ，5. 2 節で LAX をOOXML 文書に含まれる同一パーツ間の類似度を，そのパーOOXML 文書に適用する際の問題点について述べる．その後，

ツ に 属 す る XML ファイ ル の 類 似 度 を 集 約 し て 計 算 す る ．

5. 3 節で LAX+について述べる．

OOXML 文書 oq , oi の中の j 番目のパーツ pqj , pij 間の類

5. 1 既存手法: LAX

似度 Sparts (pqj , pij ) は，各パーツが含んでいる XML ファイル

LAX は与えられた 2 つの XML ファイル fbase , ftarget に対集合 Fqj , Fij から以下の式で求められる．

して類似度 Sxml (fbase , ftarget ) を求めるアルゴリズムである．
非対称な性質を持つ類似度尺度であるため，ここでは第 1 引

図4

リーフノード数の差

図5

局所一致による影響

図 3 LAX数のファイルを base, 第 2 引数のファイルを target と区別す
る．LAX の処理手順を図 3 に示し，以降では各手順の詳細を述べる．
（ 1 ） 部分木の生成:

LAX では XML ファイルの木構造を部分木に切り分ける点をカッティングポイントと呼んでいる．XML ファイル内のある
ノード x が，どれだけカッティングポイントに相応しいかを表
す値 wx は以下の式で表される．

wx = |children(x)| × dix(6)
XML ファイルではテキスト量の増大に伴い，一つの部分木の

ただし，|children(x)| はノード x の子ノードの数，dx はノー

リーフノード数が増大する傾向がある．LAX では部分木の比

ド x からリーフノードまでの最大距離，i は重み付け変数を表

較に式 7 を使っているために，base 側の部分木のリーフノード

わしている．base， target 両 XML ファイルそれぞれに対しが多い場合に部分木の類似度が低くなってしまう．例として図て，全ノード中最も大きい wx を持つノード x を見つけ，x の

4 の場合，リーフノードの傾向は base， target で類似性が見子ノードをルートノードとした部分木に元の XML ファイルをられるが，base のリーフノードが 6 つ，target が 3 つなので，分割する．以降では，分割によって生成された部分木の集合を類似度が 50%を上回ることはない．

T = {tu |1 <=u<= n} と表記する．
（ 2 ） 部分木同士の類似度計算:

LAX では式 8 において max を求めているため，局所的な一致

base の部分木集合と target の部分木集合のそれぞれの要素同士が，XML ファイル全体の類似度に強く反映されてしまうことで，部分木としての類似度を求める．LAX では，部分木 tu , tvがある．図 5 では base の全ての部分木が Target Subtree 1 との類似度を計算する関数 Ssub (tu , tv ) は以下の式で定義される．

の比較で 100%の類似度であるため，類似度計算によって求め

Ssub (tu , tv ) =|Leaf P airs(tu , tv )|× 100|Leaf (tu )|（ 2 ） 局所一致による影響力の強さ:

られた base と target の類似度は 100%となる．しかしこの値(7)

ただし，|Leaf (tu )| は部分木 tu に属するリーフノード数 ，|Leaf P airs(tu , tv )| は部分木 tu ，tv に属するリーフノードの中で，PCDATA が同じペアを作った場合のペア数とする．
（ 3 ） XML ファイルの類似度計算:
部分木同士の類似度から XML 文書全体の類似度を求める．

LAX における XML ファイル fbase , ftarget の類似度を求める関数 Sxml (fbase , ftarget ) は，各ファイルの部分木集合 Tbase ,Ttarget から以下の式で定義される．
Sxml (fbase , ftarget )∑tv )))
tu ∈Tbase (maxtv ∈Ttarget (Ssub (tu ，=|Tbase |類似度とは言い難い．
（ 3 ） 部分木のサイズの差による不公平:

LAX では式 8 で部分木の類似度を求める際に，リーフノード
数の差を考慮していない．そのため，リーフノードが少ない部
分木では類似度として大きな値が出やすい一方で，リーフノー
ドが多い部分木では大きな類似度は出にくくなる．結果として

LAX では小さな部分木が多い XML ファイルほど高い値が出
5. 3 提案手法: LAX+
5. 2 節の問題を解決するため，LAX に対して改良を行った(8)

ここでは OOXML に LAX を使用した場合に生じる問題点について述べる．各問題の解決については 5. 3 節で改良手法を（ 1 ） リーフノード数の差による不公平:映された結果で，極めて局所的であり，XML ファイル全体のやすくなる傾向がある．

5. 2 OOXML に LAX を用いる際の問題点

提案する事で行う．

は base の各部分木と Target Subtree 1 だけの類似度が強く反LAX+を提案する．改良の詳細は 5. 3. 1 節，5. 3. 2 節，5. 3. 3
節にて詳しく説明する．

5. 3. 1 双方向での base と target の比較
LAX に使われている部分木の類似度 Ssub は非対称性があり，計算においては base となる XML ファイルから target となる XML ファイルを比較した値しか考慮されない．そのため

5. 2 節（２）のような局所的な一致が起こった際にそれに対処+
Sxml(fbase ，ftarget )= min(

∑
∑

+
tv ))
tu ∈Tbase maxtv ∈Ttarget (Ssub (tu ，|Leaf (fbase )|

,

+
tv ))
tv ∈Ttarget maxtu ∈Tbase (Ssub (tu ，|Leaf (ftarget )|)(10)

ただし，Tbase ，Ttarget は base と target の XML ファイルの図6

部分木の集合，|Leaf (f )| は XML ファイル全体のリーフノー

局所的な一致の改善

ドの数とする．
することができない．そこで target から base を見た値も同時に算出するように変更を行う．変更前の LAX でも元々base，

target の全ての部分木のリーフノードの組み合わせを計算してLAX+によって求められる XML ファイル同士の類似度は，
5. 3. 2 節，5. 3. 3 節の改良によって以下のような性質を持つ．
++
Sxml(fbase ，ftaret ) = Sxml
(ftarget ，fbase )(11)いるため，この方法を取ることによる計算量の増加は僅かなもこの性質により，4. の（２）においては，半分の計算量で結果のとなる．
この方法を取れば図 6 の様に base，target どちらかが局所的を求めることができる．ただし計算量のオーダー自体は，LAXな一致によって類似度を計算している際に，より値が小さい結の O(n2 ) から変化していないため，リーフノード数が増大した果を用いるようにすることで局所的な一致を防ぐことができる．

場合は大幅に計算時間が増えることに変わりはない．

ただし，base，target 双方が局所的な一致によって類似度を計

6. 評 価 実 験

算している場合はこの方法でも局所的な一致は改善されない．
本節では，実験によって LAX+と LAX の比較，および SOS

5. 3. 2 部分木の類似度計算
5. 1 節で示したように，LAX では部分木の比較において完全と既存の全文検索エンジンとの比較を行う．

一致したリーフノードのペア数を用いているために，部分木の6. 1 LAX と LAX+の比較実験

サイズの差による影響を受けて 5. 2 節の（１）の様な問題が起

ここでは，単一の XML ファイルに対する LAX と LAX+のこってしまう．そこで部分木同士の類似度 Ssub (tu , tv ) の計算

precision，recall を実験によって求めて比較し，5. 3 節にて行っ+式を新たに Ssub(tu , tv ) として以下の様に変更する．

た LAX の改良が精度向上に貢献したかを評価し，考察を行う．

6. 1. 1 実験データ・実験手法+
Ssub(tu ，tv ) = |M atched Leaf (tu , tv )|(9)

ただし，|M atched Leaf (tu , tv )| は部分木 tu ，tv に含まれる
リーフノードのうち，相手側の 1 つ以上のリーフノードと

PCDATA が一致するものの数とする．
LAX では部分木の比較ごとに正規化した値を部分木の類似度として算出しているため，部分木のサイズが考慮されず，5. 2
節の（３）の問題が起きていたが，この方法では部分木比較の段階では正規化を行わないので，この問題も避けることができる．

5. 3. 3 XML 文書間の類似度計算
5. 3. 2 節の変更によって，部分木比較の段階での正規化は行われないため，XML ファイル間の類似度計算を行う際に正規化する．5. 3. 1 節の変更も考慮すると，それらの計算を，baseから見た target の類似度，target から見た base の類似度，の2 種類に対して行う必要がある．LAX では式 8 を使って正規化された部分木比較の結果の平均を求めていたが，改良手法では以下の式を用いる．

実験データは Web 上で収集した 287 個の pptx ファイルを用いた．それらを人手で 1 枚目のスライドのスタイルを基準にし，53 個のグループに分類して正解情報を作成した．
実験は LAX，LAX+共に以下の手順で行う．
（ 1 ） pptx 文書群から検索クエリ oq を 1 つ選択し，それ以外の文書集合を検索対象とする．
（ 2 ） 検索クエリと検索対象の各文書に対して，pptx 内の 1
枚目のスライドの書式情報を記録した XML ファイル slide1.xmlのみを使って XML ファイル同士の類似度計算を行う．
（ 3 ） 類似度に基づいて上位 k 件までランキングし，実際の正解と照らし合わせて precision, recall を求める．
（ 4 ） すべての文書が検索クエリとなるように手順 1, 2, 3を繰り返し，precision, recall の平均値を求める．

6. 1. 2 実 験 結 果
LAX，LAX+の precision-recall グラフを図 7 に示す．横軸は recall で，縦軸はその recall 値における precision の平均値を表している．図 7 から分かるように，全体的に LAX+が LAXよりも高い precision を示した．

11 点補完平均適合率は LAX が 0.374，LAX+が 0.583 となった．最も precision, recall が接近した際のそれぞれの値は LAX
は precision が 0.438，recall が 0.447，LAX+は precision が0.562，recall が 0.555 となった．

図 7 LAX(既存手法) と LAX+(提案手法) の precision-recall グラフ

図 8 docx での precision recall グラフ

以上の結果，いずれも LAX+の方が精度が高いことから，5. 3シートのスタイル情報を基準にし，人手により 31 個のグルー節において加えた変更が XML ファイル同士の類似度計算の精プに分類した．実験に際して，1 枚目のシートの類似度に基づ度を改善したことが確認された．

いた検索を行うため，対象から sheet1.xml 以外の sheetN.xml

6. 2 SOS の評価実験
ここでは，SOS を用いて実際にスタイル検索が可能である(N = 2, 3, . . .) を除外した．
•

pptx: Presentation ML 用の実験データは 6. 1 節で使かを OOXML 文書の種類ごとに調査する．また，テキスト検用されたものと同じ実験データを使用した．実験に際して，1

索と比較することで，OOXML 文書に対するスタイル検索で枚目のスタイルの類似度に基づいた検索を行うため，対象からは XML ファイル同士の類似度の活用が有効であることを示す．

slide1.xml 以外の slideN.xml，slideMasterN.xml，slide- Lay-

さらに各 OOXML 文書の ML において重要なパーツを調べ，outN.xml，notesSlideN.xml，notesMasterN.xml を除外したパーツごとの重み付けを行った場合での結果も比較する．

(N = 2, 3, . . .)．

6. 2. 1 比較対象: テキスト検索

上記のデータを用いて，実験は SOS，テキスト検索共に以下

この実験で行うテキスト検索の方法について説明する．

の手順で行った．

まず，テキスト検索エンジンにはオープンソースの全文検索（ 1 ） OOXML 文書群から検索クエリとなる文書 oq を選択

エンジン Apache Solr [13] を用いる．Apache Solr は文書を登し，それ以外の全ての文書を検索対象として類似度計算を行う．

録し検索クエリを POST するだけで簡単に全文検索ができる．

（ 2 ） 類似度によるランキングの上位 k 件までの結果から，文書の登録時には tokenizer によって単語単位に切り分けられる

実際の正解と照らし合わせて precision，recall を求める．

が，今回は tokenizer として text cjk を用いた．キーワード集（ 3 ） すべての文書が検索クエリとなるように手順 1, 2 を繰合から登録された文書のスコアを求める方法は，tf-idf [14], [15]り返し，precision, recall の平均値を求める．

をベースとしたものとなっている．

なお，SOS に関しては，OOXML 文書全体の類似度を求める

今回の実験では，検索対象となる OOXML 文書に含まれる

際に，パーツごとの類似度に重みを入れない場合と入れた場合

全 XML ファイルから開始タグ・終了タグを除去し，1 つのテでの実験も行った．重みのつけ方に関しては，同一グループとキストに統合したものを Apache Solr に登録している．文書同の類似度を異なるグループとの類似度で割った値をそれぞれの士の類似度の計算は，検索クエリとなる文書 oq 中の全 XML

パーツの重みとした。重みづけの最適化については今後の課題

ファイルから，タグを単語間の区切りとみなしてキーワードのである．

集合を抽出し，スコア付きのキーワード検索結果を取得する．

6. 2. 2 実験データ・実験手法
本実験に用いた docx, xlsx, pptx ファイルについて述べる．

•

6. 2. 3 実 験 結 果
docx, xlsx, pptx ごとの実験結果をそれぞれ図 8，図 9，図 10に示す．図中の default は SOS を OOXML 文書内の各パーツ

docx: Wordprocessing ML 用の実験データは，Web 上に重み付けをしない状態で用いた際の結果，weighting は SOS

で 250 個の拡張子.docx のファイルを収集した．正解情報は，を重み付け有りで用いた結果，text は 6. 2. 1 節のテキスト検文書全体のスタイル情報を基準にし，人手により 22 個のグルー索を用いた結果をそれぞれ表わしている．表 1 は 11 点補完平プに分類した．

均適合率，表 2 は precision と recall が最も接近した際の値で•

xlsx: Spreadsheet ML 用の実験データは Web 上で 108個の拡張子.xlsx のファイルを収集した．正解情報は，1 枚目のある．
まず，default(パーツ重み無し SOS) とテキスト検索との比SOS の default の結果を文書形式別に見ると，図 8，図 9 でdocx, xlsx に対しては高い適合率を示している．その一方，図10 で pptx に対しては適合率が低かった．図 10 の実験は 6. 1の実験と同じデータを用いており，しかも 6. 1 の方が今回の実験よりも高い値を示していることから，単体の XML ファイ
ル同士の類似度は精度がよいが，それらを集約してパーツやOOXML 文書全体の類似度を求める処理に工夫が必要である
ことを示している．

SOS に重み付けを行った際の結果 (weighting) については文
書形式ごとに異なる傾向を示した．各 precision-recall グラフ
が不自然な形をしているが，これは主に，同じ文書形式でも特定のパーツを持っている OOXML 文書と持っていない文書が存在すること，部分的な文書のグループの傾向が全体に強く反映されてしまったことの 2 つの理由による．文書形式ごとの傾向であるが，まず docx に関しては重み付け前と比較して，適
図 9 xlsx での precision-recall グラフ

合率が大幅に上昇している．xlsx については，今回試した重み付けでは適切ではなかったため，適合率が下がってしまった．

pptx については重み付けの結果 precision が大幅に上昇している．しかし，この値は 6. 1 の実験結果と比較するとまだ低く，
スライドごとにスタイルが変えられる pptx については，パーツ単位の重みづけではなく，個別のスライドのスタイル単位での重みづけ等の更なる改良が必要であることが分かった．
今回の実験では，パーツごとの重みを適切に設定できれば，類似検索の精度を改善できることが示された．ただし，実験
データごとに最適な重みは変化すると考えられるため，重みづけの最適化をどのように行うかについては今後の課題である．

7. まとめと今後の課題
本研究では，XML ファイル同士の類似度を計算するアルゴ
リズム LAX+と，それを利用して OOXML 文書の類似スタイル検索を行う手法 SOS を提案した．実験により，LAX を改良した手法である LAX+が，OOXML 文書を構成するパーツに

図 10 pptx での precision-recall グラフ

含まれている XML ファイルの類似度計算に対して有効である
表 1 11 点補完平均適合率

SOS (default) SOS (weighting)

ことを示した．また，SOS を用いて，複数の XML ファイルのtext

比較が必要な OOXML 文書の類似スタイル検索が行えること

docx

0.560

0.790

0.111

xlsx

0.822

0.689

0.298

も確認した．OOXML 文書のパーツに対する重み付けを工夫す

pptx

0.191

0.417

0.102

ることで，検索精度をより高めることができると分かった．
今後の課題として，まずパーツの重みの設定方法が必要だが，

表 2 precision-recall 最接近時の値

SOS (default)

SOS (weighting)precision recall precision

recall

現在の実験データのみでは各文書形式のパーツの傾向を読み取
text

るには文書数が少ない．よって実験データを増やし，各パーツ

precision recall

docx

0.479

0.492

0.776

0.762

0.088

0.087

xlsx

0.788

0.788

0.660

0.674

0.400

0.402

pptx

0.151

0.150

0.371

0.352

0.114

0.112

のスタイル類似検索における重要性を分析していく必要がある．
別の課題として，SOS，LAX+の処理を効率化するためにインデックスを活用することが挙げられる．また，OOXML 文書と並んでよく使用される Open Document 文書に，SOS, LAX+を適用することについても検討していきたい．

較であるが，この実験に関してはすべての文書形式で SOS がよ
い結果となった．xlsx に対してはテキスト検索も高い precisionを示したが，これは xlsx に用いられる SpreadSheet ML が他の文書形式に比べ構造化されており，さらにキーワードを抽出するパーツを持っているからであると考えられる．

謝辞 本研究の一部は日本学術振興会科学研究費補助金基盤
研究 A（#22240005）の助成により行われた．
文[1] ECMA-376 3rd edition,

献

[2]

[3]
[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]
[14]
[15]

http://www.ecma-international.org/publications/standards/Ecma-376.htm
Windows デスクトップサーチ,
http://www.microsoft.com/japan/windows/desktopsearch/default.mspx
Mac OS X Spotlight,
http://support.apple.com/kb/HT2531
Google インデックスに登録できるファイル形式,
http://support.google.com/webmasters/bin/answer.py?hl=ja&answer=35287
J.Tekli, R.Chbeir, K.Yetongnon, “An overview on XML
similarity: Background, current trends and future directions”, LE2I Laboratory UMR-CNRS, University of Bourgogne, 21078 Dijon Cedex, France Computer Science Review (2009).
K.C.TAI. “The Tree-toTree Correction Problem”, Journalof the Association for Computing Machinery Vol 26, No 3,
July 1979.
V.I.Levenshtein, “BINARY CODES CAPABLE OF CORRECTING DELETIONS, INSERTIONS,AND REVERSALS”, Presented by Academician P.S.Novikov January 4,1965) Translated from Doklady Akademii Nauk SSSR, Vol.
163,No.4,pp.845-848,August,1965. Original article submitted January 2,1965.
E.D.Demaine, S.Mozes, B.Rossman, and O.Weimann, “AnOptimal Decomposition Algorithm for Tree Edit Distance”,
ACM Trans. Algorithms, 6(1) : Article 2, 2009.
D.Buttler, “A Short Survey of Doucment Structure Similarity Algorithms”, In Proceedings of the 5th International
Conference on internal Computing,USA, pp.3-9, 2004.
S.Helmer, “Measuring the Structural Similarity of Semistructured Documents Using Entropy”, In Proceedings of the
VLDB 07Conference, pp.0122-1032, 2007.
W.Liang and H.Yokota, “LAX: An Eﬃcient Approximate
XML Join Based on Clustered Leaf Nodes for XML Data
Integration”, In Proceedings of BNCOD 05, Springer LNCS
3567, pp82-97, 2005
W.Viyanon, S.K.Madria, S.S.Bhowmick, “XML data integration based on content and structure similarity usingkeys”, Proceedings of the OTM 2008 Confederated International Conferences, CoopIS, DOA, GADA, IS, andODBASE 2008. Part I on On the Move to Meaningful Internet Systems:(pp. 484-493)
Apache Solar,
http://lucene.apache.org/solr/
G.Salton and M.J.Mcgill, “Introduction to Modern Information Retrieval”, McGraw- Hill, Tokio, 1983.
G. Salton and C. Buckley “Term-Weighting Approaches
in automatic Text Retrieval”, Information Processing andManagement:an International Journal, 24(5), pp.513-523,
1988.