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

Question

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

• "Убить насмешливая птица"
• "Глумление пианиста"

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

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

И позже способный быстро запросить значение счета для данного произвольного слова.

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

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

Answer 1

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

Answer 2

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

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

Answer 3

Использовать hash table.

Answer 4

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

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

Answer 5

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

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

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

:)