快速高效的数组计算

Question

我想计算文档中特定短语的出现次数.例如"stackoverflow论坛".假设D表示使用包含两个术语的文档设置的文档.

现在,假设我有以下数据结构:

A[numTerms][numMatchedDocuments][numOccurInADocument] 

其中numMatchedDocuments是D的大小,numOccurInADocument是特定术语在特定文档中出现的次数,例如:

A[stackoverflow][document1][occurance1]=3;

意味着,术语"stackoverflow"出现在文档"document1"中,并且它的第一次出现在位置"3".

然后我选择发生最少的术语并遍历其所有位置,以查找"论坛"是否出现在当前术语"stackoverflow"位置+ 1的位置.换句话说,如果我在第4位找到"论坛",那么这是一个短语,我找到了匹配.

每个文档的匹配很简单,并且运行速度相当快,但是当文档数量超过2,000,000时,它变得非常慢.我已经将它分发到核心上,当然它变得更快但是想知道是否有更好的算法.

谢谢,

Psudo码:

boolean docPhrase=true;
int numOfTerms=2;
// 0 for "stackoverflow" and 1 for "forums"
for (int d=0;d<D.size();d++){
 //D is a set containing the matched documents
 int minId=getTheLeastOccuringTerm();
 for (int i=0; i<A[minId][d].length;i++){ // For every position for LeastOccuringTerm
   for( int t=0;t<numOfTerms;t++){ // For every terms
      int id=BinarySearch(A[t][d], A[minId][d][i] - minId + t);
      if (id<0) docPhrase=false;
   }
 }
}

Answer 1

正如我在评论中提到的，后缀数组可以解决此类问题。我用后缀数组的简单 C# 实现回答了类似的问题（Fastest way to search a list of name in C #）。

基本思想是有一个索引对数组，它们指向文档索引以及该文档中的位置。索引对表示从文档中的该点开始并持续到文档末尾的字符串。但实际的文档及其内容在您的原始存储中仅存在一次。后缀数组只是这些索引对的数组，每个文档中的每个位置都有一对。然后，您可以按照后缀数组指向的文本顺序对后缀数组进行排序。排序后，您现在可以通过在后缀数组上执行简单的二分搜索来快速找到任何文档中的任何短语。构建（主要是排序）后缀数组可能非常耗时。但一旦构建完成，搜索速度就会非常快。由于实际的文档内容只存在一次，因此内存相当容易。

将其扩展为返回每个文档中短语匹配的计数是很简单的。

这与后缀数组的经典描述有点不同，后缀数组通常谈论的是在一个非常大的字符串上操作的后缀数组。但是，使其适用于字符串/文档数组的更改并没有那么大，尽管它可能会增加后缀数组消耗的内存量，具体取决于最大文档数和最大文档长度以及对后缀数组进行编码的方式索引对。