Как найти высокочастотные слова в книге в среде низко на памяти?

Хорошо, если вас интересуют только старшие n встречающихся слов, один из способов сделать это - два прохода с первым проходом на основе модифицированного фильтра Блума . Вместо того, чтобы использовать битовую карту для отслеживания вхождений хеша, используйте вместо этого целочисленный массив - байтовый, 16-битный, 32-битный или даже 64-битный в зависимости от вашего размера ввода. Там, где фильтр Блума просто устанавливает бит, соответствующий каждому из значений хеш-функции слова, вы увеличиваете счетчик по хеш-индексу в массиве.

Проблема этого подхода состоит в том, что два слова, вероятно, дадут одно и то же хэш-значения Таким образом, вам нужно сделать второй проход, где вы игнорируете слова, если их хэш-суммы не превышают определенного порога, что уменьшает объем памяти, который вам нужно выделить для точного подсчета.

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

Я физик, поэтому мой любимый подход - приближаться. Вам не нужно просматривать весь текст , чтобы получить наиболее часто встречающиеся слова. Вместо этого:

• анализировать фрагмент, достаточно маленький, чтобы учесть ограничения памяти,
• пропустить случайный объем текста,
• повторить, объединяя накопленные результаты.
• Остановиться, когда список удовлетворительно сходится.

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

Примечание Это делает предположение, что наиболее часто встречающиеся слова встречаются чаще всего по всему тексту, а не только в одном месте текста. Для английского текста это предположение верно, из-за частоты таких слов, как «и т. д.» во всем. Если вас беспокоит это требование, попросите алгоритм выполнить хотя бы один проход всего текста.

Скорее всего, за это проголосуют ...

Если текст на английском и вы просто хотите найти 5 самых популярных слов, вот ваша программа:

print "1. the\n";
print "2. of\n";
print "3. and\n";
print "4. a\n";
print "5. to\n";

Быстро бегает и потребляет минимум памяти!

Если производительность на самом деле не имеет значения, вы можете просто просмотреть каждое слово по очереди, проверьте, находится ли оно в верхней N "и, если это не так, подсчитайте все его вхождения. Таким образом, вы храните только N значений. Конечно, вы будете считать одни и те же слова много раз, но, как вы сказали, производительность не является проблемой - и код будет тривиальным (что обычно предпочтительнее - при прочих равных условиях).

Один из способов - это сначала отсортировать список.

Мы можем отсортировать слова на месте без особого памяти (торгуется с низкой производительностью).

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

Вы имеете в виду много памяти процесса? Если это так, то один из способов - использовать диск в качестве виртуальной памяти (он же пишет обертку файловой системы).

Возможное решение - использовать структуру данных trie для хранения всех слов, связанных с их числом

Другие решения могут быть найдены в ответах на этот связанный вопрос: Компактная структура данных для хранения списка слов?

Как и многие хорошие вопросы для интервью, вопрос сформулирован несколько двусмысленно / неточно, чтобы заставить собеседника задавать уточняющие вопросы и государственные предположения. Я думаю, что некоторые другие ответы здесь хороши, так как они основаны на этих предположениях и демонстрируют понимание в целом.

Я предполагаю, что текст хранится где-то «в автономном режиме», но есть способ перебирайте каждое слово в тексте, не загружая весь текст в память.

Затем код F # ниже находит первые N слов. Единственная структура данных - это отображение пар ключ-значение (слово, частота), и оно удерживает только верхние N из них, поэтому использование памяти равно O (N), что мало. Время выполнения равно O (numWordsInText ^ 2), что плохо, но приемлемо с учетом проблемных ограничений. Суть алгоритма проста: для каждого слова в тексте подсчитайте, сколько раз оно встречается, и, если оно находится в числе лучших N, добавьте его в список и удалите предыдущую минимальную запись.

Обратите внимание, что Фактическая программа ниже загружает весь текст в память, просто для удобства изложения.

#light
// some boilerplate to grab a big piece of text off the web for testing
open System.IO 
open System.Net 
let HttpGet (url: string) = 
    let req = System.Net.WebRequest.Create(url) 
    let resp = req.GetResponse() 
    let stream = resp.GetResponseStream() 
    let reader = new StreamReader(stream) 
    let data = reader.ReadToEnd() 
    resp.Close() 
    data 
let text = HttpGet "http://www-static.cc.gatech.edu/classes/cs2360_98_summer/hw1"
let words = text.Split([|' ';'\r';'\n'|], System.StringSplitOptions.RemoveEmptyEntries)
// perhaps 'words' isn't actually stored in memory, but so long as we can 
// 'foreach' over all the words in the text we're good
let N = 5  // how many 'top frequency' words we want to find
let FindMin map =
    // key-value pair with mininum value in a map
    let (Some(seed)) = Map.first (fun k v -> Some(k,v)) map
    map |> Map.fold_left 
        (fun (mk,mv) k v -> if v > mv then (mk,mv) else (k,v)) 
        seed
let Main() =
    let mutable freqCounts = Map.of_list [ ("",0) ]
    for word in words do
        let mutable count = 0
        for x in words do
            if x = word then
                count <- count + 1
        let minStr,minCount = FindMin freqCounts
        if count >= minCount then
            freqCounts <- Map.add word count freqCounts
        if Seq.length freqCounts > N then
            freqCounts <- Map.remove minStr freqCounts
    freqCounts 
    |> Seq.sort_by (fun (KeyValue(k,v)) -> -v) 
    |> Seq.iter (printfn "%A")
Main()

Вывод:

[the, 75]
[to, 41]
[in, 34]
[a, 32]
[of, 29]

Ну, если вы хотите абсолютно ужасного представления ...

Возьмите первое слово в книге и сосчитайте сколько раз это происходит Возьмите второе слово в книге, посчитайте, сколько раз оно встречается. Если это больше, чем последнее слово, отбросьте последнее слово. И так далее ... вы будете в конечном итоге считать одни и те же слова несколько раз, если не будете хранить их где-нибудь, но если вы действительно хотите минимизировать память, для этого потребуется всего несколько целых. Должен выполняться за O (n ^ 2) время, где n - количество слов в книге.