こんにちは、LegalOn Technologiesでエンジニアをしている神田（@kampersanda）です。

本記事では、Jaccard係数に基づく類似文書検索の高速化技法を解説し、契約書検索での実験結果を報告します。

背景と目的

共起に基づく類似文書検索の必要性

契約書検索において、クエリとして与えられた契約書本文から、それに類似する内容の契約書を見つけ出すDocument-to-Documentな検索は重要なタスクの一つです。これを類似文書検索と呼びます。

類似文書検索にもいくつかのアプローチが存在します。最近では、BERTなどから計算された文ベクトルを使って文脈や意図を解釈しつつ、意味的に似ている文書を検索するセマンティック検索の話題が多いように思います。契約書検索においてもセマンティック検索は重要です。

その一方で、単純に本文が文字列として似ている契約書を検索したい場合もあります。例えば、以下のような場面が考えられます。

同じひな形から派生した契約書の検索

契約書はひな形をベースに作成されることが大半です。同じひな形から派生した契約書は、一部の条文や当事者情報のみが書き換わり、大半の文字列は一致していることが多いです。
同じ編集履歴に属する契約書の検索

契約書は自社と相手方の審査を経て作成されます。その過程で、いくつかの編集バージョンが作成されますが、それらは大きく書き換わることは少なく、大半の文字列は一致していることが多いです。

このような検索では、本文中に出現するトークン（単語やN-gram）がどれくらい一致するかという、単純な指標が十分に機能します。このような検索を共起に基づく類似文書検索と呼びます。

契約書検索での注意点

共起に基づく類似文書検索をする場合、本文に現れるトークン数の多さには注意が必要です。共起尺度の計算時間は文書に含まれるトークンの種類数に依存し、トークン数が多い文書同士の比較には多くの時間を要します。

契約書の本文は複数の条文から構成され、長文であることが多いです。本実験で使用した日本語契約書データでは、本文当たり平均500種類程度の単語が含まれていました。このような長文データを扱う場合、素朴に共起尺度を計算するのは避け、高速化に努める必要があります。

本記事の目的

有名な共起尺度の一つにJaccard係数があります。Jaccard係数を使った検索の効率化は伝統的に研究されており、厳密解法、近似解法ともに多くの手法が存在します。

本記事は厳密解法に着目し、比較的アイデアのシンプルないくつかの高速化技法を解説します。データベースが小さい場合のための線形探索による解法と、大きい場合のための転置索引を使った解法を紹介します。また、契約書データを使った実験結果を報告し、契約書のような長文データでの効果を示します。

なお、本記事では近似解法については取り扱いません。MinHashなどの近似解法については岡野原さんの記事が参考になります。

準備

表記

ある有限集合 $U$ を全体集合として、その部分集合 $x \subseteq U$ を入力として考えます。集合 $x$ について、その要素数を $|x|$ と表記します。この要素数は集合の長さとも言い換えられます。

全体集合 $U$ はその要素について順序を持ち、集合の要素は一意に整列することができます。その順序に基づいて、要素 $a \in U$ が要素 $b \in U$ より小さいとき、 $a \prec b$ と表記します。等しいまたは小さいときは、 $a \preceq b$ と表記します。

集合の要素はこの順序で整列されているものとし、 $i$ 番目から $j$ 番目までの部分集合を $x[i..j$ ] と表記します（ $1 \leq i \leq j \leq |x|$ ）。 $x[1..i$ ] を $x$ の接頭辞、 $x[j..|x|$ ] を $x$ の接尾辞と言います。

Jaccard係数

集合 $x,y$ について、そのJaccard係数を $J(x,y)$ と表記します。

$\displaystyle J(x,y) = \frac{|x \cap y|}{|x \cup y|} = \frac{|x \cap y|}{|x|+|y|-|x \cap y|}$

簡単のため、 $x \cup y = \emptyset$ な入力は想定しません。

Overlap係数との関係

集合 $x,y$ のOverlap係数 $O(x,y)$ を導入します。

$\displaystyle O(x,y) = |x \cap y|$

このとき、ある閾値 $0 \lt t \leq 1$ について以下が成立します。

【定理】Jaccard係数とOverlap係数の関係

$\displaystyle J(x,y) \geq t \Longleftrightarrow O(x,y) \geq \frac{t}{1+t} (|x|+|y|)$

【証明】

