Найти самый большой кластер конкретного слова в блоке текста

Question

У меня есть блок текста (произвольной длины) с определенным словом, выделенным желтым цветом, когда оно появляется. Я хочу показать фрагмент текста только из 400 слов, но хочу показать фрагмент с наиболее выделенными словами.

Кто-нибудь знает хороший алгоритм для этого?

У меня есть положение символов каждого выделенного слова, поэтому алгоритм должен найти самый плотный кластер из неравномерно расположенных целых чисел?

Answer 1

Я не уверен, откуда вы знаете, что они выделены, но вот простой O (n) подход, который я бы попробовал.

сканирует слова в круговую очередь (максимальная емкость 400) и, если они выделены, увеличивает счетчик, как только вы достигнете емкости очереди, удалите слова из очереди, как это необходимо, чтобы поставить в очередь следующую. когда вы удаляете выделенное слово, счетчик уменьшается. Следите за максимальным значением, которое ваш счетчик всегда достигает, и где этот фрагмент из 400 слов начинается с максимума.

не слишком элегантно, но довольно просто.

Answer 2

вы можете сделать пословную скользящую среднюю (за последние 400 слов), сохраняя при этом отслеживаемый максимум. Как только вы закончите, ваш максимум скажет вам, какие 400 слов использовать.

Answer 3

У вас есть признаки выделенных слов ... Я думаю, что ниже это хороший, быстрый подход, так как он не требует "нахождения" каждого слова (для выполнения кругового цикла). Для этого он использует «размер куска», полученный из ряда символов, а не слов. Затем вы могли бы «округлить вверх» или «округлить вниз» до ближайшего окончания слова, и там у вас есть кусок.

Метод, позволяющий определить, сколько выделенных признаков находится в пределах «размера фрагмента» в вашем образце, может быть лучше, я думаю.

Псевдо

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

Answer 4

Это не совсем то, что вы просили, но я использовал что-то подобное в прошлом при поиске слов (charPos относится к начальной позиции символа в слове). Примечание: оператор '/' выполняет целочисленное деление, то есть 4200/2000 = 2.

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

После завершения поиска, charPositionHashtable имеет набор пар ключ / значение, содержащих «индекс» до 2000-символьных блоков и количество найденных в них слов. Возьмите максимум и используйте кусок, соответствующий этому индексу. Я думаю, это имеет преимущество в том, что лучше, чем O (n) (но я не много анализировал это).