[Solr]TextProfileSignatureによるDe-Duplication

はじめに

前回の記事で取り上げた De-Duplication ではハッシュの計算方法として、厳密には一致しなくてもほぼ同内容のドキュメントを同一として扱うためのTextProfileSignature が利用できます。Solr のドキュメントでは以下のように書かれています。

Fuzzy hashing implementation from Apache Nutch for near duplicate detection. It’s tunable but works best on longer text.

https://solr.apache.org/guide/8_8/de-duplication.html

どのくらい Fuzzy でも大丈夫なのか興味があったので調べてみました。

TextProfileSignature クラス

TextProfileSignature クラスの JavaDoc に詳しい説明がありました。

• 文字と数字以外を取り除いて小文字に統一する
• ソースを見ると、この判定には Character.isLetterOrDigit() が使われています。
• 空白区切りでトークンに分割する
• MIN_TOKEN_LEN(デフォルト2)より短いトークンを捨てる
• 各トークンの出現回数をカウントする
• 足きり用の QUANT を計算する。QUANT = QUANT_RATE * 最頻出のトークンの出現回数 (QUANT_RATEのデフォルト0.01)
• QUANT が2より小さい場合は QUANT = 2 とする。ただし、2回以上出現したトークンが存在しない場合は QUANT = 1 とする。
  • すべてのトークンが1回ずつしか出現しなかった場合は足きりせず全部使うということ
  • ソースを見ると QUANT_RATE * 再頻出のトークンの出現回数 を四捨五入している。つまり、QUANT_RATE が デフォルトの 0.01 であれば、再頻出のトークンの出現回数が250までは QUANT = 2 (1回しか出現しないトークンは捨てられる)となる。
• QUANT よりも小さい出現回数のトークンを捨てる
• 残ったトークンを出現回数順に並べて MD5 ハッシュを計算する

ちなみに、空白文字で区切ってトークンを作るという処理なので、日本語のドキュメントにはあまり有効ではなさそうで、日本語ドキュメントで曖昧な De-Deplication をするためには、Tokenizer と連携する ProfileSignature を実装する必要がありそうです。

実験

実験のため、TextProfileSignature を呼び出す簡単なプログラムを作りました。

短いドキュメントでも効果がわかりやすいように、QUANT_RATE は 1 としています。これなら、再頻出のトークンの出現回数が2ならQUANTは2、再頻出のトークンの出現回数が2ならQUANTは3となります。

'I have an apple'  8b821c9e763bb2fc567d473996cfde4a
'I have an apple.' 8b821c9e763bb2fc567d473996cfde4a

記号の有無はハッシュ値に影響を与えません。

'an apple I have' 8b821c9e763bb2fc567d473996cfde4a

トークンの出現回数が同じなら、語順はハッシュ値に影響を与えません。

'I have the apple' 9526cdfcde3ddfad02a0691d564f30ac

トークンが別のものに変わるとハッシュ値も変化します。

'I have apple. I have apple.' 5d5a0ce2d6dc15618d873d5572c4eb5e
'I have a apple. I have the apple.' 5d5a0ce2d6dc15618d873d5572c4eb5e

QUANTが2になるので、1回しか出現しない ‘a’ ‘the’ の有無はハッシュ値に影響を与えません。

'I have an apple. I have an apple. I have the apple.' d95062c38e38e90b1c34b009bf434cda
'I have the apple. I have the apple. I have an apple.' d95062c38e38e90b1c34b009bf434cda

QUANTが3になるので、2回しか出現しない ‘a’ ‘the’ の有無はハッシュ値に影響を与えません。