Самые частые слова

Question

Какой самый эффективный способ в Java получить 50 наиболее часто встречающихся слов с частотой из текста?

Я хочу найти около 1000000 текстов, каждый из которых содержит около 10000 слов, и надеюсь, что это сработает в разумные сроки.

Answer 1

Наиболее эффективным, вероятно, было бы использование Patricia trie , которое ссылается на max-heap . Каждый раз, когда вы читаете слово, find оно в дереве, идите в кучу и increase-key. Если его нет в базе данных, add и установите его ключ в куче соответствующим образом.

С кучей Фибоначчи , increase-key равно O(1).

---

Не столь необоснованным решением является использование Map<String, Integer>, добавление счетчика каждый раз, когда встречается слово, а затем выборочная сортировка его entrySet() на основе счетчика, чтобы получить первые 50.

Если сортировка O(N log N) недопустима, используйте алгоритм выбора , чтобы найти 50 лучших в O(N).

---

Какая техника лучше, действительно зависит от того, что вы просите (т.е. комментарий, является ли это скорее вопросом [algorithm], чем вопросом [java], очень красноречив).

Map<String, Integer>, за которым следует алгоритм выбора, наиболее практичен, но решение Patricia trie явно превосходит его только в эффективности использования пространства (поскольку общие префиксы не сохраняются избыточно).

Answer 2

Следующий псевдокод должен сделать свое дело:

build a map<word, count>
build a tokenizer that gives you a word per iteration
for each word*,
   if word in map, increment its count
   otherwise add with count = 1
sort words by count
for each of the first 50 words,
   output word, frequency = count / total_words

Это, по сути, O (N), и то, что предложил jpabluz. Тем не менее, если вы собираетесь использовать это для любого типа «дикого» текста, вы заметите много мусора: прописные / строчные буквы, знаки препинания, URL-адреса, стоп-слова, такие как «или» и «с очень высоким» счетчики, множественные варианты одного и того же слова ... Правильный способ сделать это состоит в том, чтобы сделать строчные буквы для всех слов, убрать все знаки препинания (и такие вещи, как URL-адреса), а также добавить удаление стоп-слов и вставку в точку, отмеченную звездочкой вышеуказанный псевдокод.

Answer 3

O(n):

1. Подсчитайте количество слов
2. Разбейте ваше текстовое слово по списку слов
3. Создать карту слова => number_of_occurences
4. Пройдите по карте и выберите макс. 50.
5. Разделите их на общее количество слов, чтобы получить частоту

Конечно, некоторые из этих шагов могут выполняться одновременно или не обязательно, в зависимости от используемых вами структур данных.

Answer 4

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