Поисковая машина своими руками

Может создаться впечатление, что бороться с нарастающим как снежный ком объёмом информации под силу только гигантам поисковой индустрии. Но не стоит отчаиваться: конструктор поисковых машин Rollyo поможет нам собственными силами справиться с информационным «девятым валом».

Авторы руководствовались простой идеей — создать инструмент, позволяющий пользователю самостоятельно определять круг ресурсов, на которых будет осуществляться поиск. Сказано — сделано, и, несмотря на продолжающееся бета-тестирование, Rollyo уже сейчас предлагает целый букет различных удобных инструментов, позволяющих в считанные минуты соорудить собственный «движок».

Для начала в специальной форме нужно ввести название вашей будущей поисковой машины, а также заполнить список адресов веб-ресурсов (до 25 на один движок), в рамках которых будет осуществляться сканирование. В названии можно использовать кириллицу, но по некоторым соображениям, о которых будет сказано ниже, лучше всё-таки использовать латинские символы.

Кроме обязательных для заполнения полей, в форме имеются и опциональные — категория поиска и ключевые слова, по которым ваш поисковик будет индексироваться в базе себе подобных. Дело в том, что на сайте Rollyo организовано целое сообщество «искателей» информации, и из множества уже готовых минипоисковиков, созданных посетителями данного ресурса, любой желающий может выбрать подходящий и добавить в собственный список. Рейтинговая система позволяет отличить самые популярные «самоделки». Вы тоже можете поучаствовать в рейтинге — для этого достаточно включить опцию, делающую ваш движок доступным для других пользователей ресурса. Теперь, думаю, понятно, почему названия поисковых машин лучше использовать английские: кириллица вряд ли позволит вашему варианту завоевать популярность.

Наконец, поисковик готов к работе.

Создавать подобных поисковых машин можно сколь угодно много: все они будут помещаться в выпадающем списке на странице вашей учётной записи на сервере Rollyo. В этот же список можно добавлять поисковики интересующей вас тематики, созданные другими пользователями сервиса. Само сканирование веб-ресурсов осуществляется с помощью движка Yahoo Search, а результаты поиска (которые можно отправить по почте или поместить в свой блог в виде ссылки) представляются в довольно удобном виде: там есть не только название материала и ссылка, но и небольшой начальный фрагмент текста.

Более широкие возможности создания поисковых средств скрыты в разделе Tools. Особое внимание разработчики уделили интеграции Rollyo с новомодным браузером Firefox, о чём косвенно говорит и внушительных размеров баннер, размещаемый на странице с результатами поиска. Для счастливых обладателей Firefox предусмотрена возможность перемещения любого из своих поисковиков в список аналогичных инструментов собственно браузера. Правда, при этом могут возникнуть небольшие проблемы с кириллицей: если название поисковика содержит русские буквы, в Firefox они попадают в «испорченном» виде. Это ещё один довод в пользу выбора «правильного» названия, использующего латинские символы. Впрочем, есть свои «вкусности» и не только для поклонников «Огненного лиса»: для создания движка можно взять за основу список закладок любого браузера — специальная страница, размещённая в этом же «инструментальном» разделе сайта, содержит подробные инструкции, позволяющие сделать это в несколько движений.

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

По результатам введённых пользователем данных создаётся небольшой фрагмент HTML-кода, который простым копированием переносится в код страницы сайта. В качестве дополнительной опции можно выбрать один из трёх вариантов цветового оформления блока, чтобы он не очень контрастировал с общим дизайном вашего сайта. В крайнем случае придётся «подправить» код — тогда получится почти локализованный вариант:

В будущем разработчики Rollyo планируют предложить своим пользователям ещё один интересный инструмент, позволяющий создавать небольшие виджеты для среды Windows и Mac OSX, но пока соответствующая страница сайта пустует.

Если рассматривать целевую аудиторию Rollyo, то, по большому счёту, данная программа представляет реальный интерес для пользователей Internet Explorer, который не обладает достаточно развитыми встроенными поисковыми средствами. У пользователей Firefox есть онлайновый ресурс Mycroft, с помощью обширной базы поисковиков которого можно настраивать собственные средства браузера. Тестируемая в данный момент девятая версия Opera обладает собственной встроенной системой настройки поисковых ресурсов, плюс к этому норвежские разработчики включили поддержку и предоставили инструментарий для создания виджетов, позволяющих в удобной форме организовать не только поиск информации, но и массу прочих полезностей. Но не будем забывать, что IE по-прежнему используется подавляющей массой сетян, из чего следует, что пользователи Rollyo обеспечены. В любом случае, разработчики данной программы предложили красивый и удобный инструмент, за который их можно вполне искренне поблагодарить.

