目次
サンプル・プログラム1の実行例

サンプル・プログラム1
サンプル・プログラムの解説
243: //2つのテキストを比較
244: $sim = similar_text($sour, $dest, $result);
PHP:Hypertext Preprocessor(ピー・エイチ・ピー:ハイパーテキストプリプロセッサー)とは、動的にHTMLデータを生成することによって、動的なウェブページを実現することを主な目的としたプログラミング言語、およびその言語処理系である。PHPは、HTML埋め込み型のサーバサイド・スクリプト言語として分類される。この言語処理系自体は、C言語で記述されている。「比較するテキスト」には、以下の文章を入れてみよう。
PHP(Hypertext Preprocessor;ピー・エイチ・ピー)とは、動的にHTMLデータを生成することによって、動的なウェブページを実現すること目的としたプログラミング言語である。PHPは、HTML埋め込み型のサーバサイド・スクリプト言語の一種で、処理系自体はC言語で記述されている。結果は 83.7% である。
2つめの文章は、一見すると元の文章とは異なっているが、じつはWikipediaの引用文の順番を変えただけである。
このような違いでは、かなり高い類似度の値となる。

次に、「比較するテキスト」に以下の文章を入れて実行してみていただきたい。これは「PHPとは何か」(ぱふぅ家のホームページ)の冒頭部分である。
「PHP(Hypertext Preprocessor)」は、オープンソースのサーバ・サイド・スクリプト言語である。サーバ・サイド・スクリプトとは、データベースサーバなどのサーバ群と Web ブラウザ(クライアント)を結ぶインターフェースの役割をするもので、Webサーバ上で動作する。HTMLに比べて、動的なページを実現することができる。結果は 27.3% となる。
なお、どこまでの値を「類似」とみなすかは、各人の判断にお任せする。
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にもとづく類似度計算プログラムを作ってみることにする。
サンプル・プログラム2の実行例

サンプル・プログラム2
解説:N-gramを求める
154: /**
155: * N-gramを求める
156: * @param string $str 対象テキスト
157: * @param string $n N数
158: * @param string $ngrams N-gramを代入する配列
159: * @return N-gramの数/FALSE:入力パラメータの異常
160: */
161: function get_ngram($str, $n, &$ngrams) {
162: $str = preg_replace("/[ \t\n\r ]+/um", '', $str);
163: $len = mb_strlen($str);
164: if ($len <= 0 || $len <= $n) return FALSE;
165:
166: $cnt = 0;
167: for ($pos = 0; $pos < $len; $pos++) {
168: $cc = mb_substr($str, $pos, $n);
169: if (isset($cc)) {
170: $ngrams[$cnt] = $cc;
171: $cnt++;
172: }
173: }
174: return $cnt;
175: }

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

N-gramへの分解は、日本語(マルチバイト文字)に対応するようにした。この点で関数 similar_text と大きく異なる。
解説:類似度を計算する
177: /**
178: * 2つのテキストの類似度を計算する
179: * @param string $sour 元のテキスト
180: * @param string $dest 比較するテキスト
181: * @return double 類似度(0~1)/FALSE:計算に失敗
182: */
183: function similar_ngram($sour, $dest) {
184: $n = 3; //N-gramのN数
185: if (($n1 = get_ngram($sour, $n, $ngrams_sour)) == FALSE) return FALSE;
186: if (($n2 = get_ngram($dest, $n, $ngrams_dest)) == FALSE) return FALSE;
187:
188: $result = count(array_intersect($ngrams_sour, $ngrams_dest));
189:
190: return (double)$result / $n2;
191: }
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ではなく、日本語として意味のある単語に分解する形態素解析技術を用いることで、類似度計算の精度を高めることができる。
そのプログラムについては、次章で紹介する。
参考サイト
- PHPで文字間の距離を測る関数「similar_text」が便利:PHPSPOT
- String::Trigram でテキストの類似度を測る:livedoor開発ブログ
- N-gramのしくみ:技術評論社
- PHPで2つの文章の類似度を計算する(KAKASI版):ぱふぅ家のホームページ
ブログなどに投稿される文章の中には、Wikipedia や他人の記事を無断引用するケースが少なくない。今回のプログラムを使えば、2つの文章の類似度を自動的に比較・判定することができるようになる。