用于文本相似性的算法/库

Question

我需要实现算法(或在开源库中找到一个)来评估文本的相似性.我需要一个有效的算法,给定两个任意文档集(相对较少数量的大块文本),它在它们之间创建匹配对 - 哪个文档最有可能从哪个文档生成.

我相信我会把它分成两部分 - 定义每对的相似系数 - 然后应用一些赋值问题算法.而对于分配算法,我可以找到很多解决方案,我找不到用于计算相似系数的好方法.

请注意,文档事先是未知的 - 文本的计算索引(如果有)也必须快速.

我知道汉明距离,Levenshtein距离一些其他算法的字符串差异.这不是我想要的 - 我正在使用文字而不是字符串.

我不是在寻找短语搜索算法​​以及像Lucene和Xapian这样的库(至少看起来像是这样).

可能是基于tf-idf的东西.

我想问题是,是否有一些东西已经解决了这个问题,或者是否有可能像lucete这样的库来做到这一点.

Answer 1

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

\n\n

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

\n\n

我们可以假设字典大小 < 1m（或 21 位），因此我们可以将三元组编码为 int64。

\n\n

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

\n\n

然后比较每对的结果：

\n\n

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

\n\n

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

\n