Вход: положительное целое число K и большой текст. Фактически текст можно рассматривать как последовательность слов. Поэтому нам не нужно беспокоиться о том, как разбить его на последовательность слов.
Вывод: K наиболее часто встречающихся слов в тексте.
Я думаю так.
используйте хеш-таблицу для записи частоты всех слов при обходе всей последовательности слов. На этом этапе ключом является «слово», а значением - «частота слова». Это занимает O (n) времени.
отсортировать пару (слово, частота слова); и ключ - "частота слов". Это занимает O (n * lg (n)) времени с обычным алгоритмом сортировки.
После сортировки мы берем только первые K слов. Это занимает O (K) времени.
Подводя итог, общее время составляет O (n + n lg (n) + K) , Поскольку K, безусловно, меньше N, то на самом деле это O (n lg (n)).
Мы можем это улучшить. На самом деле, нам просто нужны первые K слов. Частота других слов нас не волнует. Итак, мы можем использовать «частичную сортировку кучи». На шагах 2) и 3) мы не просто выполняем сортировку. Вместо этого мы меняем его на
2 ') построить кучу пар (слово, частота слова) с ключом "частота слова". На создание кучи уходит O (n) времени;
3 ') извлечь из кучи верхних K слов. Каждое извлечение составляет O (lg (n)). Итак, общее время O (k * lg (n)).
Подводя итог, это решение стоит времени O (n + k * lg (n)).
Это просто моя мысль. Я не нашел способа улучшить шаг 1).
Я надеюсь, что некоторые специалисты по информационному поиску смогут пролить больше света на этот вопрос.
источник
Ответы:
Это можно сделать за O (n) раз
Решение 1:
Шаги:
Подсчитайте слова и хешируйте их, в итоге получится такая структура.
Просмотрите хеш и найдите наиболее часто используемое слово (в данном случае "foo" 100), затем создайте массив такого размера.
Затем мы можем снова пройти по хешу и использовать количество вхождений слов в качестве индекса массива, если в индексе ничего нет, создайте массив, иначе добавьте его в массив. В итоге мы получаем такой массив:
Затем просто пройдитесь по массиву с конца и соберите k слов.
Решение 2:
Шаги:
источник
Как правило, вы не получите лучшего времени выполнения, чем описанное вами решение. Вы должны выполнить как минимум O (n) работы, чтобы оценить все слова, а затем O (k) дополнительной работы, чтобы найти верхние k терминов.
Если ваш набор задач действительно велик, вы можете использовать распределенное решение, такое как map / reduce. Пусть n обработчиков карт подсчитывают частоту для каждой 1 / n-ой текста, и для каждого слова отправляйте его одному из m рабочих редукторов, рассчитанных на основе хэша слова. Затем редукторы суммируют счет. Сортировка слиянием результатов редукторов даст вам самые популярные слова в порядке их популярности.
источник
Небольшая вариация вашего решения дает алгоритм O (n) , если мы не заботимся о ранжировании верхнего K, и решение O (n + k * lg (k)), если мы это делаем. Я считаю, что обе эти границы оптимальны в пределах постоянного множителя.
Оптимизация здесь снова происходит после того, как мы пробежимся по списку, вставив его в хеш-таблицу. Мы можем использовать алгоритм медианы медиан , чтобы выбрать K-й по величине элемент в списке. Этот алгоритм доказуемо O (n).
После выбора K-го наименьшего элемента мы разбиваем список вокруг этого элемента так же, как при быстрой сортировке. Очевидно, это тоже O (n). Все, что находится на «левой» стороне оси вращения, находится в нашей группе из K элементов, так что мы закончили (мы можем просто выбросить все остальное по мере продвижения).
Итак, эта стратегия такова:
Если вы хотите ранжировать K элементов, просто отсортируйте их с помощью любой эффективной сортировки сравнения за время O (k * lg (k)), что даст общее время выполнения O (n + k * lg (k)).
Граница времени O (n) оптимальна в пределах постоянного множителя, потому что мы должны проверять каждое слово хотя бы один раз.
Граница времени O (n + k * lg (k)) также оптимальна, потому что не существует основанного на сравнении способа отсортировать k элементов за время меньше, чем k * lg (k).
источник
Если ваш «большой список слов» достаточно велик, вы можете просто выбрать и получить оценки. В остальном мне нравится агрегация хешей.
Редактировать :
Под образцом я подразумеваю выбор некоторого подмножества страниц и вычисление наиболее частого слова на этих страницах. Если вы выбираете страницы разумным образом и выбираете статистически значимую выборку, ваши оценки наиболее часто используемых слов должны быть разумными.
Этот подход действительно разумен только в том случае, если у вас так много данных, что обрабатывать их все просто глупо. Если у вас всего несколько мегабайт, вы сможете просмотреть данные и вычислить точный ответ, не беспокоясь, вместо того, чтобы беспокоиться о подсчете оценки.
источник
Вы можете еще больше сократить время, разбив на части по первой букве слов, а затем разбив самый большой набор из нескольких слов с помощью следующего символа, пока не получите k наборов из одного слова. Вы могли бы использовать 256-стороннее дерево сортировки со списками частичных / полных слов на концах. Вам нужно будет быть очень осторожным, чтобы не создавать копии строк повсюду.
Это алгоритм O (m), где m - количество символов. Это позволяет избежать этой зависимости от k, что очень хорошо для больших k [кстати, ваше опубликованное время работы неверно, оно должно быть O (n * lg (k)), и я не уверен, что это с точки зрения м].
Если вы запустите оба алгоритма бок о бок, вы получите то, что, я уверен, является асимптотически оптимальным алгоритмом O (min (m, n * lg (k))), но мой в среднем должен быть быстрее, потому что он не включает хеширование или сортировка.
источник
В вашем описании есть ошибка: подсчет занимает O (n) времени, а сортировка занимает O (m * lg (m)), где m - количество уникальных слов. Обычно это намного меньше, чем общее количество слов, поэтому, вероятно, следует просто оптимизировать способ построения хеша.
источник
Ваша проблема такая же: http://www.geeksforgeeks.org/find-the-k-most-frequent-words-from-a-file/
Используйте Trie и min heap, чтобы эффективно решить эту проблему.
источник
Если вам нужен список из k наиболее часто встречающихся слов в вашем тексте для любого практического k и для любого естественного языка, то сложность вашего алгоритма не имеет значения.
Просто пример , скажем, несколько миллионов слов из текста, процесс , который с любым алгоритмом в считанные секунды , и наиболее частых импульсов будет очень точным.
В качестве примечания: сложность фиктивного алгоритма (1. подсчитать все 2. отсортировать подсчеты 3. выбрать лучшее) составляет O (n + m * log (m)), где m - количество разных слов в вашем текст. log (m) намного меньше, чем (n / m), поэтому остается O (n).
Практически длинный шаг на счету.
источник
Вот код
}
Вот модульные тесты
Для получения дополнительной информации см. Этот тестовый пример
источник
используйте хеш-таблицу для записи частоты всех слов при обходе всей последовательности слов. На этом этапе ключом является «слово», а значением - «частота слова». Это занимает O (n) времени. Это то же самое, что и все, что описано выше.
Во время самой вставки в хэш-карту сохраните Treeset (специфичный для java, есть реализации на каждом языке) размером 10 (k = 10), чтобы сохранить 10 самых часто используемых слов. Пока размер меньше 10, продолжайте добавлять. Если размер равен 10, если вставленный элемент больше минимального элемента, то есть первого элемента. Если да, удалите его и вставьте новый элемент
Чтобы ограничить размер набора деревьев, перейдите по этой ссылке
источник
Предположим, у нас есть последовательность слов «ad» «ad» «boy» «big» «bad» «com» «come» «cold». И К = 2. как вы упомянули "разбиение по первой букве слов", мы получили ("ad", "ad") ("boy", "big", "bad") ("com" "come" "cold") "then разбивая самый большой набор из нескольких слов с помощью следующего символа, пока не будет k наборов из одного слова. " он будет разделен («мальчик», «большой», «плохой») («com» «come» «холодный»), первый раздел («ad», «ad») будет пропущен, а «ad» - это фактически самое частое слово.
Возможно, я неправильно понимаю вашу точку зрения. Не могли бы вы подробно описать процесс создания разделов?
источник
Я считаю, что эту проблему можно решить с помощью алгоритма O (n). Мы могли производить сортировку на лету. Другими словами, сортировка в этом случае является подзадачей традиционной задачи сортировки, поскольку только один счетчик увеличивается на единицу каждый раз, когда мы обращаемся к хеш-таблице. Изначально список отсортирован, так как все счетчики равны нулю. Поскольку мы продолжаем увеличивать счетчики в хеш-таблице, мы сохраняем еще один массив хеш-значений, упорядоченных по частоте следующим образом. Каждый раз, когда мы увеличиваем счетчик, мы проверяем его индекс в ранжированном массиве и проверяем, превышает ли его счетчик значение своего предшественника в списке. Если это так, мы меняем эти два элемента местами. Таким образом, мы получаем решение, которое не превышает O (n), где n - количество слов в исходном тексте.
источник
Я тоже боролся с этим и меня вдохновил @aly. Вместо последующей сортировки мы можем просто поддерживать предварительно отсортированный список слов (
List<Set<String>>
), и слово будет в наборе в позиции X, где X - текущий счетчик слова. В общем, вот как это работает:Map<String, Integer>
.Недостатком этого является то, что список может быть большим - его можно оптимизировать, используя
TreeMap<Integer, Set<String>>
- но это добавит накладных расходов. В конечном итоге мы можем использовать смесь HashMap или нашу собственную структуру данных.Код
источник
Я просто нашел другое решение этой проблемы. Но я не уверен, что это правильно. Решение:
источник
Постарайтесь придумать особую структуру данных для решения таких проблем. В этом случае особый вид дерева, такой как trie, для хранения строк определенным образом, очень эффективен. Или второй способ создать собственное решение, например, подсчет слов. Я предполагаю, что этот ТБ данных будет на английском языке, тогда у нас в целом около 600000 слов, поэтому можно будет хранить только эти слова и подсчитать, какие строки будут повторяться + этому решению потребуется регулярное выражение для устранения некоторых специальных символов. Я уверен, что первое решение будет быстрее.
http://en.wikipedia.org/wiki/Trie
источник
Это интересная идея для поиска, и я смог найти этот документ, связанный с Top-K https://icmi.cs.ucsb.edu/research/tech_reports/reports/2005-23.pd f
Также есть реализация его здесь .
источник
Самый простой код для определения появления наиболее часто используемого слова.
источник
В таких ситуациях я рекомендую использовать встроенные функции Java. Поскольку они уже хорошо протестированы и стабильны. В этой задаче я нахожу повторения слов с помощью структуры данных HashMap. Затем я помещаю результаты в массив объектов. Я сортирую объект по Arrays.sort () и печатаю k первых слов и их повторы.
Для получения дополнительной информации посетите https://github.com/m-vahidalizadeh/foundations/blob/master/src/algorithms/TopKWordsTextFile.java . Я надеюсь, что это помогает.
источник
I recommend to use Java built-in features
Например, циклы foreach и обработка потоков ?)**
};
источник