$\displaystyle \begin{aligned} J(x,y) =\frac{O(x,y)}{|x|+|y|-O(x,y)} \geq t &\Longleftrightarrow O(x,y) \geq t(|x|+|y|-O(x,y)) \\ &\Longleftrightarrow (1+t)O(x,y) \geq t(|x|+|y|) \\ &\Longleftrightarrow O(x,y) \geq \frac{t}{1+t}(|x|+|y|) \end{aligned}$

Overlap係数は値が整数に限定され取り扱いが簡単です。そのため、 $J(x,y) \geq t$ の代わりに以下を高速化技法の導出に利用する場合もあります。

$\displaystyle O(x,y) \geq T := \left\lceil \frac{t}{1+t} (|x|+|y|) \right\rceil$

問題設定

契約書の本文に現れるトークンの集合をドキュメントと表記します。本記事では、以下のような検索問題を考えます。

入力
- ドキュメントデータベース: $D = \{ d_1, d_2, \dots, d_n \}$
- クエリドキュメント: $q$
- 閾値: $t \in (0,1$ ]
出力
- 類似ドキュメントのID集合: $R=\{ i \mid d_i \in D, J(d_i,q) \geq t \}$

線形探索による解法

顧客に依存しますが、契約書データベースの規模は数千や数万と大規模でないことも多いです。そこで、以下のような単純な線形探索による解法を考えます。

from collections.abc import Iterator

def jaccard(x: set[int], y: set[int]) -> float:
    intersection = len(x & y)
    union = len(x) + len(y) - intersection  # len(x | y)
    return intersection / union

def linear_search(
    database: list[set[int]], query: set[int], threshold: float
) -> Iterator[int]:
    for doc_id, base in enumerate(database):
        if jaccard(base, query) >= threshold:
            yield doc_id

データベースはあまり大きくない想定なので、ここでの関心はJaccard係数の計算時間です。Jaccard係数は集合の共通要素数を数え上げれば計算できるので、計算時間は要素数、つまりドキュメントのトークン数に線形です。契約書に含まれるトークン数は多いので、Jaccard係数の計算がボトルネックとなり得ます。

高速化の方針

Jaccard係数を計算しなくても、その値が閾値未満かを判断できる場合があります。極端な例ですが、len(x)=100, len(y)=1 のとき、その長さから jaccard(x,y) > 0.99 で無いことは明らかでしょう。

このようなアイデアに基づいて、Jaccard係数を計算しなくても解では無いと判断してよい条件（フィルタリング条件）がいくつか設計されています。本記事では、以下の２つのフィルタリング条件を紹介します。

Length Filtering [Bayardo et al. WWW 2007]
Position Filtering [Xiao et al. TODS 2011]

Length Filtering

集合 $x,y$ が類似するとき、その長さも近いだろうというアイデアに基づきます。

【定理】Length Filtering Principle

$\displaystyle J(x,y) \geq t \Longrightarrow t \cdot |y| \leq |x| \leq \frac{|y|}{t}$

【下限の証明】

$\displaystyle \begin{align*} t \leq \frac{|x \cap y|}{|x \cup y|} &\Longleftrightarrow t \cdot |y| \leq \frac{|x \cap y|}{|x \cup y|} \cdot |y| \\ &\Longrightarrow t \cdot |y| \leq |x| && \left(|x \cap y| \leq |x| \land \frac{|y|}{|x \cup y|} \leq 1 \right) \end{align*}$

【上限の証明】

$\displaystyle \begin{align*} t \leq \frac{|x \cap y|}{|x| + |y| - |x \cap y|} &\Longleftrightarrow t \cdot (|x|+|y|) \leq (t+1) \cdot |x \cap y| \\ &\Longrightarrow t \cdot (|x|+|y|) \leq (t+1) \cdot |y| && \left(|x \cap y| \leq |y| \right) \\ &\Longleftrightarrow |x| \leq \frac{|y|}{t} \end{align*}$

定理の対偶から、 $|x| \lt t \cdot |y|$ または $\frac{|y|}{t} \lt |x|$ を満たすときに $J(x,y) \lt t$ であることが言えます。つまり、ドキュメントの長さを使った軽量な計算によって、それらのJaccard係数が閾値 $t$ を超えないことが示せます。これは、Jaccard係数の計算をスキップできることを意味します。¹

Position Filtering

ある要素 $u \in U$ を境界とし、集合 $x$ の接頭辞と接尾辞を以下のように表記します。

接頭辞： $P_x(u)= \{ a \in x \mid a \preceq u \}$
接尾辞： $S_x(u)= \{ a \in x \mid u \prec a \}$

