На не самой популярной странице «Остановки» есть функция поиска. Например:

Поиск умеет работать даже если допустить ошибку в слове. Можно даже не одну ошибку.

А ещё можно так:

Всё это работает в браузере без машинного обучения и искусственного интеллекта.

Формально задача звучит так: есть функция get_search_results, которая получает текст запроса и возвращает список остановок, которые пользователь мог иметь в виду.

function get_search_results(prompt) {
    ...
}

Самый простой способ — искать вхождение подстроки. Если пользователь ввёл «Калинина», найти все остановки, в названии которых есть «Калинина». Это работает, но только если пользователь не ошибся.

А если ошибся? Например, написал «Калинино» или «Калининв»?

Тогда нужен механизм, который умеет прощать ошибки.

Первый подход: перебор

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

Например, пользователь ввёл «Калининва». Разбиваем на подстроки разной длины:
— Длина 1: «К», «а», «л», «и», «н», «и», «н», «в», «а»
— Длина 2: «Ка», «ал», «ли», «ин», «ни», «ин», «нв», «ва»
— Длина 3: «Кал», «али», «лин», «ини», «нин», «инв», «нва»
— И так далее.

Потом смотрим, сколько из этих подстрок встречается в названии «Улица Калинина». Чем больше — тем выше точность.

Для коротких запросов, например «Кали», этот метод тоже работает: подстроки «К», «а», «л», «и», «Ка», «ал», «ли», «Кал», «али» — почти все найдутся в названии.

Но тут есть нюанс

Если запрос длинный, количество подстрок растёт квадратично. Для слова из 10 букв это 55 подстрок. Для 15 — уже 120. Перебирать 120 подстрок для каждой из сотни остановок — на клиенте это всё равно быстро, но мы решили ограничить максимальную длину запроса семью символами. Если пользователь ввёл длинное слово, дальше семи букв мы подстроки не режем.

Вот как выглядит основная логика:

for (let i = 1; i <= prompt.length; i++) {
    if (i >= 7) break;
    for (let j = 0; j < prompt.length - i + 1; j++) {
        const sub = prompt.substring(j, j + i);
        if (stp.Name.toLowerCase().includes(sub)) {
            acc_count += 1;
        }
    }
}

Счётчик acc_count накапливает количество совпадений. Потом мы делим его на максимально возможное количество совпадений для запроса этой длины. Получается число от 0 до 1 — степень уверенности, что остановка подходит.

Альтернативные названия

В Коломне у некоторых остановок есть народные названия. Например, «Трамвайное управление» в народе — просто «Депо». А остановка «Детская художественная школа» иногда называется «Путепровод» или «Холодильник» (что?).

Мы добавили массив Alternatives для каждой остановки. Если подстрока не нашлась в официальном названии, но нашлась в одном из альтернативных, мы тоже добавляем очко, но с понижающим коэффициентом. Потому что альтернативное название — это всё-таки не основное.

for (const alt of stp.Alternatives) {
    if (alt.includes(sub)) {
        acc_count += 1 / stp.Alternatives.length;
    }
}

Нашлось ещё одно применение Alternatives — разные написания названий. К примеру, для «Площади двух революций» добавили «Площадь 2 революций» — потому что люди часто заменяют слово «двух» на цифру. А для «Бульвара 800-летия Коломны» добавили «Бульвар восьмисотлетия Коломны» — кто-то вводит и так.

Порог срабатывания

На основе этого механизма мы написали отдельную функцию get_search_results_improved, которая возвращает все остановки, у которых степень уверенности превысила порог accuracy.

А порог accuracy вычисляем эмпирически:

let accuracy = search_results.length * 0.02 + prompt.length * 0.01 + 0.25;

Если обычный поиск (простое вхождение) нашёл много результатов — порог повышаем, чтобы не выдавать мусор. Если запрос длинный — тоже повышаем, потому что длинный запрос точнее.

А что, если пользователь ввёл всё правильно

Если пользователь не ошибся, зачем запускать тяжёлый алгоритм с подстроками? Поэтому в get_search_results сначала идут простые проверки:

1. Точное совпадение с учётом заглавной буквы
2. Совпадение с пробелом перед запросом (чтобы найти слово в середине названия)
3. Простое вхождение в нижнем регистре
4. Поиск по альтернативным названиям

Только после этого, если простые методы сработали, запускаем улучшенный поиск и докладываем его результаты сверху.

search_results.push(...get_search_results_improved(prompt, accuracy));

Дубликаты и ограничения

Одна и та же остановка может попасть в результаты несколько раз — например, нашлась и по точному совпадению, и через альтернативное название. Поэтому после всех операций мы прогоняем список через removeDuplicates.

И в конце оставляем не больше семи результатов. Семь — хорошее число. Не перегружает интерфейс, но даёт достаточно выбора.

search_results = search_results.slice(0, 7);

Почему не Левенштейн

Знающие люди спросят: а почему вы не использовали расстояние Левенштейна? Оно же специально придумано для поиска с ошибками.

Расстояние Левенштейна считает, сколько букв нужно заменить, удалить или добавить, чтобы одно слово превратилось в другое. Казалось бы, идеально.

Но есть проблема. Остановка может называться «Улица Калинина», а пользователь вводит «Калинина». Расстояние Левенштейна будет большим, потому что в начале названия не хватает «Улица ». А наш алгоритм разбивает на подстроки и находит «Калинина» внутри, потому что «Калинин» и «Калинина» — это общие куски.

К тому же, Левенштейн не умеет работать с альтернативными названиями. А наш умеет.