Поиск и навигация в Internet

Часть 2. Информационно-поисковые языки

В предыдущей статье речь шла об основных принципах организации поиска в Internet и построения структуры информационно-поисковых систем (ИПС), используемых в сети. Теперь имеет смысл более подробно поговорить о таком средстве, как информационно-поисковые языки (ИПЯ) или языки запросов ИПС. Теоретические основы построения ИПЯ проиллюстрируем на конкретных примерах языков систем Lycos, AltaVista, Yahoo, OpenText, Infoseek и WAIS.

Типы информационно-поисковых языков

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

Релевантность можно представить также, как меру близости между реально полученными документами и тем, что следовало бы получить из системы. Возникают две взаимосвязанные задачи: представление информации в системе и формулирование информационных потребностей пользователя. Руководства по ИПС обычно утверждают, что в системе реализуется запрос типа "найди похожее". Но что означает эта фраза в действительности? Как вычислить эту похожесть?

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

Традиционные ИПЯ и их модификации

Наиболее распространенным является язык, позволяющий составить логические выражения из набора терминов. При этом используются булевые операторы AND, OR, NOT. Тогда запрос может выглядеть следующим образом:

((информационная and система) or ИПС) not СУБД

Эта фраза означает: <Найди все документы, которые содержат одновременно слова "информационная" и "система", либо слово "ИПС", но не содержат слова "СУБД">. Фактически, здесь имеется два запроса:

"информационная and система not СУБД" и "ИПС not СУБД",

каждый из которых подразумевает как бы два действия: сначала найти все документы, содержащие необходимые пользователю термины, а потом отсеять все из них, которые содержат термин "СУБД". Такая схема достаточно проста и поэтому наиболее широко применяется в современных ИПС, однако еще 20 лет назад уже были хорошо известны ее недостатки.

Булев поиск плохо масштабирует выдачу. Оператор AND может очень сильно сократить число документов, выдаваемых на запрос. При этом все будет зависеть от того, насколько типичными для базы данных являются поисковые термины. Оператор OR, напротив, может привести к неоправданно широкому запросу, в котором полезная информация затеряется за информационным шумом. Для успешного применения этого ИПЯ следует хорошо знать лексику системы и ее тематическую направленность. Как правило, для системы с таким поисковым языком создаются специальные документально - лексические базы данных со сложными словарями или тезаурусами, содержащими информацию о связи терминов словаря друг с другом.

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

Языки типа "Like this"

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

Поиск в нечетких множествах

При данном типе поиска весь массив документов описывается как набор нечетких множеств терминов. Каждый термин определяет некую монотонную функцию принадлежности к документам данного массива. Когда запрашивается AND, то это понимается как минимум из двух функций, соответствующих терминам запросов: OR - как максимум, NOT - как 1-<значение функции>. В соответствии с полученными значениями результат поиска также ранжируется, как и в случае с поиском по мерам близости. Этот метод поиска используется только в исследовательских системах, его распространение крайне ограничено.

Пороговые модели

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

Кластерная и вероятностная модели

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

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

Коррекция запроса по релевантности

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

Информационно-поисковые языки Internet

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

Lycos. Как и большинство систем, Lycos дает возможность применять простой запрос и более изощренный метод поиска. В простом запросе в качестве поискового критерия вводится предложение на естественном языке, после чего Lycos производит нормализацию запроса, удаляя из него так называемые stop-слова, и только после этого приступает к его выполнению. Почти сразу выдается информация о количестве документов на каждое слово, а позже и список ссылок на формально релевантные документы. В списке против каждого документа указывается его мера близости запросу, количество слов из запроса, попавших в документ, и оценочная мера близости, которая может быть больше или меньше формально вычисленной. По состоянию на апрель 1996 года, в Lycos не был реализован булевый поиск, но такие планы анонсированы. Пока нельзя вводить логические операторы в строке вместе с терминами, но использовать логику через систему меню Lycos позволяет. Такая возможность применяется для построения расширенной формы запроса, предназначенной для искушенных пользователей, уже научившихся работать с этим механизмом. Таким образом, видно, что Lycos относится к системе с языком запросов типа "Like this", но намечается его расширение и на другие способы организации поисковых предписаний.

AltaVista. Наиболее интересная возможность AltaVista - это расширенный поиск. Здесь стоит сразу оговориться, что, в отличие от многих других систем AltaVista поддерживает одноместный оператор NOT. Кроме этого, имеется еще и оператор NEAR, который реализует возможность контекстного поиска, когда термины должны располагаться рядом в тексте документа. AltaVista разрешает поиск по ключевым фразам, при этом она имеет довольно большой фразеологический словарь. Кроме всего прочего, при поиске в AltaVista можно задать имя поля, где должно встретиться слово: гипертекстовая ссылка, applet, название образа, заголовок и ряд других полей. К сожалению, подробно процедура ранжирования в документации по системе не описана, но видно, что ранжирование применяется как при простом поиске, так и при расширенном запросе. Реально эту систему можно отнести к системе с расширенным булевым поиском.

Yahoo. Данная система появилась в сети одной из первых, и сегодня Yahoo сотрудничает со многими производителями средств информационного поиска, а на различных ее серверах используется различное программное обеспечение. На мой взгляд, это самая незатейливая информационная служба, которая сосредоточилась на информации о Web, как таковой. ИПЯ Yahoo достаточно прост: все слова следует вводить через пробел, они соединяются связкой AND либо OR. При выдаче не указывается степень соответствия документа запросу, а только подчеркиваются слова из запроса, которые встретились в документе. При этом не производится нормализация лексики и не проводится анализ на "общие" слова. Хорошие результаты поиска получаются только тогда, когда пользователь знает, что в базе данных Yahoo информация есть наверняка. Ранжирование производится по числу терминов запроса в документе. Yahoo относится к классу простых традиционных систем с ограниченными возможностями поиска.

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

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

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

Internet о своих информационно-поисковых языках