НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ

УНИВЕРСИТЕТ

«МЭИ»

Институт Автоматики и вычислительной техники

Кафедра Прикладной математики

В Ы П У С К Н А Я Р А Б О Т А

бакалавра Прикладной математики и информатики

по направлению «Прикладная математика и информатика» (010500)

Тема: Разработка библиотеки .

для осуществления адаптивного поиска .

в базах данных Web-приложений .

Студент А-13-08 Захаров А. Е. .

группа подпись фамилия, и., о.,

Научный
руководитель доцент Чибизова Н. В. .

должность звание подпись фамилия, и., о.,

Консультант .

должность звание подпись фамилия, и., о.,

«Работа допущена к защите»

Зав. кафедрой д. т. н. Еремеев А. П. .

звание подпись фамилия, и., о.,

Дата_____________

Москва 2012 г.

АННОТАЦИЯ

В данной работе разработана библиотека для адаптивного поиска в базах данных Web-приложений, написанная на языке PHP.

Библиотека может использоваться разработчиками тех сайтов, где требуется, чтобы результаты поисковой выдачи основывались на поисковой истории пользователя. Поиск может осуществляться в различных базах данных (MySQL, PostgreSQL, Oracle, Microsoft SQL и др.), что существенно расширяет область применения библиотеки.

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

THE ANNOTATION

In this work a library for Web-application database adaptive search, written in PHP, has been developed.

The library can be used by developers of those sites where search results are needed to be based on a user search history. The search can be carried out in different databases (MySQL, PostgreSQL, Oracle, Microsoft SQL and others), which significantly expands the range of the library use.

The use of this library will not only allow to realize some features of major search engines, but also, as a result, will increase the efficiency of the search.

ВВЕДЕНИЕ

В наши дни умение быстро найти необходимую информацию ценится особенно высоко. И наиболее ярко это можно видеть на примере одной из крупнейших поисковых систем в мире «Яндекс»: только за сентябрь 2011 года было обработано свыше 3 миллиардов поисковых запросов. И это всего лишь 1,7% от мирового количества! Всё это является результатом бурного развития информационного поиска – большой междисциплинарной области науки, стоящей на пересечении когнитивной психологии, информатики, информационного дизайна, лингвистики, семиотики и библиотечного дела. Популярность информационного поиска обусловлена экспоненциальным ростом объёмов информации, в частности, в сети Интернет.

Десять лет назад решающими факторами при выборе поисковой системы были скорость и полнота результатов поисковой выдачи. На сегодняшний день, после появления индекса цитируемости веб-сайтов и ему подобных технологий, когда поисковые системы дают возможность получить практически любые сведения об окружающем мире, пользователи хотят, чтобы поиск был персональным и результаты их поисковых запросов подстраивались под их предпочтения. В сентябре 2011 года компания Bing впервые запустила адаптивный поиск в своей поисковой системе. А с 1 марта 2012 года поисковая система Google начинает использовать поисковые результаты пользователей из других сервисов Google Inc., в частности Google+, Gmail и YouTube.

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

Цель представленной работы – разработать библиотеку для организации адаптивного поиска в большинстве популярных баз данных (MySQL, PostgreSQL, Oracle, Microsoft SQL, InterBase и др.).

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

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

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

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

1. АНАЛИЗ ПРЕДМЕТНОЙ ОБЛАСТИ

1.1. Основные понятия информационного поиска

Информационный поиск (ИП) – процесс поиска неструктурированной документальной информации. Также информационный поиск может рассматриваться как большая междисциплинарная область науки, стоящая на пересечении когнитивной психологии, информатики, информационного дизайна, лингвистики, семиотики и библиотечного дела. Термин «информационный поиск» был впервые введён Кельвином Муром в 1948 г. в его докторской диссертации, опубликован и употребляется в литературе с 1950 г.

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

В настоящее время ИП – это бурно развивающаяся область науки, популярность которой обусловлено экспоненциальным ростом объёмов информации, в частности в сети Интернет. ИП посвящена обширная литература и множество конференций.

