DEIM Forum 2015 B5-4

SIGURE Hash: 数式検索のための高速な類似検索アルゴリズム
大橋 駿介†

相澤 彰子††,†† 東京大学大学院 情報理工学系研究科 〒 113–8656 東京都文京区本郷 7–3–1†† 国立情報学研究所 〒 101–8430 東京都千代田区一ツ橋 2–1–2
E-mail: †{sohashi,aizawa}@nii.ac.jp
あらまし

数式は科学技術を厳密に記述する言語として幅広く用いられている。数式は一般的に木構造に変換可能な

MathML や LATEX といった形式で記述されているが、このような数式データに対する情報検索技術は十分とはいえない。例えば、a2 + b2 = c2 と x2 + y 2 = z 2 のように同義ではあるが表記が異なる数式が存在するが、これは例えば一般的な木構造類似検索アルゴリズムでは検索できない。そこで、本研究においては数式の変数名の書き換えに対して不変な類似度計算アルゴリズムを開発し、このような表記の異なる数式を検索できるようにした。また、このアルゴ
リズムは入力の大きさに対してほとんど線形時間で動作するため、高いスケーラビリティを持つ。大規模な数式デー
タセットを用いた実験により、我々のアルゴリズムが既存の木構造類似検索アルゴリズムである pq-gram と比較して高速に索引を作成でき、検索結果の精度も向上していることが示された。
キーワード

数式検索，類似検索，MathML

1. は じ め にれは LaTeXML （注 1） を用いて数式を記述する XML の一種である MathML （注 2） に自動的に変換することができる。XML

数式は科学技術のコミュニケーションにおいて幅広く用いらを木構造とみなして類似検索を行う手法をいくつか紹介する。

れている記述言語である。数式は例えば論文や研究報告の形でTree Edit Distance (TED) [7] は文字列の編集距離を拡張した専門家同士の相互理解に用いられるばかりでなく、数学や理科ものであり、ある木から頂点の挿入・削除もしくは頂点のラベの教科書といった形で教育においても必要不可欠な存在となっ

ルの書き換えの 3 種類の操作をできるだけ少ない回数行って別ている。近年の情報化の進展により数式の情報も増大しており、に木に書き換えたときの操作回数を 2 つの木の距離とするもの

大量の数式から目的の情報をすばやく取り出す数式検索の技術である。ところが、TED の時間計算量は現在知られている最は専門家・非専門家を問わず大きな需要がある。しかしその一も高速なものでも木の頂点数を n として O(n3 ) [4] と次数が大方で、現在よく用いられている Web 検索エンジンは自然言語

きく、大きな木に対して何回も計算する必要がある XML 類似で記述された文書を主な対象として実装されており、記号列で検索にそのまま適用するのは難しい。pq-gram [2] は、編集操

ある数式をうまく検索することはできない。木構造類似検索や作にある重みを付けたときの TED の下限という形で TED へ

それを用いた XML 文書検索の研究も進められており、これをの近似を与える類似度計算アルゴリズムである。いったん木を

数式記述のための XML である MathML に適用するという方

特徴集合に変換してから集合の類似度を元の木の類似度とする法も考えられるが、数式そのものが持つ性質は考慮されないた手法であり、特徴集合への変換と集合の類似度計算がそれぞれめ検索の精度には問題が残る。例えば、コーシー・シュワルツ

O(n), O(n log n) 時間で可能である。MinHash [3] は集合の類の不等式 |u · v| <= ||u||||v|| に登場する変数 u, v は名前を自由似度として用いられるジャカード係数の計算を高速化する手法に書き換えてもその数学的な本質は変化しない。ところが既存である。pq-gram と MinHash を組み合わせて XML 検索に応の木構造類似検索はラベルの変化に対して鋭敏であり、変数名

用した研究 [8] も存在する。これらの木構造類似検索アルゴリ

が書き換わるとうまく検索することはできない。このような現ズムを用いることで構造の類似性を踏まえた XML 類似検索が状を踏まえ、本研究では数式の変数名の書き換えを考慮した類可能であるが、構造や表記には直接反映されない数式の意味的

似度計算アルゴリズムを提案し、これを実際に実装して大規模な類似性を捉えることは難しい。

なデータセットを用いた実験を通じて評価した。

2. 2 数 式 検 索

以下、本稿では 2. 節で関連研究を紹介し、3. 節で変数名の書

