Стратегия поиска в автоматизированных информационных системах

Стратегия поиска в автоматизированных информационных системах

КАЗАНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ КУЛЬТУРЫ И ИСКУССТВ

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

Вступительный реферат по теме:

Стратегия поиска в Автоматизированных информационно-поисковых системах

Выполнил:

Султанов Ильнур Ильдусович

Казань, 2004

Содержание

Введение 3

Проблемы поиска информации 5

Поисковые алгоритмы 7

Оценка качества 16

Дополнительные возможности предоставляемые поисковыми машинами 18

Лингвистика 20

Заключение 22

Список литературы 23

Глоссарий: 24

Введение

Проблема поиска и сбора информации - одна из важнейших проблем

информационно поисковых систем. Конечно, нельзя сравнивать в этом

отношении, скажем, средние века, когда поиск информации был проблемой

потому, что этой информации было мало, и требовались усилия только для

того, чтобы найти хоть что-то по более или менее значительному

интересующему вопросу. Проблема поиска информации приобрела новый характер

в 20-м столетии, с началом развития века информационных технологий. Теперь

она заключается не в том, что информации мало и поэтому ее трудно найти, а

в том, что ее теперь наоборот становится все больше и больше, и от этого

найти ответ на интересующий вопрос может оказаться тоже довольно сложной

задачей [2].

Так, сначала появилась возможность пойти в библиотеку и, потратив там

время на выбор нужной книги по каталогу, найти необходимую информацию. Но

каталоги не решают полностью проблем поиска информации даже в рамках одной

библиотеки, так как в каталожную запись входит относительно мало

информации: заголовок, автор, место издания и т.п. Проблема поиска

информации значительно усложняется при использование виртуальных

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

результате применения которой пользователь имеет возможность выполнять

поиск в каталогах сразу нескольких библиотек, чем, на самом деле, еще

больше усложняет себе задачу, но, с другой стороны, увеличивает шансы

решить ее [1].

На современном этапе все информационное пространство, в котором мы

живем, все больше погружается в Интернет. Интернет становится основной

формой существования информации, не отменив традиционных, такие как

журналы, радио, телевидение, телефон, всевозможные справочные службы.

В данной работе объектом исследования является Автоматизированная

информационно поисковая система. Это система где хранится информационный

массив, из которого пользователю выдается нужная информация,

осуществляющаяся либо автоматически, либо вручную.

Предмет исследования включает в себя те свойства, стороны и отношения

объекта исследования, которые необходимо изучить. Предмет обозначает

границы, в пределах которых объект изучается в данном конкретном

исследовании. Предметом исследования является стратегия информационного

поиска.

Цель исследования: Цель исследования ставится, обзор и выявление

поисковых сервисов (возможностей предоставляемые на сегодняшний день),

написание рекомендации к проведению поиска, анализ развития поисковых

систем.

Для выполнения поставленной цели в рамках исследования необходимо

решение следующих задач:

1. аналитический обзор поисковых систем;

2. определение механизма поиска в поисковых системах;

3. создание информационной системы, по АИПС;

4. оценка эффективности созданной системы;

5. разработка рекомендаций к проведению поиска используя информационную

систему.

Проблемы поиска информации

Ключ проблемы заключается в том, что выросло количество пользователей

не обладающие профессиональными навыками при поиске информации на языке

запросов. Естественно с такой проблемой столкнулся не только интернет, но и

электронные библиотеки (ЭБ) и электронные каталоги (ЭК). К таким системам

относятся библиотеки НЭБ-НСН, Интегрум - Техно в России, Лексис-Нексис,

Рейтер на Западе.

Более строгая организация каталогов в библиотеках, полное единство

форматов (или почти полное) внутри одной библиотеки не является решением

проблемы современных поисковых систем. Поиск это искусство. Ясно, что в

области искусства нельзя добиться гарантированного, или массового

результата.

Существует убеждение, что каждое новое поколение программ поиска

совершенней предыдущего. И иная точка зрения, что «все новое - это хорошо

забытое старое». Думаю, что применительно к поисковым системам истина лежит

где-то посередине.

Но что же поменялось в действительности за последние годы? Не алгоритмы

и не структуры данных, не математические модели. Поменялась парадигма

использования систем. Системой поиска стали пользоваться пользователи не

имеющие профессиональные навыки.

Особенно поисковые системы стали востребованы с возникновением

интернета. В процессе эволюции поисковых систем, стали очевидны следующие

изменения. Во-первых, люди не только «думают словами», но и «ищут словами».

В ответе системы они ожидают увидеть слово, набранное в строке запроса.

Второе: «человека ищущего» трудно «переучить искать», так же как трудно

переучить говорить или писать. Научная мысль 60-х – 80-х об итеративном

уточнении запросов, о понимании естественного языка, о поиске по смыслу, о

генерации связного ответа на вопрос, пока не удаётся создать и не

выдерживает критики.

Поисковые алгоритмы

Как и любая программа, поисковая система оперирует со структурами

данных и исполняет алгоритм. Есть четыре класса поисковых алгоритмов. Три

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

документов, при котором создаются вспомогательный файл, сиречь «индекс»,