Изначально автоматизированные информационно-поисковые системы (ИПС) использовались только для управления информационным взрывом в научной литературе. Многие университеты и публичные библиотеки стали использовать ИПС для обеспечения доступа к книгам, журналам и другим документам. Широкое распространение ИПС получили с появлением сети Интернет. У русскоязычных пользователей наибольшей популярностью пользуются поисковые системы Google, Яндекс и Рамблер.

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

Говоря о системах ИП, употребляют термины «запрос» и «объект запроса».

Запрос – это формализованный способ выражения информационных потребностей пользователем системы. Для выражения информационной потребности используется язык поисковых запросов, синтаксис варьируется от системы к системе. Кроме специального языка запросов, современные поисковые системы позволяют вводить запрос на естественном языке.

Объект запроса – это информационная сущность, которая хранится в базе автоматизированной системы поиска. Несмотря на то, что наиболее распространённым объектом запроса является текстовый документ, не существует никаких принципиальных ограничений. В частности, возможен поиск изображений, музыки и другой мультимедиа информации. Процесс занесения объектов поиска в ИПС называется индексацией. Далеко не всегда ИПС хранит точную копию объекта, нередко вместо неё хранится суррогат.

Один и первых фундаментальных обзоров задач информационного поиска и информационно-поисковых систем был представлен в работе Рейзенберга [1]. Несмотря на то, что данная работа была опубликована в 1979 году, это до сих пор один из полных и исчерпывающих обзоров по информационному поиску.

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

Таблица 1.1. Основные различия информационно-поисковых систем (ИПС)
и систем выборки данных (СВД).

Типичным примером систем выборки данных являются классические реляционные СУБД. Где в качестве языка запросов используется тот или иной диалект языка запросов SQL. Этот язык искусствен и позволяет задавать поисковые запросы лишь для поиска на точное соответствие или поиска по заданному шаблону. В современных системах выборки данных основной задачей является обеспечение надёжного и эффективного хранения данных, а также высокой скорости выполнения поисковых запросов пользователей. В свою очередь информационно-поисковые системы предназначены для решения более общей задачи поиска, чем поиск на точное соответствие, и где конечной целью поиска является выбор релевантной поисковому запросу информации. Степень релевантности информации можно определить как степень её смысловой близости к поисковому запросу, а это в свою очередь ведёт к тому, что поисковые запросы в ИПС должны быть основаны на естественном языке, то есть на том же языке, в котором сформулирована исходная информация. И системы выборки данных, и информационно-поисковые системы работают с некоторой коллекцией документов. Исходную коллекцию документов можно рассматривать как список записей, где каждая запись содержит в себе некоторый список слов, состоящих из символов алфавита. В реальных информационных системах в исходном множестве документов может содержаться дополнительная информация, описывающая документы, которая так же может использоваться, для осуществления поиска. Решающую роль при разработке современных ИПС играют объёмы исходных данных, поскольку к системам работающих на сравнительно больших объёмах данных, применяются всё более жёсткие требования к производительности и качеству поиска. Поскольку в настоящее время количество текстовой информации, представленной в электронном виде, растёт экспоненциально, вопрос реализации эффективных, масштабируемых и производительных информационно-поисковых систем на сегодняшний день остаётся открытым для исследователей.

1.2. Задачи информационного поиска

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

Классическая задача ИП, с которой началось развитие этой области, – это поиск документов, удовлетворяющих запросу, в рамках некоторой статической коллекции документов. Но список задач ИП постоянно расширяется и теперь включает: вопросы моделирования, классификацию и фильтрацию документов, проектирование архитектур поисковых систем и пользовательских интерфейсов, извлечение информации, построение языков запросов и др.

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

1.3. Методы информационного поиска

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

Полнотекстовый поиск – автоматизированный документальный поиск, при котором в качестве поискового образа документа используется его полный текст или существенные части текста. Пример системы полнотекстового поиска – любой интернет-поисковик, например Яндекс или Google. Пример результатов полнотекстового поиска в поисковой системе Google представлен на рисунке 1.1.