Реализация поиска с исправлением опечаток для веб-приложения

Реализация поиска с исправлением опечаток для веб-приложения

Пользователи делают ошибки: "наушниик", "беспродные", "samsng". Поиск без fuzzy matching возвращает пустой результат. Это теряет конверсию. Реализуем устойчивый к опечаткам поиск тремя способами — в зависимости от масштаба и требований.

Метрика расстояния: Levenshtein vs Damerau-Levenshtein

Расстояние Левенштейна: минимальное количество вставок, удалений, замен для превращения одной строки в другую.

Дамерау-Левенштейн добавляет транспозицию (перестановку соседних символов): "наушинки" → "наушники" — это 1 транспозиция, а не 2 операции. Для поиска предпочтительнее Дамерау-Левенштейн.

PostgreSQL: pg_trgm

pg_trgm — расширение PostgreSQL для similarity-поиска на основе триграмм. Работает без внешних сервисов.

CREATE EXTENSION IF NOT EXISTS pg_trgm;

-- Индекс для similarity search
CREATE INDEX idx_products_title_trgm ON products USING GIN (title gin_trgm_ops);
CREATE INDEX idx_products_description_trgm ON products USING GIN (description gin_trgm_ops);

-- Поиск с порогом схожести
SET pg_trgm.similarity_threshold = 0.3;

SELECT id, title, similarity(title, 'наушниик') AS sim
FROM products
WHERE title % 'наушниик'         -- оператор similarity
ORDER BY sim DESC
LIMIT 10;

-- Или комбинируем FTS + fuzzy:
SELECT
    p.id,
    p.title,
    p.price,
    greatest(
        similarity(p.title, 'беспродные наушники'),
        ts_rank(p.search_vector, plainto_tsquery('russian', 'беспродные наушники'))
    ) AS relevance
FROM products p
WHERE
    p.title % 'беспродные наушники'
    OR p.search_vector @@ plainto_tsquery('russian', 'беспродные')
ORDER BY relevance DESC
LIMIT 20;

% — оператор схожести, использует GIN-индекс. Без индекса деградирует до seq scan.

Настройка порога: 0.3 — либерально (много шума), 0.5 — строго (мало опечаток). Для коротких запросов (1–2 слова) порог должен быть ниже.

Meilisearch: dedicate fuzzy search engine

Meilisearch написан на Rust, поддерживает typo tolerance из коробки, прост в настройке.

# Docker
docker run -p 7700:7700 getmeili/meilisearch:latest

# Или через бинарник
curl -L https://install.meilisearch.com | sh
./meilisearch --master-key="your-master-key"

Настройка индекса:

import meilisearch

client = meilisearch.Client('http://localhost:7700', 'your-master-key')
index = client.index('products')

# Настройки поиска
index.update_settings({
    'searchableAttributes': ['title', 'brand', 'description', 'tags'],
    'filterableAttributes': ['category_id', 'status', 'price', 'brand'],
    'sortableAttributes': ['price', 'created_at', 'popularity'],
    'rankingRules': [
        'words',
        'typo',
        'proximity',
        'attribute',
        'sort',
        'exactness',
    ],
    'typoTolerance': {
        'enabled': True,
        'minWordSizeForTypos': {
            'oneTypo': 5,     # слова >= 5 символов допускают 1 опечатку
            'twoTypos': 9,    # слова >= 9 символов допускают 2 опечатки
        },
        'disableOnWords': ['iPhone', 'iPad', 'MacBook'],  # бренды без fuzzy
        'disableOnAttributes': ['sku', 'barcode'],
    },
    'pagination': {
        'maxTotalHits': 10000,
    },
})

Индексирование данных:

import asyncio
from typing import Any

