Индексирование для быстрого поиска

Любая система быстрого поиска начинается не с индекса как структуры, а с подготовки строковых данных. В JavaScript при работе с многоязычными текстами критично учитывать различия Unicode-представления, регистр и диакритические знаки.

Базовый этап подготовки включает приведение строки к каноническому виду:

const normalizeText = (str) =>
  str.normalize('NFC');

Нормализация устраняет различия в представлении одинаковых символов (например, «é» может быть представлена как один символ или как комбинация e + ́).

Следующий уровень — унификация регистра и диакритики. Однако простое .toLowerCase() недостаточно для локалей, поэтому используется Intl.Collator.

Локаль-ориентированное сравнение и ключи сортировки

Intl.Collator предоставляет механизм сравнения строк с учётом языка, чувствительности и правил сортировки.

const collator = new Intl.Collator('ru', {
  sensitivity: 'base',
  usage: 'sort'
});

Параметр sensitivity: 'base' задаёт игнорирование регистра и диакритики, что критично для поисковых индексов, где важно совпадение по «основе» слова.

Сравнение:

collator.compare('ёлка', 'Елка'); // 0 (эквивалентны)

Использование в индексировании

Хотя API не предоставляет прямого метода генерации «sort key», поведение можно имитировать через предварительную сортировку и хранение нормализованных форм:

function createSortKey(str, collator) {
  return str
    .normalize('NFC')
    .toLowerCase();
}

Более точный вариант — хранить оригинал и отдельное нормализованное поле:

const data = [
  { id: 1, title: 'Ёжик' },
  { id: 2, title: 'Ежедневник' }
];

const collator = new Intl.Collator('ru', { sensitivity: 'base' });

const indexed = data.map(item => ({
  ...item,
  key: item.title.normalize('NFC')
}));

Построение поискового индекса на основе токенизации

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

Ключевая проблема — корректное разбиение текста на токены в разных языках. Intl.Segmenter решает задачу языково-зависимой сегментации.

const segmenter = new Intl.Segmenter('ru', { granularity: 'word' });

function tokenize(text) {
  return [...segmenter.segment(text)]
    .filter(s => s.isWordLike)
    .map(s => s.segment.toLowerCase());
}

Инвертированный индекс с учётом локализации

Базовая структура индекса:

const index = new Map();

Построение:

function addToIndex(doc) {
  const tokens = tokenize(doc.title);

  for (const token of tokens) {
    if (!index.has(token)) {
      index.set(token, new Set());
    }
    index.get(token).add(doc.id);
  }
}

Такой подход позволяет получать кандидатов за O(1) по ключу токена.

Поиск с использованием локализованного сопоставления

Поиск выполняется в два этапа:

  1. получение кандидатов из индекса
  2. уточнение через Intl.Collator
function search(query, docs) {
  const tokens = tokenize(query);

  let resultIds = null;

  for (const token of tokens) {
    const ids = index.get(token) || new Set();
    resultIds = resultIds
      ? new Set([...resultIds].filter(x => ids.has(x)))
      : ids;
  }

  const collator = new Intl.Collator('ru', { sensitivity: 'base' });

  return docs.filter(doc =>
    [...resultIds].includes(doc.id) &&
    collator.compare(doc.title, query) === 0
  );
}

На практике сравнение compare === 0 используется редко; чаще применяется частичное совпадение через нормализованные формы.

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

Для поиска по префиксу или подстроке используется комбинированный подход: индекс + локализованное сравнение.

function matchScore(title, query, collator) {
  const t = title.normalize('NFC');
  const q = query.normalize('NFC');

  if (t.startsWith(q)) return 2;
  if (collator.compare(t, q) === 0) return 3;
  if (t.includes(q)) return 1;

  return 0;
}

Ранжирование строится на основе оценки:

function rankedSearch(query, docs) {
  const collator = new Intl.Collator('ru', { sensitivity: 'base' });

  return docs
    .map(doc => ({
      doc,
      score: matchScore(doc.title, query, collator)
    }))
    .filter(x => x.score > 0)
    .sort((a, b) => b.score - a.score)
    .map(x => x.doc);
}

Индексация с учётом числовых значений

Intl.Collator поддерживает корректное сравнение чисел внутри строк:

const collator = new Intl.Collator('ru', {
  numeric: true,
  sensitivity: 'base'
});

Это влияет на сортировку:

collator.compare('file2', 'file10'); // -1 (2 < 10)

Без numeric: true сортировка будет лексикографической, что нарушает порядок в индексах.

Стабильная сортировка индекса

Для ускорения поиска часто создаётся отсортированный массив ключей:

const sorted = [...data].sort((a, b) =>
  collator.compare(a.title, b.title)
);

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

function binarySearch(arr, query) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = (left + right) >> 1;
    const cmp = collator.compare(arr[mid].title, query);

    if (cmp === 0) return arr[mid];
    if (cmp < 0) left = mid + 1;
    else right = mid - 1;
  }

  return null;
}

Оптимизация хранения ключей

При больших объёмах данных повторная нормализация становится затратной. Поэтому используется предварительное хранение «поисковых ключей»:

function buildKey(str, collator) {
  return str.normalize('NFC').toLowerCase();
}

Для ускорения:

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

Разделение токенов и языковая специфика

Разные языки требуют разных стратегий сегментации. Intl.Segmenter учитывает это автоматически:

  • в русском и английском — разделение по словам
  • в китайском — по смысловым сегментам
  • в японском — комбинированная модель
const segmenter = new Intl.Segmenter('ja', { granularity: 'word' });

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

Многоязычный индекс как единая структура

При хранении мультиязычных данных индекс обычно строится с привязкой к локали:

const indexes = new Map();

function getIndex(locale) {
  if (!indexes.has(locale)) {
    indexes.set(locale, new Map());
  }
  return indexes.get(locale);
}

Каждая локаль использует свой Intl.Collator и Intl.Segmenter, что обеспечивает корректную сортировку и поиск без смешивания правил.

Комбинированная модель быстрого поиска

Эффективный поисковый механизм обычно сочетает:

  • инвертированный индекс по токенам
  • нормализованные ключи для быстрого сравнения
  • Intl.Collator для финального ранжирования
  • Intl.Segmenter для универсальной токенизации
  • сортированные структуры для бинарного поиска

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

Оглавление