我正在写一个比较文章的软件。我正在寻找一个高效和准确的算法来计算两篇文章之间的差异(变化)。这种变化应该完全取决于单词而不是字母。我尝试过levenshtein()，但它的时间复杂度为O(n*m)，这在像文章这样的大文本上执行时非常昂贵。我也尝试过similar_text()，它具有更高的时间复杂度O(n*m*3)。此外，levenshtein()和similar_text()计算了将一个字符串转换为另一个字符串所需的操作次数，这不是计算两篇大文章之差的准确方法。
我还有其他选择吗?
编辑:
我正试图从搜索引擎(Google)的角度计算近似的变化。
PostgreSQL使用tsvector作为全文搜索特性。也许这对你来说很方便
如果您可以定义如何基于单词度量文本相似性，那么您就成功了一半。例如:您可以计算两篇文章中每个单词的出现次数，然后创建两个列表的简单差异。然而，这并不适用于意义上的相似性。
如果你有一个数据库，使用他们的全文特性。如前所述，PostGres提供了这样一个特性。我用MSSQL工作，你可以简单地调用FREETEXT函数，它将计算一个"等级"，表明两个文本有多相似。
我强烈建议使用成熟的产品，而不是尝试编写自己的产品。
没有办法比较两篇文章。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) .
计算距离类型的一个简单方法是比较引用。另一种方法是选择一些与字典一致的关键词，按社会相关性的顺序计算距离。
另外，为了使用Levenshtein距离，请查看stringmetric。
在我的例子中，我需要计算两篇文章之间的差异。所以，我发现这个非常简单的解决方案对我来说非常有效。它的工作原理是简单地计算两篇文章之间的常用词的相似度除以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;
}