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

Question

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

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

如何？

score 34 · Accepted Answer

编辑距离不是一个可能的候选者，因为它取决于拼写/词序，并且考虑到您实际上有兴趣搜索的文档的大小和数量，它的计算成本比 Will 引导您相信的要高得多。

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

score 14 · Accepted Answer

这取决于您对相似的定义。

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

1）“这是一本好书”

2）“这些不是好书”

（移除、插入、删除或更改以将 (2) 变为 (1) 的字母数量称为“编辑距离”。）

要实现这一点，您需要以编程方式访问每条评论。这可能不像听起来那么昂贵，如果成本太高，您可以将比较作为后台任务进行，并将 n-most-simimiar 存储在数据库字段本身中。

另一种方法是了解（拉丁）语言的结构。如果您去除短（非大写或引用）单词，并为常见或独特的单词（或前缀）分配权重，您可以进行贝叶斯式比较。以下两个书评可能会被简化并发现是相似的：

3）“法国革命是胡说八道的战争与和平胡说八道的法国。” -> France/French(2) Revolution(1) War(1) Peace(1)

4）“这本书是法国美食的一场革命。” -> 法国(1) 革命(1)

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

书籍也有分类——以法国为背景的惊悚片是否类似于法国的历史研究，等等？标题和文本之外的元数据可能有助于保持结果的相关性。

score 10 · Accepted Answer

此链接上的教程听起来可能是您需要的。它很容易理解并且效果很好。

他的算法奖励公共子串和这些子串的公共排序，因此应该很好地挑选出相似的标题。

score 3 · Accepted Answer

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

score 3 · Accepted Answer

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

score 2 · Accepted Answer

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

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

score 2 · Accepted Answer

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

score 2 · Accepted Answer

也许您正在寻找的是可以解释的东西。我对此只有粗略的了解，但释义是一种自然语言处理概念，用于确定两段文本是否实际上表示相同的意思——尽管可能使用完全不同的词。

不幸的是，我不知道有任何工具可以让你做到这一点（尽管我有兴趣找到一个）

score 1 · Accepted Answer

如果您正在寻找相似的词，您可以转换为 soundex 和要匹配的 soundex 词......对我有用

score 1 · Accepted Answer

我尝试了一些方法，但没有一个效果很好。可能会得到这样一个相对满意的结果：首先：为所有文本的每个段落获取一个 Google SimHash 代码并将其存储在数据库中。第二：SimHash 代码的索引。第三：如上处理你要比较的文本，得到一个 SimHash 码，并通过 SimHash 索引搜索所有文本，它们之间形成一个 5-10 的汉明距离。然后将相似性与术语向量进行比较。这可能适用于大数据。

score 1 · Accepted Answer

你可以使用以下

Minhash/LSH https://en.wikipedia.org/wiki/MinHash

（另见：http : //infolab.stanford.edu/~ullman/mmds/book.pdf Minhash 章节），另见http://ann-benchmarks.com/了解最新技术

如果您有用户与文章交互的信息（点击/喜欢/查看），则协同过滤：https ://en.wikipedia.org/wiki/Collaborative_filtering
word2vec 或类似的嵌入来比较“语义”向量空间中的文章：https ://en.wikipedia.org/wiki/Word2vec
潜在语义分析：https ://en.wikipedia.org/wiki/Latent_semantic_analysis
使用 Bag-of-words 并应用一些距离度量，例如 Jaccard 系数来计算集合相似度https://en.wikipedia.org/wiki/Jaccard_index，https://en.wikipedia.org/wiki/Bag-of-words_model

score 1 · Accepted Answer

@alex77 答案中的链接指向该文章作者独立发现的Sorensen-Dice 系数- 这篇文章写得很好，值得一读。

我最终根据自己的需要使用了这个系数。但是，原始系数在处理时可能会产生错误的结果

包含一个拼写错误的三个字母单词对，例如[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>

请注意最后一个示例中的故意拼写错误： abraca dabra vs abraca badra。即使没有应用额外的二元校正，报告的系数也是 0.9。修正后应该是 0.91。

score 1 · Accepted Answer

给定一个示例文本，该程序列出了按相似度排序的存储库文本：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);
}

score 0 · Accepted Answer

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

您正在使用哪些技术？

score 0 · Accepted Answer

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

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

15 回答 15

Related

Reference