Отслеживание / подсчет частоты слов

Question

Я хотел бы получить некоторое согласие сообщества на хороший дизайн, чтобы иметь возможность хранить и запрашивать частоту слов. Я создаю приложение, в котором я должен анализировать ввод текста и хранить, сколько раз слово появилось (с течением времени). Итак, учитывая следующие входные данные:

• "Убить насмешливую птицу"
• "Насмешка над пианистом"

будет хранить следующие значения:

Word    Count
-------------
To      1
Kill    1
A       2
Mocking 2
Bird    1
Piano   1
Player  1

А позже можно будет быстро запросить значение счетчика для данного произвольного слова.

Мой текущий план состоит в том, чтобы просто хранить слова и счетчики в базе данных и полагаться на кэширование значений счетчиков слов ... Но я подозреваю, что у меня не будет достаточно обращений в кэш, чтобы сделать это жизнеспособным решением в долгосрочной перспективе.

Может ли кто-нибудь предложить алгоритмы или структуры данных или любую другую идею, которая может сделать это хорошо работающим решением?

Answer 1

Подсчет слов является каноническим примером программы MapReduce (псевдокод из Википедии):

void map(String name, String document):
  for each word w in document:
     EmitIntermediate(w, "1");

void reduce(String word, Iterator partialCounts):
  int result = 0;
  for each pc in partialCounts:
    result += ParseInt(pc);
  Emit(AsString(result));

Я не говорю, что это способ сделать это, но это определенно вариант, если вам нужно что-то, что хорошо масштабируется, когда количество отдельных слов увеличивает память доступно на одной машине. До тех пор, пока вы можете оставаться ниже предела памяти, простой цикл обновления хеш-таблицы должен помочь.

Answer 2

Я не понимаю, почему вы считаете, что база данных не будет подходящим решением. Вероятно, у вас будет только около 100000 строк, а небольшой размер таблицы будет означать, что она может храниться полностью в памяти. Сделайте слово первичным ключом, и поиск будет очень быстрым.

Answer 3

Если производительность является вашей главной целью, вы можете использовать структуру, основанную на хэше или дереве, только в оперативной памяти. Предполагая, что вы все равно выполняете некоторую полезную фильтрацию (чтобы не считать термины с несловесными символами), максимальное количество слов в вашей таблице будет в диапазоне от 10⁶ до 10⁷ (даже если задействовано несколько языков), так что это легко помещается в память текущего ПК (и полностью избегает обработки базы данных).

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

Итак, эта дилемма ясно показывает нам первое и второе правило оптимизации: 1. Не оптимизируйте преждевременно. 2. Измерьте, прежде чем оптимизировать.

:)

Answer 4

Ваше решение звучит нормально. Если кэш основан на подсчете последних использований, то он будет содержать подсчет слов для наиболее часто встречающихся слов. (Распределение слов - это что-то вроде первых 100 слов, охватывающих 90% экземпляров слов), поэтому вам не нужен очень большой кеш.

Если вы хотите улучшить производительность и отбросить базу данных, вы можете закодировать слова как три и сохранить количество использований в конечных узлах. По сути, это то, что делает база данных, если вы индексируете текстовые слова, так что вы действительно избегаете только задержки db. Если это и есть цель, то есть другие способы избежать задержки в дБ, например, использование параллельных поисков.

Answer 5

Использовать хеш-таблицу .