6

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

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

A[numTerms][numMatchedDocuments][numOccurInADocument]

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

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

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

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

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

谢谢，

伪代码：

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

1 回答 1

2

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

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

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

这与 Suffix Array 的经典描述略有不同，他们通常谈论 Suffix Array 在单个非常大的字符串上运行。但是使其适用于字符串/文档数组的更改并没有那么大，尽管它可以增加 Suffix Array 消耗的内存量，具体取决于最大文档数和最大文档长度，以及您如何编码索引对。

于 2012-12-18T01:24:52.177 回答