PHPで2つの文章の類似度を計算する

(1/1)
PHP の組み込み関数  similar_text  を使うことで、異なる 2 つの文章の類似度を計算できる。もちろん日本語にも対応している。
ブログなどに投稿される文章の中には、Wikipedia や他人の記事を無断引用するケースが少なくない。今回のプログラムを使えば、2 つの文章の類似度を自動的に比較・判定することができるようになる。

サンプル・プログラム

サンプル・プログラムの解説

プログラムの構造は簡単である。
POST 渡しされた 2 つのテキスト、$sour$dest を関数  similar_text  に投入しているだけである。
事前に、文字コードを UTF-8 に統一するために関数  mb_convert_encoding  を通し、XSS 対策として関数  htmlspecialchars  を通している。

0019:     $sour = isset($_POST['sour']) ? $_POST['sour'] : '';
0020:     $dest = isset($_POST['dest']) ? $_POST['dest'] : '';
0021:     $sour = mb_convert_encoding($sour$InternalEncoding, 'auto');
0022:     $dest = mb_convert_encoding($dest$InternalEncoding, 'auto');
0023:     $sour = htmlspecialchars($sour);             //XSS対策
0024:     $ret = similar_text($sour$dest$result);      //2つのテキストを比較
0025:     $result = sprintf('%02.1f', $result);
0026: }

たとえば、「元のテキスト」として、以下の Wikipedia の引用文を入れる。これは「PHP: Hypertext Preprocessor」からの抜粋である。

PHP: Hypertext Preprocessor(ピー・エイチ・ピー ハイパーテキスト プリプロセッサー)とは、動的に HTML データを生成することによって、動的なウェブページを実現することを主な目的としたプログラミング言語、およびその言語処理系である。
PHP は、HTML 埋め込み型のサーバサイド・スクリプト言語として分類される。この言語処理系自体は、C言語で記述されている。


「比較するテキスト」には、以下の文章を入れてみよう。

PHP(Hypertext Preprocessor;ピー・エイチ・ピー)とは、動的に HTML データを生成することによって、動的なウェブページを実現すること目的としたプログラミング言語である。
PHP は、HTML 埋め込み型のサーバサイド・スクリプト言語の一種で、処理系自体は C言語で記述されている。


結果は 84.0% である。
2 つめの文章は、一見すると元の文章とは異なっているが、じつは Wikipedia の引用文の順番を変えただけである。
このような違いでは、かなり高い類似度の値となる。

次に、「比較するテキスト」に以下の文章を入れて実行してみていただきたい。これは「PHP とは何か」(ぱふぅ家のホームページ)の冒頭部分である。

「PHP(Hypertext Preprocessor)」は、オープンソースのサーバ・サイド・スクリプト言語である。
サーバ・サイド・スクリプトとは、データベースサーバなどのサーバ群と Web ブラウザ(クライアント)を結ぶインターフェースの役割をするもので、Web サーバ上で動作する。HTML に比べて、動的なページを実現することができる。


結果は 21.7% となる。
なお、どこまでの値を「類似」とみなすかは、各人の判断にお任せする。

N-gram と類似度

テキストの隣り合う N 文字のことを N-gram を呼ぶ。
異なる 2 つの文章の N-gram を総当たりで比較することで、たとえ文節の順番が異なっていても、登場する単語の種類と頻度の比較が可能となる。
N=3 の Tri-gram としてプログラムに実装したものが、Perl の String::Trigram である。これが livedoor で利用されているということが、公式ブログ「String::Trigram でテキストの類似度を測る」に記されている。

N-gram を用いた類似度計算は、Google のような全文検索でも利用されている。

ところで、組み込み関数  similar_text  は、ソースを見ると、N-gram を忠実に実装しているわけではない。
類似度を計算するのに使える組み込み関数として  levenshtein  もあるが、こちらも N-gram ではない。
そこで次節では、PHP で N-gram にもとづく類似度計算プログラムを作ってみることにする。

サンプル・プログラム

サンプル・プログラムの解説:N-gramを求める

0013: /**
0014:  * N-gramを求める
0015:  * @param string $str    対象テキスト
0016:  * @param string $n      N数
0017:  * @param string $ngrams N-gramを代入する配列
0018:  * @return N-gramの数/FALSE:入力パラメータの異常
0019: */
0020: function get_ngram($str$n, &$ngrams) {
0021:     $str = preg_replace("/[ \t\n\r ]+/um", '', $str);
0022:     $len = mb_strlen($str);
0023:     if ($len <= 0 || $len <= $n)    return FALSE;
0024: 
0025:     $cnt = 0;
0026:     for ($pos = 0; $pos < $len$pos++) {
0027:         $cc = mb_substr($str$pos$n);
0028:         if (isset($cc)) {
0029:             $ngrams[$cnt] = $cc;
0030:             $cnt++;
0031:         }
0032:     }
0033:     return $cnt;
0034: }

ユーザー定義関数 get_ngram は、引数として与えた文字列 $str の N-gram を配列に返す。

前準備として、関数  preg_replace  を使い、空白、改行、タブなど、比較対象としない文字を削除しておく。

N-gram への分解は、日本語(マルチバイト文字)に対応するようにした。この点で関数  similar_text  と大きく異なる。

サンプル・プログラムの解説:類似度を計算する

0036: /**
0037:  * 2つのテキストの類似度を計算する
0038:  * @param string $sour   元のテキスト
0039:  * @param string $dest   比較するテキスト
0040:  * @return double 類似度(0~1)/FALSE:計算に失敗
0041: */
0042: function similar_ngram($sour$dest) {
0043:     $n = 3;      //N-gramのN数
0044:     if (($n1 = get_ngram($sour$n$ngrams_sour)) == FALSE)    return FALSE;
0045:     if (($n2 = get_ngram($dest$n$ngrams_dest)) == FALSE)    return FALSE;
0046: 
0047:     $result = count(array_intersect($ngrams_sour$ngrams_dest));
0048: 
0049:     return (double)$result / $n2;
0050: }

類似度の考え方はこうだ――。
2 つのテキストの N-gram(ここでは Tri-gram にした)を A, B とする。A と B の要素を比較し、合致した要素を C とする。C の要素数を B の要素数で除算したものを類似度とする。

PHP には配列の要素を比較し、共通要素を抽出してくれる組み込み関数  array_intersect  が用意されている。今回は  array_intersect  を利用することにした。

このプログラムを実行すると、前節の原文(Wikipedia 引用文)と 2番目の文章の類似度は 87.1%、3番目の文章(ぱふぅ家のホームページ)との類似度は 34.3%と、関数  similar_text  を使った場合より厳しい判定結果となった。

N-gram ではなく、日本語として意味のある単語に分解する形態素解析技術を用いることで、類似度計算の精度を高めることができる。
そのプログラムについては、次章で紹介する。

参考サイト

(この項おわり)
header