Отслеживание/Подсчет Частотности слова
Я хотел бы заставить некоторое общественное согласие по хорошему дизайну мочь сохранить и запросить количества частотности слова. Я создаю приложение, в котором я должен проанализировать вводы текста и сохранить, сколько раз слово появлялось (со временем). Так, учитывая следующие исходные данные:
- "Для уничтожения птицы насмешки"
- "Дразня пианиста"
Сохранил бы следующие значения:
Word Count
-------------
To 1
Kill 1
A 2
Mocking 2
Bird 1
Piano 1
Player 1
И позже смочь быстро запросить для значения количества данного произвольного слова.
Мой текущий план состоит в том, чтобы просто сохранить слова и количества в базе данных, и полагаться на кэширование значений для подсчета количества слов... Но я подозреваю, что не заставлю достаточно удачных обращений в кэш делать это длительным сроком эффективного решения.
Кто-либо может предложить алгоритмы, или структуры данных или какую-либо другую идею, которая могла бы сделать это хорошо работающим решением?
5 ответов
Я не понимаю, почему вы считаете, что база данных не подходит. Вероятно, у вас будет всего около 100000 строк, и небольшой размер таблицы будет означать, что ее можно полностью сохранить в памяти. Сделайте слово первичным ключом, и поиск будет очень быстрым.
Если производительность является вашей главной целью, вы можете использовать структуру на основе хэша или тройки только в оперативной памяти. Предполагая, что вы все равно сделаете некоторую полезную фильтрацию (чтобы не считать термины с несловосочетаниями), максимальное количество слов в вашей таблице будет в диапазоне от 10⁶ до 10⁷ (даже если задействовано несколько языков), так что это легко поместится в памяти современного ПК (и полностью избежать всей обработки базы данных).
С другой стороны, если вам придется самостоятельно реализовывать детали таблицы хэширования, то у вас будет еще больше кода, который вы можете сделать неправильно (в то время как ребята из базы данных, надеюсь, максимально отладили свой код). Поэтому даже незначительные детали в вашей собственной реализации могут снова привести к снижению производительности.
Итак, эта дилемма ясно показывает нам первое и второе правило оптимизации: 1. Не оптимизируйте преждевременно. 2. Измеряйте, прежде чем оптимизировать.
:)
Ваше решение звучит нормально. Если кеш основан на счетчике недавнего использования, то он будет содержать счетчики слов для наиболее часто встречающихся слов. (Распределение слов - это что-то вроде первых 100 слов, покрывающих 90% экземпляров слов), поэтому вам не нужен очень большой кеш.
Если вы хотите повысить производительность и удалить базу данных, вы можете закодировать слова как дерево и сохранить счетчики использования в конечных узлах. По сути, это то, что делает база данных, если вы индексируете текст слова, поэтому вы действительно избегаете только задержки db. Если это цель, то есть другие способы избежать задержки БД, например, используя параллельный поиск.
Подсчет слов - это канонический пример программы 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));
Я не говорю, что это способ сделать это , но это определенно вариант, если вам нужно что-то, что хорошо масштабируется, когда количество отдельных слов превышает объем памяти, доступной на одной машине. Пока вы можете оставаться ниже лимита памяти, простой цикл обновления хеш-таблицы должен помочь.