Алгоритм генерации "топ-списка" по частоте слов
У меня есть большая коллекция контента, созданного человеком. Я хочу найти слова или фразы, которые встречаются чаще всего. Какой эффективный способ сделать это?
6 ответов
Не изобретай велосипед. Используйте систему полнотекстового поиска, такую как Lucene.
Основная идея проста - в исполняемом псевдокоде,
from collections import defaultdict
def process(words):
d = defaultdict(int)
for w in words: d[w] += 1
return d
Конечно, дьявол кроется в деталях - как превратить большую коллекцию в итератор, дающий слова? Достаточно ли велико, что вы не можете обработать его на одной машине, а просто хотите использовать метод mapreduce, например, через hadoop? И т.д., и т. Д. NLTK может помочь с лингвистическими аспектами (выделение слов в языках, которые не разделяют их чисто).
При выполнении на одной машине (за исключением mapreduce) одна проблема, которая может возникнуть, заключается в том, что простая идея дает вам слишком много синглетонов или около того (слова, встречающиеся один или несколько раз), которые заполняют память. Вероятный ответ на этот вопрос заключается в том, чтобы сделать два прохода: один со случайной выборкой (получить только одно слово из десяти или один из ста), чтобы составить набор слов, которые являются кандидатами на высшие ранги, а затем второй проход, пропускающий слова, которые не находятся в наборе кандидатов. В зависимости от того, сколько слов вы выбираете и сколько хотите получить в результате, можно вычислить верхнюю границу вероятности того, что вы пропустите важное слово таким образом (и для разумных чисел, и для любого естественного языка). Уверяю вас, у вас все будет хорошо).
Как только у вас есть словарь, сопоставляющий слова с числами вхождений, вам просто нужно выбрать первые N слов по вхождениям - там поможет куча очередей, если словарь слишком велик для сортировки по вхождениям в полном объеме (например, в моем например, любимый исполняемый псевдокод, heapq.nlargest.
Простой / наивный способ - использовать хеш-таблицу. Пройдите по словам и увеличивайте количество по мере продвижения.
В конце процесса сортируйте пары ключ / значение по количеству.
Посмотрите на алгоритм Apriori. Его можно использовать для поиска частых предметов и / или частых наборов предметов.
Как говорится в статье в Википедии, есть более эффективные алгоритмы, которые делают то же самое, но это может быть хорошим началом, чтобы посмотреть, будет ли это применяться в вашей ситуации.
Может быть, вы можете попробовать использовать метод PATRICIA Trie или практический алгоритм для извлечения информации, закодированной в алфавитно-цифровом формате Trie?
Почему бы не простая карта с ключом в качестве слова и счетчиком в качестве значения. Это даст наиболее употребительные слова, взяв высокий счетчик значений. Это просто операция O(N).