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

Поиск по сайту с учетом морфологии русского языка на 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*, разбирает страницы регулярными выражениями сделанными для однобайтных кодировок.

Источник

Блог Валерия Леонтьева

Место публикации личных заметок. Технологии, управление, бизнес, жизнь

Поиск в MySQL. Часть 2 «Поиск с учетом русской морфологии»

Поиск в MySQL. Часть 2 «Поиск с учетом русской морфологии»

В этой статье описывается идея создания поиска в базе MySQL на основе индекса FULLTEXT с учетом русской морфологии. Никаких модулей для PHP или MySQL и других программ устанавливать на хостинг не нужно. И это важное преимущество данного алгоритма. Алгоритм подойдет для сайтов с малой и средней нагрузкой. Для крупных порталов, конечно, следует искать более скоростные и производительные решения (например, Sphinx). Мой вариант поиска работает значительно быстрее поиска на основе регулярных выражений и подойдет для большого количества web-проектов. Кстати, и не только web 🙂

Основан алгоритм на уже готовых решениях. Движок для работы с морфологией – phpMorphy. Это морфологический модуль, написанный на PHP. Он основан на словарях проекта AOT. Оба продукта распространяются под лицензией LGPL.

Анализ производится по словарю, размер словаря для русского языка

4Mb. Скорость работы

700 слов в секунду в нормальном режиме и

1000 слов с загруженным в память словарем (без предсказания).

Подключение движка морфологии.

Для начала, конечно, нужно скачать модуль phpMorphy с официального сайта. В архиве находятся два каталога: dicts – словари АОТ, src – исходники phpMorphy. Разместите эти два каталога на сервере (желательно в общем каталоге phpMorphy). Далее для работы с модулем необходимо подключить в скрипте сайта файл src/common.php. Например так:

Библиотека подключена. Теперь вкратце о ее настройках. Порядок создания объекта:

$dict_bundle = new phpMorphy_FilesBundle(’phpmorphy/dicts’, ‘rus’); // создается объект словарей, //передается путь к каталогу со словарями. В данном случае используется русский словарь.

// Создаем объект словарей

$morphy = new phpMorphy($dict_bundle, array(’storage’ => PHPMORPHY_STORAGE_MEM, ‘with_gramtab’ => false, ‘predict_by_suffix’ => true, ‘predict_by_db’ => true));

Подробнее об опциях можно почитать в README к скрипту, а вот про ‘storage’ стоит упомянуть и тут. Это важная настройка.

phpMorphy поддерживает следующие варианты работы со словарями:

Так как в начале статьи оговорено, что никаких дополнительных расширений мы не используется, в примере указано ’storage’ => PHPMORPHY_STORAGE_MEM. Если с такими настройками ваш поиск «вылетает» с ошибками о недостатке памяти, или злостный хостер ругается, что вы расходуете память больше положенного, включите’storage’ => PHPMORPHY_STORAGE_FILE.

Сразу хочу обратить ваше внимание, что алгоритм поиска будет правильно работать только при правильно настроенной локали (PHP setlocale) и кодировке в БД.

Изменения в таблицах БД.

Теперь поговорим об организации условий для поиска в БД. Напомню, что поиск у нас основан на индексах, что определяет высокую скорость выполнения поисковых запросов (подробнее в части 1).

Допустим, у нас есть некая таблица сообщений, по которой будет осуществляться поиск. В таблице есть поля: message_id, message_text, message_date. Искать нужно по полю message_text. Для организации поиска с учетом морфологии необходимо создать еще одно поле. Назовем его message_words_index. И как раз для этого поля необходимо создать индекс FULLTEXT вместе с полем message_text.

Пример создания такой таблицы:

CREATE TABLE `fn_messages` (`message_id` int(10) unsigned NOT NULL auto_increment,
`message_text` text NOT NULL, `message_date` timestamp
NOT NULL default CURRENT_TIMESTAMP,
`message_words_index` text NOT NULL,
PRIMARY KEY (`message_id`),
FULLTEXT KEY `fn_messages_words_index` (`message_text`,`message_words_index`)
) ENGINE=MyISAM;

