По заданному файлу найдите десять наиболее часто встречающихся слов максимально эффективно

Question

Это, по-видимому, вопрос для собеседования (нашел его в сборнике вопросов для собеседования), но даже если это не так, это довольно круто.

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

Я должен добавить, что ничто в вопросе не говорит о том, что слова не могут быть сохранены в памяти, но что, если это так?Если это не так, тогда вопрос не кажется таким сложным.

Answer 1

Оптимизация для моего собственного времени:

sort file | uniq -c | sort -nr | head -10

Возможно, за которым следует awk '{print $2}', чтобы убрать отсчет.

Answer 2

Я думаю, что структура данных trie - это выбор.

В дереве можно записать количество слов в каждом узле, представляющее частоту слова, состоящего из символов на пути от корня к текущему узлу.

Сложность по времени для установки дерева составляет O (Ln) ~ O (n) (где L - количество символов в самом длинном слове, которое мы можем рассматривать как константу). Чтобы найти первые 10 слов, мы можем пройти три, что также стоит O (n). Поэтому для решения этой проблемы требуется O (n).

Answer 3

Полное решение будет примерно таким:

1. сделать внешнюю сортировку O (N log N)
2. Подсчитать слово freq в файле O (N)
3. (альтернативой будет использование Trie как @Summer_More_More_Tea для подсчета частот, если вы можете позволить себе такой объем памяти) O (k * N) // для двух первых шагов
4. Используйте минимальную кучу:
   • Поместите первые n элементов в кучу
   • Для каждого оставленного слова добавьте его в кучу и удалите новый минимум в куче
   • В конце концов, куча будет содержать n-е наиболее распространенных слов O (| words | * log (n))

С Trie стоимость будет O (k * N), потому что общее количество слов обычно больше, чем размер словаря. Наконец, поскольку k меньше для большинства западных языков, вы можете предположить линейную сложность.

Answer 4

Допустим, мы назначаем случайное простое число каждому из 26 алфавитов. Затем мы сканируем файл. Всякий раз, когда мы находим слово, мы вычисляем его значение хеша (формула, основанная на положении и значении алфавитов, составляющих слово). Если мы находим это значение в хеш-таблице, то мы точно знаем, что мы не встречаемся с ним в первый раз, и мы увеличиваем его значение ключа. И поддерживать массив максимум 10. Но если мы встретим новый хеш, мы сохраняем указатель файла для этого хеш-значения и инициализируем ключ равным 0.

Answer 5

Я сделал в C # вот так (пример)

int wordFrequency = 10;
string words = "hello how r u u u u  u  u u  u  u u u  u u u u  u u u ? hello there u u u u ! great to c u there. hello .hello hello hello hello hello .hello hello hello hello hello hello ";            

var result = (from word in words.Split(new string[] { " " }, StringSplitOptions.RemoveEmptyEntries)
                          group word by word into g
                          select new { Word = g.Key, Occurance = g.Count() }).ToList().FindAll(i => i.Occurance >= wordFrequency);

Answer 6

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

Answer 7

В зависимости от размера входных данных может быть или не быть хорошей идеей сохранять HashMap. Скажем, например, наша хеш-карта слишком велика, чтобы уместиться в основную память. Это может привести к очень большому количеству передач памяти, так как большинству реализаций хэш-карт необходим произвольный доступ и они не очень хорошо работают с кешем.

В таких случаях лучшим решением будет сортировка входных данных.

Answer 8

Говорит, что лучше создать Hash и отсортировать значения. Я склонен согласиться. http://www.allinterview.com/showanswers/56657.html

Вот реализация Bash, которая делает нечто подобное ... Я думаю, http://www.commandlinefu.com/commands/view/5994/computes-the-most-frequent-used-words-of-a-text-file

Answer 9

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

Answer 10

Не самый эффективный процессор и уродливый, но это заняло всего 2 минуты:

perl -lane '$h{$_}++ for @F; END{for $w (sort {$h{$b}<=>$h{$a}} keys %h) {print "$h{$w}\t$w"}}' file | head

Зацикливание каждой строки с -n
Разделите каждую строку на @F слов с помощью -a
Каждое $_ слово увеличивает хэш %h
После достижения END из file,
sort хэшчастота
Напечатайте частоту $h{$w} и слово $w
Используйте bash head, чтобы остановиться на 10 строках

Используя текст этой веб-страницы в качестве ввода:

121     the
77      a
48      in
46      to
44      of
39      at
33      is
30      vote
29      and
25      you

Я сравнил это решение с лучшим решением для оболочки (Бен Джексон) в текстовом файле объемом 3,3 ГБ с 580 000 000 слов.
Perl 5.22 завершен за 171 секунду, а решение оболочки - за 474 секунды.