Источник

Поисковые технологии или в чем загвоздка написать свой поисковик

Когда-то давно взбрела мне в голову идея: написать свой собственный поисковик. Было это очень давно, тогда я еще учился в ВУЗе, мало чего знал про технологии разработки больших проектов, зато отлично владел парой десятков языков программирования и протоколов, да и сайтов своих к тому времени было понаделано много.

Ну есть у меня тяга к монструозным проектам, да…

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

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

Здесь я в первый раз, публично, опишу то, что было сделано лично мной. Думаю, многим будет интересно как же работают Яндекс, Google и почти все мне известные поисковики изнутри.

Есть много задач при построении таких систем, которые почти нереально решить в общем случае, однако с помощью некоторых ухищрений, придумок и хорошего понимания как работает железячная часть Вашего компьютера можно серьезно упростить. Как пример – пересчет PR, который в случае нескольких десятков миллионов страниц уже невозможно поместить в самой большой оперативной памяти, особенно если Вы, как и я, жадны до информации, и хотите кроме 1 цифры хранить еще много полезностей. Другая задача – хранение и обновление индекса, как минимум двумерной базы данных, в которой конкретному слову сопоставляется список документов, на которых оно встречается.

Просто вдумайтесь, Google хранит, по одной из оценок, более 500 миллиардов страниц в индексе. Если бы каждое слово встречалось на 1 странице только 1 раз, и на хранение этого надо было 1 байт – что невозможно, т.к. надо хранить хотя бы id страницы – уже от 4 байт, так вот тогда объем индекса бы был 500гб. В реальности одно слово встречается на странице в среднем до 10 раз, объем информации на вхождение редко когда меньше 30-50 байт, весь индекс увеличивается в тысячи раз… Ну и как прикажите это хранить? А обновлять?

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

На сегодня объем только индекса, по которому происходит поиск — 57Gb, увеличивается каждый день примерно на 1Gb. Объем сжатых текстов – 25Gb, ну и я храню кучу другой полезной инфы, объем которой очень трудно посчитать из-за ее обилия.

Источник

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

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

У читателя может возникнуть вопрос: зачем писать все с нуля, если все уже давно написано? Да, у крупных поисковиков есть API, есть такие клевые проекты, как Sphinx и Apache Solr. Но у каждого из этих решений есть свои преимущества и недостатки. Пользуясь услугами поисковиков, типа Google и Яндекс, Вы получите множество плюшек, таких как мощный морфологический анализ, исправление опечаток и ошибок в запросе, распознавание неверной раскладки клавиатуры, однако без ложки дегтя тут не обойдется. Во первых, такой поиск не интегрируется в структуру сайта — он внешний, и Вы не сможете указать ему, какие данные наиболее важны, а какие не очень. Во вторых, содержимое сайта индексируется только с определенным интервалом, который зависит от выбранного поисковика, так что если на сайте что-нибудь обновится, придется дожидаться момента, когда эти изменения попадут в индекс и станут доступными в поиске. У Sphinx и Apache Solr дела с интеграцией и индексированием гораздо лучше, но не каждый хостинг позволит из запустить.

Ничто не мешает написать поисковый механизм самостоятельно. Предполагается, что сайт работает на PHP в связке с каким-нибудь сервером баз данных, например MySQL. Давайте сначала определимся, что требуется от поиска на сайте?

Поиск с учетом языковой морфологии. Не зависимо от падежа, окончания и
других прелестей великого и могучего языка поиск должен находить то, что нужно
пользователю. Другими словами, «яблок», «яблока», «яблоки» — это формы одного и того
же слова «яблоко», что нужно учитывать в поисковом алгоритме. Одним из способов
достижения данной цели является приведение каждого слова поискового запроса и слов
содержимого сайта к базовой форме.
Возможность указать контекст поиска. То есть, возможность самостоятельно выбрать
контент сайта, в пределах которого будет работать поисковый алгоритм, а также определить
значимость для каждого из пределов. Например, рассмотрим интернет-магазин. Предполагается,
что поисковый запрос чаще всего будет содержать название искомой продукции, поэтому поиск по
названиям товара будет иметь наивысший приоритет. В качестве следующего приоритета можно
выбрать поиск по свойствам товаров, затем поиск по описанию.
Индексирование содержимого сайта. Представьте ситуацию: одновременно около 30 человек
выполняют поисковые запросы. Сервер принимает каждое соединение, управление потоком
передается интерпретатору PHP. При каждом запросе заново инициализируется поисковый
движок, заново перерывается содержимое сайта… Сложно сказать, сколько времени и
ресурсов потребуется, чтобы обработать все эти запросы. Именно для того, чтобы не
делать одну и ту же работу по сто раз, была придумана технология индексирования.
Индексирование выполняется только при изменении или добавлении содержимого сайта,
а поиск выполняется уже по индексу, а не по содержимому.
Механизм ранжирования. Ранжирование результатов поиска — это сортировка результатов поиска, выполняемая на основе оценки значимости найденных данных. Например, в каком-нибудь блоге выполняется поисковый запрос «космос». Данное слово содержится в двух статьях: в первой 16 раз, во второй — 5 раз. Вероятнее всего, первая статья будет иметь большее значение для инициатора поиска. Также каждой разновидности содержимого сайта при индексировании задается определенный коэффициент, который будет влиять на его позиции в поисковой выдаче.

