Hola, Amigos! На связи Павел Гершевич, Mobile Team Lead агентства продуктовой разработки Amiga и соавтор книги «Основы Flutter». Иногда нужно реализовать поиск по данным без участия бэкенда. Самый простой вариант — обычное вхождение строки — не прощает опечаток. Одна лишняя буква, и поиск выдает пустоту.

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

Немного теории

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

Допустим, у нас есть список адресов в едином формате:

final addresses = <String>[
  ‘г. Москва, ул. Петровка, д.2’,
  ‘г. Москва, Арбатская площадь, д. 14, ст1’,
  ...
];

И пользователь вводит в строку поиска «Орбатская 14». Что будет найдено простым вхождением строк? Правильно, ничего. Так как существует опечатка и в наших данных даже без нее нет совпадений.

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

Алгоритмы нечеткого поиска

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

Расстояние Левенштейна

Основой нечеткого поиска можно назвать расстояние Левенштейна. Оно определяет минимальное количество операций для превращения одного слова в другое. Такими операциями являются вставка, удаление и замена символа.

Например, для слов «Австрия» и «Австралия» расстояние равно 2 (добавили две буквы), для «кот» и «код» — 1 (заменили символ), а для пары «водка» и «вода» — тоже 1 (удалили букву).

Но для поиска такое не очень подходит. Причина этому — у более длинных строк может быть больше расстояние, чем у коротких. Поэтому можно применить нормализацию, чтобы все значения стали булевыми от 0 до 1. В такой шкале 0 означает полностью идентичные строки, а 1 — строки без совпадений. Например, для «Австрия» и «Австралия» такое значение будет примерно 0.222.

Расстояние Дамерау‑Левенштейна

Есть и более оптимизированный вариант такого алгоритма — расстояние Дамерау‑Левенштейна. Его отличие в том, что к операциям добавляется еще одна — перестановка соседних символов — одна из самых частых опечаток. Так что такой способ можно назвать более точным.

Например, для слов «годик» и «годки» обычное расстояние Левенштейна равно 2, а по Дамерау‑Левенштейну — всего 1, так как алгоритм видит одну операцию перестановки.

Другие варианты расстояния Левенштейна

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

Взвешенное расстояние Левенштейна. Тут каждой из операций присваивается свой вес. Если посмотреть на примеры выше, то при весе замены символа в 2 балла, а всех остальных операций в 1 символ, разница между «кот» и «код» будет такой же, как и у «Австрия» и «Австралия».

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

Другие алгоритмы нечеткого поиска

Существует еще множество алгоритмов, которые могут помочь нам реализовать нечеткий поиск.

Например, двоичный алгоритм поиска подстроки, он же Bitap, он же SHIFT‑OR. Этот алгоритм основан на операции битового сдвига (Bitshift) и если использовать его модификацию от Wu‑Manber, то это будет один из вариантов вычисления расстояния Левенштейна.

Если пойти еще дальше, то можно найти алгоритмы с большей сложностью реализации и выполнения, но более точные в поиске: расширение выборки, метод N‑грамм, ВК‑деревья. Но так как мы работаем с мобильными приложениями, то скорее всего они нам не подойдут.

Для того, чтобы реализовать поиск по точкам у нас на карте, мы выбрали расстояние Дамерау‑Левенштейна. Давайте разберем его реализацию на Dart и Flutter.

Реализуем нечеткий поиск на Dart и Flutter

Вернемся к нашему кейсу с поиском адреса и немного его усложним. Допустим, что данные заполняются разными людьми и выглядят по‑разному. А также, что это модель, где есть дополнительные данные, например, ближайшая станция метро, если оно там есть. Получаются вот такие данные:

final addresses = <Address>[
  Address(
    address: ‘г. Москва, ул. Петровка 2’,
    metro: ‘Театральная’,
  ),
  Address(
    address: ‘Москва, Арбатская площадь, дом 14, ст1’,
    metro: ‘Арбатская’,
  ),
  …
];

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

Подготовка выборки из модели данных

Сначала убираем лишнее из моделей, для этого отсекаем слова «город», «улица», «дом». Слова «строение» и «корпус», мы их будем заменять на их сокращения «ст» и «к», которые будут идти без пробела. Также сюда может попасть слово «литера» и ее сокращение «лит.». А также в конец добавляем станцию метро.

final addressStrings = addresses.map<String>((e) {
  final onlyAddress = e
    .address
    .replace(‘город’, ‘’)
    .replace(‘г.’, ‘’)... // удаляем лишнее
  return “$onlyAddress ${e.metro}”.trim();
}).toList();

Вызов функции trim в данном случае обязателен, так как уберет лишние пробелы, если они появятся.

Те же самые преобразования нам нужно будет делать и в поисковой строке.

Реализуем алгоритм расстояния Левенштейна

После того, как наши данные стали нормализованными, мы можем приступить к реализации самого поиска.

В первую очередь нам нужно подготовить сами строки — привести их к одному регистру.

double levenshtein(String s1, String s2) {
  final s1lower = s1.toLowerCase();
  final s2lower = s2.toLowerCase();

  ...
}

Далее проверить строки на пустоту. Так как мы вернем максимальную несовместимость, если одна из строк пуста. Еще из проверок крайних кейсов — полное соответствие, в его случае вернется 0.