Kamali ら [5] は数式検索の手法を分類し、それらを実験にき換えを考慮した数式の類似度計算アルゴリズムを提案する。

より比較した。これによると、主な手法を分類すると、クエリ

4. 節で既存の木構造類似検索アルゴリズムと比較して提案手法と完全に一致するものを取り出す完全マッチングと多少の表記を評価する。5. 節で結論を述べる。

2. 関 連 研 究ゆれなどを許す類似マッチングの 2 つに大きく分けられ、類似
マッチングについてはさらに共有する部分構造の多さを類似度

2. 1 XML 検索（注 1）：http://dlmf.nist.gov/LaTeXML/

数式データは多くの場合 LATEX 形式で記録されているが、こ（注 2）：http://www.w3.org/Math/とする部分構造マッチングとクエリにワイルドカードなどを許F, m, a はそれぞれ力、質量、加速度を表現していると解釈さしたパターンマッチングに分類できる。厳密マッチングは正確れる。このような数式においては変数名を書き換えると意味がだが取り出せる式の数が非常に少ない。類似マッチングの 2 つ

大きく変わる。例えば V = RI は F, m, a をそれぞれ V, R, Iの比較ではパターンマッチングは部分構造マッチングに比べてに書き換えただけであるが、一般的にはそれぞれ電圧、電気抵

ややよい精度を示したが、パターンマッチングのためのクエリ

抗、電流を表していると解釈される。このような数式に対してをユーザーが構成するのは手間がかかるとし、一般的なケース

は変数名が書き換わると類似度が低下するような類似尺度が望では部分構造マッチングによる手法がもっともよいと報告されましい。一方で、1. 節でも挙げたコーシー・シュワルツの不等ている。本稿で提案する手法は部分構造マッチングに基づいて

式は変数名を書き換えても定理が表す内容は不変である。例えいるが、マッチングの際に適切に変数を考慮する点でパターン

ば |x · y| <= ||x||||y|| と書いても同じことである。これは元の定マッチングの要素を取り入れている。大橋ら [9] は数式の意味

理が変数の間に成り立つ関係を表現しているからである。このを反映した検索法を提案した。数式処理システム Mathematica

ような数式に対しては変数名を書き換えても類似度が変わらなを用いて検索対象の数式に予め生成しておいた乱数を代入する

いような類似尺度が望ましい。本研究で提案する手法においてことで確率的に同値性を判定し、表記が異なるが同値な数式をは、それぞれの種類の変数に対応する類似尺度を提案し、これ検索できるようにしたが、検索の対象が数値を代入できるようをともに用いることで両方の数式を検索できるようにした。

な式に限られたり、そもそも Mathematica で処理できない数

3. 3 概観式が存在するなどの問題があった。本稿では変数名を正規化し数式検索システム全体の構成を説明する。数式検索システムてからハッシュすることで変数名について表記が異なる数式がは MathML を木に変換する第 1 段階、木を特徴集合に変換す検索可能でありつつ、入力の数式を一般の XML パーサを用いる第 2 段階、特徴集合の大きさを削減する第 3 段階の 3 つのて処理することで MathML で記述されたすべての数式を処理部分からなる。第 1 段階では一般的に使用される XML パー

できるようにした。また、数学検索システムの性能比較のためサーによって MathML をパースして木に変換する。第 2 段階に NTCIR-11 Math task [1] において、評価用データセットがでは、3. 2 で説明した 2 種類の変数の性質それぞれに対応する構築されている。この評価用データセットを用いた参加システ

特徴集合の生成を行う 2 種類のアルゴリズムを用いる。1 つめ

ム同士の比較によると、変数名を考慮した検索をするシステムの Subtree Hash は入力の木の部分木をハッシュした整数の集がより高い精度を達成した。本稿では提案手法の評価に際して合を生成する。この集合が Subtree Hash で生成された他の集

NTCIR11 Math task のデータセットを使用した。

合と多くの共通要素を持てば、それらのもととなった木は多く

3. 提 案 手 法
3. 1 定義の共通する部分構造を持つことを意味し、木としての類似尺度となる。2 つめの SIGURE Hash（注 3） は Subtree Hash と類似した処理を行うが、取り出された部分木はハッシュされる前に手法の説明に必要な定義を述べる。数式検索問題は与えられ

