java快速高效的数组计算

Question

我想计算文档中某个特定短语的发生次数。例如“stackoverflow论坛”。假设D表示包含这两个术语的文档集

现在，假设我有以下数据结构：

A[numTerms][numMatchedDocuments][numOccurInADocument] 

其中numMatchedDocuments是D的大小，NumOccuranDocument是特定术语在特定文档中出现的次数，例如：

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

表示术语“stackoverflow”出现在文件“document1”中，第一次出现在位置“3”

然后，我选择出现最少的术语，并在其所有位置上循环，以确定“论坛”是否出现在+1位置，即当前术语“stackoverflow”位置。换句话说，如果我在第4位找到“论坛”，那么这就是一个短语，我已经找到了一个匹配项

每个文档的匹配都很简单，运行速度也相当快，但当文档数超过2000000时，速度会非常慢。我已经将其分布到了内核上，当然速度会更快，但我想知道是否有算法上更好的方法来实现这一点

谢谢

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

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

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

如果将其扩展到返回每个文档中短语匹配的计数，那将是微不足道的

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