在文本块中查找特定单词的最大簇

Question

我有一段文本（任意长度），并且每当出现特定单词时都会用黄色突出显示。我只想显示400字的文字块，但我想用最突出的单词显示块。

有没有人知道一个很好的算法呢？

我有每个突出显示的单词的字符位置，所以算法需要找到不均匀间隔整数的最密集的集群？

Answer 1

我不确定你是如何知道它们被突出显示的，但是这里有一个我想尝试的简单的O（n）方法。

将单词扫描成一个循环队列（最大容量为400），如果它们被突出显示，则增加计数器，一旦你达到队列容量，按照需要将队列出队以排队下一个队列。当您将突出显示的字出列时，会减少计数器。跟踪您的计数器在任何时候达到的最大值以及这个400字的块在最大值处开始的位置。

不太优雅，但相当简单。

Answer 2

您可以逐字移动平均值（超过400个单词），同时记录迄今为止所见的最大值。完成后，最大限度地告诉你要使用400个单词。

Answer 3

这不完全是你要求的，但我在过去使用类似的东西，而搜索单词（charPos指的是单词的起始字符位置）。注：“/”操作者确实整数除法，即二千分之四千二= 2

if hasKey(charPositionHashtable[charPos/2000]): 
    charPositionHashtable[charPos/2000]) += 1 
else: 
    charPositionHashtable[charPos/2000]) = 1 

在搜索完成之后，charPositionHashtable有一堆包含“索引”，以2000个字符的块的键/值对，以及他们发现的单词的数量。取最大值，并使用该索引对应的块。这有好处比O（n）好，我想（但我没有做过很多分析）。

Answer 4

你有突出显示的单词的标记..我认为下面是一个好的，快速的方法，因为它不需要“找到”每个单词（做循环循环）。要做到这一点，它使用了一个由大量字符而不是单词产生的“块大小”。然后，您可以“围绕”或“向下滚动”到最近的单词结尾，然后您就可以拥有大块。

在我的例子中，可以更好地完成在样本中获得多少突出显示的标记位于“块大小”内的方法。

伪

string GetHighestDensityChunk(){ 

// {chunk size} = 400 * average word length 
// {possible start positions} = 0, highlighted indicies, and (sample - {chunk size}) 

int position 
int bestPositionSoFar = 0 
int maxHighLightedCountSoFar = 0 


for each position in {possible start position} 
{ 
    highlightedCount = GetNumberOfHighlightedWithinChunkSize(position) 

    if(highlightedCount > maxHighLightedCountSoFar) 
    { 
     maxHighLightedCountSoFar = highlightedCount 
     bestPositionSoFar = position 
    } 
} 

// "round up" to nearest word end 
// gives index of next space after end of chunk starting from current best position 
{revised chunk size} = sample.indexOf(' ', startingAt = bestPositionSoFar + {chunk size}) - bestPositionSoFar 

return sample.substring(bestPositionSoFar, {revised chunk size}) 
} 


int GetNumberOfHighlightedWithinChunkSize(position) 
{ 
    numberOfHighlightedInRange = 0 

    // starts from current position and scans forward counting highlighted indicies that are in range 
    for(int i= {possible start position}.indexOf(position); i<= {possible start position}.length; i++){ 
     if({possible start position}[i] < position + {chunk size}){ 
      numberOfHighlightedInRange++; 
     } else { 
      break; 
     } 
    } 
    return numberOfHighlightedInRange; 
}