変数名を正規化する。これによって Subtree Hash と同様に木た数式を含む文書集合 (データセット) から、数式として与えらの部分構造を取り出しつつ、変数名の書き換えに対して不変なれるクエリとの関連度が高いものから順に並べたリストを返す

類似尺度となる。この 2 つのアルゴリズムの出力集合の和集合

ものである。本研究で提案する手法において、あとで説明するをとって第 2 段階の出力とする。数式同士の類似度は、入力の通りデータセットやクエリの数式は XML パーサによってまず数式をこの特徴集合に変換したあとで式 1 によって定まるジャ

根・順序・ラベル付き木、すなわち木の頂点には根と呼ばれる

カード係数によって計算する。

頂点を基準とした子孫・先祖関係があり、ある頂点に付いている子には左から右といった順序があり、各頂点には文字列が付いているもの、に変換される。以下、本稿で単に木といった場
合には根・順序・ラベル付き木であるとする。数式を MathMLで表現する時、もとの数式の演算子・変数・定数の識別子はそれぞれ異なるタグ付けがされる。Presentation MathML ではそれぞれ mo, mi, mn タグが、Content MathML では csymbol,

ci, cn タグが用いられる。したがって、あるノードのラベルが変数名であるかどうかはその親ノードのラベル (タグ名) が何であるかを見ればわかる。本稿では親ノードのラベルが ci, miであるノードを変数ノードと呼ぶこととする。

3. 2 変数の性質
数式の変数をそれが表す意味という観点から 2 つの性質を持つことを説明する。変数名には名前それ自身に意味がある場合とそうでない場合がある。たとえば、単に n といった場合には一般に自然数が想定されるし、F = ma といった場合にはJaccard(A, B) =|A ∩ B||A ∪ B|(1)

第 3 段階では、ジャカード係数を効率的に計算するための前処理として MinHash [3] を用いる。MinHash は乱択アルゴ
リズムの一種であり、元の集合の要素に乱択されたハッシュ関数を適用しその最小値を返すものである。この操作により、MinHash が衝突する確率はもとの集合でのジャカード係数と一致するようになる。したがって、十分な数の MinHash 関数を用意することで高い精度でもとのジャカード係数を推定することができる。提案手法では前処理として MinHash 関数を

n 個乱択し、それぞれの関数に対してデータセット中の数式のハッシュ値を転置インデックスに保存した。
ユーザーからクエリが与えられた時には、クエリにも 3 段階の処理を適用し、この転置インデックスを参照してデータセッ（注 3）：日本語の時雨と同じように発音する。

ト中の数式とクエリの類似度を推定し、類似度の高いものから

Algorithm 1 SubtreeHash(n)順に出力とする。この時の計算時間は転置インデックスで参照

Require: n : root node of the tree

した数式の個数に比例するため、検索結果リストにおける類似

1: function SubtreeHash(n)度の総和に比例する。

2:C ← {c | c is child of n}3:a ← hash(label(n))

4:

if |C| = 0 then

図 1 提案手法の全体図

5:6:return (a, {a})
else

7:

X ← newV ector()8:

H ← {}

9:for c in C do

10:

(xsub , Hsub ) ← SubtreeHash(c)11:X.append(xsub )H ← H ∪ Hsub

12:
13:

end for14:x ← RollingHash(a, X)

15:
16:

return (x, H ∪ {x})end if

17: end function

18: function RollingHash(a, array)

3. 4 Subtree Hash

19:

x←0

Subtree Hash は入力の木の部分木を表す整数の集合を特徴

20:

for h in array do

集合として返す関数である。擬似コード 1 にアルゴリズムの擬21:

似コードを示した。関数の引数 n は特徴集合を求めたい木の22:

end for23:

return x

根ノードである。この擬似コードでは再帰を実装する都合によx ← x∗a+h

24: end function

