5

我需要实现算法（或在开源库中找到一个）来评估文本相似性。对于给定的两组任意文档（相对较少的大文本块），我需要一种有效的算法，以便在它们之间创建匹配对 - 最有可能从哪个文档生成哪个文档。

我相信我会将其一分为二——定义每一对的相似系数——然后应用一些分配问题算法。虽然对于分配算法，我可以找到大量的解决方案，但我找不到用于计算相似系数的好解决方案。

请注意，文档是事先不知道的——文本的计算索引（如果有的话）也必须很快。

我知道汉明距离、列文斯坦距离以及其他一些用于字符串差异的算法。不过，这不是我要找的——我故意使用文本这个词而不是字符串。

我不是在寻找短语搜索算法​​，也不是在寻找像 Lucene 和 Xapian 这样的库的用途（至少看起来是这样）。

可能是基于 tf–idf 的东西。

我想问题是，是否有一些东西已经解决了这个问题，或者是否有可能使用像 lucte 这样的库来解决这个问题。

4

1 回答 1

1

这是我作为起点要做的事情（只是因为它简单快捷）：

  • 使用共享映射或 hash_map 将单词映射到数字
  • 对于每个文本，构建相应的单词级三元组计数图
  • 比较重叠

我们可以假设字典大小小于 1m（或 21 位），所以我们可以在 int64 中编码一个三元组。

void CountTrigrams(const vector<string>& words, 
                   map<string, int> * dict, 
                   map<int64, int> * result) {
  int64 trigram = 0;
  for (int i = 0; i < words.size(); i++) {
    const& word = words[i];
    int id;
    auto di = dict->find(word);
    if (di == dict->end()) {
      id = dict.size();
      dict[word] = id;
    } else {
      id = di->second;
    }
    trigram = ((trigram << 21) | id) & 0x7fffffffffffffff;
    if (i > 2) {
      auto ti = result->find(trigram);
      if (ti == result->end()) {
        result[trigram] = 1;
      } else {
        ti->second++;
      }
    }
  }
}

然后比较每一对的结果： 

int Compare(const map<int64, int> & t1, const map<int64, int> & t2) {
  int score = 0;
  for (auto i = t1.first(); i != t1.end(); i++) {
    auto j = t2.find(t1->first);
    if (j != t2.end()) {
      score += MAX(i->second, j->second);
    }
  }
  return score;
}

以某种方式标准化分数可能是有意义的，例如除以三元组的总数。

于 2013-05-17T04:55:16.007 回答