BonBonSlick
@BonBonSlick
Junior Web Developer Trainee

Поиск и сортировка по % схожести строки?

Среда Doctrine ORM + pgSql.
Пример поиск юзера по имени
Тестовые данные
Rodger
Sauron
Ron
Rin
Ro

Англ - Японские имена.

Юзер вбивает букву R в поиске и понятно дело что если искать просто по LIKE %r%
выдаваемый результат будет в порядке ORDER BY user.name
Rin
Rodger
Sauron
Ro
Ron

это примерный порядок, из головы, при запросе
WHERE user.name LIKE %searchInput% ORDER BY user.name DESC


Что требуется
Ro //  потому что: 1 - начинается на R  + 2 - R это 50% схожесть с searchInput который = 'R'
Rin // идет вторым потому что I перед O в алфавите и схожесть с R, 33%
Ron

// Rodger - выпал, потому что Rodger от R это 1/6, или около 16.8% что менее 30%
// Sauron - выпал из поиска, R в слове, а не в начале имени

примерный порядок, а вот примерный запрос
WHERE user.name LIKE searchInput%
AND WHERE userNameSimilarity > 30%
 ORDER BY user.name DESC 
ORDER BY userNameSimilarity % DESC
  • Вопрос задан
  • 103 просмотра
Решения вопроса 2
Stalker_RED
@Stalker_RED
Соседство в алфавите - так себе критерий. Большая часть опечаток происходит из-за соседства кнопок на клавиатуре (и не забудьте разные раскладки), при неправильном вводе "на слух", или же просто неграмотными пользователями. Для этого давно разработаны алгоритмы нечеткого поиска (или же fuzzy search), в том числе с учетом произношения (soundex) и для больших тесктов (системы антиплагиат, шиндлы, и т.д.).

В postgresql есть встроенные функции для подсчета расстояния Левенштейна и Soundex (и нескольких других).

Для расчета расстояния Хэмминга есть какой-то плагин.

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

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

Гуглите n-gram index, для Постгреса тоже есть реализации.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы