Как устроен поисковый индекс

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

Продолжим использовать шесть документов и прежние URL. Индекс не меняет содержимое страницы и не создаёт новые адреса. Результатом урока станет модуль core.js, который строит словарь и находит документы, содержащие все слова запроса независимо от их непосредственного соседства.

Словарь связей

Рассмотрим маленькую часть учебного корпуса. В XML-уроке встречаются linq и xml, а в других материалах этих сочетаний нет. После обработки словарь может выглядеть следующим образом:

linq → xml
xml  → xml
markdown → markdown
таблиц → sql

Слева записан термин, справа — ID документа. Название xml справа относится к личности материала, а не к слову. В большой библиотеке один термин будет связан с несколькими ID. Эта разница особенно важна, когда ID случайно совпадает с названием технологии.

Не будем сохранять один ID много раз только потому, что слово повторено в статье. Первое устройство индекса отвечает на вопрос о наличии термина. Частоту и значимость поля рассмотрим отдельно; сейчас повторение слова не должно создавать повторные карточки.

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

Нормализация и термины

Одинаковое правило нужно применять к документу и к запросу. Если индекс содержит слово в нижнем регистре, а запрос остаётся в исходном, совпадение не появится. В первом модуле сохраняем приведение регистра, Unicode-нормализацию и замену ё на е.

Регулярное выражение выделяет последовательности букв, цифр и подчёркивания. Это простой учебный токенизатор. Он распознаёт русские буквы благодаря Unicode-классам, но пока теряет часть пунктуации технических названий. Отдельный урок исправит C# и .NET; введение индекса само по себе не решает все языковые вопросы.

Слова запроса превращаются в уникальные термины. Запрос xml xml не должен дважды требовать одно совпадение или искусственно повышать оценку. При этом мы пока не удаляем служебные слова автоматически. Такое удаление требует решения о языке и назначении коротких запросов.

Создайте public/core.js. Ниже полный модуль этой версии:

export function normalize(value) {
  return String(value).normalize("NFKC").toLocaleLowerCase("ru").replace(/ё/g, "е");
}

export function tokenize(value) {
  return [...new Set(normalize(value).match(/[\p{L}\p{N}_]+/gu) || [])];
}

export function buildIndex(documents) {
  const byId = new Map();
  const postings = new Map();
  for (const doc of documents) {
    if (byId.has(doc.id)) throw new Error("Повторяющийся ID");
    byId.set(doc.id, doc);
    const terms = tokenize([doc.title, ...doc.headings, doc.text].join(" "));
    for (const term of terms) {
      if (!postings.has(term)) postings.set(term, new Map());
      postings.get(term).set(doc.id, 1);
    }
  }
  return { byId, postings };
}

export function searchIndex(index, query) {
  const terms = tokenize(query);
  if (!terms.length) return { hits: [], total: 0 };
  let candidates = new Map(index.postings.get(terms[0]) || []);
  for (const term of terms.slice(1)) {
    const posting = index.postings.get(term) || new Map();
    for (const [id, score] of candidates) {
      if (!posting.has(id)) candidates.delete(id);
      else candidates.set(id, score + posting.get(id));
    }
  }
  const hits = [...candidates].map(([id, score]) => ({ ...index.byId.get(id), score }));
  hits.sort((a, b) => b.score - a.score || a.id.localeCompare(b.id));
  return { hits, total: hits.length };
}

Map используется для словаря и для поиска документа по ID. Это избавляет от специальных свойств обычного объекта и делает получение значения явным. Вложенный Map хранит ID и пока условную оценку 1.

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

Пересечение списков

Для запроса LINQ XML токенизатор создаёт два термина. Берём кандидатов из первого списка и оставляем только те ID, которые присутствуют во втором. Это пересечение: найденный документ должен содержать оба слова.

В XML-уроке между этими словами может находиться to. Поиск подстроки такую фразу не находил, а новая версия ищет слова раздельно. Ожидаемый результат для LINQ XML — карточка xml. Мы изменили смысл совпадения, а не только ускорили старое правило.

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

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

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

Подключение модуля к странице

В app.js предыдущего урока добавьте импорт в начало файла:

import { buildIndex, searchIndex } from "./core.js";

После функции loadDocuments создайте загрузчик индекса. Он использует уже существующую загрузку JSON и не заменяет функцию render:

let indexPromise;
function loadIndex() {
  if (!indexPromise) {
    indexPromise = loadDocuments().then(buildIndex).catch(error => {
      indexPromise = undefined;
      throw error;
    });
  }
  return indexPromise;
}

В обработчике отправки формы замените получение документов и вызов find такими строками:

const index = await loadIndex();
const found = searchIndex(index, query).hits;
render(found);

Остальная обработка сообщений пока остаётся прежней. Старую функцию find и её локальную нормализацию можно удалить: поиск теперь выполняется модулем. Полные согласованные файлы этой контрольной точки находятся в учебных исходниках после урока 4.

Обратите внимание на формат результата: hits содержит карточки, а total — число совпадений до будущей пагинации. Уже сейчас называем поля так, чтобы не пришлось объяснять один и тот же параметр разными словами при переходе к серверу.

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

Индекс разделяет подготовку и запросы и меняет поиск фразы на поиск терминов. Но в нём пока нет опечаток, морфологии и веса заголовка. Запрос «соединить таблицы» может не найти документ с формой «соединение таблиц»: программа всё ещё сравнивает конкретные термины.

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

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

Теперь у нас есть первая полная контрольная версия: экспортированные документы, модуль индекса и страница поиска. Следующий урок введёт разные веса полей, чтобы слово в названии урока влияло на порядок сильнее случайного упоминания в тексте.