Теперь пару слов о том, что нам предстоит реализовать:

морфологический анализатор,
алгоритм ранжирования,
алгоритм индексирования,
алгоритм поиска.

В конце статьи будет показан пример реализации поиска на примере простого интернет-магазина. Тем, кому лень все это изучать и просто нужен готовый поисковик, можно смело забирать движок из репозитория GitHub FireWind.

Принцип работы

Со стороны бэкенда поиск работает так:

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

Подготовка

Задача поставлена, теперь можно перейти к делу. Я использую Linux в качестве рабочей ОС, однако постараюсь не использовать ее экзотических возможностей, чтобы любители Windows смогли «собрать» поисковый движок по аналогии. Все, что Вам нужно — это знание основ PHP и умение обращаться с MySQL. Поехали!

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

Теперь вооружаемся своим любимым текстовым редактором и подготавливаем каркас:

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

Морфологический анализатор

Русский язык — довольно сложная штука, которая радует своим разнообразием и шокирует иностранцев конструкциями, типа «да нет, наверное». Научить машину понимать его, да и любой другой язык, — довольно непростая задача. Наиболее успешны в этом плане поисковые компании, типа Google и Яндекс, которые постоянно улучшают свои алгоритмы и держат их в секрете. Придется нам сделать что-то свое, попроще. К счастью, колесо изобретать не придется — все уже сделано за нас. Встречайте, phpMorphy — морфологический анализатор, поддерживающий русский, английский и немецкий языки. Более подробную информацию можно получить тут, однако нас интересуют только две его возможности: лемматизация, то есть получение базовой формы слова, и получение грамматической информации о слове (род, число, падеж, часть речи и т.д.).

Нужна библиотека и словарь для нее. Все это добро можно найти тут. Библиотека находится в одноименной папке «phpmorphy», словари расположены в «phpmorphy-dictionaries». Скачиваем последние версии в корневую папку проекта и распаковываем:

Отлично! Библиотека готова к использованию. Пришло время написать «оболочку», которая абстрагирует работу с phpMorphy. Для этого создадим еще один файл morphyus.php в корневой директории:

Пока реализовано только два метода. get_words разбивает текст на массив слов, фильтруя при этом HTML-теги и сущности типа » «. Метод lemmatize возвращает массив лемм слова, либо false, если таковых не нашлось.

Механизм ранжирования на уровне морфологии

Давайте остановимся на такой единице языка, как предложение. Наиболее важной частью предложения является основа в виде подлежащего и/или сказуемого. Чаще всего подлежащее выражается существительным, а сказуемое глаголом. Второстепенные члены в основном употребляются для уточнения смысла основы. В разных предложениях одни и те же части речи порой имеют совершенно разное значение, и наиболее точно оценить это значение в контексте текста сегодня может только человек. Однако программно оценить значение какого-либо слова все-таки можно, хоть и не так точно. При этом алгоритм ранжирования должен опираться на так называемый профиль текста, который определяется его автором. Профиль представляет из себя ассоциативный массив, ключами которого являются части речи, а значениями соответственно ранг (или вес) каждой из них. Пример профиля я покажу в заключении, а пока попробуем перевести эти размышления на язык PHP, добавив еще один метод к классу morphyus:

Индексирование содержимого сайта

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

Сначала из текста формируется массив слов, и делается это с помощью метода get_words.
Согласно профилю, из текста отбрасываются незначимые части речи.
Значимые оцениваются по пятибальной шкале, с помощью метода weigh.
Для каждого сова выполняется поиск лемм, иначе говоря базовых форм.
Рассчитывается количество повторений каждого слова и суммарный ранг.
Все данные записываются в объект и в виде JSON записываются в базу данных.

В результате получается объект следующего формата:

Пишем инициализатор и первый метод ядра поискового движка:

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

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

Источник