Information Retrieval and Web Search まとめ(23): 重複検知

前回は Web クローラの要件やそのアーキテクチャについて解説した。今回は、重複した文書の検知について扱う。

重複ページの検知

重複 (duplication): 完全一致はフィンガープリント (fingerprint) によって検知できる
準重複 (near-duplication): 近似マッチ (approximate match)
- 構文的な類似度を編集距離によって計算する
- その類似度の閾値で準重複コンテンツを検知する
- これは推移的にはならないが、推移的として扱うこともある
  - A と B、B と C がそれぞれ準重複だったとして、A と C は準重複とは限らない

特徴量
- 文書のセグメント
  - 自然な、もしくは人工的な場所で分割
- shingles
  - 単語 n-gram　などを使う
類似度の指標
- それぞれの文書の shingles に対して定義される
- ジャッカード係数 (Jaccard coefficient)
  - 共通集合の要素数 / 和集合の要素数
文書 $d_j$ のshingleを $S(d_j)$ で表すとすると、文書 $d_1$ と $d_2$ のジャッカード係数は

各文書に対してスケッチベクトル (sketch vector) を作成する
- スケッチベクトルの次元数 m は ~200 次元
- スケッチベクトルの要素が t 以上（80% 以上など）かぶっている文書は準重複 (near duplicate) であるとみなせる
準備
- 文書の shingles をのいずれかの値に写像する、以下のような集合関数を用意する
  - $H(d_j)$ は、文書 $d_j$ の shingles $S(d_j)$ の各要素のハッシュ値からなる集合
  - $m = 64$ のとき、 $H(d_j)$ の要素は 64 ビット非負整数のいずれかの値をとる
- のランダムな置換 (permutation) を用意する
  - $1 .. 2^{m}$ を $1 .. 2^{m}$ のいずれかの値にランダムに入れ替える写像
  - 置換は全単射なので異なる値が同じ値に写像されることはない
- の各要素をによって置換したものをとする
  - $H(d_j)$ の各要素 $h \in H(d_j)$ に対して、対応する値 $\pi(h) \in \Pi(d_j)$ が存在する
文書 $d_j$ の $\pi$ によるスケッチ $x_j^{\pi}$ は $\text{min}(\Pi(d_j))$ （ $\Pi(d_j)$ のうち最小の整数）で計算される

このスケッチの計算を 200 個のランダム置換に対して行う
- 200 次元のスケッチベクトルを計算する場合
このようにして得られた 200 個のスケッチ $x_j^{\pi_1}, x_j^{\pi_2}, ..., x_j^{\pi_{200}}$ を並べたものを、文書 j のスケッチベクトル $\phi_j$ とする
文書 i と文書 j のペアに対するジャッカード係数 $J(S(d_i), S(d_j))$ を $|\phi_i \cap \phi_j| \, / \, 200$ で推定する