призванный упростить и ускорить сам поиск. Это алгоритмы инвертированных

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

этап индексирования отсутствует, а поиск происходит при помощи

последовательного просмотра документов. Такой поиск называется прямым.

Прямой поиск

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

|char* strstr(char *big, |ПРЯМОЙ ПОИСК ТЕКСТА. |

|char *little) | |

| | |

Несмотря на кажущуюся простоту, последние 30 лет прямой поиск

интенсивно развивается. Было выдвинуто немалое число идей, сокращающих

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

улучшенные варианты появляются постоянно.

Хотя прямой просмотр всех текстов – довольно медленное занятие, не

следует думать, что алгоритмы прямого поиска не применяются в интернете.

Норвежская поисковая система Fast (www.fastsearch.com) использовала чип,

реализующий логику прямого поиска упрощенных регулярных выражений, и

разместила 256 таких чипов на одной плате. Это позволяло Fast-у обслуживать

довольно большое количество запросов в единицу времени.

Кроме того, есть масса программ, комбинирующих индексный поиск для

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

весьма популярный, в том числе и в Рунете, glimpse.

У прямых алгоритмов есть положительные черты. Например, неограниченные

возможности по приближенному и нечеткому поиску. Ведь любое индексирование

всегда сопряжено с упрощением и нормализацией терминов, а, следовательно, с

потерей информации. Прямой же поиск работает непосредственно по

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

Инвертированный файл

Эта простейшая структура данных. Первая категория людей знает, что это

такое, по «конкордансам» - алфавитно упорядоченным исчерпывающим спискам

слов из одного текста или принадлежащих одному автору (например «Конкорданс

к стихам А. С. Пушкина», «Словарь-конкорданс публицистики Ф. М.

Достоевского»). Вторые имеют дело с той или иной формой инвертированного

списка всякий раз, когда строят или используют «индекс БД по ключевому

полю».

Проиллюстрируем эту структуру при помощи замечательного русского

конкорданса - «Симфонии», выпущенной московской патриархией по тексту

синодального перевода Библии [симфония].

Рис. 1

Перед нами упорядоченный по алфавиту список слов. Для каждого слова

перечислены все «позиции», в которых это слово встретилось. Поисковый

алгоритм состоит в отыскании нужного слова и загрузке в память уже

развернутого списка позиций.

Чтобы сэкономить на дисковом пространстве и ускорить поиск, обычно

прибегают к двум приемам. Во-первых, подробность самой позиции. Чем

подробнее задана такая позиции, например, в случае с «Симофонией» это

«книга+глава+стих», тем больше места потребуется для хранения

инвертированного файла.

В наиподробнейшем варианте в инвертированном файле можно хранить и

номер слова, и смещение в байтах от начала текста, и цвет и размер шрифта,

да много чего еще. Чаще же просто указывают только номер документа, скажем,

книгу Библии, и число употреблений этого слова в нем. Именно такая

упрощенная структура считается основной в классической теории

информационного поиска – Information Retrieval (IR).

Второй (никак не связанный с первым) способ сжатия: упорядочить позиции

для каждого слова по возрастанию адресов и для каждой позиции хранить не

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

список для нашей странички в предположении, что мы запоминаем позицию

вплоть до номера главы:

ЖЕНЩИНА: [Быт.1],[+11],[0],[+2],[+4],[+2],[+4],..

Дополнительно на разностный способ хранения адресов накладывают какой-

нибудь способ упаковки: зачем отводить небольшому целому числу

фиксированное «огромное» количество байт, ведь можно отвести ему почти

столько байт, сколько оно заслуживает. Здесь уместно упомянуть коды Голомба

или встроенную функцию популярного языка Perl: pack(“w”).

В литературе встречается и более тяжелая система упаковочных алгоритмов

самого широкого спектра: арифметический, Хафман, LZW, и т.д. Прогресс в

этой области идет непрерывно. На практике в поисковых системах они

используются редко: выигрыш невелик, а мощности процессора расходуются

неэффективно.

В результате всех описанных ухищрений размер инвертированного файла,

как правило, составляет от 7 до 30 процентов от размера исходного текста, в

зависимости от подробности адресации.

занесены в «Красную книгу»

Неоднократно предлагались другие, отличные от инвертированного и

прямого поиска алгоритмы и структуры данных. Это, прежде всего, суффиксные

деревья, а также сигнатуры.

Первый из них функционировал и в интернете, будучи запатентованным

алгоритмом поисковой ситемы OpenText.

Мне доводилось встречать суффиксные индексы в отечественных поисковых

системах.

Второй - метод сигнатур - представляет собой преобразование документа к

поблочным таблицам хеш-значений его слов - "сигнатуре" и последовательному

просмотру "сигнатур" во время поиска.

Широкого распространения эти два метода не получили.

МАТЕМАТИЧЕСКИЕ МОДЕЛИ

Приблизительно 3 из 5 поисковых систем и модулей функционируют безо

всяких математических моделей. Их разработчики не ставят перед собой задачу

реализовывать абстрактную модель. Принцип здесь: лишь бы программа хоть что-

нибудь находила.

