поиск с учетом языковой морфологии
Морфологический поиск
Точный поиск, реализуемый в базах данных это очень хорошо, когда дело касается точных фраз. Но что делать, когда среди документов есть Киевская карта но нету Карты Киева? В дело включаются языковые фильтры.Во-первых уже на лексическом уровне становится сложно оперировать с монолитным блоком текста что-бы учитывать всевозможные перестановки слов и расстояния между ними. Во-вторых, чем глубже копать в язык, тем ясней становится то, что семантический web — невероятно сложная планка для автоматических анализаторов и генераторов каких-то образов и моделей, что уж говорить про то что-бы написать RDF вручную.Морфология изучает изменение формы объектов в разных областях науки (ботанике например). Поэтому есть два пути — либо
учитывать все формы при поиске, либо вырезать корень слова и искать
только по нему. Последний способ называется stemming, отличается
быстротой, простотой и не нуждается в словарях. Именно его используют Битрикс и MS Sharepoint, Sphinx. Проблемы возникают со словами где корень изменчив (бег-бежать, расти-прирост, лев-львица). Я не буду рассказывать про стемминг, посмотрите как это реализовано php с русской морфологией. Меня больше интересуют словари. Национальный корпус русского языка приводит примерно какие характеристики могут иметься у любого слова. Теперь мы плавно подходим к пониманию того что нам необходима современная морфологическая база слов (RMU, AOT), прототип для семантической сети.
Поиск на сайте своими руками
Наверное, многие когда-нибудь задумывались, как сделать поиск на сайте? Безусловно, для крупных сайтов с большим количеством контента поиск является просто незаменимой вещью. В большинстве случаев пользователь, впервые посетив Ваш сайт в поисках чего-либо важного, не станет разбираться в навигационных панелях, выпадающих меню и прочих элементах навигации, а в спешке попытается найти что-нибудь похожее на поисковую строку. И если такой роскоши на сайте не окажется, либо он не справится с поисковым запросом, то посетитель просто закроет вкладку. Но статья не о значении поиска для сайта и не о психологии посетителей. Я расскажу, как реализовать небольшой алгоритм полнотекстового поиска, который, надеюсь, избавит начинающих разработчиков от головной боли.
У читателя может возникнуть вопрос: зачем писать все с нуля, если все уже давно написано? Да, у крупных поисковиков есть API, есть такие клевые проекты, как Sphinx и Apache Solr. Но у каждого из этих решений есть свои преимущества и недостатки. Пользуясь услугами поисковиков, типа Google и Яндекс, Вы получите множество плюшек, таких как мощный морфологический анализ, исправление опечаток и ошибок в запросе, распознавание неверной раскладки клавиатуры, однако без ложки дегтя тут не обойдется. Во первых, такой поиск не интегрируется в структуру сайта — он внешний, и Вы не сможете указать ему, какие данные наиболее важны, а какие не очень. Во вторых, содержимое сайта индексируется только с определенным интервалом, который зависит от выбранного поисковика, так что если на сайте что-нибудь обновится, придется дожидаться момента, когда эти изменения попадут в индекс и станут доступными в поиске. У Sphinx и Apache Solr дела с интеграцией и индексированием гораздо лучше, но не каждый хостинг позволит из запустить.
Ничто не мешает написать поисковый механизм самостоятельно. Предполагается, что сайт работает на PHP в связке с каким-нибудь сервером баз данных, например MySQL. Давайте сначала определимся, что требуется от поиска на сайте?
В конце статьи будет показан пример реализации поиска на примере простого интернет-магазина. Тем, кому лень все это изучать и просто нужен готовый поисковик, можно смело забирать движок из репозитория GitHub FireWind.
Принцип работы
Подготовка
Задача поставлена, теперь можно перейти к делу. Я использую Linux в качестве рабочей ОС, однако постараюсь не использовать ее экзотических возможностей, чтобы любители Windows смогли «собрать» поисковый движок по аналогии. Все, что Вам нужно — это знание основ PHP и умение обращаться с MySQL. Поехали!
Наш проект будет состоять из ядра, где будут собраны все жизненно необходимые функции, а также модуля морфологического анализа и обработки текста. Для начала создадим корневую папку проекта firewind, а в ней создадим файл core.php — он и будет ядром.
Теперь вооружаемся своим любимым текстовым редактором и подготавливаем каркас:
Тут мы создали основной класс, который можно будет использовать на Ваших сайтах. На этом подготовительная часть заканчивается, пора двигаться дальше.
Морфологический анализатор
Русский язык — довольно сложная штука, которая радует своим разнообразием и шокирует иностранцев конструкциями, типа «да нет, наверное». Научить машину понимать его, да и любой другой язык, — довольно непростая задача. Наиболее успешны в этом плане поисковые компании, типа Google и Яндекс, которые постоянно улучшают свои алгоритмы и держат их в секрете. Придется нам сделать что-то свое, попроще. К счастью, колесо изобретать не придется — все уже сделано за нас. Встречайте, phpMorphy — морфологический анализатор, поддерживающий русский, английский и немецкий языки. Более подробную информацию можно получить тут, однако нас интересуют только две его возможности: лемматизация, то есть получение базовой формы слова, и получение грамматической информации о слове (род, число, падеж, часть речи и т.д.).
Нужна библиотека и словарь для нее. Все это добро можно найти тут. Библиотека находится в одноименной папке «phpmorphy», словари расположены в «phpmorphy-dictionaries». Скачиваем последние версии в корневую папку проекта и распаковываем:
Отлично! Библиотека готова к использованию. Пришло время написать «оболочку», которая абстрагирует работу с phpMorphy. Для этого создадим еще один файл morphyus.php в корневой директории:
Пока реализовано только два метода. get_words разбивает текст на массив слов, фильтруя при этом HTML-теги и сущности типа » «. Метод lemmatize возвращает массив лемм слова, либо false, если таковых не нашлось.
Механизм ранжирования на уровне морфологии
Давайте остановимся на такой единице языка, как предложение. Наиболее важной частью предложения является основа в виде подлежащего и/или сказуемого. Чаще всего подлежащее выражается существительным, а сказуемое глаголом. Второстепенные члены в основном употребляются для уточнения смысла основы. В разных предложениях одни и те же части речи порой имеют совершенно разное значение, и наиболее точно оценить это значение в контексте текста сегодня может только человек. Однако программно оценить значение какого-либо слова все-таки можно, хоть и не так точно. При этом алгоритм ранжирования должен опираться на так называемый профиль текста, который определяется его автором. Профиль представляет из себя ассоциативный массив, ключами которого являются части речи, а значениями соответственно ранг (или вес) каждой из них. Пример профиля я покажу в заключении, а пока попробуем перевести эти размышления на язык PHP, добавив еще один метод к классу morphyus:
Индексирование содержимого сайта
Как уже говорилось выше, индексирование заметно ускоряет выполнение поискового запроса, так как поисковому движку не нужно обрабатывать контент каждый раз заново — поиск выполняется по индексу. Но что же все-таки происходит при индексировании? Если по порядку, то:
В результате получается объект следующего формата:
Пишем инициализатор и первый метод ядра поискового движка:
Теперь при добавлении или изменении данных в таблицах достаточно просто вызвать данную функцию, чтобы проиндексировать их, но это не обязательно: индексирование может быть и отложенным. Первым аргументом метода make_index является исходный текст, вторым — коэффициент значимости индексируемых данных. Ранг каждого слова, кстати, расчитывается по формуле:
Хранение индексированных данных
Очевидно, что индекс нужно где-нибудь хранить, да еще и привязать к исходным данным. Наиболее подходящим местом для них будет база данных. Если индексируется содержимое файлов, то можно создать отдельную таблицу в базе данных, которая будет содержать индекс название каждого файла, а для содержимого, которое уже хранится в базе, можно добавить еще одно поле типа в структуру таблиц. Такой подход позволит разделять типы содержимого при поиске, например, названия и описание статей в случае блога.
Нерешенным остался лишь вопрос формата индексированного содержимого, ведь make_index возвращает объект, и так просто в базу данных или файл его не запишешь. Можно использовать JSON и хранить его в полях типа LONGTEXT, можно BSON или CBOR, используя тип данных LONGBLOB. Два последних формата позволяют представлять данные в более компактном виде, чем первый.
Как говорится, «хозяин — барин», так-что решать, где и как все будет храниться, Вам.
Benchmark
Давайте проверим, что у нас получилось. Я взял текст своей любимой статьи «Темная материя интернета», а именно содержимое узла #content html_format и сохранил его в отдельный файл.
На моей машине с конфигурацией:
CPU: Intel Core i7-4510U @ 2.00GHz, 4M Cache
RAM: 2×4096 Mb
OS: Ubuntu 14.04.1 LTS, x64
PHP: 5.5.9-1ubuntu4.5
Индексирование заняло около секунды:
Думаю, вполне неплохой результат.
Реализация поиска
Остался последний и самый главный метод, метод поиска. В качестве первого аргумента метод принимает индекс поискового запроса, в качестве второго — индекс содержимого, в котором выполняется поиск. В результате выполнения возвращается суммарный ранг, рассчитанный на основе ранга найденных слов, либо 0, если ничего не нашлось. Это позволит сортировать поисковую выдачу.
Все! Поисковый движок готов к использованию. Но есть одно но… На самом деле это не джин-волшебник, и просто закинув его на свой сайт Вы не получите ничего. Его нужно интегрировать, причем этот процесс во многом зависит от архитектуры Вашего сайта. Рассмотрим этот процесс на примере небольшого интернет магазина.
Реализация поиска на примере интернет-магазина
Допустим, информация о продаваемой продукции хранится в таблице production:
А описание в таблице description:
Поле production.keywords будет содержать индекс ключевых слов продукта, description.index будет содержать индексированное описание. И все это будут храниться в формате JSON.
Вот пример функции добавления нового продукта:
Здесь поисковый механизм был интегрирован в функцию добавления нового продукта магазина. А теперь обработчик поисковых запросов:
Данный сценарий принимает поисковый запрос в виде GET-параметра query и выполняет поиск. В результате выводятся найденные продукты магазина.
Заключение
В статье был описан один из вариантов реализации поиска для сайта. Это самая первая его версия, поэтому буду только рад узнать Ваши замечания, мнения и пожелания. Присоединяйтесь к моему проекту на Github: https://github.com/axilirator/firewind. В планах добавить туда еще кучу всяких возможностей, вроде кэширования поисковых запросов, подсказок при вводе поискового запроса и алгоритма побуквенного сравнения, который поможет бороться с опечатками.
Всем спасибо за внимание, ну и с днем информационной безопасности!
Поиск с учетом языковой морфологии
Поиск с учетом морфологии русского языка
Начнем с подключения phpMorphy. Это делается очень просто. Сперва скачайте дистрибутив, словари, распакуйте все это в отдельную папку, соблюдая структуру вложенных каталогов. Словари разместите в папке dict. Теперь откроем файл примера из папки examples и посмотрим настройки:
В настройках используется важный параметр storage, он может принимать одно из трех значений: PHPMORPHY_STORAGE_FILE (не загружать файлы словарей в память целиком, это самый медленный вариант, но самый экономный в плане работы с ресурсами сервера), PHPMORPHY_STORAGE_SHM (загружать файл словаря целиком в shared-память, требуется расширение PHP shmop) или PHPMORPHY_STORAGE_MEM (также загружать файл в память целиком если не используется shmop, по скорости работы ничем не отличается от предыдущего). На виртуальном хостинге, скорее всего, придется использовать первый вариант, а на выделенном сервере для большей скорости лучше применять варианты с использованием памяти. Выберите вариант под свои задачи. Остальные настройки и их значения подробно расписаны в официальной документации.
Словари загружены, скрипт подключен, можно пробовать его в деле. Допустим, что надо найти текст «Примерная строка поиска»:
Обратите внимание, что перед передачей phpMorphy поисковая строка переводится в верхний регистр и разделяется на отдельные слова. Вот что у нас получается. Нормализованные слова (массив $base_form):
Array (
[СТРОКА] => Array (
[0] => СТРОКА
)
[ПРИМЕРНАЯ] => Array (
[0] => ПРИМЕРНЫЙ
)
[ПОИСКА] => Array (
[0] => ПОИСК
)
)
Все словоформы (массив $all_forms):
Array (
[СТРОКА] => Array (
[0] => СТРОКА
[1] => СТРОКИ
[2] => СТРОКЕ
[3] => СТРОКУ
[4] => СТРОКОЙ
[5] => СТРОКОЮ
[6] => СТРОК
[7] => СТРОКАМ
[8] => СТРОКАМИ
[9] => СТРОКАХ
)
[ПРИМЕРНАЯ] => Array (
[0] => ПРИМЕРНЫЙ
[1] => ПРИМЕРНОГО
[2] => ПРИМЕРНОМУ
[3] => ПРИМЕРНЫМ
[4] => ПРИМЕРНОМ
[5] => ПРИМЕРНАЯ
[6] => ПРИМЕРНОЙ
[7] => ПРИМЕРНУЮ
[8] => ПРИМЕРНОЮ
[9] => ПРИМЕРНОЕ
[10] => ПРИМЕРНЫЕ
[11] => ПРИМЕРНЫХ
[12] => ПРИМЕРНЫМИ
[13] => ПРИМЕРЕН
[14] => ПРИМЕРНА
[15] => ПРИМЕРНО
[16] => ПРИМЕРНЫ
[17] => ПРИМЕРНЕЕ
[18] => ПРИМЕРНЕЙ
[19] => ПОПРИМЕРНЕЕ
[20] => ПОПРИМЕРНЕЙ
)
[ПОИСКА] => Array (
[0] => ПОИСК
[1] => ПОИСКА
[2] => ПОИСКУ
[3] => ПОИСКОМ
[4] => ПОИСКЕ
[5] => ПОИСКИ
[6] => ПОИСКОВ
[7] => ПОИСКАМ
[8] => ПОИСКАМИ
[9] => ПОИСКАХ
)
)
Корни слов (массив $pseudo_root):
Array (
[СТРОКА] => Array (
[0] => СТРОК
)
[ПРИМЕРНАЯ] => Array (
[0] => ПРИМЕР
)
[ПОИСКА] => Array (
[0] => ПОИСК
)
)
Как нам это поможет в поиске? Тут есть несколько вариантов. Например, при загрузке или редактировании статьи ее текст при помощи phpMorphy разбирается на нормализованные слова (то есть начальная форма слова) и они сохраняются в базу. Это может быть дополнительное поле в таблице статей, для которого создается индекс FULLTEXT.
SELECT * FROM `articles`
WHERE MATCH (`article_text_index`) AGAINST (‘+СТРОКА +ПРИМЕРНЫЙ +ПОИСК’)
Еще один вариант я встречал в движке форума punBB. Там текст каждого сообщения разделялся на отдельные слова, а затем они сохранялись в таблицу со ссылкой на сообщение. Поисковая строка также сперва разбивается по отдельным словам, и поиск в базе выполняется уже по этим данным, а не по исходному тексту. В нашем случае можно облегчить задачу и повысить точность поиска, если каждое слово перед занесением в базу и слова из поисковой строки будут преобразоваться к начальной форме.
SELECT DISTINCT(`index_article_id`) FROM `index_articles`
WHERE `index_word` IN (‘СТРОКА’, ‘ПРИМЕРНЫЙ’, ‘ПОИСК’)
Релевантность поиска в этом случае можно считать по количеству входящих слов, добавив в запрос команду GROUP.
Для совсем небольших сайтов, где не планируется большая нагрузка, можно извлечь корни из слов искомой строки, а затем использовать эти данные в запросе:
SELECT * FROM `articles`
WHERE UPPER(`article_text`) LIKE ‘%СТРОК%’
OR UPPER(`article_text`) LIKE ‘%ПРИМЕР%’
OR UPPER(`article_text`) LIKE ‘%ПОИСК%’
Искать по всем словоформам в этом случае не имеет смысла, точность результата будет такая же, а нагрузка на базу возрастет.
Как работают поиск с учетом морфологии, точный поиск и слова исключения?
ПОИСК С УЧЕТОМ МОРФОЛОГИИ
Все ключевые слова и фразы в поисковых строках «Ключевые фразы», а также фильтрах «Место поставки», «Организатор» и «Заказчик» применяются в поиске с учетом морфологии. В новом поиске ключевые слова и фразы нужно писать полностью, а система будет узнавать их в таком виде и автоматически применять различные склонения и числа к введенному вами слову, подбирая закупки.
Обратите внимание, система различает части речи. Это значит, если вы указываете в поисковой строке существительное «пожар», то поиск будет совершен именно по существительному. В выдачу не попадут закупки, содержащие прилагательные с корнем слова «пожар», например, «пожарный». Прописывайте нужные ключевые фразы полностью, старайтесь подобрать как можно больше вариантов того, как могут называться товары или услуги, которые вы предлагаете и готовы поставить/оказать.
Так, чтобы найти закупки, содержащие ключевые слова «консервы» и «консервированный», нужно ввести оба этих слова (раньше это решал один запрос – «консерв*»).
Если вы вводите в поиск с учетом морфологии ключевую фразу, система учитывает морфологию каждого слова ключевой фразы (изменяет по падежам и числам), позволяет словам в словосочетании меняться местами, а также допускает появление между словами ключевой фразы до 2-х других слов.
Так, если вы ввели в поисковую строку «продукты питания», в выдачу попадет в том числе закупка с такой формулировкой: «поставка продуктов для организации питания».
Более подробно о поиске с учетом морфологии узнавайте у менеджеров или сообщите нам – мы подготовим более подробную инструкцию.
ТОЧНЫЙ ПОИСК
Вместе с поиском по морфологии мы добавили точный поиск. Теперь с помощью точного поиска можно будет закрепить форму слова: автоматически система будет искать слово, написанное именно в указанном вами падеже и числе. Если вы вводите в точный поиск ключевую фразу, то он закрепит и форму каждого слова, и порядок слов в словосочетании, и не допустит, чтобы между словами попали другие слова.
Давайте рассмотрим пример выше: ключевую фразу «продукты питания» введем в поисковую строку точного поиска. В выдачу НЕ попадут закупки со следующими формулировками: «поставка продуктов для организации питания», «поставка продуктов лечебного питания», «продуктов питания», «продукты детского питания».
Что же тогда попадет в выдачу? Например, попадет закупка с такой формулировкой: «прочие продукты питания».
И, кстати, закупки со всеми перечисленными выше формулировками попадут в выдачу, если вы будете искать фразу «продукты питания» в поиске с учетом морфологии.
ИСКЛЮЧЕНИЯ
Под поиск с учетом морфологии и точный поиск мы обновили слова-исключения. Раньше слова-исключения могли вычеркнуть в том числе и интересные, подходящие под запрос закупки в силу особенностей ввода ключевого слова. Сейчас исключить ненужные закупки можно более точечно и аккуратно, не потеряв при этом важные закупки.
Слова и фразы исключения работают также с учетом морфологии: точная форма исключений заставила бы пользователей прописывать большое количество словоформ-исключений. Наша основная рекомендация – не торопитесь исключать что-либо. Создайте сначала основной запрос из нескольких подходящих ключевых фраз и слов, примените поиск и оцените выдачу. Часто убрать лишнее помогает прописывание не ключевых слов, а ключевых фраз.
Если в выдачу попадают закупки, не имеющие отношения к вашей сфере бизнеса, то исключайте неподходящие слова. Например, вы занимаетесь флористикой и поставкой живых цветов. Вы можете смело исключить нерелевантные закупки по запросу «искусственный».
ВАЖНО! Мы начинаем собирать словарь слов-исключений. Русский язык – великий язык) Готовых решений нет, и мы уже начинаем находить слова, которые требуют особого подхода. Так, одно из этих слов – «молоко». Это тот продукт, который нужен вам для поиска закупок? Обратитесь к менеджеру, менеджер сразу поможет вам правильно настроить поисковые запросы.
Поиск по сайту с учетом морфологии русского языка на PHP + карта сайта
Начинаем «рыть» интернет. Ну как же так? У всех есть поиск на своем сайте. Как-то же люди его делают. Есть например, лобовое решение, давно описанное мной: контекстный поиск на сайте, который не учитывает склонение слов и не индексирует слова на страницах. Но чем дальше углубляешься в задачу тем больше понимаешь, что задача совсем нетривиальная.
Во-вторых нужно получить исходную форму всех слов. Тут есть несколько вариантов, например можно использовать стример, который отрезает приставку, суффикс и окончание у слов. Или более сложную систему, использующую словари.
В третьих это все нужно загрузить в базу и проиндексировать, чтобы поиск занимал минимум времени.
Потратив две недели своего времени, перепробовав большое количество различных вариантов и алгоритмов я остановился на следующем:
1. Для сканирования я использую упрощенный парсер, который с помощью регулярного выражения вырезает все href со страницы:
Теперь нужно отделить внешние ссылки от внутренних и рекурсивно обратиться к парсеру с адресом внутренней ссылки. Вот тут и начинаются «грабли». Внутренние ссылки могут быть указаны как внешние с http://домен/адрес, они могут быть относительно текущей страницы, они могут быть относительно тега base. Далее необходимо проверить не запрещена ли индексация этой страницы в robots.txt и не была ли эта страница уже отсканирована. Для проверки можно воспользоваться примером разбора robots.txt и примером поиска по SQL
2. Далее мы должны выделить все слова на странице, для этого воспользуемся регулярным выражением:
На виртуальном хостинге, скорее всего, придется использовать первый вариант, а на выделенном сервере для большей скорости лучше применять варианты с использованием памяти. Выберите вариант под свои задачи, если к модулю планируются частые обращения, то лучше, конечно, использовать вариант с разделяемой памятью.
Пример работы библиотеки phpmorphy есть здесь.
3. Теперь нужно сделать таблицы базы данных, в которых мы будем хранить все результаты сканирования и разбора:
Теперь нужно сделать форму запроса поискового выражения. Простейшая форма поискового запроса выглядит так:
Скачать скрипт поиска по сайту
39$) Вы получите полный открытый, подробно откоментированный скрипт поиска с генератором карты сайта.
Содержимое архива:
Инструкция по установке:
Возможности скрипта поиска по сайту
Что скрипт не может:
39$) Вы можете выбрать один из двух вариантов скрипта, которые существенно отличаются друг от друга.
Скрипт поиска для сайта в кодировке UTF-8 использует функции работы с двухбайтными символами mb_*, разбирает страницы регулярными выражениями сделанными для кодировки UTF-8 (unicod / Юникод), создает таблицы БД в utf-8.
Скрипт поиска для сайта в кодировке Windows-1251 использует функции для работы только с однобайтными кодировками str*, разбирает страницы регулярными выражениями сделанными для однобайтных кодировок.