私は、特定の単語が現れるたびに黄色で強調表示されたテキストブロック（任意の長さ）を持っています。私はテキストの400単語の塊を表示したいが、私は最も強調表示された単語で塊を表示したい。テキストブロック内の特定の単語の最大のクラスタを見つける
これについて誰かが良いアルゴリズムを知っていますか？
私は各強調表示された単語の文字位置を持っているので、アルゴリズムは不均一な間隔の整数の最も密なクラスターを見つける必要がありますか？
どのように強調表示されているかわかりませんが、ここでは簡単なO（n）aproachを試してみます。
ワードを循環キュー（最大400）にスキャンし、強調表示されている場合はカウンタをインクリメントし、キューの容量に達すると、次のキューにエンキューするのに必要なワードをデキューします。ハイライトされた単語をデキューすると、カウンタが減少します。あなたのカウンターが常に到達する最大値と、400ワードのこのチャンクが最大値から始まる最大値を記録します。
あまりにもエレガントではありますが、かなり単純です。
これまでに見た最大値を記録しながら、単語単位での移動平均（過去400ワード）を実行できます。一度やり終えると、あなたの最大値はあなたが使用する400語を教えてくれます。
これはまさにあなたが求めているものではありませんが、これまでのように、単語を検索しながら（charPosは単語の開始文字位置を参照しています）使用しました。注意：「/」演算子は整数の除算を行い、2000分の4200 = 2すなわち
if hasKey(charPositionHashtable[charPos/2000]):
charPositionHashtable[charPos/2000]) += 1
else:
charPositionHashtable[charPos/2000]) = 1
検索が完了した後、charPositionHashtable 2000文字単位に「インデックス」を含むキー/値ペアの束を持って、それらの中に発見された単語の数。最大値をとり、そのインデックスに対応するチャンクを使用します。これはO（n）より優れているという利点があると思います（しかし、私はこれについて多くの分析をしませんでした）。
あなたは強調表示された単語の記号を持っています。以下は、すべての単語を「見つける」（循環ループを行うために）必要としないので、優れた高速アプローチです。これを行うために、単語ではなく文字の数から導かれた "チャンクサイズ"を使用します。次に、最も近い単語の末尾に「切り上げ」または「切り捨て」することができます。そこにあなたのチャンクがあります。
サンプルの先にある「チャンクサイズ」内にいくつのハイライトされたインデックスがあるかを取得する方法は、私が考えるほうがよいでしょう。私はちょうどdangit、書き上げたものだ
擬似
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;
}
1！ –
+1良い答え！ – viksit