り、関数は特徴集合だけでなく与えたノードを根とする部分木を表す整数も組み合わせたタプルを返している。従って、引数のノードを根とする部分木に対応する整数をどのように求めるかは返り値の第 1 要素の動きを追うことで理解できる。子ノー
ドがない場合はそのノードのラベルにハッシュ (文字列のハッシュならば何でもよい) を適用した値をその部分木に対応する整数とする (2 行目から 6 行目)。子ノードがある場合は、まずそれらの子ノードに対して再帰的に処理を実行し、それぞれを根とする部分木を表す整数を求める (10 行目)。これを子の順序に従って整数列 X とし、これに対してローリングハッシュ [6]を適用する。ハッシュに用いる定数は現在のノードのラベルから決定する (3 行目の a を用いる)。関数全体として木全体の特徴集合を返すために、再帰的処理の結果もマージしている (擬似コード中の H)。
この関数の時間計算量は、入力の木のノードを n として O(n)である。木の各ノードに対して関数 SubtreeHash はちょうど1 回呼び出され、また関数 RollingHash において array の要
素として各部分木が登場するのもたかだか 1 回であるからである。

3. 5 SIGURE Hash3. 5. 1 naive SIGURE Hash
Structure Information Greedy Unification REcursive (SIGURE) Hash は Subtree Hash と同様に部分木の集合を取り出
すが、取り出したあとで部分木に登場する整数を正規化する点が他と異なる。Subtree Hash は部分木を取り出してその集合の類似度を比較することと同等であるが、変数名が異なるものの数学的に同値な数式に対しては異なる特徴集合を得るため検索結果に現れることはない。このような問題に対し変数名を正規化する手法が考えられるが、1 つの数式に対して正規化を 1
回しか行わないと図 3. 5. 1 のように部分木だけで見ると同値であるが全体で見た時とは変数の出現順が異なるために書き換え
結果がクエリと異なり検索できないことがある。そこで、各部
分木をあらわす整数を求めるときに、その部分木のスコープを考慮して変数名を書き換えるようにすることでこの問題を回避する事を考える。naive SIGURE Hash はこれを実現するハッシュ関数である。擬似コード 2 にアルゴリズムを示す。
図2

単純な変数書き換えで生じうる問題の例

基本的な処理の流れは Subtree Hash に類似しているが、引の計算結果を再利用できなかったのは子ノードでの変数出現順

数に変数名書換の結果を表す連想配列 V が追加されている。

がそのままには利用できないからである。例えば、図 3. 5. 1 で

これが空の状態で各ノードを根としたときの部分木を表す整の右側の f のノードが根ノードならばそれらの子ノードの変数数を求めるのが N SHrec 関数である (4 行目から 7 行目)。

は図に示された 2, 3 ではなく 1, 2 と書き換えられ、これに基づ

N SHrec を再帰的に呼び出すことで木を pre-order で走査しいて計算されたハッシュ値は再利用できない。そこで、子ノー(23 行目から 28 行目)、V に現れない変数名が登場するたびにドでの結果を再利用するために根ノードによって変化する各変新しい変数名をそれに追加して正規化の結果を V に保存する数に割り当てられるハッシュ値を変数のまま残し、各ノードで(12 行目から 14 行目)。そのノードが変数ノードであるかどうの計算結果のハッシュ値は多項式として保持するようにしたのかは isV ariableN ode 関数で検査している (11 行目) 。

が以下に説明する SIGURE Hash である。

関数 N SHrec の時間計算量は O(n) である。再帰によって各ノードを巡回し、各ノードでならし O(1) 時間 ( RolingHash

擬似コードをアルゴリズム 3,4 に、木が与えられたときの計算例を図 3. 5. 2 に示した。

関数の処理に最悪 O(n) 時間かかるが、引数 X の長さの総和はノード数に一致するのでならし計算量では定数時間となる) でハッシュ値を計算しているからである。従って、関数

N aiveSIGU REHash 関数の時間計算量は O(n2 ) である。
Algorithm 2 NaiveSIGUREHash(n)Require: n : root node of the tree

Algorithm 3 SIGUREHash(n)Require: n : root node of the tree
1: function SIGUREHash(n)2:(X, V, H) ← SHrec(n)3:return H

4: end function
5: function SHrec(n)1: function NaiveSIGUREHash(n)6:H ← {}

V ← newHashM ap()2:

7:

S ← {s | s is a descendant of n}

Xv ← newHashM ap()3:

8:

if isV ariableN ode(n) then4:for s in S do

9:

V [label(n)] ← length(V )5:(x, V ) ← N SHrec(n, newHashM ap())

10:

H ← H ∪ {x}Xv [label(n)] ← 1

6:

11:

X ← (Xv , 0)

7:

end for8:

return H

12:
13:

9: end function
10: function NSHrec(n, V )11:12:

