Методики поиска по тексту

Привет, друзья!

В этой статье я постарался простым и понятным языком рассказать о том, как работают разные методы поиска текста — от посимвольного поиска до сложных методик, таких как обратный индекс и полнотекстовый поиск. Чтобы объяснения были доступнее, я намеренно избегал сложных терминов и использовал пример с книгой и поиском по её страницам.

Также поделюсь своим личным опытом: как применял подобные технологии в стартапе Many Flats для поиска недвижимости. Надеюсь, статья будет вам интересна и полезна. Как всегда, буду рад вашему мнению и вопросам! 😊

Введение в мир поиска текста

Представьте, что книга, которую мы читаем, — это база данных, а каждый абзац — это отдельная строка данных. Когда мы хотим найти слово "автомобиль", мы можем перелистывать страницы одну за другой, проверяя, есть ли это слово на каждой из них.

В маленькой книге это не сложно, но если книга очень большая, например, 1000 страниц, то процесс может занять много времени. То же самое происходит в базах данных, когда мы ищем слово с помощью обычного поиска.

Теперь представьте, что нам нужно найти не просто слово "автомобиль", а все машины, связанные с определённой маркой. Тогда поиск становится ещё сложнее. Рассмотрим различные методы поиска текста и их влияние на производительность.

Первый метод. Посимвольный поиск с LIKE в SQL

Проблема: Давайте посмотрим на стандартный метод поиска в базе данных — использование оператора LIKE. Это как если бы мы искали слово в книге, открывая каждую страницу по очереди.

Пример запроса: SELECT * FROM cars WHERE name LIKE '%Toyota%';

Этот запрос ищет слово "Toyota" в любом месте текста. Это удобно, но это поиск методом перебора символов, и когда базы данных растут, поиск по каждому слову становится медленным, особенно если слово встречается не в начале, а в середине или конце строки.

Вывод: Метод LIKE не предназначен для полнотекстового поиска. Он подходит для простого поиска по шаблону, но когда речь идёт о больших объемах данных, его использование становится неэффективным.

Второй метод. Полнотекстовый поиск с FULLTEXT индексом

Обратный индекс - главный ключ к быстром поиску

Представьте, что мы записываем на отдельный лист все уникальные слова, встречающиеся в книге, и присваиваем каждому слову уникальный номер.

Затем, просматривая текст книги, мы отмечаем на этом листочке, на каких страницах и в каких абзацах каждое слово из книги встречается.

Такой список с указанием точных координат, где именно встречаются слова в книге, называется обратным индексом. Вот как выглядит обратный индекс для таблицы автомобилей в базе данных:

Как обратный индекс ускоряет процесс поиска?

Допустим у нас пришёл поисковый запрос "автомобиль Toyota Verso, 2.0 D4D mid grade, LHD".

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

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

Пример анализа частоты упоминания слов в книге:

• "автомобиль" упоминается 10,453 раза,

• "Toyota" — 1,047 раз,

• "Verso" — 472 раза,

• "D4D" — всего 7 раз,

• а другие слова имеют свои частоты.

Самым редким оказывается "D4D". Система начинает с него, проверяет только 7 строк, уточняя также по этому обратному индексу, содержат ли эти строки остальные слова из запроса.

Таким образом, обратный индекс не требует перебора строк базы данных. Вся работа по поиску осуществляется в обратном индексе, который основан на предварительно собранной информации о том, какие слова встречаются в книге и на каких страницах и абзацах они упоминаются.

В то время как в книге могут быть миллионы слов, в обратном индексе их количество будет всего несколько сотен. Именно благодаря этому использование обратного индекса на несколько порядков быстрее по сравнению с обычным посимвольным поиском.

Что добавляется к обратному индексу при полнотекстовом поиске?

Проблема: Если мы хотим найти не просто слово, а его части или похожие слова (например, "автомобили" вместо "автомобиль"), обычный поиск не подойдёт. Он найдёт только точные совпадения, а это неудобно, когда нужно искать различные формы слова или похожие термины.

Полнотекстовый поиск — это метод, который позволяет искать не только точные совпадения, но и слова, которые могут быть похожи, или же различные формы слов. Это как если бы мы искали слово "автомобиль" и одновременно искали все его варианты — "автомобили", "авто" и так далее.

