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

Задача

Определитель языка

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

Соберите определитель языка — тот, что в статье о наивном Байесе, по точным правилам.

Есть n обучающих предложений, у каждого известен язык, и m вопросов. Все тексты уже очищены: в них только строчные буквы и одиночные пробелы, без пробелов по краям. Триграммы текста t — все подряд идущие тройки символов строки «пробел + t + пробел»; символ — это буква или пробел (в UTF-8 буква может занимать несколько байт). У текста длины k ровно k триграмм.

Для каждого языка L посчитаем: dL — сколько у него обучающих предложений, cL(g) — сколько раз триграмма g встретилась в его предложениях, NL — сколько всего триграмм в его предложениях. V — сколько разных триграмм во всех обучающих предложениях вместе. Ответ на вопрос x — язык с наибольшим

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

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

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

Вход

В первой строке n и m (1 ≤ n, m ≤ 25 000). В каждой из следующих n строк — код языка (латинские буквы, без пробелов), пробел и предложение. Дальше m строк с вопросами. Каждое предложение и каждый вопрос непусты; всего символов в предложениях не больше 10⁶, в вопросах — не больше 2·10⁵; языков не больше 20.

Выход

m строк — код языка для каждого вопроса.

Примеры

Пример 1

Вход
6 4
ru мама мыла раму
ru кот спит на окне
uk мама мила раму
uk кіт спить на вікні
en mother washed the frame
en the cat sleeps
кот мыл окно
кіт мив вікно
the frame sleeps
zzz
Выход
ru
uk
en
ru

Пример 2

Вход
3 3
aa ab ab ab
bb ba ba ba
bb ba ba
ab
ba
c
Выход
aa
bb
bb

Ограничения

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

Разбор

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

1Подсказка 1

Вопрос из четвёртого теста — несколько тысяч символов. Какой порядок величины у произведения нескольких тысяч вероятностей, каждая меньше сотой? Влезет ли оно в double?

2Подсказка 2

Логарифм — возрастающая функция: сравнивать языки по логарифмам вероятностей — то же самое, что по вероятностям. А логарифм произведения — сумма логарифмов.

3Идея

Обучение — подсчёт: для каждого языка словарь «триграмма → сколько раз», общее число триграмм NL и число предложений dL; общий словарь всех триграмм даёт V. Ответ — сумма логарифмов, ровно как в формуле условия. Произведение вероятностей считать нельзя: при средней вероятности триграммы около 10⁻³ уже на сотне символов оно меньше наименьшего положительного double, 4,9·10⁻³²⁴, становится нулём у всех языков, и ответ решает порядок перебора. В третьем тесте так ломаются 14 обычных предложений, самое короткое из них — 89 символов.

4Разбор

Логарифмы вероятностей знакомых триграмм удобно посчитать один раз после обучения: для каждого языка словарь «триграмма → ln((c + 1)/(NL + V))» и отдельное число для незнакомой триграммы, ln(1/(NL + V)). Тогда ответ на вопрос из k символов — k обращений к словарю на каждый язык и ни одного логарифма.

Сглаживание даёт смешной эффект, который виден в первом примере. Вопрос «zzz» не похож ни на один язык: все его триграммы незнакомы всем трём. Каждая стоит 1/(NL + V), и дороже всего она для языка с самыми длинными текстами. Побеждает язык с наименьшим NL — здесь «ru». Сглаживание отдаёт незнакомое тому, кто меньше всего видел.

Строку обучения удобно резать по первому пробелу: код языка пробелов не содержит, а предложение — содержит. В Go триграммы режутся по рунам: кириллическая или польская буква занимает в UTF-8 два байта.

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

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

6Типичные ошибки
  • Произведение вместо суммы логарифмов. Работает на коротких фразах и тихо ломается на длинных: все языки получают 0.0, и выигрывает первый по алфавиту.
  • Забыть сглаживание. Незнакомая триграмма даёт ln 0 = −∞ у языка, где её не было, — а такая найдётся почти в каждом вопросе. Ответ становится случайным.
  • V только по триграммам языка. В условии V — общий словарь всех языков, один для всех. Если взять для каждого языка его собственный словарь, вероятности сдвигаются, и в части тестов ответ другой.
  • Длина в байтах. В Python и Go длина строки и срезы считаются по-разному: в Go len — байты. Триграммы «по байтам» режут буквы пополам.

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

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