У меня есть большая коллекция человеческого контента. Я хочу найти слова или фразы, которые происходят чаще всего. Каков эффективный способ сделать это?Алгоритм для создания «верхнего списка» с использованием частоты слов
Не изобретайте велосипед. Используйте полнотекстовую поисковую систему, такую как Lucene.
Я действительно люблю lucene, но я думаю, что здесь немного переборщить. Подсчет слов достаточно прост, используя хеш-таблицу. –
Откуда вы знаете, что решение является излишним? У вас есть лучшее понимание «большой коллекции человеческого контента», чем я? – hobodave
Я не хочу начинать войну слов здесь. Вполне возможно, что вы правы. Одна из причин того, что это может быть хорошим решением, заключается в том, что lucene включает в себя отличные токенизаторы, которые могут быть полезны здесь. С другой стороны: 1. Lucene - довольно большая зависимость, которая делает и оптимизирована, чтобы сделать намного больше, чем того, что требуется для 2.Таблицы хэша доступны для более или менее всех языков на планете, в то время как lucene ограничен несколькими платформами. –
Простым/наивным способом является использование хеш-таблицы. Проходите через слова и увеличивайте счет, когда идете.
В конце процесса сортируйте пары ключ/значение по количеству.
Это не поможет с фразами. OP специально спросил о «словах или фразах», что гораздо менее тривиально. – hippietrail
основная идея проста - в исполняемом псевдокоде
from collections import defaultdict
def process(words):
d = defaultdict(int)
for w in words: d[w] += 1
return d
Конечно, дьявол кроется в деталях - как же превратить большую коллекцию в итератор уступая слова? Достаточно ли это, что вы не можете обработать его на одной машине, но, скорее, нужно использовать метод mapreduce, например. через hadoop? Etc и т. Д. NLTK может помочь с лингвистическими аспектами (изолировать слова на языках, которые не разделяют их чисто).
При выполнении одной машины (net of mapreduce) может возникнуть одна проблема: простая идея дает вам слишком много одиночек или около них (слова происходят один или несколько раз), которые заполняют память. Вероятностная реплика к этому состоит в том, чтобы сделать два прохода: один со случайной выборкой (получить только одно слово из десяти или один из сотни), чтобы сделать набор слов, которые являются кандидатами на высшие чины, затем второй проход пропускает слова, которые не входят в набор кандидатов. В зависимости от того, сколько слов вы отбираете и сколько хотите в результате, можно вычислить верхнюю границу вероятности того, что вы пропустите важное слово таким образом (и для разумных чисел и любого естественного языка , Я заверяю вас, что вы будете в порядке).
Если у вас есть словарный словарь, сопоставляющий слова с номерами вхождений, вам просто нужно выбрать верхние N слов по вхождениям - куча очереди поможет там, если словарь слишком велик, чтобы сортировать по вхождению во всей полноте (например, в моем любимом исполняемом псевдокоде, например, heapq.nlargest сделает это).
Это относится только к тривиальному случаю слов, тогда как ОП специально задает вопрос о словах или фразах. – hippietrail
Посмотрите на Apriori algorithm. Его можно использовать для поиска частых предметов и/или частых наборов предметов.
Как говорится в статье в wikipedia, существуют более эффективные алгоритмы, которые делают то же самое, но это может быть хорошим началом, если это применится к вашей ситуации.
Возможно, вы можете попробовать использовать PATRICIA trie or practical algorithm to retrieve information coded in alphanumeric trie?
Почему не простая карта с ключом как слово и счетчик в качестве значения. Он даст верхние используемые слова, взяв счетчик высоких значений. Это всего лишь операция O (N).
Этот ответ уже был дан. Дважды. – hobodave
И он игнорирует фразы, которые конкретно рассматриваются в вопросе OP: 'слова или фразы'. – hippietrail
Можете ли вы предоставить более подробную информацию? В частности: что такое «большая коллекция» ?, «Что эффективно?» например каковы ваши ожидания времени, какой язык вы используете и т. д. – hobodave