Отслеживание в реальном времени 100 лучших слов в твиттере в минуту/час/день

Недавно я наткнулся на этот вопрос интервью:

Given a continuous twitter feed, design an algorithm to return the 100 most
frequent words used at this minute, this hour and this day.

Я думал о системе с хэш-картой word -> count, связанной с 3-мя минутными кучами для текущей минуты, часа и дня.

Каждое входящее сообщение токенизируется, дезинфицируется, а количество слов обновляется в хеш-карте (и ключ увеличения в кучах, если слово уже существует в нем)

Если какое-либо из слов не существует в куче (и размер кучи == 100), проверьте, есть ли их frequency > min value в куче, и если да, то извлеките-min и вставьте в кучу.

Есть ли лучшие способы сделать это?


nlp algorithm
person barefootshoes    schedule 17.04.2012    source источник

Ответы (2)


arrow_upward
9
arrow_downward

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

Вам нужен массив из 1440 (24*60) word+count хэш-карт, организованных так, как вы описываете; это ваши поминутные счета. Вам нужны две дополнительные хеш-карты — для скользящего итога часа и дня.

Определите две операции с хэш-картами — add и subtract, с семантикой объединения количества одинаковых слов и удаления слов, когда их количество падает до нуля.

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

Наконец, вам нужен способ создать 100 лучших слов с учетом хеш-карты. Это должна быть тривиальная задача — добавить элементы в массив из word+count записей, отсортировать по количеству и сохранить первые 100.

person Sergey Kalinichenko    schedule 17.04.2012
comment
Спасибо dasblinkenlight имеет смысл. Я надеялся не отслеживать слова каждую минуту. через час что-то вроде слияния счетов за текущую мин. в течение часа и повторного использования той же карты в течение следующей минуты. Но это не поможет сохранить топ-100 слов за последний час, так как мы теряем данные о более старых минутах. - person barefootshoes; 17.04.2012
comment
@barefootshoes вы абсолютно правы: эта проблема чем-то похожа на рисование бегущей змеи в видеоигре: хотя каждый шаг меняет только две точки (голову и хвост), вам все равно нужно сохранить расположение всего тела змеи. - person Sergey Kalinichenko; 17.04.2012
comment
@dasblinkenlight - не поделитесь кодом? Я могу теоретически понять, но не могу придумать рабочее решение. - person Tyr1on; 06.12.2019

arrow_upward
1
arrow_downward

dasblinkenlight указал на ошибку, связанную с тем, что вы не исключили элементы из вашей хеш-карты.

Однако есть еще одна вещь, которую следует добавить: для фактического вычисления первых K слов с заданной минутой/часом/днем быстрее использовать разбиение (O(n)), а не сортировку (O(nlgn)):

  1. сбросить хэш-карту количества слов мин/час/день в массив: O(n)
  2. используйте выбор медианы медианы, чтобы получить K-й элемент: O (n)
  3. разбиение вокруг K-го элемента: O(n)

ХТН.

person galactica    schedule 24.07.2013