查找具有相似文本的文章的算法

StackOverflow https://stackoverflow.com/questions/246961

题

我在数据库中有很多文章（带有标题、文本），我正在寻找一种算法来找到 X 个最相似的文章，例如当你提出问题时 Stack Overflow 的“相关问题”。

我尝试用谷歌搜索这个问题，但只找到了有关其他“相似文本”问题的页面，例如将每篇文章与所有其他文章进行比较并将相似之处存储在某处。所以在我刚刚输入的文本上“实时”执行此操作。

如何？

有帮助吗？

解决方案

编辑距离不太可能成为候选人，因为它会拼写/单词顺序考虑到您实际感兴趣的文档的大小和数量，Will会让您相信依赖，并且计算成本高得多。

像Lucene这样的东西是要走的路。您索引所有文档，然后当您想要查找与给定文档类似的文档时，将您的给定文档转换为查询，并搜索索引。 Lucene内部将使用 tf-idf 和倒排索引，使整个过程花费的时间与可能匹配的文档数量成正比，而不是文档总数集合。

其他提示

这取决于你对类似的定义。

编辑距离算法是（拉丁语）字典建议的标准算法，可以处理整个文本。如果两个文本在相同的顺序中具有基本相同的单词（eh字母），则两个文本类似。因此，以下两本书评论将非常相似：

1）“这是一本很棒的书”

2）“这些不是好书”

（要删除，插入，删除或改为将（2）转换为（1）的字母数称为“编辑距离”。）

要实现此功能，您需要以编程方式访问每个评论。这可能不像听起来那么昂贵，如果成本过高，你可以将比较作为后台任务进行，并将最类似的数据存储在数据库字段中。

另一种方法是了解（拉丁语）语言的结构。如果您删除短（非元素化或引用）单词，并为常用或唯一的单词（或前缀）分配权重，则可以进行贝叶斯比较。以下两本书评可能会被复制，并且发现类似：

3）“法国革命是等等的战争与和平等等等等法国。” - ＆GT;法国/法国（2）革命（1）战争（1）和平（1）（注意字典已用于法国和法国的结合）

4）“这本书真是一场法国菜的革命。” - ＆GT;法国（1）革命（1）

要实现这一点，您需要在评论创建/更新时识别“关键字”，并查找类似的评论在查询的where子句中使用这些关键字（理想情况下，“全文”搜索，如果数据库支持它），可能会对结果集进行后处理，以便对找到的候选人进行评分。

书籍也有类别 - 在法国设置的惊悚片类似于法国的历史研究，等等？标题和文本之外的元数据可能有助于保持结果的相关性。

此链接上的教程听起来可能就是您所需要的。它易于遵循并且运行良好。

他的算法奖励了常见的子串和这些子串的共同排序，所以应该很好地选择相似的标题。

我建议您使用 Apache Lucene 索引您的文章，性能，全功能的文本搜索引擎库完全用Java编写。它是一种适用于几乎所有需要全文搜索的应用程序的技术，尤其是跨平台的。索引后，您可以轻松找到相关文章。

使用的一种常见算法是自组织地图。 它是一种神经网络，可以自动对您的文章进行分类。然后，您只需找到当前文章在地图中的位置，并且其附近的所有文章都是相关的。该算法的重要部分是如何向量量化您的输入。有几种方法可以处理文本。你可以散列你的文档/标题，你可以计算单词并将其用作n维向量等。希望有所帮助，尽管我可能已经打开了一个潘多拉的盒子，让你在AI中无尽的旅程。

SO只对标题进行比较，而不是对问题的正文进行比较，因此只对相当短的字符串进行比较。

您可以在文章标题和关键字上使用他们的算法（不知道它是什么样子）。 如果你有更多的cpu时间来刻录，也可以在文章的摘要中。

借用Lucene的全文建议，但请注意java不是必需的; 可以使用.NET端口。另请参阅主Lucene页面以获取其他项目的链接，包括 Lucy，一个C端口。

也许您正在寻找的是释义。我只是粗略地了解这一点，但释义是自然语言处理概念，以确定是否两个文本段落实际上意味着同样的事情 - 尽管可能使用完全不同的词语。

不幸的是我不知道有任何工具允许你这样做（虽然我有兴趣找到一个）

您可以使用SQL Server全文索引来进行智能比较，我相信SO正在使用ajax调用，它会执行查询以返回类似的问题。

您使用的是哪些技术？

如果你正在寻找伤口相似的单词，你可以转换为soundex和soundex单词匹配...为我工作

我尝试了一些方法，但都没有效果。可能会得到一个相对满意的结果，如下所示：    首先：为所有文本的每个段落获取一个Google SimHash代码并将其存储在数据库中。    第二：SimHash代码的索引。    第三步：处理你的文本，如上所述进行比较，得到一个SimHash代码，并通过SimHash索引搜索所有文本，除了形成汉明距离，如5-10。然后将simility与term vector进行比较。   这可能适用于大数据。

@alex77 的答案中的链接指向 索伦森骰子系数 这是该文章的作者独立发现的 - 这篇文章写得很好，非常值得一读。

我最终使用这个系数来满足我自己的需要。然而，原始系数在处理时可能会产生错误的结果

  • 包含一个拼写错误的三个字母单词对，例如 [and,amd] 和
  • 三个字母的单词对，是字谜词，例如 [and,dan]

