1

我正在编写一个软件来比较文章。我正在寻找一种有效且准确的算法来计算两篇文章之间的差异（变化）。变化应该完全取决于单词而不是字母。我已经尝试过levenshtein()，但它的时间复杂度为O(n*m)，在像文章这样的大文本上执行时非常昂贵。我也尝试过 similar_text()具有更高时间复杂度的O(n*m*3)。此外，levenshtein()并similar_text()计算将一个字符串转换为另一个字符串所需的操作数，这不是计算两篇大文章之间差异的准确方法。

我还有什么其他选择？

编辑：

我试图从搜索引擎（Google）的角度大致计算变化。

4

5 回答 5

1

PostgreSQL 使用tsvector来实现它的全文搜索功能。也许这对你来说很方便。

于 2013-01-20T17:05:14.680 回答
1

如果您可以定义如何根据单词来衡量文本相似度，那么您就成功了一半。例如：您可以计算两篇文章中每个单词的出现次数，然后创建两个列表的简单差异。但是，这不适用于含义上的相似性。

如果您有数据库，请使用它们的全文功能。如前所述，PostGres 提供了这样的功能。我使用 MSSQL，您可以简单地调用 FREETEXT 函数，该函数将计算一个“等级”，表明两个文本的相似程度。

我强烈建议使用成熟的产品，而不是尝试编写自己的产品。

于 2013-01-20T17:26:10.190 回答
1

没有办法比较两篇文章。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

计算一种距离的一种简单方法是比较参考。另一种方法是根据字典选择一些关键词，并按照社会相关性的顺序计算距离。

另外，为了使用Levenshtein distance看看stringmetric。

于 2013-01-20T17:49:11.403 回答
0

就我而言，我需要计算两篇文章之间的差异。所以，我发现这个非常简单的解决方案非常适合我。它的工作原理是简单地将相似度计算为两篇文章之间的常用词除以max(文章 A 中的单词数，文章 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 回答