Реферат: Внастоящее время используется несколько подходов к представлению ин­формации в базах данных для обеспечения последующего поиска этой информа­ции [65, 67]

Модели поиска

В настоящее время используется несколько подходов к представлению ин­формации в базах данных для обеспечения последующего поиска этой информа­ции [65, 67]. Рассмотрим два наиболее популярных подхода. Первый базируется на теории множеств, а второй на векторной алгебре. Оба подхода достаточно эф­фективны на практике, однако у них есть общий недостаток, который следует из основного упрощающего предположения, заключающегося в том, что смысл до­кумента, его основное содержание определяется множеством ключевых слов — терминов и понятий, входящих в него. Конечно же, такие подходы частично ведут к потере содержательных оттенков текстов, зато позволяют выполнять быстрый поиск и группировку документов по формальным признакам. Сегодня эти подходы — самые популярные. Следует заметить, что существуют и другие мето­ды, например семантические, в рамках которых делаются попытки выявить смысл текста за счет анализа грамматики текста, использования баз знаний и различных тезаурусов, отражающих семантические связи между отдельными словами и их группами. Очевидно, что такие подходы требуют больших затрат на поддержку баз знаний и тезаурусов для каждого языка, тематики и вида документов.

^ Булева модель поиска

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

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

В рамках булевой модели документы и запросы представляются в виде мно­жества морфемных основ ключевых слов, будем их в дальнейшем называть тер­мами. Пусть документальный массив С состоит из множества документов d\, ...,dn, а документ dv содержит множество различных термов T(di). Обозначим через r=UM„T(dj) словарь массива С, представляющий собой множество всех

термов, встречающихся в документах из ^ С, и через T(dt) — словарь документа d%. В булевой модели запрос пользователя представляет собой логическое выраже­ние, в котором ключевые слова (термы запроса) связаны логическими операто­рами AND, OR и NOT. В различных поисковых системах в Internet пользователи могут пользоваться умолчаниями, не используя в явном виде логических опера­ций, а просто перечисляя ключевые слова. Чаще всего по умолчанию предполага­ется, что все ключевые слова соединяются логической операцией AND (— в этих случаях в результаты поиска включаются только те документы, которые содержат одновременно все ключевые слова запроса. В тех системах, в которых пробел меж­ду словами приравнивается к оператору OR, в результаты поиска включаются до­кументы, в которые входит хотя бы одно из ключевых слов запроса.

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

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

Существует несколько подходов к формированию архитектуры поисковых систем, соответствующих булевой модели и нашедших свое воплощение в реаль­ных системах. Одной из наиболее удачных реализаций структуры базы данных информационно-поисковой системы на мэйнфреймах фирмы IBM была признана модель данных системы STAIRS (Storage and Information Retrieval System), ко­торая, благодаря изначально удачным архитектурным решениям до сих пор продолжает развиваться. База данных информационно-поисковых систем этой традиционной архитектуры состоит из следующих основных таблиц [27]:

текстовой, содержащей текстовую часть всех документов;

таблицы указателей текстов, включающей указатели местонахождения до­кументов в текстовой таблице, а заодно и форматные поля всех документов;

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

инверсной, содержащей списки номеров документов и координаты всех вхождений отдельных слов в полях документов.

Процессы, происходившие при поиске информации в базе данных STAIRS, сегодня реализуются средствами современных СУБД и ИПС документального типа. Поиск термина в базе данных осуществляется следующим образом.

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

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

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

По номеру документа осуществляется прямое обращение к фрагменту тек­стовой таблицы — документу — и последующий его вывод.

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

^ Векторно-пространственная модель

Большинство известных информационно-поисковых систем и систем класси­фикации информации в той или иной мере основываются на использовании век­торной модели описания данных (Vector Space Model) [66, 68]. Векторная модель является классической алгебраической моделью. В рамках этой модели документ описывается вектором в некотором евклидовом пространстве, в котором каждо­му используемому в документе терму ставится в соответствие его весовой коэф­фициент (значимость), который определяется на основе статистической инфор­мации о его вхождении в отдельном документе или в документальном массиве. Описание запроса, который соответствует необходимой пользователю тематике, также представляет собой вектор в том же евклидовом пространстве термов. В результате для оценки близости запроса и документа используется скаляр'ное произведение соответствующих векторов описания тематики и документа.

В рамках этой модели с каждым термом ц в документе d) (и запросе q) сопос­тавляется некоторый неотрицательный вес wy. Таким образом, каждый документ и запрос могут быть представлены в виде ^-мерного вектора Щ/Ц _ i,... к, где к — общее количество различных термов во всех документах. Согласно векторной модели, близость документа af, к запросу q оценивается как корреляция между векторами их описаний. Эта корреляция может быть вычислена как скалярное произведение соответствующих векторов описаний. При этом весовые коэффици­енты отдельных термов можно вычислять множеством различных способов.

Один из возможных простейших (но эффективных) подходов — использовать в качестве веса терма wi; в документе d, нормализованную частоту его использо­вания fregtj в данном документе.

Щ = tfij = freqij / max] frequ i

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

щ = tf A-idfy = tfij xlog N / щ,

где iii — число документов, в которых используется терм /), а Л' — общее число документов в массиве.

Обычно значения весов wtj нормируются (дополнительно делятся на квадратный корень из суммы весов всех термов, входящих в документ), что позволяет рас­сматривать документ как ортонормированныи вектор. Такой метод взвешивания термов имеет стандартное обозначение — tfxidf, где tf указывает на частоту исполь­зования термина в документе (term frequency), a idf — на величину, обратную чис­лу документов массива, содержащих данный терм (inverse document frequency).

Когда возникает задача определения тематической близости двух документов или документа и запроса, в этой модели используется простое скалярное произ­ведение sim(di, d2) двух векторов \\mi\\i = \,.., * и \&'i2\ - 1,.., а. которое, очевидно, со­ответствует косинусу угла между векторами-образами документов d\ и d2. Очевид­но, sim(di,d2) принадлежит диапазону [0, 1]. Чем больше величина simidu d2) — тем более близки документы dl и d2. Для любого документа d, имеем sim(di,di)= 1. Ана­логично мерой близости запроса q r документу dL считается величина sim{q, dt).

Векторно-пространственная модель представления данных автоматически обеспечивает системам, построенным на ее основе, такие возможности:

обработку сколь угодно больших запросов;

простую реализацию режима поиска документов, подобных уже найденным;

сохранение результатов поиска в некотором виртуальном массиве с после­дующим уточняющим поиском в нем.

^ Гибридные модели поиска

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