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

Question

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

Как сделать эту операцию менее трудоемкой? Какие стратегии / решения?

-Snehal

Answer 1

Как насчет создания двоичного дерева ключей слов (когда вы продолжаете читать слова из файла). Это помогает искать уже повторенные слова в O (Log (n)). Итак, в итоге вы получаете O (nLog (n)) для поиска по верхнему слову.

Основной алгоритм будет

для каждого слова в файле:

1. Создать уникальный ключ для данного слова (взвешенный символ ascii, например, "bat" может быть 1 * 'b' + 2 * 'a' + 3 * 'c';
2. Добавьте это слово к дереву. Если слово уже существует, увеличьте новый счетчик.
3. Подача слова и текущего счетчика для веденияTop5 (word, count). keepTop5 () поддерживает динамический список количества лучших 5 и связанных слов.

В конце файла у вас 5 лучших слов.

Answer 2

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

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