👣 Улучшаем локальный поиск на Dart и Flutter

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


Почему простое вхождение не работает:

Пользователи часто ошибаются. Вместо «Арбатская» пишут «Орбатская», вместо «Петровка» - «Питровка». Простой поиск по вхождению подстроки такие запросы игнорирует. А отправлять каждый запрос на сервер - долго и не всегда возможно.


Что такое расстояние Левенштейна:

Это число, которое показывает, сколько операций нужно, чтобы превратить одну строку в другую. Операции - вставка, удаление, замена символа. Например, «кот» -> «код»: одна замена символа, расстояние = 1. «Австрия» -> «Австралия»: нужно добавить две буквы, расстояние = 2.

Для поиска удобнее использовать нормализованное значение от 0 до 1, где 0 - полное совпадение, 1 - строки разные.


Более точный вариант - расстояние Дамерау‑Левенштейна:

Оно добавляет еще одну операцию - перестановку соседних символов. Это одна из самых частых опечаток: «годки» вместо «годик». Обычное расстояние Левенштейна даст 2, а расстояние Дамерау‑Левенштейна - 1, потому что достаточно переставить буквы.


Как это реализовать во Flutter:

Автор приводит пример поиска по адресам и станциям метро. Алгоритм:

🔵Привести строки к нижнему регистру.

🔵Вычислить расстояние Дамерау‑Левенштейна между поисковым запросом и каждым элементом списка.

🔵Добавить к адресу название метро, если оно есть.

🔵Отсортировать результаты по близости (чем меньше расстояние, тем выше результат).

🔵Отфильтровать только те, где расстояние меньше заданного порога (например, 0.5).


🔗 Читать подробнее


💡 Вывод:

Такой поиск имеет смысл не везде. В идеале - отдать поиск на бэкенд, если он это умеет. Если нет и приходится искать локально, расстояние Дамерау-Левенштейна может спасти ситуацию. Но не ждите чудес: алгоритм требовательный к ресурсам, а порог совпадения придется подбирать вручную.


Подписаться на канал:
➡️ Flutter & Dart | Мобильный трудоголик

Закрытый канал:
🚀 Мобильный трудоголик PRO