if isV ariableN ode(n) thenif label(n) not in key(V ) thenV [label(n)] ← hash(length(V ))

13:
14:

end if15:

return (V [label(n)], V )return (X, V, {Eval(X, V )})end if14:

C ← {c | c is child of n}15:a ← hash(label(n))

16:

if |C| = 0 then17:

X ← (Xv , a)

18:
19:

return (X, V, {Eval(X, V )})
else

20:

X ← (Xv , 0)21:

C ← {c | c is child of n}

H ← {}

22:a ← hash(label(n))

for c in C do

18:

23:

19:

if |C| = 0 then(Xsub , V, Hsub ) ← SHrec(c)24:X ← M erge(X, V, Xsub , Vsub , a)16:

end if

17:

20:
21:

return (a, V )

26:

22:

X ← newV ector()

23:

for c in C do

27:

▷ Traverse from left child.

24:(xsub , V ) ← N SHrec(c, V )25:

X.append(xsub )26:

end for27:

x ← RollingHash(a, X)

28:
29:

H ← H ∪ Hsub

25:

else

return (x, V )end if

30: end function

28:▷ Traverse from left child.

end forreturn (X, V, H ∪ {Eval(X, V )})end if

29: end function

このアルゴリズムでは、各部分木の計算結果を整数ではなく登場する変数とその順序 V とその変数からなる多項式の係数

X に分離することで結果を再利用できるようにしている。Xはさらに係数部分の Xv と定数項 c に分かれる。 X と V の組が決まるとその部分木に対応する値が決まるようになってお3. 5. 2 SIGURE Hash

り、これは Eval 関数で計算する。木を巡回した時に現在見てNaive SIGURE Hash によって、適切な正規化を考慮した特いるノードと子ノードの X, V を結合する処理は M erge 関

徴集合を生成することが可能となったが、Subtree Hash より数で行われている。M erge 関数はローリングハッシュの 1 ス

も計算量が悪化しており、大規模なデータに対して適用するにテップを X, V の組に対して行う関数である。X は多項式のは不適である。ところで、Naive SIGURE Hash が子ノードで係数として計算すればよく、V は Vsub にのみ登場する変数を

Algorithm 4 Auxiliary function used in SIGUREHash

図 3 SIGURE Hash の計算例

1: function Eval(X, V )2:(Xv , c) ← X

3:

h←c

4:

for v in key(V ) doh ← h + Xv [v] ∗ hash(V [v])5:
6:

end for7:

return h

8: end function
9: function Merge(X, V, Xsub , Vsub , a)10:

Xv,ret ← newHashM ap()

11:

Vret ← newHashM ap()

12:

Xv , c ← X

13:Xv,sub , csub ← Xsubfor v in key(V ) do ▷ Traverse from the key which has the14:

smallest value.
15:
16:

Vret [v] ← length(Vret )理全体として O(nk) となる。実用上 k は n に対して十分小さ

Xv,ret [v] ← Xv [v] ∗ a

いので、このアルゴリズムは実データに対してほぼ線形時間で17:

end for18:

for v in key(Vsub ) do ▷ Traverse from the key which has
the smallest value.

19:

if v not in key(V ) then20:

Vret [v] ← length(Vret )21:

Xret [v] ← 0

動作する。

4. 実

験

4. 1 実 験 内 容
提案手法の有効性を確かめるために、NTCIR11-Math2 [1]22:

end ifで用いられた数式検索用のデータセットを用いて実際に提案手

23:

Xret [v] ← Xret [v] + Xsub [v]法を実装し、索引付け時間と検索精度の観点で既存の木構造

24:

end for

類似検索と比較した。検索精度の基準としては、出力リストの25:

cret ← c ∗ a + csub

上位 10 個以内に関連する文書が含まれる割合である P@10 と26:

return ((Xv,ret , cret ), Vret )27: end function

それぞれの関連文書がリストに登場した位置での適合率の平均である MAP (Mean Average Precision) を用いた。また、

Subtree Hash と SIGURE Hash が実際に異なる種類の類似性
V の後ろに追加すれば pre-order での順序が保たれる。このを捉えていることを確かめるため、これらを単独で用いた際の時、V の計算においてそれぞれの係数に掛かる数字は定数 a し

検索結果を比較した。

かないので V に 2 次以上の項が含まれることはない。ゆえに

