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

Question

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

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

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

Answer 1

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

Answer 2

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

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

шаг 3 : перебирать фрагменты, сортировать фрагменты и всегда сохранять первые десять появлений.

Пример:

Шаг 1 :

a b a 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

Answer 3

A Дерево корней или один из его вариантов, как правило, позволяет сэкономить место на хранилище, сворачивая общие последовательности.
Для его построения потребуется O (nk) - где k - «максимальная длина всех строк в наборе».

Answer 4

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

Answer 5

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