Доступ к
Однажды по работе мне потребовалась информация по ультрафиолетовой дозиметрии, я послал запрос в один из подписных листов и в течение суток получил 6 ответов из США, Канады и Новой Зеландии (среди них Stephan Straus stephen@unicaat.yorku.ca, Martin Brown brauwnma@
Серверу subject при этом игнорируется.
Команды имеют следующий формат: заглавные буквы указывают на возможное сокращение, угловые скобки выделяют опционный параметр, а вертикальная черта отмечает значение этого параметра. Существует стандартный набор параметров ключевых слов, которые могут использоваться совместно с командами в качестве параметров. Важными ключевыми словами являются:
PW=пароль — это ключевое слово служит для описания слова-пароля. Если вы завели слово-пароль для данного PW=, чтобы ваши команды были выполнены. Эта функция создана, чтобы блокировать возможность исполнения команд, используя ваш электронный адрес. Если вы зарегистрировали ваш пароль в сервере PW= во все команды, где это требуется согласно описанию.
F=формат — это ключевое слово управляет форматом файла (или внутренней структурой файла), в котором он будет вам послан. По умолчанию F=командное_ключевое_слово в командах, где это требуется
В последние годы появилась возможность создания подписных листов на основе UNIX программы Majordomo. Количество таких списков резко возросло, их создают группы студентов, оздоровительные клубы и т.д. Но свободный доступ к команде subscribe открывает также широкие возможности для злоупотреблений. Так, фирмы и частные лица, занимающиеся рассылкой subscribe должна исполняться либо только
Первичной задачей
В рамках
SUBscribe имя_списка <полное_имя>
Эта команда нужна для включения подписчика в список для рассылки. Вы можете использовать эту команду для изменения имени (но не электронного адреса), под которым вы уже известны в списке. Имя_списка — это наименование списка, на который вы хотите подписаться.
Адрес, куда будет переправлен ваш запрос, вам будет прислан. Для того, чтобы быть исключенным из списка, посылайте команду:
UNSubscribe имя_списка | * <(NETWIDE>
Наличие круглой скобки только слева не является опечаткой. Чтобы ликвидировать подписку по всем спискам (NETWIDE. Эта версия команды рекомендуется при смене вашего электронного адреса или при длительном отпуске. Для получения перечня имеющихся списков в сервере List.
List <option> <F=формат>
Параметр option может принимать следующие значения.
Short
Отображается резюме всех списков, контролируемых
Long
(детально) Пересылает вам файл (называемый node-name LISTS), который содержит исчерпывающие описания всех списков, поддерживаемых сервером.
Global <эталон>
Выдается полный список всех известных почтовых списков
Для получения листинга почтовых списков существует команда REView. Формат команды:
REView имя_списка <(> <option>
Листинг будет вам переслан в виде файла с именем list-name LIST (или list-name node-name). Почтовый список состоит из двух частей: управляющая секция и подписная секция. Управляющая секция содержит параметры списка, которые включают в себя информацию о том, кто решает вопросы включения в список или его пересмотра, а также архивации. Подписная секция содержит e-mail адреса и имена всех членов списка. REView -команда позволяет вам получить листинг любой или обеих этих секций (по умолчанию — обеих) для любого из списков. Следует иметь в виду, что по решению владельца списка командой REView может выдаваться только список членов этого списка. В этом случае вам не будет позволено просматривать список e-mail адресов, если вы не член списка. Члены списка могут ограничить доступ к своему e-mail адресу по команде REView, если они установили опцию CANCEL. имя_списка — имя REView относятся:
Short
Получаемая информация ограничивается управляющей секцией (только параметры списка).
Countries
Выдается перечень членов списка, упорядоченный с учетом гражданства.
LOCal
Если список имеет пару (соединен с другим списком того же имени, обслуживаемым другим сервером), вы получите полный листинг в отклик на команду REView.
При подключении к какому-либо списку, вам будет поставлен в соответствие перечень параметров по умолчанию. Эти параметры могут быть вами изменены для любого из списков, где вы являетесь подписчиком. Команда Query позволяет просмотреть текущие значения параметров (опций) для любого списка. Формат команды:
Query имя_списка | *
Параметр имя_списка представляет собой наименование списка, на который вы подписались. Если вы используете символ "*" вместо имени списка, вы получите информацию о ваших личных параметрах для всех списков, на которые вы подписаны.
Для изменения параметров вашей подписки применяется команда SET. Она имеет формат:
SET имя_списка | * options
После выполнения команды SET сервер пришлет вам подтверждение успешного изменения параметра по электронной почте. Важными опциями команды SET являются:
Mail | DIGests | INDex | NOMail
Эти опции варьируют способ, которым вы получаете сообщения. Mail означает, что вы хотите получать сообщения по электронной почте (значение по умолчанию).
Предусмотрена возможность изменения формата заголовков почтовых сообщений.
SHORThdr | FULLhdr | IETFhdr | DUALhdr
Все почтовые сообщения состоят из секции заголовка и тела сообщения. Заголовок содержит информацию об отправителе, получателе, дате и времени отправки. Перечисленные выше опции команды SET указывают на тип заголовка почтового сообщения, который вы хотите иметь. SHORThdr означает, что
CONCEAL | NOCONCEAL
Указывает на то, хотите вы или нет, чтобы ваше имя и почтовый адрес появлялся в ответ на команду REView, выданную одним из подписчиков списка. По умолчанию работает NONCONCEAL. Обратите внимание, что полный список подписчиков доступен владельцу списка и администратору
Некоторые команды позволяют пользователю манипулировать файлами, которые хранятся в депозитарии
Команда PW позволяет вам добавить, изменить или ликвидировать ваше персональное слово-пароль. Команда имеет следующий формат:
PW options
Слово-пароль блокирует возможность несанкционированного использования вашего электронного адреса. Настоятельно рекомендуется воспользоваться этой возможностью. Запрос на регистрацию слова-пароля может быть воспринят в любое время; аналогично, оно может быть изменено и аннулировано также, когда вы захотите. Слово-пароль может включать в себя от одного до 8 алфавитно-цифровых символов.
В последние годы Интернет-форумы обычно строятся на базе WEB-технологии, но пока эта техника не предоставляет полной функциональности подписных листов, и по этой причине последние продолжают существовать, хотя и не развиваются столь бурно, как это было десять лет назад. Многие коммерческие компании используют технику подписных листов для рассылки рекламных материалов своим клиентам.
Развитие Интернет начиналось как средство общения и удаленного доступа (электронная почта, telnet, FTP). Но постепенно эта сеть превратилась в средство массовой информации, отличающееся тем, что операторы сети и сами могут быть источниками информации, и определяют, в свою очередь, то, какую информацию они хотят получить.
Среди первых поисковых систем были
Первые WWW-системы работали в режиме меню (система
(рис 5.1) Пример дерева гиперсвязейГиперсвязь, помеченная буквой А, может явиться причиной образования цикла при обходе дерева. Исключить такие связи невозможно, так как они носят принципиальный смысловой характер. По этой причине любая автоматизированная программа обхода дерева связей должна учитывать такую возможность и предотвращать циклы обхода.
Задача непроста даже в случае поиска нужного текста в пределах одного достаточно большого по емкости диска, когда вы заранее не знаете или не помните, в каком субкаталоге или в каком файле содержится искомый текст. Для облегчения ручного поиска на серверах FTP в начале каждого субкаталога размещается индексный файл.
Для решения этой задачи в большинстве операционных систем имеются специальные утилиты (например, grep для UNIX). Но даже они требуют достаточно много времени, если, например, дисковое пространство лежит в пределах нескольких десятков гигабайт или более, а каталог весьма разветвлен. В полнотекстных базах данных для ускорения поиска используется индексация по совокупности слов, составляющих текст. Хотя индексация также является весьма времяемкой процедурой, но производить ее, как правило, приходится только один раз. Проблема здесь заключается в том, что объем индексного файла оказывается сравним (а в некоторых случаях превосходит) с исходным индексируемым файлом. Первоначально каждому документу ставился в соответствие индексный файл, в настоящее время индекс готовится для тематической группы документов или для поисковой системы в целом. Такая схема индексации экономит место в памяти и ускоряет поиск. Для документов очень большого размера может использоваться отдельный индекс, а в поисковой системе — иерархический набор индексов. Индексированием называетсяпроцесс перевода с естественного языка на информационно-поисковый. В частности, под индексированием понимается отнесение документа, в зависимости от содержимого, к определенной рубрике некоторой классификации. Индексирование можно свести к проблеме распознавания образов. Классификация определяет разбиение пространства предметных областей на непересекающиеся классы. Каждый класс характеризуется набором признаков и специфических для него терминов (ключевых слов), выражающих основные понятия и отношения между ними.
Слова в любом тексте в информационном отношении весьма неравнозначны. И дело не только в том, что текст содержит много вспомогательных элементов предлогов, местоимений или артиклей (например, в англоязычных текстах).
Для сокращения объема индексных регистров и ускорения самого процесса индексации вводятся так называемые стоп-листы. В эти стоп-листы вносятся слова, которые не несут смысловой нагрузки (например, предлоги или некоторые вводные слова).
Но при использовании стоп-листов необходима определенная осторожность. Например, занеся в стоп-лист, неопределенный артикль английского языка "а", можно заблокировать нахождение ссылки на "витамин А".
Немалое влияние оказывает изменяемость слов из-за склонения или спряжения. Последнее делает необходимым лингвистический разбор текста перед индексацией. Хорошо известно, что смысл слова может меняться в зависимости от контекста, и это также усложняет проблему поиска. Практически все современные информационные системы для создания и обновления индексных файлов используют специальные программные средства.
Существующие поисковые системы успешно работают с HTML-документами, с обычными ASCII-текстами и новостями usenet. Трудности возникают для текстов Winword и даже для текстов Postscript. Связано это с тем, что такие тексты содержат большое количество управляющих символов и слов. Трудно (практически невозможно) осуществлять поиск для текстов, которые представлены в графической форме, здесь следует ждать успеха от широкого внедрения MPEG-7. К сожалению, к числу графических объектов очень часто относятся и математические формулы, которые в HTML имеют формат рисунков (это уже недостаток самого языка). Так что можно без преувеличения сказать, что в этой крайне важной области, уже имеющей немалые успехи, мы все же находимся лишь в начале пути. Ведь море информации, уже загруженной в Интернет, требует эффективных средств навигации. От того, что информации в сети много, мало толку, если мы не можем быстро найти то, что нужно. И в этом, я полагаю, убедились многие читатели, получив на свой запрос список из нескольких тысяч документов. Практически это эквивалентно списку нулевой длины, так как заказчик в обоих случая не получает того, что хотел.
Встроенная в язык HTML метка <meta> создана для предоставления информации о содержании документа для <meta http-equiv=response content=description name=description URL=url>. Параметр http-equiv=response ставит в соответствие элементу заголовок HTTP ответа. Значение параметра http-equiv интерпретируется приложением, обрабатывающим HTML документ. Значение параметра content определяется значением, содержащимся в http-equiv.
Современная поисковая система содержит в себе несколько подсистем.
Следует иметь в виду, что работа web-агентов и системы поиска напрямую не связана друг с другом. WEB-агенты (роботы) работают постоянно, вне зависимости от поступающих запросов. Их задача — выявление новых информационных серверов, новых документов или новых версий уже существующих документов. Под документом здесь подразумевается HTML-, текстовый или nntp-документ. WEB-агенты имеют некоторый базовый список зарегистрированных серверов, с которых начинается просмотр. Этот список постоянно расширяется за счет анализа гиперссылок. При просмотре документов очередного сервера выявляются URL и по ним производится дополнительный поиск. Таким образом, WEB-агенты осуществляют обход дерева гиперссылок. Каждый новый или обновленный документ передается системе обработки. Роботы могут в качестве побочного продукта выявлять разорванные гиперсвязи, способствовать построению зеркальных серверов.
Обычно работа роботов приветствуется, ведь благодаря им сервер может обрести новых клиентов, ради которых он и создавался. Но при определенных обстоятельствах может возникнуть желание ограничить неконтролируемый доступ роботов к серверам узла. Одной из причин может быть постоянное обновление информации каких-то серверов, другой причиной может стать то, что для доставки документов используются скрипты CGI. Динамические вариации документа могут привести к бесконечному разрастанию индекса. Для
Когда "воспитанный" робот заходит в ЭВМ, он проверяет наличие в корневом каталоге файла
# robots.txt for http://store.in.ru user-agent: * # * соответствует любому имени робота disallow: /cgi-bin/ # не допускает робот в каталог cgi-bin disallow: /tmp/ # не следует индексировать временные файлы disallow: /private/ # не следует заходить в частные каталоги
Файл содержит обычный текст, который легко редактировать, после символа # следуют комментарии. Допускается две директивы. user-agent: — определяет имя робота, к которому обращены следующие далее инструкции; если не имеется в виду какой-то конкретный робот и инструкции должны выполняться всеми роботами, в поле параметра записывается символ *.
Автор исходного текста может заметно помочь поисковой системе, умело выбрав заголовок и подзаголовок, профессионально пользуясь терминологией и перечислив ключевые слова в подзаголовках. Исследования показали, что автор (а иногда и просто посторонний эксперт) справляется с этой задачей быстрее и лучше, чем вычислительная машина. Но такое пожелание вряд ли станет руководством к действию для всех без исключения авторов. Ведь многие из них, давая своему тексту образный заголовок, рассчитывают (и не без успеха) привлечь внимание читателей. Но машинные системы поиска не воспринимают (во всяком случае, пока) образного языка. Например, в одном лабораторном проекте, который был разработан для лексического разбора выражений, состоящих из существительных с определяющим прилагательным, и по своей теме связанных с компьютерной тематикой, система была не способна определить во фразе "иерархическая компьютерная архитектура" то, что прилагательное "иерархическая" относится к слову "архитектура", а не к "компьютерная" (Vickery Vickery 1992; здесь подразумевается английский текст, где часто трудно отличить прилагательное от существительного). То есть, система была не способна отличать образное использование слова в выражении от его буквального значения.
В свою очередь, специалисты, занятые в области поисковых и информационных систем, способны заметно облегчить работу авторам, снабдив их необходимыми современными тезаурусами, где перечисляются нормативные значения базовых терминов в той или иной научно-технической области, а также устойчивых словосочетаний. Параллельно могут быть решены проблемы синонимов.
В настоящее время, несмотря на впечатляющий прогресс в области вычислительной техники, степень соответствия документа определенным критериям запроса надежнее всего может определить человек. Но темп появления электронных документов в сети достигает ошеломляющего уровня (частично это связано с преобразованием в электронную форму старых документов и книг методом сканирования). Написание рефератов для последующего их использования поисковыми системами — достаточно изнурительное занятие, требующее к тому же весьма высокой профессиональной подготовки. Именно по этой причине уже в течение некоторого времени предпринимаются попытки перепоручить этот процесс ЭВМ.
Для этого нужно выработать критерии оценки важности отдельных слов и фраз, составляющих текст. Оценку значимости предложений выработал Г.Лун. Он предложил оценивать предложения текста в соответствии с параметром:
$$V_{пр} = \frac{N_{зс}^2}{N_с}$$где Vпр — значимость предложения; Nзс — число значимых слов в предложении; а Nc — полное число слов в предложении. Используя этот критерий, из любого документа можно отобрать некоторое число предложений. Понятно, что они не будут составлять членораздельного текста. Нужно учитывать также, что "значимые слова" должны браться из тематического тезауруса или отбираться экспертом. По этой причине методика может лишь помочь человеку, а не заменить его (во всяком случае, на современном этапе развития вычислительной техники).
Автоматическая система выявления ключевых слов обычно использует статистический частотный анализ (методика В. Пурто). Пусть f — частота, с которой встречаются различные слова в тексте, а u — относительное значение полезности (важности).
Тогда зависимость f(u) апроксимируется формулой $$f(u)=C\frac1u$$, то есть произведение частоты встречи слов и их полезности является константой. В теории автоматического анализа документов данная гипотеза используется для вывода следствия о существовании двух пороговых значений частот. Слова с частотой менее нижнего порога считаются слишком редкими, а с частотой, превосходящей верхний порог, — общими, не несущими смысловой нагрузки. Слова с частотой, находящейся посередине между данными порогами, в наибольшей степени характеризуют содержимое данного конкретного документа [Г. Лун; 2]. К сожалению, выбор порогов — процедура достаточно субъективная. Ключевые слова, выявляемые программно, ранжируются согласно частоте их использования. Замечено, что определенное значение имеет не только частота применения слова в конкретном документе, но и число документов, в которых это слово встречается.
В работах Спарка Джонса экспериментально показано, что если N — число документов и n — число документов, в которых встречается данный индексный термин (ключевое слово), то вычисление его веса по формуле:
приводит к более эффективным результатам поиска, чем вообще без использования оценки значимости индексного термина.
Одним из известных путей облегчения процедуры поиска является группирование документов по определенной, достаточно узкой тематике в кластеры. В этом случае запрос с ключевым словом, фигурирующем в заголовке кластера, приведет к тому, что все документы кластера будут включены в список найденных. Кластерный метод наряду с очевидными преимуществами (прежде всего заметное ускорение поиска) имеет столь же явные недостатки. Документы, сгруппированные по одному признаку, могут быть случайно включены в перечень документов, отвечающих запросу, по той причине, что одно из ключевых слов кластера соответствует запросу. В результате в перечне найденных документов вы можете с удивлением обнаружить тексты, не имеющие никакого отношения к интересующей вас теме.
Некоторые поисковые системы предоставляют возможность поиска документов, где определенные ключевые слова находятся на определенном расстоянии друг от друга (
Наиболее эффективным инструментом при поиске можно считать возможность использования в запросе булевых логических операторов AND, OR и NOT. Объединение ключевых слов с помощью логических операторов может сузить или расширить зону поиска.
Проблема соответствия ( релевантности ) документа определенному запросу совсем не проста.
Индексные файлы, содержащие информацию о WEB-сайтах, занимают около 200 Гигабайт дискового пространства (данные шестилетней давности), поиск по содержимому которых производится за время, меньшее одной секунды (на самом деле, реальный поиск осуществялется в объеме, более чем в десять раз меньшем).
Пример широко известной несколько лет назад поисковой системы alta vista, где задействовано большое число суперЭВМ, показывает, что дальнейшее движение по такому пути вряд ли можно считать разумным, хотя прогресс в вычислительной технике может и опровергнуть это утверждение. Тем не менее, даже в случае фантастических достижений в области создания еще более мощных ЭВМ, можно утверждать, что распределенные поисковые системы могут оказаться эффективнее. Во-первых, местный администратор быстрее может найти общий язык с авторами текстов, которые могут точнее выбрать набор ключевых слов. Во-вторых, распределенная система способна распараллелить обработку одного и того же информационного запроса. Распределенная система памяти и процессоров может, в конце концов, стать более адекватной потокам запросов к информации, содержащейся на том или ином сервере. Способствовать этому может также создание тематических серверов поиска, где концентрируется информация по относительно узкой области знаний. Для таких серверов возможен отбор документов экспертами, они же могут определить списки ключевых слов для многих документов. Здесь возможна автоматическая предварительная процедура фильтрации документов по наличию определенного набора ключевых слов. Способствует этому и существование тематических журналов (в том числе электронных), где сконцентрированы статьи по определенной тематике.
В случаях, когда поисковая система выдает заказчику большой список документов, отвечающих критериям его запроса, бывает важно, чтобы они были упорядочены согласно их степени соответствия (наличие ключевых слов в заголовке, большая частота использования ключевых слов в тексте документа и т.д.). Но простые критерии здесь не всегда срабатывают: так, объемный документ имеет больше шансов попасть в список результата поиска, поскольку в нем много слов и с большой вероятностью там встречается ключевое слово. По этому критерию Британская энциклопедия должна попасть в результирующий список любого запроса. Для компенсации искажений, вносимых длиной документов, используется нормализация весов индексных терминов.
Нормализация представляет собой способ уменьшения абсолютного значения веса индексных терминов, обнаруженных в документе. Одним из наиболее распространенных методов, решающих данную проблему, является косинусная нормализация. При использовании этого метода нормализации вес каждого индексного термина делится на Евклидову длину вектора оцениваемого документа. Евклидова длина вектора определяется формулой:
$$L=\sqrt{w_1^2+w_2^2+...+w_n^2},$$
где wi = tf x idf
– вес i -того термина в документе, tf (IDF (Inverted Document Frequency) — величина, обратная частоте, с которой данный термин встречается во всей совокупности документов. Окончательная формула для вычисления веса термина ( w ) в документе с учетом косинусного фактора нормализации представляется формулой:
Термины, которые отсутствуют в тексте документа, имеют нулевой вес. В списке, возвращаемом на запрос, документы перечисляются в порядке уменьшения данного численного значения.
В работах Букштейна, Свенсона и Хартера было показано, что распределение функциональных слов, в отличие от специфических слов, с хорошей точностью описывается распределением Пуассона. То есть, если отыскивается распределение функционального слова w в некотором множестве документов, тогда вероятность f(n) того, что слово w будет встречено в тексте n раз представляется функцией:
– x варьируется от слова к слову и для конкретного слова должно быть пропорционально длине текста. Слова, распределенные в совокупности документов согласно Пуассону, полезной информации не несут.
Для представления документов используется векторная модель, в которой любой документ характеризуется бинарным вектором x = x1,x2,...,xn, где значения xi = 0 или 1, в зависимости от того, присутствует в тексте i -ый индексный термин или нет. Рассматриваются два взаимно исключающих события:
w1 — документ удовлетворяет запросу; w2 — документ не удовлетворяет запросу
Для определения того, какие документы удовлетворяют запросу, а какие нет, необходимо вычислить условные вероятности P(w1|x) и P(w2|x).
Непосредственно получить значения этих вероятностей нельзя, поэтому необходимо найти другой альтернативный подход для их определения с помощью известных нам величин. По формуле Байеса для
$$P(w_i|x)=\frac{P(x|w_i)P(w_i)}{P(x)},$$
где i=1, 2.
В приведенной формуле P(w1) — первоначальная вероятность соответствия ( i = 1 ) или несоответствия ( i = 2 ) запросу, величина P(x|wi) пропорциональна вероятности соответствия или несоответствия запросу для данного x ; в недискретном случае она представляет собой функцию плотности распределения и обозначается как P(x|wi).
Окончательно:
$$P(x)=\sum_{i=1}^2P(x|w_i)P(w_i),$$
что представляет собой вероятность получения документа x в ответ на запрос, при условии, что он будет ему соответствовать. P(x) выступает в качестве нормализующего фактора (т.е. с его помощью достигается выполнение условия P(w1|x)+P(w2|x)=1 ).
Для определения релевантности документа используется вполне очевидное правило:
Если P(w1|x)>P(w2|x), то документ удовлетворяет запросу [1].
В противном случае считается, что документ не удовлетворяет запросу. При равенстве значений вероятности решение о релевантности документа принимается произвольно.
Правило [1] основано на том, что при его использовании просто минимизируется средняя вероятность ошибки принятия нерелевантного документа за релевантный и наоборот. То есть, для любого документа x вероятность ошибки P(error|x) равна:
Таким образом, для минимизации средней вероятности ошибки необходимо минимизировать функцию $$P(error)=\sum_xP(error|x)P(x)$$
Не углубляясь в теорию вероятностного нахождения релевантных документов, укажем еще одно правило, которое можно использовать вместо [1]:
(l21-l11)P(x|w1)P(w1)>(l12-l22)P(x|w2)P(w2)
В формуле [2] коэффициенты lij стоимостной функции определяют потери, вносимые при ожидании события wi, когда на самом деле произошло событие wj.
Для практической реализации вероятностного поиска вводится упрощающее предположение относительно P(x|wi). Принимается, что значения xi вектора x являются статистически независимыми. Данное утверждение математически представляется в виде:
P(x|wi)=P(x1|wi)P(x2|wi)...P(xn|wi).
Определим переменные: pi=Pr ob(xi=1/w1) и qi=Pr ob(xi=1/w2), представляющие собой вероятность того, что в документе присутствует i -ый индексный термин при условии, что документ является релевантным (нерелевантным). Соответствующая вероятность для отсутствия индексных терминов имеет вид: 1-pi=Pr ob(xi=0/wi)
Вероятностные функции, используемые для подстановки в правило [1], имеют вид:
$$P(x|w_1)=\prod_{i=1}^np_i^{x_i}(1-p_i)^{1-x_i}$$ и
$$P(x|w_2)=\prod_{i=1}^nq_i^{x_i}(1-q_i)^{1-x_i}.$$
Подставляя значения P(x|wi) в [2] и логарифмируя, получаем:
$$g(x)=\sum_{i=1}^n(a_ix_i+b_i(1-x_i))+e=\sum_{i=1}^nc_ix_i+C,$$ где
$$c_i=\log\frac{p_i(1-q_i)}{q_i(1-p_i)}$$ и$$C=\sum_{i=1}^n\log\frac{(1-p_i)}{(1-q_i)}+\log\frac{P(w_1)}{P(w_2)}+\log\frac{l_{21}-l_{11}}{l_{12}-l_{22}}.$$
Функция G(x) представляет собой не что иное, как весовую функцию, в которой коэффициенты Сi есть веса присутствующих в документе индексных терминов. Константа С одинакова для всех документов x, но, конечно, различна для разных запросов и может рассматриваться в качестве порогового значения для поисковой функции. Единственными параметрами, которые могут меняться для данного запроса, являются параметры стоимостной функции, вариации которых позволяют получать в ответе большее или меньшее число документов.
Теперь рассмотрим коэффициенты Сi функции G(x) с использованием следующей терминологии:
| Релевантные документы | Нерелевантные документы | Общее количество документов | |
|---|---|---|---|
| xi=1 | r | n-R | n |
| xi=0 | R-r | N-n-R-r | N-n |
| Всего | R | N-R | N |
N — полное число документов в системе
R — число релевантных документов
r — число релевантных документов, выданных в ответ на запрос
n — полное число документов, выданных в ответ на запрос
Таблица приводит результаты запроса, направленного системе поиска. Представленная таблица должна существовать для каждого из индексных терминов.
Если мы обладаем всей информацией о релевантных и нерелевантных документах в коллекции, то применимы следующие оценки:
$$p_i=\frac{r}{R}$$ и$$q_i=\frac{n-r}{N-R}$$
Тогда функция g(x) может быть переписана в виде
$$g(x)=\sum_{i=1}^nx_i\log\frac{\frac{r}{(R-r)}}{\frac{(n-r)}{(N-n-R+r)}}+C$$
Коэффициент при xi показывает, до какой степени можно провести дискриминацию по i -тому термину в рассматриваемой коллекции документов. В действительности N может рассматриваться как полное количество документов не только во всей коллекции, но и в некотором ее подмножестве.
Все приведенные формулы были выведены при условии, что индексные термины являются статистически независимыми. В общем случае это, конечно, не так. В теории вероятностного поиска моделируется зависимость между различными индексными формулами, в связи с чем вид функции G(x) несколько меняется.
Многие системы поиска информации основаны на словарях и тезаурусах для корректировки запросов и представления индексируемых документов, чтобы увеличить шансы найти необходимый документ. На практике, большинство словарей составляется вручную. Словари создаются с помощью одного из двух основных способов:
В первом случае связываются слова, являющиеся взаимозаменяемыми, то есть, в словарях и тезаурусах они принадлежат одному и тому же классу. Иначе говоря, можно выбрать по одному слову из каждого класса, и совокупность выбранных слов может быть использована для создания контролируемого словаря. Выбирая слова из созданного контролируемого словаря, можно проводить индексацию документов или формировать поисковые запросы.
Во втором случае для создания тезауруса используются семантические связи между словами для построения, например, иерархической структуры связей. Создание такого типа словарей является достаточно сложным и трудоемким процессом.
Однако были предложены способы и для автоматического создания словарей. В то время как созданные вручную словари опираются на семантику (т.е. распознают синонимы, являются более обширными, используют более тонкие взаимосвязи), автоматически созданные тезаурусы, в основном, базируются на синтаксическом и статистическом анализе. Но, так как использование синтаксиса не приводит к серьезному увеличению эффективности работы систем, то значительно большее внимание уделяется статистическим методам.
Основное допущение, используемое для автоматического создания классов ключевых слов, заключается в следующем: если ключевые слова a и b могут быть взаимозаменяемы в том смысле, что мы готовы принять документ, содержащий ключевое слово b вместо ключевого слова a и наоборот, то данное обстоятельство верно из-за того, что слова a и b имеют одинаковое значение или ссылаются на одинаковые темы.
Основываясь на описанном принципе, нетрудно видеть, что создание классификации слов может быть автоматизировано. Можно определить два основных приближения для использования классификации ключевых слов:
Для простейшей поисковой стратегии, использующей только что описанные дескрипторы, независимо от того, являются ли они ключевыми словами или названиями классов, созданных на основе группы ключевых слов, "расширенное" представление документов и запросов с помощью любого из вышеописанных способов может существенно повысить число соответствий между документами и запросами и, следовательно, увеличить значение параметра
В отчетах об экспериментальных работах по использованию автоматической классификации ключевых слов, проведенных ранее Спарком Джонсом, сообщается, что использование автоматической классификации приводит к увеличению эффективности работы системы по сравнению с системой, использующей неклассифицированные ключевые слова.
Работа Минкера и др. не подтвердила выводы Спарка Джонса и фактически показала, что в некоторых случаях применение классификации ключевых слов приводит к существенному ухудшению работы системы в целом. Д. Сальтон в своем отзыве о работе Минкера определил, что целесообразность использования классификации ключевых слов для улучшения эффективности работы поисковых систем еще полностью не определена и является объектом дальнейших экспериментальных исследований. Действительно, при работе в Интернет с поисковыми системами, построенными на классификации ключевых слов, (такими, как lycos и excite ), заметно существенное увеличение документов, не представляющих собой ничего общего с запросом, но, тем не менее, имеющих довольно высокий ранг и, следовательно, по мнению поисковой системы, наиболее точно соответствующих заданному запросу.
Для дальнейшего увеличения эффективности системы используется так называемая кластеризация документов.
Существуют две основные области применения методов классификации в системах поиска и локализации информации. Это — кластеризация (классификация) ключевых слов и кластеризация документов.
Под кластеризацией документов понимается создание таких групп документов, что документы, принадлежащие одной группе, оказываются, в некоторой степени, связанными друг с другом. Другими словами, документы принадлежат одной группе потому, что ожидается, что эти документы будут находиться вместе в результате обработки запроса. Логическая организация документов достигается, в основном, двумя следующими способами.
Первый — путем непосредственной классификации документов, и второй — посредством промежуточного вычисления некоторой величины соответствия между различными документами.
Было теоретически доказано, что первый метод является очень сложным для практической реализации, так что любые экспериментальные результаты не могут считаться достаточно надежными. Второй способ классификации заслуживает подробного внимания и, по сути, может считаться единственным реальным подходом к решению проблемы.
На практике почти невозможно сопоставить каждый из документов каждому из запросов из-за слишком больших затрат машинного времени на проведение таких операций. Было предложено много различных способов для уменьшения количества необходимых для выполнения запроса операций сравнения. Наиболее многообещающей была идея использовать группы взаимосвязанных документов, применяя процедуры автоматического определения соответствия документов. Проводя сравнения запроса всего лишь с одним документом, являющимся представителем группы (заранее определенным), и таким образом определяя группу документов, в которой и происходит дальнейший поиск, мы существенно уменьшаем затрачиваемое на обработку запроса машинное время.
Реальный прорыв в совершенствовании систем поиска может дать создание программ, способных осуществлять анализ контекста. Этот анализ можно выполнять автоматически или в диалоговом режиме (клиенту задаются вопросы, которые позволяют уточнить контекст запроса).
Доступ к
Однажды по работе мне потребовалась информация по ультрафиолетовой дозиметрии, я послал запрос в один из подписных листов и в течение суток получил 6 ответов из США, Канады и Новой Зеландии (среди них Stephan Straus stephen@unicaat.yorku.ca, Martin Brown brauwnma@
Серверу subject при этом игнорируется.
Команды имеют следующий формат: заглавные буквы указывают на возможное сокращение, угловые скобки выделяют опционный параметр, а вертикальная черта отмечает значение этого параметра. Существует стандартный набор параметров ключевых слов, которые могут использоваться совместно с командами в качестве параметров. Важными ключевыми словами являются:
PW=пароль — это ключевое слово служит для описания слова-пароля. Если вы завели слово-пароль для данного PW=, чтобы ваши команды были выполнены. Эта функция создана, чтобы блокировать возможность исполнения команд, используя ваш электронный адрес. Если вы зарегистрировали ваш пароль в сервере PW= во все команды, где это требуется согласно описанию.
F=формат — это ключевое слово управляет форматом файла (или внутренней структурой файла), в котором он будет вам послан. По умолчанию F=командное_ключевое_слово в командах, где это требуется
В последние годы появилась возможность создания подписных листов на основе UNIX программы Majordomo. Количество таких списков резко возросло, их создают группы студентов, оздоровительные клубы и т.д. Но свободный доступ к команде subscribe открывает также широкие возможности для злоупотреблений. Так, фирмы и частные лица, занимающиеся рассылкой subscribe должна исполняться либо только
Первичной задачей
В рамках
SUBscribe имя_списка <полное_имя>
Эта команда нужна для включения подписчика в список для рассылки. Вы можете использовать эту команду для изменения имени (но не электронного адреса), под которым вы уже известны в списке. Имя_списка — это наименование списка, на который вы хотите подписаться.
Адрес, куда будет переправлен ваш запрос, вам будет прислан. Для того, чтобы быть исключенным из списка, посылайте команду:
UNSubscribe имя_списка | * <(NETWIDE>
Наличие круглой скобки только слева не является опечаткой. Чтобы ликвидировать подписку по всем спискам (NETWIDE. Эта версия команды рекомендуется при смене вашего электронного адреса или при длительном отпуске. Для получения перечня имеющихся списков в сервере List.
List <option> <F=формат>
Параметр option может принимать следующие значения.
Short
Отображается резюме всех списков, контролируемых
Long
(детально) Пересылает вам файл (называемый node-name LISTS), который содержит исчерпывающие описания всех списков, поддерживаемых сервером.
Global <эталон>
Выдается полный список всех известных почтовых списков
Для получения листинга почтовых списков существует команда REView. Формат команды:
REView имя_списка <(> <option>
Листинг будет вам переслан в виде файла с именем list-name LIST (или list-name node-name). Почтовый список состоит из двух частей: управляющая секция и подписная секция. Управляющая секция содержит параметры списка, которые включают в себя информацию о том, кто решает вопросы включения в список или его пересмотра, а также архивации. Подписная секция содержит e-mail адреса и имена всех членов списка. REView -команда позволяет вам получить листинг любой или обеих этих секций (по умолчанию — обеих) для любого из списков. Следует иметь в виду, что по решению владельца списка командой REView может выдаваться только список членов этого списка. В этом случае вам не будет позволено просматривать список e-mail адресов, если вы не член списка. Члены списка могут ограничить доступ к своему e-mail адресу по команде REView, если они установили опцию CANCEL. имя_списка — имя REView относятся:
Short
Получаемая информация ограничивается управляющей секцией (только параметры списка).
Countries
Выдается перечень членов списка, упорядоченный с учетом гражданства.
LOCal
Если список имеет пару (соединен с другим списком того же имени, обслуживаемым другим сервером), вы получите полный листинг в отклик на команду REView.
При подключении к какому-либо списку, вам будет поставлен в соответствие перечень параметров по умолчанию. Эти параметры могут быть вами изменены для любого из списков, где вы являетесь подписчиком. Команда Query позволяет просмотреть текущие значения параметров (опций) для любого списка. Формат команды:
Query имя_списка | *
Параметр имя_списка представляет собой наименование списка, на который вы подписались. Если вы используете символ "*" вместо имени списка, вы получите информацию о ваших личных параметрах для всех списков, на которые вы подписаны.
Для изменения параметров вашей подписки применяется команда SET. Она имеет формат:
SET имя_списка | * options
После выполнения команды SET сервер пришлет вам подтверждение успешного изменения параметра по электронной почте. Важными опциями команды SET являются:
Mail | DIGests | INDex | NOMail
Эти опции варьируют способ, которым вы получаете сообщения. Mail означает, что вы хотите получать сообщения по электронной почте (значение по умолчанию).
Предусмотрена возможность изменения формата заголовков почтовых сообщений.
SHORThdr | FULLhdr | IETFhdr | DUALhdr
Все почтовые сообщения состоят из секции заголовка и тела сообщения. Заголовок содержит информацию об отправителе, получателе, дате и времени отправки. Перечисленные выше опции команды SET указывают на тип заголовка почтового сообщения, который вы хотите иметь. SHORThdr означает, что
CONCEAL | NOCONCEAL
Указывает на то, хотите вы или нет, чтобы ваше имя и почтовый адрес появлялся в ответ на команду REView, выданную одним из подписчиков списка. По умолчанию работает NONCONCEAL. Обратите внимание, что полный список подписчиков доступен владельцу списка и администратору
Некоторые команды позволяют пользователю манипулировать файлами, которые хранятся в депозитарии
Команда PW позволяет вам добавить, изменить или ликвидировать ваше персональное слово-пароль. Команда имеет следующий формат:
PW options
Слово-пароль блокирует возможность несанкционированного использования вашего электронного адреса. Настоятельно рекомендуется воспользоваться этой возможностью. Запрос на регистрацию слова-пароля может быть воспринят в любое время; аналогично, оно может быть изменено и аннулировано также, когда вы захотите. Слово-пароль может включать в себя от одного до 8 алфавитно-цифровых символов.
В последние годы Интернет-форумы обычно строятся на базе WEB-технологии, но пока эта техника не предоставляет полной функциональности подписных листов, и по этой причине последние продолжают существовать, хотя и не развиваются столь бурно, как это было десять лет назад. Многие коммерческие компании используют технику подписных листов для рассылки рекламных материалов своим клиентам.
Развитие Интернет начиналось как средство общения и удаленного доступа (электронная почта, telnet, FTP). Но постепенно эта сеть превратилась в средство массовой информации, отличающееся тем, что операторы сети и сами могут быть источниками информации, и определяют, в свою очередь, то, какую информацию они хотят получить.
Среди первых поисковых систем были
Первые WWW-системы работали в режиме меню (система
(рис 5.1) Пример дерева гиперсвязейГиперсвязь, помеченная буквой А, может явиться причиной образования цикла при обходе дерева. Исключить такие связи невозможно, так как они носят принципиальный смысловой характер. По этой причине любая автоматизированная программа обхода дерева связей должна учитывать такую возможность и предотвращать циклы обхода.
Задача непроста даже в случае поиска нужного текста в пределах одного достаточно большого по емкости диска, когда вы заранее не знаете или не помните, в каком субкаталоге или в каком файле содержится искомый текст. Для облегчения ручного поиска на серверах FTP в начале каждого субкаталога размещается индексный файл.
Для решения этой задачи в большинстве операционных систем имеются специальные утилиты (например, grep для UNIX). Но даже они требуют достаточно много времени, если, например, дисковое пространство лежит в пределах нескольких десятков гигабайт или более, а каталог весьма разветвлен. В полнотекстных базах данных для ускорения поиска используется индексация по совокупности слов, составляющих текст. Хотя индексация также является весьма времяемкой процедурой, но производить ее, как правило, приходится только один раз. Проблема здесь заключается в том, что объем индексного файла оказывается сравним (а в некоторых случаях превосходит) с исходным индексируемым файлом. Первоначально каждому документу ставился в соответствие индексный файл, в настоящее время индекс готовится для тематической группы документов или для поисковой системы в целом. Такая схема индексации экономит место в памяти и ускоряет поиск. Для документов очень большого размера может использоваться отдельный индекс, а в поисковой системе — иерархический набор индексов. Индексированием называетсяпроцесс перевода с естественного языка на информационно-поисковый. В частности, под индексированием понимается отнесение документа, в зависимости от содержимого, к определенной рубрике некоторой классификации. Индексирование можно свести к проблеме распознавания образов. Классификация определяет разбиение пространства предметных областей на непересекающиеся классы. Каждый класс характеризуется набором признаков и специфических для него терминов (ключевых слов), выражающих основные понятия и отношения между ними.
Слова в любом тексте в информационном отношении весьма неравнозначны. И дело не только в том, что текст содержит много вспомогательных элементов предлогов, местоимений или артиклей (например, в англоязычных текстах).
Для сокращения объема индексных регистров и ускорения самого процесса индексации вводятся так называемые стоп-листы. В эти стоп-листы вносятся слова, которые не несут смысловой нагрузки (например, предлоги или некоторые вводные слова).
Но при использовании стоп-листов необходима определенная осторожность. Например, занеся в стоп-лист, неопределенный артикль английского языка "а", можно заблокировать нахождение ссылки на "витамин А".
Немалое влияние оказывает изменяемость слов из-за склонения или спряжения. Последнее делает необходимым лингвистический разбор текста перед индексацией. Хорошо известно, что смысл слова может меняться в зависимости от контекста, и это также усложняет проблему поиска. Практически все современные информационные системы для создания и обновления индексных файлов используют специальные программные средства.
Существующие поисковые системы успешно работают с HTML-документами, с обычными ASCII-текстами и новостями usenet. Трудности возникают для текстов Winword и даже для текстов Postscript. Связано это с тем, что такие тексты содержат большое количество управляющих символов и слов. Трудно (практически невозможно) осуществлять поиск для текстов, которые представлены в графической форме, здесь следует ждать успеха от широкого внедрения MPEG-7. К сожалению, к числу графических объектов очень часто относятся и математические формулы, которые в HTML имеют формат рисунков (это уже недостаток самого языка). Так что можно без преувеличения сказать, что в этой крайне важной области, уже имеющей немалые успехи, мы все же находимся лишь в начале пути. Ведь море информации, уже загруженной в Интернет, требует эффективных средств навигации. От того, что информации в сети много, мало толку, если мы не можем быстро найти то, что нужно. И в этом, я полагаю, убедились многие читатели, получив на свой запрос список из нескольких тысяч документов. Практически это эквивалентно списку нулевой длины, так как заказчик в обоих случая не получает того, что хотел.
Встроенная в язык HTML метка <meta> создана для предоставления информации о содержании документа для <meta http-equiv=response content=description name=description URL=url>. Параметр http-equiv=response ставит в соответствие элементу заголовок HTTP ответа. Значение параметра http-equiv интерпретируется приложением, обрабатывающим HTML документ. Значение параметра content определяется значением, содержащимся в http-equiv.
Современная поисковая система содержит в себе несколько подсистем.
Следует иметь в виду, что работа web-агентов и системы поиска напрямую не связана друг с другом. WEB-агенты (роботы) работают постоянно, вне зависимости от поступающих запросов. Их задача — выявление новых информационных серверов, новых документов или новых версий уже существующих документов. Под документом здесь подразумевается HTML-, текстовый или nntp-документ. WEB-агенты имеют некоторый базовый список зарегистрированных серверов, с которых начинается просмотр. Этот список постоянно расширяется за счет анализа гиперссылок. При просмотре документов очередного сервера выявляются URL и по ним производится дополнительный поиск. Таким образом, WEB-агенты осуществляют обход дерева гиперссылок. Каждый новый или обновленный документ передается системе обработки. Роботы могут в качестве побочного продукта выявлять разорванные гиперсвязи, способствовать построению зеркальных серверов.
Обычно работа роботов приветствуется, ведь благодаря им сервер может обрести новых клиентов, ради которых он и создавался. Но при определенных обстоятельствах может возникнуть желание ограничить неконтролируемый доступ роботов к серверам узла. Одной из причин может быть постоянное обновление информации каких-то серверов, другой причиной может стать то, что для доставки документов используются скрипты CGI. Динамические вариации документа могут привести к бесконечному разрастанию индекса. Для
Когда "воспитанный" робот заходит в ЭВМ, он проверяет наличие в корневом каталоге файла
# robots.txt for http://store.in.ru user-agent: * # * соответствует любому имени робота disallow: /cgi-bin/ # не допускает робот в каталог cgi-bin disallow: /tmp/ # не следует индексировать временные файлы disallow: /private/ # не следует заходить в частные каталоги
Файл содержит обычный текст, который легко редактировать, после символа # следуют комментарии. Допускается две директивы. user-agent: — определяет имя робота, к которому обращены следующие далее инструкции; если не имеется в виду какой-то конкретный робот и инструкции должны выполняться всеми роботами, в поле параметра записывается символ *.
Автор исходного текста может заметно помочь поисковой системе, умело выбрав заголовок и подзаголовок, профессионально пользуясь терминологией и перечислив ключевые слова в подзаголовках. Исследования показали, что автор (а иногда и просто посторонний эксперт) справляется с этой задачей быстрее и лучше, чем вычислительная машина. Но такое пожелание вряд ли станет руководством к действию для всех без исключения авторов. Ведь многие из них, давая своему тексту образный заголовок, рассчитывают (и не без успеха) привлечь внимание читателей. Но машинные системы поиска не воспринимают (во всяком случае, пока) образного языка. Например, в одном лабораторном проекте, который был разработан для лексического разбора выражений, состоящих из существительных с определяющим прилагательным, и по своей теме связанных с компьютерной тематикой, система была не способна определить во фразе "иерархическая компьютерная архитектура" то, что прилагательное "иерархическая" относится к слову "архитектура", а не к "компьютерная" (Vickery Vickery 1992; здесь подразумевается английский текст, где часто трудно отличить прилагательное от существительного). То есть, система была не способна отличать образное использование слова в выражении от его буквального значения.
В свою очередь, специалисты, занятые в области поисковых и информационных систем, способны заметно облегчить работу авторам, снабдив их необходимыми современными тезаурусами, где перечисляются нормативные значения базовых терминов в той или иной научно-технической области, а также устойчивых словосочетаний. Параллельно могут быть решены проблемы синонимов.
В настоящее время, несмотря на впечатляющий прогресс в области вычислительной техники, степень соответствия документа определенным критериям запроса надежнее всего может определить человек. Но темп появления электронных документов в сети достигает ошеломляющего уровня (частично это связано с преобразованием в электронную форму старых документов и книг методом сканирования). Написание рефератов для последующего их использования поисковыми системами — достаточно изнурительное занятие, требующее к тому же весьма высокой профессиональной подготовки. Именно по этой причине уже в течение некоторого времени предпринимаются попытки перепоручить этот процесс ЭВМ.
Для этого нужно выработать критерии оценки важности отдельных слов и фраз, составляющих текст. Оценку значимости предложений выработал Г.Лун. Он предложил оценивать предложения текста в соответствии с параметром:
$$V_{пр} = \frac{N_{зс}^2}{N_с}$$где Vпр — значимость предложения; Nзс — число значимых слов в предложении; а Nc — полное число слов в предложении. Используя этот критерий, из любого документа можно отобрать некоторое число предложений. Понятно, что они не будут составлять членораздельного текста. Нужно учитывать также, что "значимые слова" должны браться из тематического тезауруса или отбираться экспертом. По этой причине методика может лишь помочь человеку, а не заменить его (во всяком случае, на современном этапе развития вычислительной техники).
Автоматическая система выявления ключевых слов обычно использует статистический частотный анализ (методика В. Пурто). Пусть f — частота, с которой встречаются различные слова в тексте, а u — относительное значение полезности (важности).
Тогда зависимость f(u) апроксимируется формулой $$f(u)=C\frac1u$$, то есть произведение частоты встречи слов и их полезности является константой. В теории автоматического анализа документов данная гипотеза используется для вывода следствия о существовании двух пороговых значений частот. Слова с частотой менее нижнего порога считаются слишком редкими, а с частотой, превосходящей верхний порог, — общими, не несущими смысловой нагрузки. Слова с частотой, находящейся посередине между данными порогами, в наибольшей степени характеризуют содержимое данного конкретного документа [Г. Лун; 2]. К сожалению, выбор порогов — процедура достаточно субъективная. Ключевые слова, выявляемые программно, ранжируются согласно частоте их использования. Замечено, что определенное значение имеет не только частота применения слова в конкретном документе, но и число документов, в которых это слово встречается.
В работах Спарка Джонса экспериментально показано, что если N — число документов и n — число документов, в которых встречается данный индексный термин (ключевое слово), то вычисление его веса по формуле:
приводит к более эффективным результатам поиска, чем вообще без использования оценки значимости индексного термина.
Одним из известных путей облегчения процедуры поиска является группирование документов по определенной, достаточно узкой тематике в кластеры. В этом случае запрос с ключевым словом, фигурирующем в заголовке кластера, приведет к тому, что все документы кластера будут включены в список найденных. Кластерный метод наряду с очевидными преимуществами (прежде всего заметное ускорение поиска) имеет столь же явные недостатки. Документы, сгруппированные по одному признаку, могут быть случайно включены в перечень документов, отвечающих запросу, по той причине, что одно из ключевых слов кластера соответствует запросу. В результате в перечне найденных документов вы можете с удивлением обнаружить тексты, не имеющие никакого отношения к интересующей вас теме.
Некоторые поисковые системы предоставляют возможность поиска документов, где определенные ключевые слова находятся на определенном расстоянии друг от друга (
Наиболее эффективным инструментом при поиске можно считать возможность использования в запросе булевых логических операторов AND, OR и NOT. Объединение ключевых слов с помощью логических операторов может сузить или расширить зону поиска.
Проблема соответствия ( релевантности ) документа определенному запросу совсем не проста.
Индексные файлы, содержащие информацию о WEB-сайтах, занимают около 200 Гигабайт дискового пространства (данные шестилетней давности), поиск по содержимому которых производится за время, меньшее одной секунды (на самом деле, реальный поиск осуществялется в объеме, более чем в десять раз меньшем).
Пример широко известной несколько лет назад поисковой системы alta vista, где задействовано большое число суперЭВМ, показывает, что дальнейшее движение по такому пути вряд ли можно считать разумным, хотя прогресс в вычислительной технике может и опровергнуть это утверждение. Тем не менее, даже в случае фантастических достижений в области создания еще более мощных ЭВМ, можно утверждать, что распределенные поисковые системы могут оказаться эффективнее. Во-первых, местный администратор быстрее может найти общий язык с авторами текстов, которые могут точнее выбрать набор ключевых слов. Во-вторых, распределенная система способна распараллелить обработку одного и того же информационного запроса. Распределенная система памяти и процессоров может, в конце концов, стать более адекватной потокам запросов к информации, содержащейся на том или ином сервере. Способствовать этому может также создание тематических серверов поиска, где концентрируется информация по относительно узкой области знаний. Для таких серверов возможен отбор документов экспертами, они же могут определить списки ключевых слов для многих документов. Здесь возможна автоматическая предварительная процедура фильтрации документов по наличию определенного набора ключевых слов. Способствует этому и существование тематических журналов (в том числе электронных), где сконцентрированы статьи по определенной тематике.
В случаях, когда поисковая система выдает заказчику большой список документов, отвечающих критериям его запроса, бывает важно, чтобы они были упорядочены согласно их степени соответствия (наличие ключевых слов в заголовке, большая частота использования ключевых слов в тексте документа и т.д.). Но простые критерии здесь не всегда срабатывают: так, объемный документ имеет больше шансов попасть в список результата поиска, поскольку в нем много слов и с большой вероятностью там встречается ключевое слово. По этому критерию Британская энциклопедия должна попасть в результирующий список любого запроса. Для компенсации искажений, вносимых длиной документов, используется нормализация весов индексных терминов.
Нормализация представляет собой способ уменьшения абсолютного значения веса индексных терминов, обнаруженных в документе. Одним из наиболее распространенных методов, решающих данную проблему, является косинусная нормализация. При использовании этого метода нормализации вес каждого индексного термина делится на Евклидову длину вектора оцениваемого документа. Евклидова длина вектора определяется формулой:
$$L=\sqrt{w_1^2+w_2^2+...+w_n^2},$$
где wi = tf x idf
– вес i -того термина в документе, tf (IDF (Inverted Document Frequency) — величина, обратная частоте, с которой данный термин встречается во всей совокупности документов. Окончательная формула для вычисления веса термина ( w ) в документе с учетом косинусного фактора нормализации представляется формулой:
Термины, которые отсутствуют в тексте документа, имеют нулевой вес. В списке, возвращаемом на запрос, документы перечисляются в порядке уменьшения данного численного значения.
В работах Букштейна, Свенсона и Хартера было показано, что распределение функциональных слов, в отличие от специфических слов, с хорошей точностью описывается распределением Пуассона. То есть, если отыскивается распределение функционального слова w в некотором множестве документов, тогда вероятность f(n) того, что слово w будет встречено в тексте n раз представляется функцией:
– x варьируется от слова к слову и для конкретного слова должно быть пропорционально длине текста. Слова, распределенные в совокупности документов согласно Пуассону, полезной информации не несут.
Для представления документов используется векторная модель, в которой любой документ характеризуется бинарным вектором x = x1,x2,...,xn, где значения xi = 0 или 1, в зависимости от того, присутствует в тексте i -ый индексный термин или нет. Рассматриваются два взаимно исключающих события:
w1 — документ удовлетворяет запросу; w2 — документ не удовлетворяет запросу
Для определения того, какие документы удовлетворяют запросу, а какие нет, необходимо вычислить условные вероятности P(w1|x) и P(w2|x).
Непосредственно получить значения этих вероятностей нельзя, поэтому необходимо найти другой альтернативный подход для их определения с помощью известных нам величин. По формуле Байеса для
$$P(w_i|x)=\frac{P(x|w_i)P(w_i)}{P(x)},$$
где i=1, 2.
В приведенной формуле P(w1) — первоначальная вероятность соответствия ( i = 1 ) или несоответствия ( i = 2 ) запросу, величина P(x|wi) пропорциональна вероятности соответствия или несоответствия запросу для данного x ; в недискретном случае она представляет собой функцию плотности распределения и обозначается как P(x|wi).
Окончательно:
$$P(x)=\sum_{i=1}^2P(x|w_i)P(w_i),$$
что представляет собой вероятность получения документа x в ответ на запрос, при условии, что он будет ему соответствовать. P(x) выступает в качестве нормализующего фактора (т.е. с его помощью достигается выполнение условия P(w1|x)+P(w2|x)=1 ).
Для определения релевантности документа используется вполне очевидное правило:
Если P(w1|x)>P(w2|x), то документ удовлетворяет запросу [1].
В противном случае считается, что документ не удовлетворяет запросу. При равенстве значений вероятности решение о релевантности документа принимается произвольно.
Правило [1] основано на том, что при его использовании просто минимизируется средняя вероятность ошибки принятия нерелевантного документа за релевантный и наоборот. То есть, для любого документа x вероятность ошибки P(error|x) равна:
Таким образом, для минимизации средней вероятности ошибки необходимо минимизировать функцию $$P(error)=\sum_xP(error|x)P(x)$$
Не углубляясь в теорию вероятностного нахождения релевантных документов, укажем еще одно правило, которое можно использовать вместо [1]:
(l21-l11)P(x|w1)P(w1)>(l12-l22)P(x|w2)P(w2)
В формуле [2] коэффициенты lij стоимостной функции определяют потери, вносимые при ожидании события wi, когда на самом деле произошло событие wj.
Для практической реализации вероятностного поиска вводится упрощающее предположение относительно P(x|wi). Принимается, что значения xi вектора x являются статистически независимыми. Данное утверждение математически представляется в виде:
P(x|wi)=P(x1|wi)P(x2|wi)...P(xn|wi).
Определим переменные: pi=Pr ob(xi=1/w1) и qi=Pr ob(xi=1/w2), представляющие собой вероятность того, что в документе присутствует i -ый индексный термин при условии, что документ является релевантным (нерелевантным). Соответствующая вероятность для отсутствия индексных терминов имеет вид: 1-pi=Pr ob(xi=0/wi)
Вероятностные функции, используемые для подстановки в правило [1], имеют вид:
$$P(x|w_1)=\prod_{i=1}^np_i^{x_i}(1-p_i)^{1-x_i}$$ и
$$P(x|w_2)=\prod_{i=1}^nq_i^{x_i}(1-q_i)^{1-x_i}.$$
Подставляя значения P(x|wi) в [2] и логарифмируя, получаем:
$$g(x)=\sum_{i=1}^n(a_ix_i+b_i(1-x_i))+e=\sum_{i=1}^nc_ix_i+C,$$ где
$$c_i=\log\frac{p_i(1-q_i)}{q_i(1-p_i)}$$ и$$C=\sum_{i=1}^n\log\frac{(1-p_i)}{(1-q_i)}+\log\frac{P(w_1)}{P(w_2)}+\log\frac{l_{21}-l_{11}}{l_{12}-l_{22}}.$$
Функция G(x) представляет собой не что иное, как весовую функцию, в которой коэффициенты Сi есть веса присутствующих в документе индексных терминов. Константа С одинакова для всех документов x, но, конечно, различна для разных запросов и может рассматриваться в качестве порогового значения для поисковой функции. Единственными параметрами, которые могут меняться для данного запроса, являются параметры стоимостной функции, вариации которых позволяют получать в ответе большее или меньшее число документов.
Теперь рассмотрим коэффициенты Сi функции G(x) с использованием следующей терминологии:
| Релевантные документы | Нерелевантные документы | Общее количество документов | |
|---|---|---|---|
| xi=1 | r | n-R | n |
| xi=0 | R-r | N-n-R-r | N-n |
| Всего | R | N-R | N |
N — полное число документов в системе
R — число релевантных документов
r — число релевантных документов, выданных в ответ на запрос
n — полное число документов, выданных в ответ на запрос
Таблица приводит результаты запроса, направленного системе поиска. Представленная таблица должна существовать для каждого из индексных терминов.
Если мы обладаем всей информацией о релевантных и нерелевантных документах в коллекции, то применимы следующие оценки:
$$p_i=\frac{r}{R}$$ и$$q_i=\frac{n-r}{N-R}$$
Тогда функция g(x) может быть переписана в виде
$$g(x)=\sum_{i=1}^nx_i\log\frac{\frac{r}{(R-r)}}{\frac{(n-r)}{(N-n-R+r)}}+C$$
Коэффициент при xi показывает, до какой степени можно провести дискриминацию по i -тому термину в рассматриваемой коллекции документов. В действительности N может рассматриваться как полное количество документов не только во всей коллекции, но и в некотором ее подмножестве.
Все приведенные формулы были выведены при условии, что индексные термины являются статистически независимыми. В общем случае это, конечно, не так. В теории вероятностного поиска моделируется зависимость между различными индексными формулами, в связи с чем вид функции G(x) несколько меняется.
Многие системы поиска информации основаны на словарях и тезаурусах для корректировки запросов и представления индексируемых документов, чтобы увеличить шансы найти необходимый документ. На практике, большинство словарей составляется вручную. Словари создаются с помощью одного из двух основных способов:
В первом случае связываются слова, являющиеся взаимозаменяемыми, то есть, в словарях и тезаурусах они принадлежат одному и тому же классу. Иначе говоря, можно выбрать по одному слову из каждого класса, и совокупность выбранных слов может быть использована для создания контролируемого словаря. Выбирая слова из созданного контролируемого словаря, можно проводить индексацию документов или формировать поисковые запросы.
Во втором случае для создания тезауруса используются семантические связи между словами для построения, например, иерархической структуры связей. Создание такого типа словарей является достаточно сложным и трудоемким процессом.
Однако были предложены способы и для автоматического создания словарей. В то время как созданные вручную словари опираются на семантику (т.е. распознают синонимы, являются более обширными, используют более тонкие взаимосвязи), автоматически созданные тезаурусы, в основном, базируются на синтаксическом и статистическом анализе. Но, так как использование синтаксиса не приводит к серьезному увеличению эффективности работы систем, то значительно большее внимание уделяется статистическим методам.
Основное допущение, используемое для автоматического создания классов ключевых слов, заключается в следующем: если ключевые слова a и b могут быть взаимозаменяемы в том смысле, что мы готовы принять документ, содержащий ключевое слово b вместо ключевого слова a и наоборот, то данное обстоятельство верно из-за того, что слова a и b имеют одинаковое значение или ссылаются на одинаковые темы.
Основываясь на описанном принципе, нетрудно видеть, что создание классификации слов может быть автоматизировано. Можно определить два основных приближения для использования классификации ключевых слов:
Для простейшей поисковой стратегии, использующей только что описанные дескрипторы, независимо от того, являются ли они ключевыми словами или названиями классов, созданных на основе группы ключевых слов, "расширенное" представление документов и запросов с помощью любого из вышеописанных способов может существенно повысить число соответствий между документами и запросами и, следовательно, увеличить значение параметра
В отчетах об экспериментальных работах по использованию автоматической классификации ключевых слов, проведенных ранее Спарком Джонсом, сообщается, что использование автоматической классификации приводит к увеличению эффективности работы системы по сравнению с системой, использующей неклассифицированные ключевые слова.
Работа Минкера и др. не подтвердила выводы Спарка Джонса и фактически показала, что в некоторых случаях применение классификации ключевых слов приводит к существенному ухудшению работы системы в целом. Д. Сальтон в своем отзыве о работе Минкера определил, что целесообразность использования классификации ключевых слов для улучшения эффективности работы поисковых систем еще полностью не определена и является объектом дальнейших экспериментальных исследований. Действительно, при работе в Интернет с поисковыми системами, построенными на классификации ключевых слов, (такими, как lycos и excite ), заметно существенное увеличение документов, не представляющих собой ничего общего с запросом, но, тем не менее, имеющих довольно высокий ранг и, следовательно, по мнению поисковой системы, наиболее точно соответствующих заданному запросу.
Для дальнейшего увеличения эффективности системы используется так называемая кластеризация документов.
Существуют две основные области применения методов классификации в системах поиска и локализации информации. Это — кластеризация (классификация) ключевых слов и кластеризация документов.
Под кластеризацией документов понимается создание таких групп документов, что документы, принадлежащие одной группе, оказываются, в некоторой степени, связанными друг с другом. Другими словами, документы принадлежат одной группе потому, что ожидается, что эти документы будут находиться вместе в результате обработки запроса. Логическая организация документов достигается, в основном, двумя следующими способами.
Первый — путем непосредственной классификации документов, и второй — посредством промежуточного вычисления некоторой величины соответствия между различными документами.
Было теоретически доказано, что первый метод является очень сложным для практической реализации, так что любые экспериментальные результаты не могут считаться достаточно надежными. Второй способ классификации заслуживает подробного внимания и, по сути, может считаться единственным реальным подходом к решению проблемы.
На практике почти невозможно сопоставить каждый из документов каждому из запросов из-за слишком больших затрат машинного времени на проведение таких операций. Было предложено много различных способов для уменьшения количества необходимых для выполнения запроса операций сравнения. Наиболее многообещающей была идея использовать группы взаимосвязанных документов, применяя процедуры автоматического определения соответствия документов. Проводя сравнения запроса всего лишь с одним документом, являющимся представителем группы (заранее определенным), и таким образом определяя группу документов, в которой и происходит дальнейший поиск, мы существенно уменьшаем затрачиваемое на обработку запроса машинное время.
Реальный прорыв в совершенствовании систем поиска может дать создание программ, способных осуществлять анализ контекста. Этот анализ можно выполнять автоматически или в диалоговом режиме (клиенту задаются вопросы, которые позволяют уточнить контекст запроса).
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.