logo标签列表

寻找相似文本文章的算法

stringalgorithmtextlanguage-agnosticsimilarity
63

我有一个数据库中存储了许多文章(包括标题和正文)。我正在寻找一种算法，能够找到与某篇文章最相似的X篇文章，就像在Stack Overflow当你提出问题时看到的"Related Questions"那样。

我试着通过谷歌搜索，但是只找到了其他类似的"相似文本"问题页面，例如将每篇文章与所有其他文章进行比较并在某处存储相似性。而SO在我刚刚输入的文本上实时进行了处理。

如何实现呢？

15个回答
34

编辑距离不太可能成为选择，因为它与拼写和单词顺序有关，并且在考虑到您实际感兴趣的搜索文档的大小和数量时，比Will所说的要更加计算密集。

像Lucene这样的工具是最好的选择。您可以对所有文档进行索引，然后当您想要查找类似于给定文档的文档时，将您的给定文档转换为查询，并搜索索引。在内部，Lucene将使用tf-idf和倒排索引来使整个过程所需的时间与可能匹配的文档数量成正比，而不是与整个集合中的文档总数成正比。

14

这取决于你对“相似”一词的定义。

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

1）“这是一本好书”

2）“这些不是好书”

（将（2）转换为（1）所需的删除、插入、删除或更改字母的数量称为“编辑距离”。）

要实现这个功能，您需要以编程方式访问每个评论。这可能没有听起来那么昂贵，如果太昂贵，您可以将比较作为后台任务执行，并将n个最相似的存储在数据库字段中。

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

3）“法国革命是嗯嗯 咆哮与平息嗯嗯 法国。”-> France/French（2）Revolution（1）War（1）Peace（1）（请注意，已使用字典将“France”和“French”组合起来）

4）“这本书是嗯嗯法国菜的一次革命。”-> France（1）Revolution（1）

要实现这个功能，您需要在创建/更新评论时识别评论中的“关键词”，并在查询的where子句中使用这些关键词查找相似的评论（如果数据库支持，则最好使用“全文”搜索），然后对结果集进行后处理以得分。

图书还有分类-在法国的惊悚小说是否类似于关于法国历史的研究等等？除标题和文本之外的元数据可能有助于保持结果相关。

10

这个链接上的教程似乎是你需要的。它易于跟随并且效果非常好。

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

3
我建议使用 Apache Lucene 对文章进行索引，它是一个高性能、功能齐全的文本搜索引擎库，完全由 Java 编写。它适用于几乎所有需要全文搜索的应用程序，特别是跨平台应用程序。一旦索引完成，你可以轻松地找到相关文章。
3

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

2

您可以使用以下方法：

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

(还可参见：http://infolab.stanford.edu/~ullman/mmds/book.pdf Minhash 章节)，也可参见http://ann-benchmarks.com/以了解最新技术。

  1. 如果您有用户与文章的互动信息（点击/喜欢/查看等），可以使用协同过滤算法：https://en.wikipedia.org/wiki/Collaborative_filtering

  2. 使用Word2vec或类似的嵌入技术，在“语义”向量空间中比较文章：https://en.wikipedia.org/wiki/Word2vec

  3. 使用潜在语义分析：https://en.wikipedia.org/wiki/Latent_semantic_analysis

  4. 使用词袋模型，并应用一些距离度量，如Jaccard系数来计算集合相似度：https://en.wikipedia.org/wiki/Jaccard_index, https://en.wikipedia.org/wiki/Bag-of-words_model

2

SO只对问题的标题进行比较，不会对正文进行比较，所以仅对短字符串进行比较。

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

2
2
也许你正在寻找的是能够进行改写的工具。我只有一些基础知识，但改写是自然语言处理的一个概念，用于确定两个文本段落是否实际上具有相同的意思，即使它们可能使用完全不同的单词。
不幸的是，我不知道任何可以让你做到这一点的工具（尽管我很感兴趣找到一个）。
另一个关于改写的问题... https://dev59.com/aHVD5IYBdhLWcg3wTJvF - Vinnie
1
给定一段示例文本，该程序会按相似性排序列出存储库文本： 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);
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接