4. 2 実験データ・実装|V | = |X| が常に成り立つ。呼び出し元にはこれらの再利用に実験においては、NTCIR11-Math2 データセットを用いた。

必要な X, V を返しつつ、 Eval(X, V ) の結果を H に加えて

これは数式検索システムの評価を目的としたデータセットであ特徴集合を作っていく (27 行目)。

り、約 10 万の論文を約 830 万の検索単位に分割したものであ

具体的な入力例を用いて動作を説明する。例えば、入力の式

る。データサイズは約 180GB であり、約 6000 万個の数式が含が g(f (x, y), f (y, z)) であったとしよう。この式は図 3. 5. 2 にまれる。また、このデータセットに対する 50 の検索クエリと示されるような木に変換されたとする。それぞれの葉ノード

一部の検索単位に対するクエリへの関連度も含まれる。

はアルゴリズム 3 の 8 行目から 12 行目までの処理によりそ

実験では、提案手法である Subtree Hash と SIGURE Hashの変数のみが 1 番目に登場したいう情報 (env) と、部分木をを統合したものの他に、Subtree Hash 単独, SIGURE Hash

表す整数はその変数のハッシュ値そのものになるという情報

単独をそれぞれ用いるもの、そして既存手法として pq-gram(value) が求められる。左側の f のノードは子ノードの結果との 4 通りの類似検索手法を実装して比較した。pq-gram のパ

M erge 関数を用いることで自身の結果を求める。図の例ではラメータには、[2] を参考に p = q = 3 を用いた。XML パー

hash(f ) = 3 であったとしており、これによって、value にはサ、MinHash の部分については 4 手法で共通のものを用い、

32 (x) + 31 (y) となっている。右側の f のノードでも同様にし

MinHash 関数の個数は 30 個とした。また、大きなデータセッて value は 32 (y) + 31 (1) となる。そして根の g のノードでトに対応するため、これを分割してそれぞれに対して担当のプは、hash(g) = 4 として value は 42 (9x + 3y) + 41 (9y + 3z) とロセスを割り当てることによる並列化を実装した。

なる。
このアルゴリズムの時間計算量は O(nk) である。Eval,

実験環境は Intel Xeon E7-4870 @ 2.40GHz * 4, 1TB RAM,

Python 2.7 を使用し、32 プロセスで並列化した。

M erge 関数はともに各ノードにつき 1 回呼び出され、これら

4. 3 処 理 時 間の計算量はともにループに着目して最悪 O(k) であるから、処表 4. 3 に処理時間を示した。pq-gram はノード数 n の木に

表1
クエリ

f (z) = z d + c|u · v| <= ||u||||v||||x + y||p <= ||x||p + ||y||pE(λ) = −m2dyn (λ)
SEH = G1 od3 x√

3−g (3)A = U SV T

表2
類似尺度

クエリごとの比較

クエリのキーワード

Subtree

SIGURE

Mandelbrot, dynamical plane

0.07450.1492

Cauchy Schwarz

0.00190.0572

minkowski inequality

0.02150.0748

Electron Energy, Quantum Dynamics, NJL 0.2539

0.0250entropy, bound, Bekenstein-Hawking

0.22220.0054

singular value decomposition, matrix

0.21670.0277

処理時間の比較

2 つの変数の関係が意味の中心となっている。一方、Subtree

索引作成 [秒] 平均クエリ処理時間 [秒]Subtree

18865

5.69

SIGURE

20854

10.29

Subtree + SIGURE

21854

8.07

pq-gram

112388

3.68

Hash が優位な 3 つはいずれも変数名そのものに意味が含まれている。物理学に由来する 2 つの数式はそれぞれの変数が物理量に対応しているし、特異値分解についても同一の変数が複数回登場することはなく、その関係性というよりは相異なる行列
によって分解することに意味があるような式である。以上で確対して線形時間で動作し (p + q)n 個の要素を持つ特徴集合を生成するのに対して、Subtree, SIGURE Hash はともに n 個の要素を持つ特徴集合を生成する。本実験では p = q = 3 に設定しているためちょうどその要素数に 6 倍の差があり、それがそのまま索引作成時間に反映されている。クエリ処理時間については、転置インデックスを採用しているため数式の平均類似度が高ければ処理時間が長くなる傾向がある。たとえば SIGURE

