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

Ответ 1

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

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

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

Ответ 2

Я думаю, что trie data structure является выбором.

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

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

Ответ 3

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

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

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

Ответ 4

Я сделал в С#, как это (образец)

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

Ответ 5

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

Ответ 6

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

Ответ 7

Говорит, что создание хеша и сортировка значений лучше всего. Я склонен согласиться. 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

Ответ 8

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

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

Ответ 9

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

Ответ 10

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

Ответ 11

Если список слов не будет помещаться в память, вы можете разделить файл, пока он не появится. Создайте гистограмму каждой части (последовательно или параллельно) и объедините результаты (детали которых могут быть немного затруднительными, если вы хотите гарантировать правильность для всех входов, но не должны ставить под угрозу работу O (n) или O (n/k) для k задач).

Ответ 12

A Дерево Radix или один из его вариантов, как правило, позволит вам сохранить пространство для хранения, сбрасывая общие последовательности.
Построение его займет O (nk) - где k - "максимальная длина всех строк в наборе".

Ответ 13

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

Шаг 2. Для каждого отсортированного фрагмента вычисляемые пары (слова, nr_occurrence), в его точке вы можете отказаться от кусков, потому что вам нужны только отсортированные пары.

Шаг 3. Итерируйте по кускам и сортируйте куски и всегда держите первую десятку.

Пример:

Шаг 1:

a b a ab abb a a b b c c ab ab

разбивается на:

кусок 1: a b a ab
кусок 2: abb a a b b
кусок 3: c c ab ab

Шаг 2:

кусок 1: a2, b1, ab1 кусок 2: a2, b2, abb1
кусок 3: c2, ab2

Шаг 3 (объедините куски и сохраните первую десятку):

a4 b3 ab3 c2 abb1

Ответ 14

    int k = 0;
    int n = i;
    int j;
    string[] stringList = h.Split(" ".ToCharArray(),
                                  StringSplitOptions.RemoveEmptyEntries);
    int m = stringList.Count();
    for (j = 0; j < m; j++)
    {
        int c = 0;
        for (k = 0; k < m; k++)
        {
            if (string.Compare(stringList[j], stringList[k]) == 0)
            {
                c = c + 1;
            }
        }
    }

Ответ 15

Не самый эффективный процессор и UGLY, но потребовалось всего 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 of 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

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