String::Trigram でテキストの類似度を測る

カテゴリ
ブックマーク数
このエントリーを含むはてなブックマーク はてなブックマーク - String::Trigram でテキストの類似度を測る
このエントリーをはてなブックマークに追加

こんにちは。検索グループ解析チームの nabokov7 です。 今回は、livedoor キーワードでの事例より、テキストの類似度を測るのに便利な手法を紹介します。

livedoor キーワードは、livedoor ブログでその日その日で話題になった語をランキング表示するサービスです。

当初、はてなキーワードやWikipediaを足して2で割ったようなサービスを作れといった開き直った指示のもとで開発が開始されたともいう、分社化前の芸風の名残で、キーワードの検索結果にはユーザが自由に解説を書き込める Wikipedia 的スペースもついています。

で、この解説部分に、さまざまなサイトから文章をまる写ししちゃう人がとても多いのですね。

特に多いウィキペディア日本語版からの剽窃を防止するために、livedoor キーワードでは以下のような対策を講じることにしました。

  1. ウィキペディア日本語版の解説の冒頭部分を、最初から引用して表示しておく。
  2. 一部の認定ユーザに、書き込み削除の投票権を与える。
問題は、後者の措置をとる際の判断基準です。このようにグレーゾーンの大きな判断の場合には、最終的にはなんらかの客観的な(例えば数値に置き換え可能な)指標が必要です。例えば「文章が酷似していたらアウト」ではなくて「○文字一致していればアウト」のような。

ただ、「○文字一致していればアウト」という単純な指標だと、文の順序や語尾をちょっとだけ変えただけでチェックをすり抜けてしまいます。
実際、他所の文章をまるごとコピペしてある事例より、一部をちょっとだけかえてある事例の方がずっと多いように思います。以下は、実際に livedoor キーワードに書き込まれた解説の例です。

「梅雨」
北海道と小笠原諸島を除く日本において見られる特有の気象で、5月から7月半ばにかけて毎年めぐってくる、雨の多い期間のこと。梅雨に入ることを梅雨入り、梅雨が終わって夏になることを梅雨明けと言い、日本各地の地方気象台・気象庁が梅雨入り・梅雨明けの発表をする。
これは、日本語版 Wikipeida の以下のパラグラフを改変したものだと思われます。
梅雨(ばいう、つゆ)とは、北海道と小笠原諸島を除く日本や朝鮮半島南部、華南や華中の沿海部や台湾において見られる特有の気象で、5月から7月半ばにかけて毎年めぐってくる、雨の多い期間のこと。梅雨の時季が始まることを梅雨入り、梅雨が終わって夏になることを梅雨明けと言い、日本では、各地の地方気象台・気象庁が梅雨入り・梅雨明けの発表をする。
「梅雨」(2007年6月7日 (木) 14:52UTCの版)『ウィキペディア日本語版』より引用

ちなみにこのようにコピー元の文章にちょっとだけ手を加える人っていうのは、必ずしも剽窃を隠そうという悪意があってやっているわけでもないみたいですね。引用元の記述を切り貼りして、語尾を整えることが作文だと普通に思っている人も多いようです。
確かに、学校で自由研究とか発表っていえばだいたいそうやって書き上げたものですしね。

しかし、上のような例は人が見れば普通にコピーだと判断できますし、願わくばプログラム的にもこれをコピーだと判断できるようにしたいものです。

そんなときにこそこれ ! String::Trigram

String::Trigram は、トライグラム(3-gram) を使って文の類似度を計算してくれるライブラリです。

一般的に N-gram とは、対象となる文の中の、となりあったN個の文字の並びを指します。
例えば

文A「ライブドアでブログを書く」
文B「ブログをライブドアで書く」
の二つの文には、それぞれ以下のような10種類のトライグラム(3-gram)が含まれています。
A「ライブドアでブログを書く」
ライブ *
 イブド *
  ブドア *
   ドアで *
    アでブ
     でブロ
      ブログ *
       ログを *
        グを書
         を書く
B「ブログをライブドアで書く」
ブログ *
 ログを *
  グをラ
   をライ
    ライブ *
     イブド *
      ブドア *
       ドアで *
        アで書
         で書く

文Aと文Bでは語順が入れ替わっていますが、トライグラムに分解して要素比較すると、それぞれ10あるトライグラムのうち、6つまで (図中 '*' で示したもの) が共通であることがわかります。
このような手法で文章同士の類似度を測ったり、もっとも似ている文章を引っ張ってきてくれたりするのが、この String::Trigram なのです。

具体的な使い方は perldoc に任せるとしまして、ここでは実際にこれがどれくらいの精度で「似た文章」を見分けてくれるのか、実際の動作例をお見せしましょう。

この画面は、livedoor キーワードで、解説が剽窃かどうか判断の難しい事例が出た場合に、ユーザやサポートチームに線引きをしてもらうために公開しているツールです。 上と下のテキストエリアに、それぞれ剽窃の疑いのあるテキストと、オリジナルの対応部分とを入れ、compare ボタンを押すと String::Trigram による類似度が表示されます。お試しください。

例えば先に挙げた「梅雨」の解説の例だと、ウィキペディア日本語版の解説原文と、その改変コピーの二つの文章の類似度は 0.65(65%) ほどになります。

パラメータや文字列の長さにもよりますが、100文字程度の二つの文章が人の目にも明らかに似ている場合、この値は 0.4〜0.5 を超えます。0.6 を超えると、細部の入れ替え以外はほぼ同一であるという感じがします。
一方、全く関係のないテキスト同士の類似度は、たかだか数パーセント以内に収まります。

この手法は上のような事例の他、スパム検出などにも利用可能なのですが、その話はまた次の機会にでも。

レスポンス
コメント(1)
トラックバック(0)

このエントリーをはてなブックマークに追加