快速高效地处理数组的计算

Question

我希望能够统计文档中特定短语的出现次数。例如 "stackoverflow 论坛"。假设 D 表示包含这两个词的文档集。

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

A[numTerms][numMatchedDocuments][numOccurInADocument] 

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

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

意思是，术语“stackoverflow”出现在文档“document1”中，第一次出现的位置为“3”。

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

每个文档的匹配都很简单并且运行速度合理，但是当文档数量超过200万时，速度变得非常慢。我已将其分布在核心上，并且当然会更快，但想知道是否有更好的算法方法来完成此操作。

谢谢，

伪代码：

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;
   }
 }
}

- DotNet

---

也许可以将您当前的实现代码发布出来供参考。 - OmniOwl

你需要预先存储这些吗？还是可以实时填充结构（例如，当人们搜索时）？ - sdasdadas

@sdasdadas 我不确定你所说的“存储”是什么意思。数组并没有被存储，而是从索引中获取，这很快速且没有问题。计数才是问题所在。 - DotNet

听起来像是后缀数组可以解决的问题。这个回答我给出了一个稍微不同的问题，展示了后缀数组的简单实现：https://dev59.com/FmPVa4cB1Zd3GeqP9uDT 在这里和网络上都有相当数量的实现。 - hatchet - done with SOverflow

@DotNet - 你的文档有多大？ - hatchet - done with SOverflow

Answer 1

如我在评论中提到的，后缀数组可以解决这种问题。我曾经回答过一个类似的问题(在C#中搜索名称列表的最快方法)，并给出了一个简单的C#实现的后缀数组。

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

将其扩展以返回每个文档中短语匹配的计数将是微不足道的。

这与后缀数组的经典描述略有不同，后缀数组通常是针对一个单一的非常大的字符串进行操作。但是为了使它适用于字符串/文档数组，所需的更改并不大，尽管这可能会增加后缀数组消耗的内存量，具体取决于文档的最大数量和最大文档长度以及您如何编码索引对。

- hatchet - done with SOverflow