例えば $x = \{ 1,3,4,6 \}$ のとき、 $P_x(4) = \{ 1,3,4 \}, S_x(4) = \{ 6 \}$ です。²

Overlap係数について、以下の定理が得られます。

【定理】Position Filtering Principle

$\displaystyle O(x,y) \geq T \Longrightarrow O(P_x(u),P_y(u)) + \min(|S_x(u)|,|S_y(u)|) \geq T$

【証明】

$\displaystyle \begin{align*} O(x,y) \geq T &\Longleftrightarrow O(P_x(u),P_y(u)) + O(S_x(u),S_y(u)) \geq T \\ &\Longrightarrow O(P_x(u),P_y(u)) + \min(|S_x(u)|,|S_y(u)|) \geq T \end{align*}$

Overlap係数を計算するために、 $x$ と $y$ の要素を前方から比較しつつ共通要素数を数え上げているとします。例えば、以下のようなアルゴリズムです。

def overlap(x: list[int], y: list[int]) -> int:
    """xとyは整列済み配列"""
    i, j = 0, 0
    intersection = 0
    while i < len(x) and j < len(y):
        if x[i] == y[j]:
            i += 1
            j += 1
            intersection += 1
        elif x[i] < y[j]:
            i += 1
        else:
            j += 1
    return intersection

このとき、イテレーション毎にある接頭辞の共通要素数 $O(P_x(u),P_y(u))$ が計算されているはずです。次のイテレーションに入る前に、現時点の共通要素数と残りの接尾辞の長さのminの合計を計算し、それが $T$ 未満のときはイテレーションを打ち切ることができます。（それを導入したアルゴリズムは後に示します。）

高速化のための要素順序

Position Filteringでは接頭辞の共通要素数を利用します。この共通要素数が少なければ、早い段階で計算を打ち切ることができるため、重複し難い要素が前方にあるのが好ましいです。

このためには、データベースでの出現が少ない順に若いトークンIDを割り当てるのが良いでしょう。ジップ則より単語の出現には偏りがあるはずなので、多くのケースで効果的に機能します。

アルゴリズム

上記のフィルタリング条件を使って、 $J(x,y) \geq t$ かどうかを判定するアルゴリズムは以下のように書けます。

import math
from collections.abc import Iterator

def check_jaccard(x: list[int], y: list[int], t: float) -> bool:
    """jaccard(x,y) >= t なら True を返す。"""

    # Length Filter
    if len(x) < len(y) * t or len(y) / t < len(x):
        return False

    # Overlap threshold
    T = math.ceil(t / (1 + t) * (len(x) + len(y)))

    i, j = 0, 0
    intersection = 0
    while i < len(x) and j < len(y):
        if x[i] == y[j]:
            i += 1
            j += 1
            intersection += 1
        elif x[i] < y[j]:
            i += 1
        else:
            j += 1

        # Position Filter
        if intersection + min(len(x) - i, len(y) - j) < T:
            return False

    # intersection >= T holds because the last iteration
    # of the above while loop always evaluates it. 
    return True
    
def faster_linear_search(
    database: list[list[int]], query: list[int], threshold: float
) -> Iterator[int]:
    for doc_id, base in enumerate(database):
        if check_jaccard(base, query, threshold):
            yield doc_id

転置索引を使った解法

線形探索による解法は、データベースが大きい場合に非効率です。そこで、索引を使った高速化を考えます。索引を使った解法では、Filter-and-Verificationの2ステップで検索を実現します。

Filter: 索引を用いて解候補 $R' \supseteq R$ を絞り込む
Verification: $i \in R'$ について $J(d_i,q) \geq t$ を評価し $R$ を得る

Verificationステップには check_jaccard がそのまま流用できます。ここでの関心は、Filterステップを効率的に実現する索引の構築です。

基本的なアイデア

この解法では、以下のように転置索引を使って解候補を得ます。

トークンをキーとし、 $d_i$ が検索できるような転置索引を構築する
$q$ のトークンを使って検索し、ヒットした $d_i$ を解候補とする

つまり、 $q$ に含まれるトークンを全く含まない $d_i$ は解にはなり得えないので、それ以外のドキュメントのみを解候補として検証すれば良いというアイデアです。

しかし、この素朴な方法では $q$ のトークンが一つでも一致する全ての $d_i$ が解候補となってしまいます。解候補が多すぎると高速化には繋がりません。そこで、

見逃しが無いように $R' \supseteq R$ を保証しつつ、
できる限り小さいサイズの $R'$ が得られる

ような改善が必要です。

