Опечатки и синонимы

После обработки словоформ поиск всё ещё требует буквального присутствия внутренних терминов. Пользователь может написать JS вместо JavaScript или переставить буквы в Nginx. Такие запросы не обязательно выражают другую задачу. Теперь научим индекс рассматривать ограниченный набор альтернатив.

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

Альтернативы внутри одного условия

Для запроса из двух слов по-прежнему нужны два условия. Но каждое условие может содержать варианты. Например, первая группа означает «javascript или js», а вторая — «запрос». Между группами остаётся пересечение, внутри группы используется объединение.

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

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

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

Небольшой словарь

В core.js добавьте словарь после функций токенизации. Значения уже записаны в нормализованном виде:

const SYNONYMS = new Map([
  ["js", ["javascript"]],
  ["javascript", ["js"]],
  ["джс", ["javascript"]]
]);
const PROTECTED = new Set(["csharp", "cpp", "dotnet", "nodejs"]);

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

PROTECTED отмечает технические обозначения, для которых не будем угадывать опечатку. Точная обработка C# уже определена предыдущим уроком; случайное похожее слово не должно автоматически становиться названием языка.

Одно изменение или перестановка

Для учебного исправления используем ограниченное сравнение: одна замена, вставка, удаление либо перестановка соседних символов. Ниже полная функция, которую нужно добавить в core.js:

function near(a, b) {
  if (a === b) return true;
  if (Math.abs(a.length - b.length) > 1) return false;
  if (a.length === b.length) {
    const changed = [];
    for (let i = 0; i < a.length; i++) if (a[i] !== b[i]) changed.push(i);
    if (changed.length === 1) return true;
    if (changed.length !== 2) return false;
    const [i, j] = changed;
    return j === i + 1 && a[i] === b[j] && a[j] === b[i];
  }
  const longer = a.length > b.length ? a : b;
  const shorter = a.length > b.length ? b : a;
  let i = 0;
  while (i < shorter.length && longer[i] === shorter[i]) i++;
  return longer.slice(i + 1) === shorter.slice(i);
}

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

Пример рассчитан на короткие термины нашего корпуса. JavaScript считает длину строки в кодовых единицах; для произвольных символов за пределами базовой плоскости потребовалось бы более аккуратное представление. Это ещё одна причина не называть функцию универсальной языковой обработкой.

Подготовка групп

Добавьте функцию queryGroups. Она сначала проверяет точный термин и известные синонимы, а к похожим словам обращается только при отсутствии найденных альтернатив.

function queryGroups(index, query) {
  return tokenize(query).map(term => {
    let variants = [term, ...(SYNONYMS.get(term) || [])]
      .filter(value => index.postings.has(value));
    if (!variants.length && term.length >= 4 && !PROTECTED.has(term)) {
      variants = [...index.postings.keys()]
        .filter(value => !PROTECTED.has(value) && near(term, value))
        .sort()
        .slice(0, 8);
    }
    return [...new Set(variants)];
  });
}

Число 8 ограничивает размер одного расширения в учебной версии. Это выбранный предел, а не правило внешнего поискового движка. Если существует больше похожих терминов, часть не попадёт в группу; такое ограничение должно быть видно при оценке.

Мы не расширяем известное точное слово опечатками автоматически. Сначала используем доказанное присутствие термина. Такой порядок уменьшает риск, что короткий точный запрос начнёт находить множество соседних названий.

Перебор всего словаря при неизвестном слове подходит только для небольшого учебного индекса. Его стоимость растёт вместе с числом уникальных терминов. Позднее измерим её отдельно и сравним с готовым серверным поиском.

Поиск по группам

Замените searchIndex целиком. Построение индекса, токенизатор и формат документов остаются прежними.

export function searchIndex(index, query) {
  const groups = queryGroups(index, query);
  if (!groups.length || groups.some(group => !group.length)) {
    return { hits: [], total: 0 };
  }
  let candidates;
  for (const group of groups) {
    const scores = new Map();
    for (const term of group) {
      for (const [id, score] of index.postings.get(term)) {
        scores.set(id, Math.max(scores.get(id) || 0, score));
      }
    }
    if (!candidates) candidates = scores;
    else for (const [id, score] of candidates) {
      if (!scores.has(id)) candidates.delete(id);
      else candidates.set(id, score + scores.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 };
}

Для ngnix ожидается кандидат по термину nginx, а для JS — документ, содержащий JavaScript. Запрос из неизвестного набора без подходящих альтернатив остаётся пустым. Программа не обязана находить материал любой ценой.

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

Проверка границ

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

Короткие названия особенно чувствительны к исправлениям: одна буква может менять смысл полностью. Наш нижний предел длины защищает часть таких случаев. Для кодов ошибок, артикулов и номеров версий может понадобиться полное отключение исправления.

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

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

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

Есть ещё менее заметный случай. Когда ошибочная строка случайно совпала с настоящим словом словаря, наша функция не рассматривает соседние термины. Это осознанный приоритет точного совпадения. Он ограничивает угадывание, но иногда пропускает намерение пользователя. Для более сложного продукта можно предложить отдельную альтернативу «Возможно, вы искали…», сохранив исходную выдачу. Такое изменение требует нового договора интерфейса и оценки; оно не появляется автоматически из функции near.

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