Это один из исследовательских проектов, который я сейчас изучаю.Требование почти такое же, как у вас, и мы разработали хорошие алгоритмы для решения проблемы.
Входные данные
Входные данные представляют собой бесконечный поток английских слов или фраз (мы называем их tokens).
Выход
- Вывод top N токенов, которые мы видели до сих пор (из всех токенов, которые мы видели!)
- Output topN токенов в историческом окне, скажем, в последний день или на прошлой неделе.
Применение этого исследования состоит в том, чтобы найти горячую тему или тенденции темы в Twitter или Facebook.У нас есть сканер, который сканирует веб-сайт, который генерирует поток слов, которые поступают в систему.Затем система будет выводить слова или фразы с максимальной частотой либо в целом, либо исторически.Представьте, что в последние пару недель фраза «Кубок мира» будет многократно появляться в Twitter.Так же как и «осьминог Павел».:)
Строка в целые числа
Система имеет целочисленный идентификатор для каждого слова.Хотя в Интернете есть почти бесконечные возможные слова, но после накопления большого набора слов возможность поиска новых слов становится все ниже и ниже.Мы уже нашли 4 миллиона разных слов и присвоили уникальный идентификатор каждому.Весь этот набор данных может быть загружен в память в виде хэш-таблицы, занимая примерно 300 МБ памяти.(Мы реализовали нашу собственную хеш-таблицу. Реализация Java требует огромных затрат памяти)
Каждая фраза может быть идентифицирована как массив целых чисел.
Это важно, потому что сортировка и сравнение по целым числам намного быстрее , чем по строкам.
Архивные данные
Система хранит архивные данные для каждого токена.В основном это пары (Token, Frequency).Однако таблица, в которой хранятся данные, будет настолько огромной, что нам придется разделить таблицу физически.Схема однократного разбиения основана на nграммах токена.Если токен является одним словом, это 1 грамм.Если токен состоит из двух слов, это 2грамма.И это продолжается.Примерно в 4 грамма у нас есть 1 миллиард записей с размером таблицы около 60 ГБ.
Обработка входящих потоков
Система будет поглощать входящие предложения, пока память не будет полностью использована (Yaнам нужен MemoryManager).После принятия N предложений и сохранения в памяти система делает паузу и начинает разбивать каждое предложение на слова и фразы.Каждый токен (слово или фраза) считается.
Для очень частых токенов они всегда хранятся в памяти.Для менее частых токенов они сортируются на основе идентификаторов (помните, что мы переводим строку в массив целых чисел) и сериализуем в файл на диске.
(Однако для вашей проблемы, поскольку вы учитываете только слова, вы можете поместить все частотно-частотные карты только в память. Тщательно разработанная структура данных потребует только 300 МБ памяти для 4 миллионов различных слов. Некоторыеподсказка: используйте ASCII char для представления строк), и это очень приемлемо.
Между тем, будет другой процесс, который активируется, когда он находит какой-либо дисковый файл, сгенерированный системой, а затем начинает объединять его.Поскольку файл на диске отсортирован, объединение потребует аналогичного процесса, как сортировка слиянием.Здесь также необходимо позаботиться о некотором дизайне, так как мы хотим избежать слишком большого числа случайных обращений к диску.Идея состоит в том, чтобы избежать одновременного чтения (процесс слияния) / записи (системный вывод) и позволить процессу слияния считывать данные с одного диска при записи на другой диск.Это похоже на реализацию блокировки.
Конец дня
В конце дня система будет иметь много частых токенов с частотой, хранящейся в памяти, и много других менее частых токенов, хранящихся в нескольких дисковых файлах.(и каждый файл отсортирован).
Система сбросит карту памяти в файл на диске (отсортируйте ее).Теперь проблемой становится слияние набора отсортированных файлов на диске.Используя аналогичный процесс, мы получили бы один отсортированный дисковый файл в конце.
Затем последняя задача - объединить отсортированный дисковый файл в архивную базу данных.В зависимости от размера архивной базы данных алгоритм работает, как показано ниже, если он достаточно большой:
for each record in sorted disk file
update archive database by increasing frequency
if rowcount == 0 then put the record into a list
end for
for each record in the list of having rowcount == 0
insert into archive database
end for
Интуиция заключается в том, что через некоторое время количество вставок станет все меньше и меньше.Все больше и больше будет только обновление.И это обновление не будет оштрафовано индексом.
Надеюсь, это все объяснение поможет.:)