Словарь опечаток
Поисковая строка электронной библиотеки должна исправлять опечатки на лету: человек набирает слово, и через долю секунды под строкой появляется «Вы имели в виду…». Слов в словаре десятки тысяч, запросов — тысячи в секунду, и сравнивать каждый запрос с каждым словом некогда.
Для каждого запроса выведите подсказку. Если запрос есть в словаре, подсказка — он сам. Иначе — слово словаря на расстоянии редактирования ровно 1: одна вставка, одно удаление или одна замена буквы. Если таких слов несколько, выбирается самое частое, а из одинаково частых — меньшее при сравнении строк по кодам символов. Если ни одного слова на расстоянии 1 нет, подсказки нет. Перестановка двух соседних букв — это две правки, а не одна.
Один из тестов — весь словарь «Войны и мира», 47 585 слов с частотами, и 20 000 опечаток в его частых словах; другой — английский перевод романа.
Вход
В первой строке число слов словаря n (1 ≤ n ≤ 50 000). Дальше n строк: слово и сколько раз оно встретилось (от 1 до 106). Слова различны. Потом число запросов q (1 ≤ q ≤ 20 000) и q строк-запросов. Слова и запросы состоят из строчных русских (а–я, ё) или латинских букв, длина — от 1 до 30.
Выход
q строк: подсказка для каждого запроса или -, если подсказки нет.
Примеры
Пример 1
5 князь 1329 казнь 9 кнезу 1 мир 120 мор 120 5 кнезь мир мхр кнзяь ветер
князь мир мир - -
Пример 2
2 ba 50 abc 2 4 ab bc abcd a
abc ba abc ba
Ограничения
- Время · Python
- 8000 мс
- Время · Go
- 3000 мс
- Память
- 256 МБ
- Проверка
- 8 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Сравнивать запрос со всеми словами близкой длины — правильно, но это 20 000 × 30 000 проверок. Нужен способ сразу получить короткий список кандидатов, как в хеш-таблице.
2Подсказка 2
Перебрать все строки на расстоянии 1 от запроса и поискать их в словаре? Для слова из восьми русских букв это 8 удалений, 8 · 33 замен и 9 · 33 вставок — больше пятисот поисков на запрос. Можно ли обойтись одними удалениями?
3Подсказка 3
Если a и b отличаются одной заменой на месте i, то, удалив i-ю букву из обоих, получим одну и ту же строку. Если b получается из a вставкой, то удаление этой буквы из b даёт само a. Что можно заготовить заранее для каждого слова словаря?
4Идея
Назовём тенью слова его само и все строки, которые получаются из него удалением одной буквы. Если расстояние между a и b не больше 1, их тени пересекаются: при замене общая строка — оба слова без изменённой буквы, при вставке — само короткое слово. Значит, заранее кладём каждое слово словаря в хеш-таблицу под каждой строкой его тени, а для запроса смотрим только корзины его тени. Обратное неверно: у «ab» и «ba» общая тень «a», а расстояние 2. Поэтому каждого кандидата проверяем.
5Разбор
Подготовка: для слова длины L — L + 1 строк тени, в среднем 9,3 на слово: для словаря романа это 444 тысячи записей в 408 тысячах корзин. Запрос: строим его тень, собираем всех, кто лежит в её корзинах, и проверяем каждого кандидата за линейное время. Расстояние ровно 1 проверяется без таблицы: при равной длине — ровно одна несовпадающая позиция, при длинах, отличающихся на единицу, — после первого расхождения хвост короткого слова совпадает с хвостом длинного без одной буквы.
Второй пример — ловушка для решения без проверки. Тени «ab» и «ba» пересекаются, «ba» в 25 раз частее «abc», но подсказка для «ab» — «abc»: до «ba» две правки.
Этот приём называют симметричным удалением; на нём устроена библиотека SymSpell Вольфа Гарбе. Для расстояния k тень — все строки, получаемые удалением до k букв, и она растёт как Lk, зато не зависит от размера алфавита: замены и вставки в китайском или японском пришлось бы перебирать по тысячам знаков.
5+Решение
6Сложность
Подготовка — O(Σ L²): у каждого слова L + 1 строк длины до L. Запрос — O(L² + c · L), где c — число кандидатов, обычно несколько штук. Прямой перебор стоил бы O(q · n · L) — сотни миллионов сравнений на 20 000 запросах.
7Типичные ошибки
- Тень без проверки. Общая строка в тенях — подсказка, а не доказательство: у «ab» и «ba», у «ад» и «да» есть общие строки, а расстояние 2. Без проверки решение предлагает слова на расстоянии 2 (второй пример).
- Байты вместо букв. Русская буква в UTF-8 — два байта. Удаление «одного байта» в Go портит строку; работайте с рунами.
- Перебор всего словаря. Даже с фильтром по длине это десятки тысяч проверок на запрос.
- Сам запрос забыт. Если запрос есть в словаре, подсказка — он сам, даже если рядом есть слово частее.