Достигается это двумя методами со странными названиями - “стемминг” (оставляем только корни слов) и “лемматизация“ (приводим слова к базовой форме). При стемминге слова "катать", "катался" и "катание" сводятся к одному слову в виде корня "кат". В отличие от стемминга, который просто обрабатывает корни, лемматизация более сложна и приводит слово к его нормальной, словарной форме. Например, вместо "пошёл" будет использовано слово "идти". Это помогает уменьшить количество разных форм одного слова и улучшить точность поиска.

Чтобы включить полнотекстовый поиск в базе данных, нужно создать специальный индекс FULLTEXT следующей командой:

MySQL: CREATE FULLTEXT INDEX idx_description ON cars (Description);

PostgreSQL: CREATE INDEX idx_description_fulltext ON cars USING gin(to_tsvector('english', Description));

Теперь можно искать по всему тексту: SELECT * FROM cars WHERE MATCH(model, description) AGAINST('Toyota');

Этот запрос ищет все записи, где встречается слово "Toyota", но не только точное слово, а все его формы и похожие слова.

Что делает ElasticSearch таким мощным инструментом для поиска?

ElasticSearch от компании Elastic также как FULLTEXT индекс в базах данных использует обратный индекс, но он обладает дополнительными мощными инструментами.

1. Главное преимущество ElasticSearch, которое делает его таким быстрым, — это распределенная архитектура. Представьте, что у нас есть библиотека с десятками залов. Каждый зал хранит часть книг, и когда мы ищем, система может быстро обратиться ко всем этим залам одновременно. Это значительно ускоряет поиск, в отличие от традиционного подхода, когда мы ищем книгу только в одном месте.

2. Второе преимущество ElasticSearch, что он способен анализировать текст, который мы ищем, и не просто находит точное совпадение с нашими словами, а пытается понять их смысл. Например, если мы ищем слово “путеводитель”, ElasticSearch может найти книги, где есть такие слова, как ”гид” или “путеводитель по истории”. Он понимает, что все эти слова связаны между собой. В отличие от обычного поиска, который находит только точные совпадения, ElasticSearch учитывает синонимы и различные формы слов, что делает поиск гораздо более точным.

3. Третий крутой инструмент в ElasticSearch — это агрегации. Например, если мы хотим узнать, на каких страницах книги встречается слово “гид”, ElasticSearch не только найдет его, но и подсчитает, на каких страницах оно встречается чаще всего, а также в каком контексте. Это похоже на то, как если бы мы могли не только найти все страницы с нужным словом, но и сразу понять, где оно наиболее важно. Это очень круто!

В отличии от других систем поиск, также стоит отметить, что ElasticSearch гораздо быстрее обрабатывает большие объемы данных. Представьте, что в библиотеке тысячи книг, и нам нужно найти в каждой из них слово “гид”. В традиционном поиске система будет поочередно проверять каждую книгу. В ElasticSearch поиск будет происходить одновременно по многим книгам, что значительно сокращает время поиска.

Когда стоит выбрать ElasticSearch?

• Когда нужно искать в большом объеме данных. Например, если у вас есть большая база данных товаров в интернет-магазине, и вы хотите быстро найти нужное слово в каждом из них.

• Когда поисковые запросы становятся сложными. Например, вы хотите не только найти слово, но и узнать, где оно встречается чаще, или какие товары его используют в разных контекстах.

• Когда нужно делать поиск быстро. Если у вас тысячи каталогов товаров, и вы хотите найти слово за секунды, а не за минуты.

ElasticSearch очень мощный инструмент, но он может требовать специальных знаний для настройки и обслуживания. Например, если мы используем ElasticSearch в большой компании, нам нужно следить за его работой, чтобы поддерживать высокую производительность. В одном популярном интернет-магазине у нас в команде был специально выделенный сотрудник, который только и занимался ElasticSearch, его настройками, оптимизировацией запросов и анализом производительности системы.

Если вам нужно не просто найти слова в базе данных, а сделать поиск умным, быстрым и точным, ElasticSearch — это ваш выбор. Он предоставляет гораздо больше возможностей и гибкости по сравнению с обычным поиском в базах данных, что делает его идеальным для сложных поисковых задач.

Мой личный опыт создания полнотекстового поиска

