查找文本相似文章的算法

Edit distance 不是一个可能的候选人,因为它将取决于拼写/词序,而且计算上比威尔贵得多,这让你相信,考虑到你实际上对搜索感兴趣的文档的大小和数量。

像Lucene这样的东西才是出路。为所有文档编制索引,然后当希望查找与给定文档类似的文档时,可以将给定文档转换为查询,然后搜索索引。内部Lucene将使用 tf-idf 和一个 inverted index 要使整个过程花费的时间与可能匹配的文档数成比例,而不是与集合中的文档总数成比例。

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

这个 edit-distance 算法是(拉丁语)词典建议的标准算法,可以处理整个文本。如果两个文本的单词(eh字母)的顺序基本相同,那么它们是相似的。因此,以下两个书评将相当相似:

1)“这是一本好书”

2)“这些不是好书”

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

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

另一种方法是理解(拉丁语)语言的结构。如果删除短(非大写或引用)单词,并为常见或唯一的单词(或前缀)指定权重,则可以进行贝叶斯比较。以下两篇书评可能是相似的,并且被发现是相似的:

3)“法国大革命是布拉布拉战争和和平布拉法国。”—>法国/法国(2)大革命(1)战争(1)和平(1)(请注意,已使用字典将法国和法国结合起来)

4)“这本书是法国烹饪革命。”—>法国(1)革命(1)

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

书也有分类-惊悚片集在法国类似于法国的历史研究,等等?超出标题和文本的元数据对于保持结果相关可能很有用。

本教程 link 听起来可能是你需要的。这很容易理解,而且效果很好。

他的算法既奖励常见子串,也奖励这些子串的常见顺序,因此应该很好地选择相似的标题。

我建议用 Apache Lucene , 一个高性能、全功能的完全由Java编写的文本搜索引擎库。它是一种适用于几乎所有需要全文搜索的应用程序的技术,尤其是跨平台搜索。 . 一旦建立索引,您就可以很容易地找到相关的文章。

使用的一种常见算法是 Self-Organizing Map . 它是一种自动分类文章的神经网络。然后您可以简单地找到当前文章在地图中的位置,并且它附近的所有文章都是相关的。算法的重要部分是 vector quantize your input . 有几种处理文本的方法。你可以散列你的文档/标题,你可以数数单词,并将其用作N维向量等。希望这有帮助,尽管我可能已经为你打开了一个潘多拉盒子,让你在人工智能中度过了一段漫长的旅程。

所以比较只在题目上,而不是正文上,所以只在相当短的字符串上。

你可以在文章标题和关键词上使用他们的算法(不知道它是什么样子)。 如果您有更多的CPU时间来燃烧,也可以在文章的摘要上。

附上Lucene建议全文,但注意到Java不是必需的; a .NET port is available . 也看到 main Lucene page 用于链接到其他项目,包括 Lucy, a C port .

也许你要找的是一些可以 paraphrasing . 我只是粗略地知道这一点,但释义是 natural language processing 确定两段文字是否 意思是 同样的事情-尽管可能使用完全不同的词。

不幸的是,我不知道有什么工具可以让你这么做(尽管我有兴趣找到一个)

您可以使用SQL Server全文索引进行智能比较,我相信使用Ajax调用也是如此,它执行查询以返回类似的问题。

你在使用什么技术?

如果你在寻找伤害相似的词,你可以转换成soundex和soundex词来匹配…为我工作

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

你可以使用 1)MNHASH/LSH https://en.wikipedia.org/wiki/MinHash

(也见: http://infolab.stanford.edu/~ullman/mmds/book.pdf )

或

2)协同过滤: https://en.wikipedia.org/wiki/Collaborative_filtering

@alex77答案中的链接指向 Sorensen-Dice Coefficient 这篇文章是作者独立发现的——这篇文章写得很好,值得一读。

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

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

在第一种情况下,DICE错误地报告系数为零,而在第二种情况下,系数变为0.5,这是错误的高。

改进 has been suggested 从本质上讲,它包括取单词的第一个和最后一个字符,并创建一个额外的双字。

在我看来,只有三个字母的单词才需要改进——换言之,其他的大单词有一个缓冲效果,可以掩盖问题。 下面给出了实现此改进的代码。

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 达布拉 阿巴卡 巴德拉 . 即使没有额外的双随机校正,报告的系数为0.9。经过修正,应该是0.91。

希望这能帮助其他人。

给定一个示例文本,该程序列出按相似性排序的存储库文本: simple implementation of bag of words in 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的set特性非常适合执行这项任务。你会惊讶地发现,这种方法与GScholar、ADS、WOS或Scopus提供的那些“类似/相关论文”选项相比有多好。