Prefix Filteringに基づくトークンの絞り込み

不必要にヒット件数を増やさないように、索引やクエリに使用するトークンを絞り込むのが基本戦略です。閾値 $t$ が大きいとき、直感的に全てのトークンを登録する必要は無さそうに思います。

[Xiao et al. TODS 2011] では、トークンの絞り込みを目的として以下のPrefix Filtering Principleを提案しています。³

【定理】Prefix Filtering Principle

$\displaystyle J(x,y) \geq t \Longrightarrow x[1..\ell_x ] \cap y[1..\ell_y] \neq \emptyset$

where

$\displaystyle \ell_x = \left\lfloor \frac{1-t}{1+t} \cdot |x| \right\rfloor +1, \ell_y = \left\lfloor (1-t) \cdot |y| \right\rfloor +1$

すなわち $J(x,y) \geq t$ のとき、 $x$ の長さ $\ell_x$ の接頭辞と $y$ の長さ $\ell_y$ の接頭辞が少なくとも一つは共通するトークンを持ちます。この定理を利用すれば、以下のような手順で転置索引を用いたFilterステップが実現できます。

データベース中の $d_i$ について接頭辞長 $\ell_{d_i} = \left\lfloor \frac{1-t}{1+t} \cdot |d_i| \right\rfloor +1$ を計算し、 $d_i[1..\ell_{d_i}$ ] に含まれるトークンを転置索引に登録する
クエリ $q$ の接頭辞長 $\ell_q = \left\lfloor (1-t) \cdot |q| \right\rfloor +1$ を計算し、 $q[1..\ell_q$ ] に含まれるトークンを使って転置索引を検索し解候補 $R’$ を得る

手順2の検索によりヒットしない $d_i$ について、 $d_i [ 1 .. \ell_{d_i} ] \cap q[1..\ell_q ] = \emptyset$ であることが保証されます。つまり、定理の対偶より $J(d_i,q) \lt t$ であることが保証されるため、解候補 $R’$ に見逃しが無いこと、つまり $R' \supseteq R$ が保証されます。

高速化のための要素順序

Position Filteringと同じく、接頭辞の共通要素が少ないほど解候補数は少なくて済みます。つまり、Position Filteringで導入した要素順序は転置索引による解法でも効果的です。

アルゴリズム

転置索引の構築アルゴリズムと検索アルゴリズムを以下に示します。⁴

import math
from collections.abc import Iterator

def index_search(
    database: list[list[int]], query: list[int], threshold: float
) -> Iterator[int]:
    # Build an inverted index
    index: dict[int, list[int]] = {}
    for doc_id, base in enumerate(database):
        l = math.floor(len(base) * (1-threshold) / (1+threshold)) + 1
        for e in base[:l]:
            if e not in index:
                index[e] = []
            index[e].append(doc_id)
    
    # Search
    deduplicator: set[int] = {}
    l = math.floor(len(query) * (1-threshold)) + 1
    for e in query[:l]:
        for doc_id in index.get(e, []):
            if doc_id in deduplicator:
                # 一度チェックしたものはスキップ
                continue            
            deduplicator.add(doc_id)
            if check_jaccard(base, query, threshold):
                yield doc_id

実験

弊社で保有する契約書データを使って、解説した高速化技法の性能を評価します。計算機環境はGCPのn1-standard-16です。実装はRustを使用しました。実験に使用したコードは以下で公開しています。

github.com

データセット

データベースに10,000件、クエリに100件の日本語契約書データを使用します。Vaporetto 0.6.3 (bccwj-suw+unidicモデル) を使って単語に分割し、出現する単語をトークンとしました。ストップワードは考慮していません。

統計量

データベースに含まれる契約書データについて、ドキュメントの長さ（i.e., トークン数）の分布を以下に示します。平均と標準偏差は図の中に記載しています。

各トークンの出現数について、多い順にプロットした結果を以下に示します。出現頻度に偏りがあることがわかります。

クエリ当たりの解の数を以下に示します。

閾値	解の数
t=0.9	0.96 ± 2.17
t=0.8	1.82 ± 3.48
t=0.5	22.56 ± 44.58

Length Filterの検出率に関する結果

check_jaccard にて、Length Filterで検索が打ち切れた割合を調査しました。データベースとクエリセットの全対の類似しない事例についての割合を計測しました。

閾値	解の数
t=0.9	89.3%
t=0.8	77.6%
t=0.5	40.7%