Пять лет назад я самостоятельно изобретал систему поиска текста. Мы с товарищем запустили стартап ManyFlats.com — систему поиска выгодной недвижимости. Суть проекта заключалась в том, что я разработал систему, которая парсила ведущие сайты недвижимости в Германии, Испании, Италии, Португалии, Австрии, Латвии и Литве. Мы собирали данные обо всех предложениях: аренда или продажа, жилые объекты, земельные участки и коммерческая недвижимость.

Скриншот первой версии проекта ManyFlats:

Техническая часть

Как мы это делали — это отдельная история. Если вкратце: использовалась имитация работы 20 браузеров, перебор через 7000 IP-адресов, решатели капч и многое другое. Огромный поток информации в сыром виде сначала поступал в кэш, а затем в начальную базу данных. После этого в работу вступала система построения обратного индекса, которую я разработал. Она включала стемминг и лемматизацию (тогда я даже не знал, что эти процессы так называются). На выходе система генерировала множество SQLite-файлов — фактически под каждое ключевое слово создавался отдельный файл с результатами выдачи.

При вводе поискового запроса достаточно было открыть соответствующий SQLite-файл с готовыми результатами, применить дополнительные фильтры при необходимости — и вуаля, почти мгновенный результат! Система работала великолепно для операций чтения.

Скриншот второй версии проекта ManyFlats:

Можно было искать на русском языке по немецким сайтам. К слову, на немецких сайтах нет не то что русскоязычных версий страниц, но даже англоязычных нет. На скриншоте — та же вторая версия проекта, но с другим дизайном. Она была заточена под распознавание голосового запроса и дальнейший поиск на основе текстового запроса, но с возможностью использовать также привычные фильтры.

Бизнес-часть

Мы знали, какие объекты продаются, какие сдаются в аренду, их точные координаты и полное описание. Подсмотрев методы оценки недвижимости у латвийских специалистов, я применил их в нашем проекте. В итоге мы могли находить объекты, которые явно дешевле рыночной цены. А самое главное — мы сделали возможность поиска объектов по их доходности. Система заранее рассчитывала доходность каждого объекта в базе данных и показывала потенциальную прибыль от сдачи объекта в аренду после покупки, а также предоставляла обоснование расчётов.

Мы пошли ещё дальше: я разработал поиск на любом языке по всем проиндексированным сайтам. Это работало так: поисковый запрос пользователя (будь то текст, набранный на клавиатуре, голосовой запрос или параметры через форму) переиндексировался. Затем система сопоставляла запрос с обратным индексом, и результаты выдавались на экран за доли секунды.

Третья и финальная версия проекта ManyFlats (к тому времени переименовали его в Propby):

Главная страница, на которой видно, какие тепловые карты я научился делать благодаря лайфхакам (разукрашивал прямо картинку):

Что стало с проектом?

Буквально через пару недель после запуска я впервые в жизни презентовал наш стартап руководителям семи венчурных фондов, причём онлайн. Посмотреть можно на YouTube в ролике "Венчурная кухня 9" по адресу: https://youtu.be/hBZMVKy9vAY?si=GVcXBIOjDbhR5_xK.

Тогда денег не дали, идею раскритиковали, но я глубже погрузился в сферу proptech (property technologies — технологии в недвижимости). Спустя год - проект закрылся. Самое ценное: я познакомился с потрясающими людьми, двое из которых стали моими друзьями.

Чему меня научил этот опыт

Как же я был удивлён, когда спустя время, изучая ElasticSearch, понял, что изобретал тогда полнотекстовый поиск. Я отлично представляю, какие именно проблемы Elastic решали на каждом этапе, так как сам с ними сталкивался. Конечно, ElasticSearch — это профессиональная система, и стоило просто её использовать, вместо того чтобы изобретать велосипед.

Зато я многому научился: профессионально работать с текстами, понимать проблемы этой сферы, строить тепловые карты, генерировать качественные отчёты по оценке недвижимости и многое другое. Могу говорить об этом часами, но пора заканчивать.

Если вам интересны практические советы, истории из жизни различных проектов, разбор простыми словами сложных технологий и архитектурных решений, подписывайтесь на мой Telegram-канал "Системный архитектор для людей". Там я делюсь опытом, который помогает создавать эффективные системы и делает сложные вещи понятными. Присоединяйтесь, будет интересно!