Как только речь заходит о повышении качества поиска, о большом объеме

информации, о потоке пользовательских запросов, кроме эмпирически

проставленных коэффициентов полезным оказывается оперировать каким-нибудь

пусть и несложным теоретическим аппаратом. Модель поиска – это некоторое

упрощение реальности, на основании которого получается формула (сама по

себе никому не нужная), позволяющая программе принять решение: какой

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

коэффициенты приобретают физический смысл и становятся понятней.

Все многообразие моделей традиционного информационного поиска (IR)

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

множеств, расширенная булевская), алгебраические[1][1] (векторная,

обобщенная векторная, латентно-семантическая, нейросетевая) и

вероятностные.

Булевское семейство моделей самое известное, реализующие полнотекстовый

поиск. Есть слово - документ считается найденным, нет – не найденным.

Собственно, классическая булевская модель – это мостик, связывающий теорию

информационного поиска с теорией поиска и манипулирования данными.

Критика булевской модели, вполне справедливая, состоит в ее крайней

жесткости и непригодности для ранжирования. Поэтому еще в 1957 году Joyce и

Needham (Джойс и Нидхэм) предложили учитывать частотные характеристики

слов, чтобы «... операция сравнения была бы отношением расстояния между

векторами...».

Векторная модель и была с успехом реализована в 1968 году отцом-

основателем науки об информационном поиске Джерардом Солтоном (Gerard

Salton)[2][2] в поисковой системе SMART (Salton's Magical Automatic

Retriever of Text). Ранжирование в этой модели основано на естественном

статистическом наблюдении, что чем больше локальная частота термина в

документе (TF) и больше «редкость» (т.е. обратная встречаемость в

документах) термина в коллекции (IDF), тем выше вес данного документа по

отношению к термину. Обозначение IDF ввела Karen Sparck-Jones (Карен Спарк-

Джоунз) в 1972 в статье про различительную силу (term specificity). С этого

момента обозначение TF*IDF широко используется как синоним векторной

модели.

Наконец, в 1977 году Robertson и Sparck-Jones (Робертсон и Спарк-

Джоунз) обосновали и реализовали вероятностную модель (предложенную еще в

1960), также положившую начало целому семейству. Релевантность в этой

модели рассматривается как вероятность того, что данный документ может

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

существующего первоначального набора релевантных документов, выбранных

пользователем или полученных автоматически при каком-нибудь упрощенном

предположении. Вероятность оказаться релевантным для каждого следующего

документа рассчитывается на основании соотношения встречаемости терминов в

релевантном наборе и в остальной, «нерелевантной» части коллекции. Хотя

вероятностные модели обладают некоторым теоретическим преимуществом, ведь

они располагают документы в порядке убывания "вероятности оказаться

релевантным", на практике они так и не получили большого распространения.

Важно заметить, что в каждом из семейств простейшая модель исходит из

предположения о взаимонезависимости слов и обладает условием фильтрации:

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

Продвинутые («альтернативные») модели каждого из семейств не считают слова

запроса взаимонезависимыми, а, кроме того, позволяют находить документы, не

содержащие ни одного слова из запроса.

Поиск «по смыслу»

Способность находить и ранжировать документы, не содержащие слов из

запроса, часто считают признаком искусственного интеллекта или поиска по

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

Для примера опишу лишь одну, самую популярную модель, работающую по

смыслу. В теории информационного поиска данную модель принято называть

латентно-семантически индексированием (иными словами, выявлением скрытых

смыслов). Эта алгебраическая модель основана на сингулярном разложении

прямоугольной матрицы, ассоциирующей слова с документами. Элементом матрицы

является частотная характеристика, отражающая степень связи слова и

документа, например, TF*IDF. Вместо исходной миллионно-размерной матрицы

авторы метода, предложили использовать 50-150 «скрытых смыслов»[3][3],

соответствующих первым главным компонентам ее сингулярного разложения.

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

(остальные приравнять нулю), мы получим ближайшую из всех возможных

аппроксимацию исходной матрицы ранга k (в некотором смысле ее «ближайшую

семантическую интерпретацию ранга k»). Уменьшая ранг, мы отфильтровываем

нерелевантные детали; увеличивая, пытаемся отразить все нюансы структуры

реальных данных.

Операции поиска или нахождения похожих документов резко упрощаются, так

как каждому слову и каждому документу сопоставляется относительно короткий

вектор из k смыслов (строки и столбцы соответствующих матриц). Однако по

причине малой ли осмысленности «смыслов», или по какой иной[4][4], но

использование LSI в лоб для поиска так и не получило распространения. Хотя

во вспомогательных целях (автоматическая фильтрация, классификация,

разделение коллекций, предварительное понижение размерности для других

моделей) этот метод, по-видимому, находит применение.

Оценка качества

Какова бы ни была модель, поисковая система нуждаетсяв «тюнинге» - оценке

качества поиска и настройке параметров. Оценка качества – идея,

фундаментальная для теории поиска. Ибо именно благодаря оценке качества

можно говорить о применимости или не применимости той или иной модели и

даже обсуждать их теоретичеcкие аспекты.

Страницы: 1, 2