if (s1lower == s2lower) return 0.0;
if (s1lower.isEmpty || s2lower.isEmpty) return 1.0;

Теперь мы можем перейти именно к самому сравнению. Для начала распределим так, чтобы s1 у нас была длиннее, а s2 короче. Это поможет алгоритму съедать меньше памяти. Поэтому проверяем и меняем через дополнительную временную переменную.

int _calculateDistance(String s1, String s2) {
  if (s1.length < s2.length) {
    final temp = s1;
    s1 = s2;
    s2 = temp;
  }

  ...
}

Также вынесем длину строк в переменные, чтобы не вычислять их несколько раз. А также создадим 2 массива одинаковой длины. Один будет за прошлый ряд в матрице, а второй за текущий.

final len1 = s1.length;
final len2 = s2.length;

List<int> prevRow = List<int>.generate(len2 + 1, (i) => i);
List<int> currRow = List<int>.filled(len2 + 1, 0);

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

for (int i = 1; i <= len1; i++) {
  curr[0] = i;

  ...

  final tmp = prevRow;
  prevRow = currRow;
  currRow = tmp;
}

Как видно из кода выше, мы в самом начале задаем значение для первого элемента в ряду. А уже в самом конце меняем их между собой. А что происходит посередине?

Именно там мы проходимся по сходству и проверяем самое минимальное действие для преобразования. Для этого создаем еще один цикл, но в этот раз он основывается на второй строке.

for (int j = 1; j <= len2; j++) {
  final cost = s1.codeUnitAt(i - 1) == s2.codeUnitAt(j - 1) ? 0 : 1;

  currRow[j] = min(
    prevRow[j] + 1,
    min(currRow[j - 1] + 1, prevRow[j - 1] + cost),
  );

  if (i > 1 &&
      j > 1 &&
      s1.codeUnitAt(i - 1) == s2.codeUnitAt(j - 2) &&
      s1.codeUnitAt(i - 2) == s2.codeUnitAt(j - 1)) {
    currRow[j] = min(currRow[j], prevRow[j - 2] + cost);
  }
}

Давайте разберем вычисление подробнее. Сначала мы смотрим, одинаковые ли символы. Если одинаковые, то выдаем 0, если нет, то 1.

Далее переходим к вычислению по Левенштейну. Тут мы упираемся в ограничение библиотеки dart:math, которая может найти минимальное значение только из двух переменных, а в нашем случае их уже три. Поэтому, сначала сравниваем 2, потом результат сравниваем с третьей. Каждая из этих трех переменных — одна операция: удаление, добавление или замена символа.

Но мы же хотим вычислить расстояние Дамерау‑Левенштейна, а в нем есть еще одна операция — перестановка символов. Для нее проводим дополнительную проверку. Для первых символов в строках мы не можем провести такое сравнение, поэтому, добавляем проверку, что индексы наших циклов должны быть больше 1. Потом проверяем еще совпадение между символами перекрестно — для s1 берем i -1, а для s2 берем j - 2, если они совпадают, то проделываем тоже самое для i - 2 и j - 1. Если все сошлось и это перестановка, то еще раз получаем минимальное значение — между значением перестановки и тем, что мы получили по алгоритму расстояния Левенштейна.

Итог такой операции — строка матрицы, в которой последний элемент и есть расстояние Дамерау‑Левенштейна. Его нам и нужно вернуть:

return prevRow[len2];

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

return _calculateDistance(s1lower, s2lower) / s2lower.length;

Сравнение двух строк у нас теперь есть, осталось сделать так, чтобы это было именно поиском по списку адресов.

final distances = <(Address, double)>[];

for (final addr in addresses) {
  final addrDistance = levenshtein(searchString, addr.address);

  distances.add(
    addr,
    addr.metro != null && addr.metro.isNotEmpty
      ? min(
          levenshtein(searchString, addr.metro ?? ‘’),
          addrDistance,
        )
      : addrDistance,
  );
}

final distanceK = 0.5;

distances.sort((a, b) => a.$2.compareTo(b.$2));
final results = distances
  .where((e) => e.$2 < distanceK)
  .map((e) => e.$1)
  .toList();

Мы специально ввели коэффициент минимальной дистанции, чтобы оно работало именно как поиск. Его вы можете менять под себя, чтобы выдавать только более точные результаты. Такие результаты уже получаются отсортированными по релевантности, поэтому их можно считать готовыми к выводу.

Что если мы хотим сделать так, чтобы в этих результатах подсвечивались совпадения? Это можно сделать, только будет максимально сложно. Так как такой алгоритм потребует в разы больше вычислительной мощности. В любом случае для подсвечивания можно обойтись и вхождением строки.

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

Как определить нужен ли вам нечеткий поиск?

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

Нужно ли мне обрабатывать опечатки локально в поиске? Если ваш ответ да, то переходим к следующему пункту.

Приложение работает полностью локально? Если так, то нечеткий поиск — ваше спасение. Если нет, переходим далее.

Может ли бэкенд организовать поиск по этим данным на своей стороне? Выбирайте локальный поиск только если нельзя поиск отдать на бэкенд.

Заключение

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

Если есть вопросы — буду ждать вас в комментариях. А еще подписывайтесь на телеграм‑канал про Flutter‑разработку — я часто там пишу и делюсь полезными инсайтами и новостями из мира мобильной разработки.