CS
Задачник Базовый курс EN

Задача

Фильтр учится на ходу

классификация вероятностная структура подсчёт вариантов потоковая обработка хеширование

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

Правила модели те же, что в задаче «Определитель языка». Все тексты — строчные буквы и одиночные пробелы. Триграммы текста t — тройки подряд идущих символов строки «пробел + t + пробел». По предложениям, которые есть сейчас: dL — сколько их у языка L, n — сколько всего, cL(g) — сколько раз триграмма g встречается в предложениях языка L, NL — сколько всего триграмм в них, V — сколько разных триграмм во всех предложениях вместе. Ответ на вопрос x — язык с dL > 0 и наибольшим

$$\ln\frac{d_L}{n} + \sum_{g \in x} \ln\frac{c_L(g) + 1}{N_L + V}.$$

Если наибольших несколько — код, который раньше по алфавиту. Если предложений нет вовсе, ответ — -.

Третий и четвёртый тесты построены на предложениях Tatoeba из статьи.

Вход

В первой строке q — число операций (1 ≤ q ≤ 2·10⁵). Дальше q строк, каждая — одна из операций:

  • + L текст — добавить предложение на языке L (код из латинских букв); предложения нумеруются с единицы в порядке добавления;
  • - k — убрать предложение номер k; оно было добавлено и ещё не убрано;
  • ? текст — вопрос.

Тексты непусты. Всего символов во всех добавлениях не больше 10⁶, во всех вопросах — не больше 2·10⁵; языков не больше 20.

Выход

На каждый вопрос — строка с кодом языка или -.

Примеры

Пример 1

Вход
11
? кот
+ ru кот спит
+ uk кіт спить
+ ru кот ест
? кіт
? кот
- 3
- 1
? кот
+ en the cat
? the cat
Выход
-
uk
ru
uk
en

Пример 2

Вход
9
+ aa ab ab
+ bb ba ba
? ab
- 1
? ab
- 2
? ab
+ aa ab
? ba
Выход
aa
bb
-
aa

Ограничения

Время · Python
8000 мс
Время · Go
2000 мс
Память
256 МБ
Проверка
7 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

Решение «на каждый вопрос посчитать модель заново по всем предложениям» верно, но в третьем тесте это 1400 раз по 21 тысяче предложений. Что из подсчёта меняется, когда добавляют или убирают одно предложение?

2Подсказка 2

Все величины формулы — суммы по предложениям. Добавление предложения прибавляет его вклад, удаление — вычитает. Сложнее всего с V: когда оно растёт и когда уменьшается?

3Идея

Модель наивного Байеса — это счётчики, а счётчики умеют не только расти, но и уменьшаться. Храним для каждого языка словарь cL, сумму NL и число предложений dL; для каждого предложения — его язык и триграммы, чтобы потом их вычесть. Добавление и удаление стоят столько, сколько символов в предложении.

Число разных триграмм V счётчиками по языкам не получить: триграмма может исчезнуть из одного языка и остаться в другом. Нужен ещё один словарь — сколько раз каждая триграмма встречается во всех предложениях вместе. V — число его ключей с ненулевым значением: триграмма, у которой счётчик дошёл до нуля, удаляется из словаря, и V уменьшается.

4Разбор

На вопрос из k символов: для каждого языка с dL > 0 сумма ln(cL(g) + 1) по триграммам вопроса, минус k·ln(NL + V), плюс ln(dL/n). Логарифмы счётчиков меняются вместе со счётчиками, поэтому заранее их не сохранить, но ln(c + 1) зависит только от целого c: таблица ln 1, ln 2, ln 3, … считается один раз и растёт по мере надобности. Тогда вопрос стоит k обращений к словарю на язык и ни одного логарифма в цикле.

Пятый тест проверяет именно V. Сначала есть два небольших языка, потом добавляют третий — триста предложений из букв, которых в первых двух нет, и V вырастает на тысячи. Знаменатель NL + V у языка с короткими текстами растёт относительно сильнее, чем у языка с длинными, и ответ на тот же вопрос меняется. Третий язык убирают — и ответ обязан вернуться. Если V только растёт, не возвращается.

Так и работают обучаемые спам-фильтры: кнопка «это спам» прибавляет слова письма к счётчикам спама, «это не спам» — переносит их обратно.

4+Решение
5Сложность

O(длины предложения) на добавление и удаление, O(L·длины вопроса) на вопрос; память — счётчики плюс сами триграммы предложений, O(суммы длин).

6Типичные ошибки
  • Пересчитывать всё на каждый вопрос. Верно и медленно: время — сумма длин всех предложений, умноженная на число вопросов.
  • V только растёт. Счётчик «видели когда-нибудь» вместо «есть сейчас». Пятый тест.
  • Язык без предложений. Когда у языка убрали все предложения, он не участвует: его ln(dL/n) = −∞. Первый пример.

Алгоритмы задачи

ML Алгоритм Наивный Байес Считает, как часто каждый признак встречается в каждом классе, и складывает логарифмы этих частот. O(N) обучение, O(L·m) ответ 2 задачи DS Структура данных Хеш-таблица Поиск, вставка и удаление по ключу в среднем за O(1): ключ превращается в номер ячейки массива. O(1) в среднем 2 задачи
Каталог алгоритмов