$t = 0.9$ のとき、90%程度がLength Filterによって検索を打ち切れていることがわかります。 $t$ が小さくなると、フィルタリング条件が緩くなり検出率は低下しています。

検索時間に関する結果

解説した技法の検索時間を計測しました。ベンチマークツールcriterionを使用し、10回試行の平均を算出しました。計測は全て主記憶上で行いました。

結果を以下の表に記載します。クエリ当たりの検索時間を示しています。単位はミリ秒です。

検索技法	t=0.9	t=0.8	t=0.5
線形探索 (No Filter）	5,446 ± 3.55	5,415 ± 1.64	5,420 ± 1.49
線形探索 (Length Filter）	723 ± 1.30	1,470 ± 0.78	3,661 ± 3.49
線形探索 (Position Filter）	49 ± 0.14	135 ± 0.24	1,280 ± 1.52
線形探索 (Both Filters）	38 ± 0.10	131 ± 0.26	1,264 ± 0.70
転置索引	9 ± 0.03	83 ± 0.29	1,409 ± 1.01

フィルタリング無しの単純な線形探索では検索に5秒近く要しています。高々1万件程度のデータベースへの検索としてはかなり遅く感じます。フィルターを導入することで、この検索時間は改善します。特に閾値 $t$ が大きいときに顕著で、両方のフィルターを有効にすると $t = 0.9$ で100倍以上改善します。転置索引を導入すると更に改善し、10ミリ秒程度で検索可能です。契約書のような長いドキュメントにおいて、フィルタリングや索引の必要性が確認できます。

$t$ が小さくなると、フィルタリング条件が緩くなり改善率も低下します。 $t = 0.5$ で4倍程度の改善に留まっています。フィルタリングを導入する場合、 $t$ を大きくして解を絞り込むことも高速化には重要であることがわかります。

転置索引と線形探索を比較すると、 $t = 0.9$ で転置索引が4倍程度高速です。追加で索引の保存が必要なので、妥当な改善であるかは解釈に依ると思います。また、 $t$ が小さくなるに連れて線形探索が優位になります。フィルタリングの効果と比べて索引への検索の方がオーバヘッドとなっているのでしょう。

線形探索で十分か、転置索引も必要かは、データベースの規模と閾値によって変わってくるものと思われます。少なくとも1万件程度の規模では、線形探索でも10ミリ秒オーダーで検索できているので、索引は無くても良さそうです。

おわりに

本記事では、Jaccard係数に基づく類似文書検索の高速化技法を解説し、契約書データを使った実験結果を報告しました。

Length Filterは長さを使用したIF文を一つ加えるだけで良いので、Jaccard係数を使用している既存のコードにお手軽に適用できると思います。Position Filterと転置索引は頻度に基づくトークンのマッピングが必要なので、導入には少し手間が必要です。しかしその効果は大きいので、高速化をしたい場合は検討してみてください。

本記事ではアイデアのシンプルなものに限定して紹介しましたが、Jaccard係数のような集合の類似度検索に関する研究は伝統的にされており、他にもいろんな手法が存在します。サーベイ論文もいくつか存在しますが、個人的には [Section 3, Wang et al. VLDBJ 2018] が非常によくまとまっておりオススメです。ご興味がありましたら是非読んでみてください。

メンバー募集中!!

株式会社LegalOn Technologies では、MLエンジニアや検索エンジニアなど、複数のポジションでエンジニアを募集しています。気軽にご応募ください。

herp.careers

[Mann et al. GVD 2014] でより強い上限が提案されています。↩
整数値昇順が要素の順序である想定です。↩
証明は複雑なので [Lemma 4.4, Xiao et al. TODS 2011] を参照してください。↩
簡単のため同じ関数内に構築アルゴリズムと検索アルゴリズムを記載していますが、索引は事前に構築しておくとよいでしょう。↩

LegalOn Technologies Engineering Blog

LegalOn Technologies 開発チームによるブログです。

Jaccard係数に基づく類似文書検索の高速化技法

背景と目的

共起に基づく類似文書検索の必要性

契約書検索での注意点

本記事の目的

準備

表記

Jaccard係数

Overlap係数との関係

問題設定

線形探索による解法

高速化の方針

Length Filtering

Position Filtering

高速化のための要素順序

アルゴリズム

転置索引を使った解法

基本的なアイデア

Prefix Filteringに基づくトークンの絞り込み

高速化のための要素順序

アルゴリズム

実験

データセット

統計量

Length Filterの検出率に関する結果

検索時間に関する結果

おわりに

メンバー募集中!!