在第一种情况下，Dice 错误地报告系数为零，而在第二种情况下，系数显示为 0.5，这个值过高，具有误导性。

一种提升 已建议 其本质是采用单词的第一个和最后一个字符并创建一个额外的二元组。

在我看来，只有 3 个字母的单词才真正需要改进 - 在较长的单词中，其他二元组具有掩盖问题的缓冲作用。下面给出了实现此改进的我的代码。

function wordPairCount(word)
{
 var i,rslt = [],len = word.length - 1;
 for(i=0;i < len;i++) rslt.push(word.substr(i,2));
 if (2 == len) rslt.push(word[0] + word[len]);
 return rslt;
}

function pairCount(arr)
{
 var i,rslt = [];
 arr = arr.toLowerCase().split(' ');
 for(i=0;i < arr.length;i++) rslt = rslt.concat(wordPairCount(arr[i]));
 return rslt;
}

function commonCount(a,b)
{
 var t;
 if (b.length > a.length) t = b, b = a, a = t; 
 t = a.filter(function (e){return b.indexOf(e) > -1;});
 return t.length;
}

function myDice(a,b)
{
 var bigrams = [],
 aPairs = pairCount(a),
 bPairs = pairCount(b);
 debugger;
 var isct = commonCount(aPairs,bPairs);
 return 2*commonCount(aPairs,bPairs)/(aPairs.length + bPairs.length); 
}

$('#rslt1').text(myDice('WEB Applications','PHP Web Application'));
$('#rslt2').text(myDice('And','Dan'));
$('#rslt3').text(myDice('and','aMd'));
$('#rslt4').text(myDice('abracadabra','abracabadra'));
*{font-family:arial;}
table
{
 width:80%;
 margin:auto;
 border:1px solid silver;
}

thead > tr > td
{
 font-weight:bold;
 text-align:center;
 background-color:aqua;
}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.0.0/jquery.min.js"></script>
<table>
<thead>
<tr>
<td>Phrase 1</td>
<td>Phrase 2</td>
<td>Dice</td>
</tr>
<thead>
<tbody>
<tr>
<td>WEB Applications</td>
<td>PHP Web Application</td>
<td id='rslt1'></td>
</tr>
<tr>
<td>And</td>
<td>Dan</td>
<td id='rslt2'></td>
</tr>
<tr>
<td>and</td>
<td>aMd</td>
<td id='rslt3'></td>
</tr>
<tr>
<td>abracadabra</td>
<td>abracabadra</td>
<td id='rslt4'></td>
</tr>
</tbody>
</table>

请注意最后一个示例中故意的拼写错误：阿布拉卡达布拉 对阵阿布拉卡巴德拉. 。即使没有应用额外的二元组校正，报告的系数也是 0.9。经过修正后，该值为 0.91。

希望这会对遇到此线程的其他人有所帮助。

给定示例文本，该程序列出按相似性排序的存储库文本：在C ++中简单实现单词包。该算法在样本文本和存储库文本的总长度上是线性的。此外，该程序是多线程的，可以并行处理存储库文本。

以下是核心算法：

class Statistics {
  std::unordered_map<std::string, int64_t> _counts;
  int64_t _totWords;

  void process(std::string& token);
public:
  explicit Statistics(const std::string& text);

  double Dist(const Statistics& fellow) const;

  bool IsEmpty() const { return _totWords == 0; }
};

namespace {
  const std::string gPunctStr = ".,;:!?";
  const std::unordered_set<char> gPunctSet(gPunctStr.begin(), gPunctStr.end());
}

Statistics::Statistics(const std::string& text) {
  std::string lastToken;
  for (size_t i = 0; i < text.size(); i++) {
    int ch = static_cast<uint8_t>(text[i]);
    if (!isspace(ch)) {
      lastToken.push_back(tolower(ch));
      continue;
    }
    process(lastToken);
  }
  process(lastToken);
}

void Statistics::process(std::string& token) {
  do {
    if (token.size() == 0) {
      break;
    }
    if (gPunctSet.find(token.back()) != gPunctSet.end()) {
      token.pop_back();
    }
  } while (false);
  if (token.size() != 0) {
    auto it = _counts.find(token);
    if (it == _counts.end()) {
      _counts.emplace(token, 1);
    }
    else {
      it->second++;
    }
    _totWords++;
    token.clear();
  }
}

double Statistics::Dist(const Statistics& fellow) const {
  double sum = 0;
  for (const auto& wordInfo : _counts) {
    const std::string wordText = wordInfo.first;
    const double freq = double(wordInfo.second) / _totWords;
    auto it = fellow._counts.find(wordText);
    double fellowFreq;
    if (it == fellow._counts.end()) {
      fellowFreq = 0;
    }
    else {
      fellowFreq = double(it->second) / fellow._totWords;
    }
    const double d = freq - fellowFreq;
    sum += d * d;
  }
  return std::sqrt(sum);
}

比较摘要之间相似性的最简单，最快捷的方法可能是利用集合概念。首先将抽象文本转换为单词集。然后检查每组重叠的程度。 Python的设置功能非常适合执行此任务。你会惊讶地发现这种方法与那些“相似/相关的论文”相比有多好。 GScholar，ADS，WOS或Scopus提供的选项。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top