Прямой ответ
Нечёткий поиск находит строки, отличающиеся от запроса на несколько правок. Мера различия — редакционное расстояние: минимальное число односимвольных вставок, удалений и замен, превращающих одну строку в другую.
def levenshtein(a: str, b: str) -> int:
prev = list(range(len(b) + 1))
for i, ca in enumerate(a, 1):
cur = [i]
for j, cb in enumerate(b, 1):
cur.append(min(prev[j] + 1, cur[j - 1] + 1, prev[j - 1] + (ca != cb)))
prev = cur
return prev[-1]
levenshtein("ноутбук", "нотбук") # 1 — пропущена одна буква
levenshtein("клавиатура", "клвиатра") # 2
Расстояние между «ноутбук» и «нотбук» равно единице, поэтому запрос с порогом одна правка находит оба варианта.
| Запрос | Кандидат | Расстояние |
|---|---|---|
| ноутбук | нотбук | 1 |
| ноутбук | ноутбукe | 1 |
| ноутбук | наутбук | 1 |
| ноутбук | компьютер | 8 |
Поисковые движки реализуют нечёткий поиск на уровне индекса: Lucene строит автомат по терминам и обходит его с ограничением на число правок, поэтому перебор всех терминов словаря не выполняется.
Параметр fuzziness в Elasticsearch задаёт допустимое число правок. Значение AUTO выбирает порог по длине термина: короткие термины допускают меньше правок, длинные — больше.
{
"query": {
"fuzzy": {
"title": {
"value": "нотбук",
"fuzziness": "AUTO",
"prefix_length": 1,
"max_expansions": 50
}
}
}
}
Параметр prefix_length исключает правки в первых символах термина, что снижает число ложных совпадений. О практических приёмах — в статье про поиск при опечатках.
Почему расстояние Левенштейна не всегда отражает опечатку
Редакционное расстояние считает все правки равнозначными, а реальные опечатки распределены неравномерно.
Соседние клавиши. Замена буквы на соседнюю по клавиатуре встречается чаще замены на удалённую букву. Расстояние одинаково — единица, — но вероятность опечатки различается в разы. Учёт раскладки требует отдельной модели; о раскладке — в статье про транслитерацию и раскладку.
Перестановка соседних символов. Расстояние Левенштейна считает перестановку двумя правками — удалением и вставкой. Расстояние Дамерау — Левенштейна добавляет перестановку как отдельную операцию с весом единица, что точнее отражает частую опечатку.
Длина строки. Одно и то же расстояние означает разную степень сходства для строк разной длины. Расстояние две для четырёхсимвольной строки — половина строки, для двадцатисимвольной — незначительное отличие.
Практическое следствие: порог допустимых правок выбирают относительно длины термина, а не фиксированным числом. Именно это делает режим AUTO в поисковых движках.
Отдельное ограничение — семантика. «Ноутбук» и «нетбук» отличаются одной буквой, но обозначают разные устройства. Нечёткий поиск по форме слова не различает смысл, поэтому для коротких терминов с близким написанием порог стоит снижать.
Практика: настройка нечёткого поиска
1. Используйте автоматический порог вместо фиксированного. Фиксированное число правок для коротких терминов даёт слишком много ложных совпадений.
2. Задавайте длину префикса. Исключение правок в первых символах снижает число кандидатов и ускоряет запрос.
3. Ограничивайте число развёртываний термина. Параметр max_expansions ограничивает количество терминов, рассматриваемых для одного слова запроса, что влияет на время выполнения.
4. Применяйте нечёткий поиск к отдельным полям. Поиск с допуском опечаток по всем полям индекса увеличивает время запроса без улучшения выдачи.
5. Проверяйте выдачу на реальных опечатках. Набор опечаток из реальных запросов показывает ложные совпадения, которые не видны на синтетических примерах.
6. Сочетайте с точным поиском. Сначала выполняется точный запрос, а нечёткий применяется при пустом либо коротком результате.
7. Измеряйте задержку. Нечёткий запрос выполняется медленнее точного, поскольку обход автомата по терминологическому словарю требует дополнительного времени.
Рекомендации:
- Не применяйте нечёткий поиск к числовым и кодовым полям. Артикулы и идентификаторы ищутся точным совпадением, а допуск правок приводит к выдаче чужих товаров.
- Фиксируйте порог в тестах. Изменение порога меняет выдачу, поэтому проверка результатов на наборе запросов входит в тесты.
- Учитывайте язык. Правила выбора порога зависят от длины слов в языке, поэтому настройка для английского не переносится на русский без проверки.
- Различайте поиск и сопоставление записей. Задача дедупликации записей использует расстояние иначе, чем поиск по запросу, и требует отдельной настройки.
- Проверяйте поведение на длинных запросах. Много слов в запросе с допуском опечаток в каждом даёт комбинаторный рост кандидатов.
Практический сценарий: ложные совпадения при поиске по артикулу
Контекст: поиск по артикулу возвращал товары с другими артикулами.
- Диагностика. Запрос по артикулу «AB-1024» возвращал позиции «AB-1034» и «AB-1025». Поле артикула участвовало в нечётком поиске вместе с заголовком.
- Причина. Нечёткий поиск применялся ко всем полям индекса, включая кодовое поле, где допуск правок не требуется. Расстояние один для артикула означает другой товар.
- Действия. (а) Исключили поле артикула из нечёткого поиска, оставив точное совпадение; (б) ограничили нечёткий поиск полем заголовка и описания; (в) установили длину префикса два символа для заголовка; (г) добавили набор реальных запросов с опечатками в тесты и зафиксировали ожидаемую выдачу; (д) измерили задержку до и после изменения — время запроса снизилось, поскольку обход автомата выполнялся по меньшему числу полей.
- Результат. Поиск по артикулу возвращает только точное совпадение, а нечёткий поиск работает по текстовым полям.
Вывод: допуск опечаток применяется к текстовым полям и не применяется к кодовым. Разделение полей по способу поиска устраняет ложные совпадения и снижает время запроса, а фиксация ожидаемой выдачи в тестах предотвращает регрессии при изменении порога.
FAQ
Чем расстояние Дамерау — Левенштейна отличается от Левенштейна? Добавляет перестановку соседних символов как отдельную операцию с весом единица. В модели Левенштейна перестановка считается двумя правками.
Почему порог зависит от длины слова? Одинаковое число правок означает разную степень сходства для коротких и длинных слов, поэтому автоматический режим масштабирует порог по длине.
Замедляет ли нечёткий поиск запрос? Да, поскольку выполняется обход терминологического словаря с ограничением на правки. Ограничение числа полей и развёртываний снижает влияние.
Подходит ли нечёткий поиск для дедупликации записей? Частично. Задача сопоставления записей требует учёта структуры полей и весов, поэтому расстояние используется как один из признаков, а не как единственное правило.
Источники: Levenshtein distance (Wikipedia), Elasticsearch fuzzy query, Apache Lucene documentation — ссылки в шапке.