Hash では変数 1 個を含む部分木はクエリを含むほとんどの数
式に含まれているので、これに対する転置インデックスの参照などに長時間を要した。

認したように、Subtree Hash と SIGURE Hash はそれぞれ、
変数名そのものが重要である数式と変数の関係性が重要である
数式をそれぞれ検索することができていた。

5. 結

論

数式には同義ではあるが表記が異なるものが存在し、これが一般的な木構造類似検索手法を数式検索に適用することを難しくしていた。本研究で新しく開発した SIGURE Hash アルゴ
リズムはこの問題を解決するとともにほとんど線形の時間計算量も併せ持つことで高速な処理時間を実現することを可能にした。また、このアルゴリズムを並列化した上で実装し、実際に4. 4 検 索 精 度

大規模な数式検索データセットを用いて実験することにより、
表3

既存の木構造類似検索アルゴリズムよりも高い精度かつ短い前

検索精度の比較

類似尺度

P@10

Subtree0.0700 0.0461

SIGURE

0.0700 0.0288

MAP

Subtree + SIGURE 0.0820 0.0637
pq-gram

0.0420 0.0446

処理時間で検索を行えることを確かめた。
今後の課題としては、提案手法はハッシュ関数であるため衝突の可能性などがあるが、これに関する理論的な評価を与える
ことが挙げられる。

6. 謝
表 4. 4 に検索精度を示した。P@10, MAP いずれの基準においても提案手法が pq-gram を上回っている。Subtree Hash,

辞本研究の一部は JSPS 科研費 2430062, 25245084 助成を受けた。

SIGURE Hash それぞれの精度は MAP で pq-gram 以下か同程度であるが、これらを結合するとより高い精度が達成されており、これらの手法がそれぞれ異なる数式を検索していることを示している。NTCIR11-Math task [1] に参加した他のシス
テムと比較すると、クエリとして与えられる数式とキーワードを共に活用したものには劣るが、数式だけを用いたものとほぼ同等の精度を達成している。

4. 5 クエリ特性
Subtree Hash と SIGURE Hash で特に MAP の差が大き
いクエリについて、それぞれが優位なものを 3 つずつ、クエ
リとその精度を表 4. 2 示す。キーワードは数式を表す英語のフレーズである。SIGURE Hash が優位な 3 つは数式中の変数の関係がその数式の意味の中心に据えられているという特徴がある。例えばマンデルブロ集合を記述する漸化式では数列の項の関係が意味の中心であるし、残りの 2 つの不等式も比較される

文

献[1] Akiko Aizawa, Michael Kohlhase, Iadh Ounis, and Moritz
Schubotz. Ntcir-11 math-2 task overview. In Proceedings of
NTCIR-11 Math-2 task Workshop Meeting [1], 2014.
[2] Nikolaus Augsten, Michael Böhlen, and Johann Gamper.
The pq-gram distance between ordered labeled trees. ACM
Transactions on Database Systems (TODS), 35(1):4, 2010.
[3] Andrei Z Broder. On the resemblance and containment of
documents. In Compression and Complexity of Sequences
1997. Proceedings, pages 21–29. IEEE, 1997.
[4] Erik D Demaine, Shay Mozes, Benjamin Rossman, andOren Weimann. An optimal decomposition algorithm fortree edit distance.
ACM Transactions on Algorithms(TALG), 6(1):2, 2009.
[5] Shahab Kamali and Frank Wm Tompa. Retrieving documents with mathematical content. In Proceedings of the36th international ACM SIGIR conference on Research and

[6]

[7]
[8]

[9]

development in information retrieval, pages 353–362. ACM,
2013.
Richard M Karp and Michael O Rabin. Eﬃcient randomized pattern-matching algorithms. IBM Journal of Researchand Development, 31(2):249–260, 1987.
Kuo-Chung Tai. The tree-to-tree correction problem. Journal of the ACM (JACM), 26(3):422–433, 1979.
Peisen Yuan, Chaofeng Sha, Xiaoling Wang, Bin Yang, Aoying Zhou, and Su Yang. Xml structural similarity searchusing mapreduce. In Web-Age Information Management,
pages 169–181. Springer, 2010.
大橋駿介, 高須淳宏, and 相澤彰子. 表記が異なる同義の数式の高速な検索法. 第 6 回データ工学と情報マネジメントに関するフォーラム (DEIM2014), 2014.