Таблица готова к работе с полнотекстовым морфологическим поиском.

Внесение данных в таблицу.

При добавлении записей в таблицу, их нужно готовить для проведения поиска. Первые три поля заполняются как обычно, а в последнее вносятся слова сообщения в обработанной начальной форме. Что бы получить начальную форму слов, используется phpMorphy. Создадим функцию function Words2BaseForm($text), в которую передается исходный текст сообщения, а возвращает она в виде строки набор слов в начальных формах. Например:

Содержимое столбца «Получено» будет помещено в поле message_words_index. Скачать функцию function Words2BaseForm($text) можно здесь.

Поиск данных.

При получении запроса на поиск для обработки фразы поиска используется другая функция, созданная для работы с phpMorphy: function Words2AllForms($text). Принимая разделенные пробелом слова для поиска, она возвращает эти слова во всех их морфологических формах. Таким образом, в полях message_text и message_words_index будут искаться все формы слов, а результаты выведутся по релевантности. Можно создавать индекс и искать только по полю message_words_index, но в этом случае вывод по релевантности будет нарушен.

Замечу, что создание дополнительного поля message_words_index необходимо еще и потому, что система phpMorphy может привести к начальной форме даже те слова, которых нет в словарях. Она это делает по анализу слова в соответствии с
правилами морфологии языка. А вот обратная система не сработает. Поэтому поиск по начальной форме даст более точные результаты.

Итак, передаем поисковый запрос в функцию function Words2AllForms($text), а возвращенный ей результат помещаем в запрос на выборку (вместе с изначальным условием для соблюдения релевантности). Скачать функцию function Words2AllForms($text) можно здесь.

Запрос имеет следующий вид:

SELECT SQL_CALC_FOUND_ROWS * from messages WHERE MATCH (message_text, message_words_index) AGAINST (изначальный_текст, обработанный_текст) LIMIT 0, 10;

Подсветка найденных слов.

Не буду писать про организацию подсветки много слов. Скажу лишь, что она основана на словоформах, полученных из function Words2AllForms($text). Скачать PHP-код подсветки найденных слов можно здесь.

Заключение.

Протестировать данный алгоритм поиска можно на сайте http://kadrovik.by.

Сама идея поиска «распространяется» под лицензией BSD и принадлежит мне (Валерию Леонтьеву). При перепечатке статьи ссылка на эту страницу обязательна. Обращаю внимание, что использованные в алгоритме библиотеки распространяются по лицензии LGPL.

Ссылки.

Продолжение! Внимание, при использовании описанной технологии обязательно прочитайте продолжение статьи. Правки в этот материал решено не вносить. Поиск в MySQL. Часть 3 «FULLTEXT IN BOOLEAN MODE»

Поиск в MySQL. Часть 2 «Поиск с учетом русской морфологии» : 20 комментариев

Хм, только я вот не понял предлагаемые проги распространяются бесплатно или за деньги? 🙂

Подсветка слов работает для всего текста хранимого в поле `message_text` А что есля я хочу выводить подсвечиваемые слова прямо в списке результатов поиска? Т.е подсвечиваемое влово + или — три слова около него.

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

Сегодня нашел схожую статью на тему морфо-поиска. Читайте: http://kurapov.name/article/2271

Здравствуйте. А как быть, если текст в UTF-8? Конвертирую его с помощью iconv’а в цп1251, слова мне назад не отдаются…

Честно говоря, я не пробовал эту библиотеку с UTF-8. Так что все, что могу ответить — надо пробовать и разбираться. Если PHP работает в UTF, есть подозрение, что он не сможет нормально работать с самим файлом морфологии. Возможно, проблема в этом.
Если Вы разберетесь, просьба тут отписать.

Возникла аналогичная проблема с UTF-8. Хотелось бы узнать, кто как решал, если решал.

