🌍 Добрай раніцы! 🇧🇾

🌍 Добрай раніцы! 🇧🇾

Чем прекрасно программирование, тем что мы можем узнавать что-то новое хоть каждый день, все что нужно от нас, это желание.
Желание быть лучше, чем мы были вчера 💪.
Не все профессии имеют такую особенность, нам с вами очень повезло. Надеюсь вы узнаете что-то новое из поста и кайфанёте 🌈.

Каждый день мы пользуемся поиском, без него никак, каждая уважающая себя система имеет функцию поиска. Я постоянно пользуюсь поиском в VSCode (Ctrl+P, Ctrl+Shift+F, Ctrl+T и тд). Но я даже и не знал, что эти поиски поддерживают Fuzzy Matching, как итог я терял секунды на ввод правильной последовательности того, что ищу.

Прикормил? Интересно? Тогда читаем дальше 😮

🚀 Разбираемся

Fuzzy matching это техника нахождения строк, при котором совпадение запроса с необходимым приблизительное, а не символ в символ.

Обычно как? Мы что-то ввели и на выходе получаем булево значение (совпало / не совпало), а в FM не так, в этом типе поиска возвращается оценка похожести.

Мера измерения в таком поиске это distance: минимальное число операций (вставка, удаление, замена символа), чтобы превратить одну строку в другую.

💡 Пример:

➡️ "javasrcript" → "javascript" = расстояние 1 (удаление лишней r)
➡️ "кедчуп" → "кетчуп" = расстояние 1 (замена д→т)
➡️ "resutl" → "result" = расстояние 1 по Damerau-Levenshtein (транспозиция tl→lt), но 2 по обычному Levenshtein. Ниже станет понятно почему разные расстояния.

Пока писал пост, вспомнил случай:
Покупал билеты на отдых себе и жене, через турагенство, и нам выдали билеты на самолет, так вот у жены была допущена ошибка в фамилии, я уже думал все, буду отдыхать один 😃, но нет. Большинство авиакомпаний допускают незначительные ошибки в имени — обычно 1–3 символа. По сути, они применяют что-то вроде FM.

🔖 Пройдемся по алгоритмам

Алгоритмов на самом деле много, покажу парочку популярных:

1️⃣ Levenshtein Distance

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

Сложность O(m×n), где m и n — длины строк. Для коротких строк — норм, для длинных текстов будет больно.

2️⃣ Damerau-Levenshtein

Расширяет классический Levenshtein, добавляя транспозицию — перестановку соседних символов.

➡️ "tl" → "lt" = 1 операция, а не 2

Почему это важно? В 1964 году Фред Дамерау проанализировал ошибки в и установил, что более 80% опечаток — это одиночная ошибка одного из четырёх типов: лишняя буква, пропущенная буква, неправильная буква или перестановка двух соседних букв. Все четыре типа вместе дают эти 80%, и транспозиция — один из самых частых среди них.

В таком случае если набрали "тпи" вместо "тип", ничего страшного — найдете что хотели 🔥

3️⃣ Jaro-Winkler Similarity

Тут подход другой. Возвращает score от 0.0 до 1.0. Получаем бонус за совпадение первых символов ⭐️

Формула по сути двухэтапная: сначала считается Jaro similarity (учитывает совпадающие символы и транспозиции), а потом Winkler добавляет бонус за общий префикс длиной до 4 символов.

Логика тут имеется: начало слова люди добычно набирают правильно, ошибки чаще в середине и конце. Держите сайтик, тут можно сравнить слова и получить score.

4️⃣ Subsequence Matching

Я поресерчил и нашел какой алгоритм поиска используется в vscode, это как раз subsequence + бонусы за подряд идущие совпадения. Когда мы нажимаем Ctrl+P и набираем usrrep — он находит файл UserRepository.ts.

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

Это не Levenshtein здесь важен именно порядок символов, а не расстояние редактирования.

👨‍💻 Где я еще встретил такой поиск

🔹 Google Search — вы вводите что-то близкое к тому что хотели, можно не переживать вас поправят
🔹 PostgreSQL — расширение pg_trgm
🔹 fzf — если пользуетесь терминалом, попробуйте, удобная утилита для поиска.
🔹 Git — git grep, интеграции с fzf для поиска по коммитам

💬 Делитесь своим мнением в комментариях 👇! Если вам понравился пост, не забудьте поставить лайк! 👍

#PATTERNS #ALGORITHMS