Алгоритмы сопоставления

Tom Select реализует механизм сопоставления (matching) как комбинацию нормализации входной строки, разбиения на токены, вычисления взвешенного рейтинга релевантности и последующей сортировки результатов. Алгоритм оптимизирован под интерактивный ввод, где ключевым фактором становится не полнота поиска, а скорость реакции и предсказуемость ранжирования.

Перед тем как выполняется любое сравнение строк, входные данные проходят этап нормализации. Он включает:

  • приведение текста к нижнему регистру;
  • удаление диакритических знаков (в зависимости от настроек);
  • устранение лишних пробелов;
  • унификацию Unicode-представления.

Нормализация снижает энтропию данных и позволяет алгоритму сопоставления работать стабильно вне зависимости от языка и способа ввода. Например, строки Résumé, resume и RESUME после обработки становятся эквивалентными.

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

Токенизация и разбиение строки

После нормализации выполняется разбиение строк на токены. Токенизация в Tom Select основана на разделении по пробелам и дополнительным разделителям (знаки препинания, дефисы, подчеркивания).

Пример:

"New York City" → ["new", "york", "city"]

Токены используются для:

  • частичного совпадения;
  • поиска по подстрокам;
  • оценки степени совпадения между множеством слов.

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

Базовый алгоритм вычисления score

Ключевой элемент механизма — функция оценки релевантности (score). Для каждого элемента списка вычисляется числовое значение, отражающее степень соответствия запросу.

Общая идея:

score = Σ (matchWeight * fieldWeight)

Где:

  • matchWeight — степень совпадения конкретного поля или токена;
  • fieldWeight — вес поля, заданный конфигурацией.

Чем выше итоговый score, тем выше позиция элемента в выдаче.

Если совпадений нет, элемент исключается из результата.

Роль searchField

Параметр searchField определяет, какие поля объекта участвуют в сопоставлении.

Пример структуры данных:

{
  title: "JavaScript Developer",
  company: "Tech Corp",
  tags: "frontend js remote"
}

Конфигурация:

searchField: ["title", "company", "tags"]

Алгоритм:

  • каждое поле рассматривается отдельно;
  • вычисляется score по каждому полю;
  • итоговый score агрегируется (обычно берётся максимум или сумма с весами).

Это позволяет реализовать многомерный поиск, где разные поля имеют разную семантическую значимость.

Взвешивание полей и sortField

Помимо searchField, используется sortField, который влияет на финальное ранжирование.

Пример:

sortField: [
  { field: "score", direction: "desc" },
  { field: "title", direction: "asc" }
]

Логика:

  1. сначала сортировка по релевантности;
  2. затем стабилизация порядка по дополнительным критериям.

Внутри системы сортировки score всегда имеет приоритет, поскольку отражает качество совпадения.

Частичное совпадение и подстроки

Алгоритм сопоставления поддерживает несколько уровней совпадений:

  • полное совпадение: строка идентична запросу;
  • префиксное совпадение: начало строки совпадает с вводом;
  • внутреннее совпадение: подстрока присутствует внутри значения;
  • токенное совпадение: совпадают отдельные слова.

Рейтинг уменьшается по мере удаления от полного совпадения. Например:

"react" > "react js" > "learn react tutorial" > "javascript framework react"

Fuzzy-поведение и устойчивость к ошибкам ввода

Хотя базовый алгоритм не является полноценным Levenshtein-фаззи поиском, он включает эвристики:

  • допущение неполных токенов;
  • игнорирование порядка слов;
  • частичное совпадение префиксов токенов.

Это создаёт эффект «мягкого поиска», при котором:

  • опечатки частично компенсируются;
  • результаты остаются релевантными при неполном вводе.

Например:

"javscrpt" → может сопоставиться с "javascript"

через частичное совпадение токенов.

Диакритика и языковая устойчивость

Обработка диакритических знаков — важный этап для многоязычных интерфейсов. Алгоритм приводит строки к базовой латинской форме:

"café" → "cafe"
"naïve" → "naive"

Это расширяет область совпадений без изменения исходных данных.

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

Кастомная функция scoreFunction

Tom Select позволяет переопределить стандартную логику сопоставления через scoreFunction.

Сигнатура:

scoreFunction: function(search, option) {
  return number;
}

Механика:

  • функция вызывается для каждого элемента;
  • возвращает числовой score;
  • результаты сортируются по этому значению.

Это полностью заменяет стандартный алгоритм.

Пример расширенной логики:

scoreFunction: function(search, option) {
  let score = 0;

  if (option.title.includes(search)) score += 10;
  if (option.tags.includes(search)) score += 5;

  return score;
}

Такой подход позволяет внедрять доменно-специфичную релевантность.

Влияние threshold и фильтрация результатов

Некоторые реализации используют порог отсечения (threshold), ниже которого элементы исключаются из выдачи.

Логика:

if (score < threshold) → исключить

Это предотвращает попадание нерелевантных элементов в список, особенно при больших наборах данных.

Оптимизация вычислений

Алгоритм сопоставления оптимизирован под частые вызовы при вводе текста:

  • кеширование нормализованных значений;
  • предварительная токенизация элементов списка;
  • сокращение повторных вычислений score для неизменённых строк.

Дополнительно применяется debounce на уровне ввода, что снижает частоту пересчёта результатов при быстром наборе текста.

Поведение при больших наборах данных

При значительных объёмах данных алгоритм использует:

  • раннее отсечение по несовпадению префикса;
  • ограничение количества обрабатываемых элементов;
  • приоритетное вычисление наиболее вероятных совпадений.

Это позволяет сохранять интерактивную скорость даже при тысячах опций.

Роль структуры данных и индексации

Хотя Tom Select не строит полноценный поисковый индекс, внутренняя структура данных может быть подготовлена заранее:

  • заранее нормализованные поля;
  • предрассчитанные токены;
  • кэшированные веса.

Это приближает поведение к легковесному in-memory search engine.

Сравнение строк и стабильность результатов

Алгоритм стремится обеспечить детерминированность:

  • одинаковый ввод всегда даёт одинаковый порядок результатов;
  • при равных score применяется вторичная сортировка;
  • стабильность важна для UI-ожиданий пользователя.

Это исключает «прыгающие» результаты при повторных вычислениях.

Обработка пустого запроса

При пустом вводе алгоритм:

  • либо возвращает ограниченный список элементов;
  • либо показывает дефолтный набор без фильтрации.

Score в этом случае либо не вычисляется, либо считается равным базовому значению.

Такой режим используется для отображения «каталога по умолчанию» без активного поиска.

Оглавление