async def sync_products_to_meilisearch(products: list[dict[str, Any]]) -> None:
    """Батчевая синхронизация продуктов."""
    documents = [
        {
            'id': p['id'],
            'title': p['title'],
            'brand': p.get('brand', ''),
            'description': p.get('description', ''),
            'category_id': p['category_id'],
            'price': float(p['price']),
            'status': p['status'],
            'tags': [t['name'] for t in p.get('tags', [])],
            'created_at': p['created_at'].timestamp(),
            'popularity': p.get('view_count', 0),
        }
        for p in products
        if p['status'] == 'published'
    ]

    # Meilisearch принимает батчи до 100MB
    batch_size = 1000
    for i in range(0, len(documents), batch_size):
        batch = documents[i:i + batch_size]
        task = index.add_documents(batch)
        # Ждём завершения (опционально)
        index.wait_for_task(task.task_uid)

Поиск:

from dataclasses import dataclass


@dataclass
class SearchParams:
    query: str
    category_id: int | None = None
    price_min: float | None = None
    price_max: float | None = None
    page: int = 1
    hits_per_page: int = 20
    sort: str = 'relevance'  # relevance | price:asc | price:desc | created_at:desc


def build_filter(params: SearchParams) -> str | None:
    filters = ['status = "published"']

    if params.category_id:
        filters.append(f'category_id = {params.category_id}')
    if params.price_min is not None:
        filters.append(f'price >= {params.price_min}')
    if params.price_max is not None:
        filters.append(f'price <= {params.price_max}')

    return ' AND '.join(filters) if filters else None


def search_products(params: SearchParams) -> dict:
    sort_map = {
        'price:asc':   ['price:asc'],
        'price:desc':  ['price:desc'],
        'created_at:desc': ['created_at:desc'],
        'relevance':   [],  # дефолтный ranking rules
    }

    results = index.search(params.query, {
        'filter':       build_filter(params),
        'sort':         sort_map.get(params.sort, []),
        'page':         params.page,
        'hitsPerPage':  params.hits_per_page,
        'attributesToHighlight': ['title', 'description'],
        'highlightPreTag':  '<mark>',
        'highlightPostTag': '</mark>',
        'attributesToCrop': {'description': 200},
        'showMatchesPosition': False,
    })

    return results

Ответ Meilisearch при запросе "наушниик sony":

{
  "hits": [
    {
      "id": 1234,
      "title": "Sony WH-1000XM5 беспроводные наушники",
      "_formatted": {
        "title": "Sony WH-1000XM5 беспроводные <mark>наушники</mark>"
      }
    }
  ],
  "query": "наушниик sony",
  "processingTimeMs": 4,
  "totalHits": 38,
  "page": 1,
  "hitsPerPage": 20
}

Elasticsearch: fuzzy_query

Если Elasticsearch уже используется для FTS — fuzzy в нём встроен:

{
  "query": {
    "bool": {
      "should": [
        {
          "multi_match": {
            "query": "наушниик",
            "fields": ["title^3", "brand^2", "description"],
            "fuzziness": "AUTO",
            "prefix_length": 2,
            "max_expansions": 50
          }
        },
        {
          "match_phrase": {
            "title": {
              "query": "наушниик",
              "slop": 2
            }
          }
        }
      ]
    }
  }
}

prefix_length: 2 — первые 2 символа должны совпадать точно. Это снижает количество ложных срабатываний и ускоряет запрос.

AUTO fuzzy: 0 опечаток для слов ≤2 символов, 1 для 3–5 символов, 2 для 6+ символов.

Выбор подхода

Для небольшого каталога (до 100k записей) с PostgreSQL в стеке — pg_trgm достаточно. Для крупного каталога с фасетами, фильтрами и требованием <10ms — Meilisearch. Для аналитической платформы с агрегациями — Elasticsearch.

Сроки

pg_trgm (расширение, индексы, запросы, tuning threshold): 1 день. Meilisearch (деплой, настройка индекса, синхронизация, API): 2–3 дня. Fuzzy в существующем Elasticsearch кластере: 1 день.