Finde größten Cluster eines bestimmten Wortes in einem Textblock

Question

Ich habe einen Textblock (beliebiger Länge) mit einem bestimmten Wort gelb hervorgehoben, wenn es erscheint. Ich möchte nur einen 400-Wort-Chunk des Textes zeigen, aber ich möchte den Chunk mit den hervorgehobenen Wörtern zeigen.

Kennt jemand einen guten Algorithmus dafür?

Ich habe die Zeichenposition jedes hervorgehobenen Wortes, also muss der Algorithmus den dichtesten Cluster von ungleichmäßig verteilten ganzen Zahlen finden?

Answer 1

Ich bin nicht sicher, wie Sie wissen, dass sie hervorgehoben sind, aber hier ist eine einfache O (n) -Approach, die ich versuchen würde.

scannen Sie die Wörter in eine ringförmige Warteschlange (max. Kapazität von 400) und wenn sie hervorgehoben sind, erhöhen Sie den Zähler, sobald Sie die Warteschlangenkapazität erreicht haben, entziehen Sie die Wörter, um den nächsten in die Warteschlange einzureihen. Wenn Sie ein hervorgehobenes Wort entfernen, dekrementieren Sie den Zähler. Behalte den maximalen Wert im Auge, den dein Zähler zu jeder Zeit erreicht, und wo dieser Block von 400 Wörtern bei max.

nicht zu elegant, aber ziemlich einfach.

Answer 2

Sie könnten einen Wort-für-Wort-Durchschnitt (über die letzten 400 Wörter) tun, während Sie das bisher gesehene Maximum verfolgen. Wenn Sie fertig sind, sagt Ihnen Ihr Maximum, welche 400 Wörter verwendet werden sollen.

Answer 3

Das ist nicht genau das, wonach Sie gefragt haben, aber ich habe in der Vergangenheit so etwas verwendet, während ich nach den Wörtern gesucht habe (charPos bezieht sich auf die Anfangszeichenposition des Wortes). Hinweis: Die '/' Operator tut Integer-Division, also 4200/2000 = 2.

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

Nachdem die Suche abgeschlossen ist, charPositionHashtable hat eine Reihe von Schlüssel/Wert-Paare einen "Index" auf 2000 Zeichen Stücke enthält, und die Anzahl der gefundenen Wörter in ihnen. Nimm das Maximum und verwende den Chunk, der diesem Index entspricht. Das hat den Vorteil, besser zu sein als O (n), denke ich (aber ich habe nicht viel Analyse dazu gemacht).

Answer 4

Sie haben die Indizes der hervorgehobenen Wörter .. Ich denke, die unten ist eine gute, schnelle Ansatz, da es nicht "jedes Wort finden" (um die Kreisschleife zu tun). Um dies zu tun, verwendet es eine "Chunk-Größe", die von einer Anzahl von Zeichen anstelle von Wörtern abgeleitet ist. Sie könnten dann auf die nächste Wortendung "aufrunden" oder "abrunden" und dort haben Sie Ihren Brocken.

Die Methode zu erhalten, wie viele hervorgehobene Indices innerhalb einer "Chunk-Größe" voraus in Ihrer Probe sind, könnte besser gemacht werden, denke ich.

Pseudo

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