1

私は記事を比較するためのソフトウェアを書いています。2 つの記事の差 (変動) を計算する効率的で正確なアルゴリズムを探しています。バリエーションは、文字ではなく単語に完全に依存する必要があります。試してみlevenshtein()ましたが、時間の複雑さがO(n*m)あり、記事のような大きなテキストで実行すると非常に高価です。O(n*m*3)similar_text()の時間複雑度が高いものも試し ました。さらに、ある文字列を別の文字列に変換するために必要な操作の数を計算しますが、これは 2 つの大きな記事の違いを正確に計算する方法ではありません。levenshtein()similar_text()

他にどのようなオプションがありますか?

編集：

検索エンジン（Google）の観点からおおよその変動を計算しようとしています。

4

5 に答える 5

1

単語に基づいてテキストの類似性を測定する方法を定義できれば、途中です。例：両方の記事の各単語の出現をカウントしてから、2つのリストの単純な違いを作成できます。ただし、これは意味による類似性には機能しません。

データベースがある場合は、フルテキスト機能を使用してください。前述のように、PostGresはそのような機能を提供します。私はMSSQLを使用しており、FREETEXT関数を呼び出すだけで、2つのテキストがどれほど類似しているかを示す「ランク」を計算できます。

自分で書くのではなく、成熟した製品を使用することを強くお勧めします。

于 2013-01-20T17:26:10.190 に答える
1

PostgreSQLは、全文検索機能にtsvectorを使用します。多分それはあなたにとって非常に便利になるかもしれない何かです。

于 2013-01-20T17:05:14.680 に答える
1

2 つの記事を比較する方法はありません。記事ではなく、2 つの単語を比較するように設計されていますlevenshtein()。similar_text()

最も単純なアルゴリズムは、次のように、記事を単語ごとに展開し、単語ごとの類似性を見つけて、タスクに応じていくつかの計算を行うことです。

// not tested!
function similar_articles($articleA, $articleB) {
  $wordsA = array_unique(preg_split('@[\W]+@', $articleA));
  $wordsB = array_unique(preg_split('@[\W]+@', $articleA));
  $resultSimilarity = 0;
  foreach($wordsA as $wordA) {
    $wordSimilarity = 0;
    foreach($wordsB as $wordB) {
      similar_text($wordA, $wordB, $percent);
      $wordSimilarity = max($wordSimilarity, $percent);
    }
    $resultSimilarity += $wordSimilarity;
  }
  return($resultSimilarity / count($wordsA));
}

注: similar_articles($artileA, $articleB)!=similar_articles($artileB, $articleA)のためsimilar_text($wordA, $wordB)!= similar_text($wordB, $wordA)。

于 2013-01-20T17:35:17.193 に答える
0

距離の種類を計算する簡単な方法は、参照を比較することです。別の方法は、辞書と一致するいくつかのキーワードを選択し、社会的関連性の高い順に距離を計算することです。

また、レーベンシュタイン距離を使用するには、 stringmetricを参照してください。

于 2013-01-20T17:49:11.403 に答える
0

私の場合、2 つの記事間の変動を計算する必要がありました。そのため、非常にシンプルなソリューションが私にとって非常にうまく機能することがわかりました。これは単純に、2 つの記事に共通する単語をmax(number of words in article A, number of words in article B) で割ったものとして類似度を計算することによって機能します。次に、100 から類似度を引いて変動率を求め、変動を計算します。以下のコードはそれをすべて説明しています。

function get_variation($article1,$article2){

      $wordsA = array_unique(preg_split('@[\W]+@', $article1));
      $wordsB = array_unique(preg_split('@[\W]+@', $article2));
      $intersection = array_intersect($wordsA, $wordsB);
      $similarity = (count($intersection)/ (max(count($wordsA),count($wordsB))) * 100);
      $similarity =  number_format($similarity, 2, '.', '');
      $variation = 100-$similarity;
      return $variation;
}
于 2013-01-21T19:06:47.237 に答える