AppSell » Блог » Den.Apps » Разработка на Flutter

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

На что обратить внимание:

Данные нужно предварительно нормализовать: удалить слова «город», «улица», «дом», привести сокращения к единому виду.

Большие списки лучше обрабатывать в изоляте, чтобы не тормозить UI.

Коэффициент отсечения подбирается экспериментально под ваши данные.

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

Пример:

import 'package:flutter/material.dart';

/// Модель адреса

class Address {

  final String address;

  final String? metro;

  const Address({required this.address, this.metro});

}

/// Расстояние Дамерау-Левенштейна с нормализацией

double levenshtein(String s1, String s2) {

  final a = s1.toLowerCase();

  final b = s2.toLowerCase();

  if (a == b) return 0.0;

  if (a.isEmpty || b.isEmpty) return 1.0;

  final matrix = List.generate(

    a.length + 1,

    (i) => List<int>.filled(b.length + 1, 0),

  );

  for (int i = 0; i <= a.length; i++) matrix[i][0] = i;

  for (int j = 0; j <= b.length; j++) matrix[0][j] = j;

  for (int i = 1; i <= a.length; i++) {

    for (int j = 1; j <= b.length; j++) {

      final cost = a[i - 1] == b[j - 1] ? 0 : 1;

      // Левенштейн

      matrix[i][j] = [

        matrix[i - 1][j] + 1,

        matrix[i][j - 1] + 1,

        matrix[i - 1][j - 1] + cost,

      ].reduce((x, y) => x < y ? x : y);

      // Дамерау-Левенштейн (перестановка)

      if (i > 1 && j > 1 && 

          a[i - 1] == b[j - 2] && 

          a[i - 2] == b[j - 1]) {

        matrix[i][j] = matrix[i][j] < matrix[i - 2][j - 2] + 1

            ? matrix[i][j]

            : matrix[i - 2][j - 2] + 1;

      }

    }

  }

  return matrix[a.length][b.length] / b.length;

}

/// Нормализация строки (удаление лишних слов)

String normalize(String input) {

  return input

      .toLowerCase()

      .replaceAll('город', '')

      .replaceAll('г.', '')

      .replaceAll('улица', '')

      .replaceAll('ул.', '')

      .replaceAll('дом', '')

      .replaceAll('д.', '')

      .replaceAll('строение', 'ст')

      .replaceAll('корпус', 'к')

      .trim();

}

/// Поиск с обработкой опечаток

List<Address> fuzzySearch(List<Address> addresses, String query) {

  if (query.isEmpty) return [];

  final normalizedQuery = normalize(query);

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

  for (final addr in addresses) {

    final normalizedAddress = normalize(addr.address);

    var distance = levenshtein(normalizedQuery, normalizedAddress);

    // Если есть метро, тоже участвует в поиске

    if (addr.metro != null && addr.metro!.isNotEmpty) {

      final metroDistance = levenshtein(normalizedQuery, normalize(addr.metro!));

      distance = distance < metroDistance ? distance : metroDistance;

    }

    results.add((addr, distance));

  }

  const threshold = 0.5; // коэффициент отсечения

  results.sort((a, b) => a.$2.compareTo(b.$2));

  return results

      .where((e) => e.$2 < threshold)

      .map((e) => e.$1)

      .toList();

}

// Пример использования

void main() {

  final addresses = [

    Address(address: 'г. Москва, ул. Петровка, д.2', metro: 'Театральная'),

    Address(address: 'г. Москва, Арбатская площадь, д. 14, ст1', metro: 'Арбатская'),

    Address(address: 'г. Москва, Тверская ул., д.5', metro: 'Тверская'),

  ];

  final query = 'Орбатская 14'; // пользователь ввел с опечаткой

  final results = fuzzySearch(addresses, query);

  print('Поиск: "$query"');

  for (final addr in results) {

    print('Найдено: ${addr.address} (метро: ${addr.metro})');

  }

}

Вывод:

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

08.05.2026 40 423