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

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

Користувачи роблять помилки: "навушниик", "бесплодные", "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: movimento пошуку з исправленням

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

Elasticsearch: Fuzzy запит

Якщо 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 (розширення, індекси, запити, настройка порога): 1 день. Meilisearch (deploy, настройка індексу, синхронізація, API): 2–3 дні. Fuzzy в існуючому Elasticsearch кластері: 1 день.