Пробовал поиск с использованием phpMorphy, он не работает с UTF-8, но при помощи iconv я менял кодировку строки в cp1251, извлекал корень слова, и дальше конвертировал обратно в UTF-8. Но столкнулся с проблемой при выборке из БД, в базе текст также в UTF, и почему то конструкция приведения текста в верхний регистр отказывается работать 🙁

Офигенный модуль! Разработчику респект!:-) Ему бы еще пару функций контент-анализа…
Как только прикручу к движку сайта — поставлю ссылку! Только одно непонятно: почему у автора в блоге поиск от Google?

Потому, что лень к вордпресу прикручивать свой поиск. Проще поставить гугл. Да и гугл лучше ищет, чем этот двиг на базе PHPMORPHY. И Яндекс.Сервер тоже лучше ищет. Но у обоих есть очевидные недостатки. Так что описанный выше алгоритм работает (пока) на других сайтах, например http://kadrovik.by. Там его можно вдоволь потестить, если есть желание.

У мну запрос не проходит:-(
SELECT SQL_CALC_FOUND_ROWS * from messages WHERE MATCH (message_text, message_words_index) AGAINST (изначальный_текст, обработанный_текст) LIMIT 0, 10;
Так вот, «обработанный_текст» сервер в упор воспринимать не хочет. Без него всё работает, но это же не совсем правильно?… Кстати, Words2AllForms возвращает массив. Пробовал и массив в запрос вставлять, и строку. Никак:-( Help! Версия сервера: 5.0.45

Разобрался. Поправка в запрос:
SELECT SQL_CALC_FOUND_ROWS * from messages WHERE MATCH (message_text, message_words_index) AGAINST (изначальный_текст[ПРОБЕЛ]обработанный_текст_в_текстовом_формате) LIMIT 0, 10;
То есть, массив, полученный от Words2AllForms, нужно привести к строке с пробелами. Я правильно всё понял?

Слова
ЭЛЕМЕНТ ФУНКЦИЯ ТОЛЬКО ВЕДЬ ТАКЖЕ СИЛЬНЫЙ СИЛЬНО ПРОИЗВОДИТЬ ПОЛУЧАТЬ НАПОМИНАТЬ ИЗВЛЕКАТЬ ВОЗВРАЩАТЬ ПЕРВЫЙ ПЕРВОЕ НАЧАЛЬНЫЙ МАССИВ КОНЕЧНЫЙ ИЗВЛЕЧЕНИЕ ДОВОЛЬНО ДОВОЛЬНЫЙ ВСТРЯСКА ВСЕГО ВЕСЬ

и вообще почему вы решили, что getAllForms можно скормить массив — по моему он только с одним словом работает…

Вот так переписал вашу функцию…. работает и возвращает уже готовую строку всех словоформ поискового запроса склеенных в строку… и сразу пишем её в БД

так как при попадании в тексте английских слов — ругается благим матом потому, что словарь только русский….

Notice: iconv_strlen() [function.iconv-strlen]: Detected an illegal character in input string in …\src\unicode.php on line 142
Странно все и как-то мутно, ставишь заглушку, выдает то что было

при выводе обратно, конечно через ж…, но работает

Спасибо за информацию, очень помогла.

Использую базу с кодировкой UTF-8, и для того чтобы всё заработало пришлось внести некоторые изменения:
1. Заменить в morphy.functions.php все strtoupper на mb_strtoupper($v, ‘UTF-8’)
2. Исправить функцию Words2AllForms как указано выше.

Но это мелочи, в остальном всё отлично прижилось 🙂

Добавить комментарий Отменить ответ

Для отправки комментария вам необходимо авторизоваться.

Источник

Поиск на сайте своими руками

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

У читателя может возникнуть вопрос: зачем писать все с нуля, если все уже давно написано? Да, у крупных поисковиков есть 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. В планах добавить туда еще кучу всяких возможностей, вроде кэширования поисковых запросов, подсказок при вводе поискового запроса и алгоритма побуквенного сравнения, который поможет бороться с опечатками.

Всем спасибо за внимание, ну и с днем информационной безопасности!

Источник