Лекция 1. Мировоззрение. Исторические типы мировоззрения.

Оглавление

Технологии поиска информации

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

Разработала доцент кафедры ИС

Абасова Н.И.

Иркутск 2012

Введение.. 2

1. Основные принципы технологии поиска информации.. 3

1.1 Понятия и определения.. 3

1.2 Информационная потребность пользователя.. 4

1.3 Релевантность. 6

1.4 Общая схема процесса поиска.. 8

2. Представление информации в ИПС.. 10

2.1. Индексирование документов.. 10

2.2. Векторная модель текста.. 11

2.3. Статистический анализ текстов. Закон Ципфа.. 12

2.4. Анализ информационных массивов.. 16

2.4.1. Понятие относительной частоты.. 16

2.4.2 Распределение частоты встречаемости терминов.. 17

2.4.3 Определение весов терминов.. 19

2.4.4 Частотная модель. 20

2.4.5 Вероятностная модель. 21

2.4.6 Латентно-семантический анализ. 22

2.5 Хранение индексированных документов.. 23

3 Модели поиска информации.. 26

3.1 Булева модель поиска.. 27

3.2 Функции подобия "документ-запрос". 30

3.2.1 Алгоритм расширенного булевого поиска.. 31

3.2.2 Алгоритм наибольшего цитирования.. 32

3.2.3 Векторный алгоритм поиска.. 33

3.2.4 Расширенный векторный алгоритм поиска.. 34

4. Классификация документов.. 34

4.1. Основные свойства классификации.. 36

4.2 Формирование рубрик.. 38

5 Эффективность поисковых систем.. 40

5.1 Критерии эффективности.. 40

5.2. Полнота и точность поиска.. 42

5.3. Недостатки основных характеристик.. 45

6 Современные информационно-поисковые системы.. 47

6.1. Словарные информационно-поисковые системы.. 48

6.2 Классификационные информационно-поисковые системы.. 51

6.3. Метапоисковые системы.. 54

Заключение.. 56

Список рекомендуемой литературы.. 58

Введение

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

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

В ХХ веке развитие информационных технологий повлияло на все сферы человеческой жизни. Не стал исключением и информационный поиск. В 60 и 70е годы для ускорения процессов каталогизации и поиска появились первые автоматизированные информационно-поисковые системы (ИПС). Они применялись в каталогах и информационных отделах крупных библиотек. Тогда и начались серьезные исследования теории и практики информационного поиска и построения ИПС (английское обозначение информационно-поисковых систем – information storage and retrieval systems, information retrieval systems).

Говоря об ИПС, следует разделять понятия «поиск информации» и «поиск данных». Поиск информации – это более широкое понятие, допускающее более мягкие критерии соответствия искомой информации потребности пользователя. В отличие от систем поиска данных, которые имеют дело со строго формализованными данными и запросами, ИПС работают с информационными объектами разной (чаще всего небольшой) степени формализованности, в основном с текстами на естественном языке. Точность работы ИПС определяется релевантностью найденных документов, четкого однозначного критерия которой не существует

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

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

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

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

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

Современные теоретические и практические исследования информационного поиска сконцентрированы вокруг нескольких крупных международных конференций. К ним относятся серия конференций TREC (Text Retrieval Conference), проводимая институтом NIST (National Institute for Standards and Technology) США, конференции SIGIR (Special Interest Group on Information Retrieval), организованные международной группой исследователей и разработчиков технологий информационного поиска ACM (Association of Computing Machinery), а также конференция, которая занимается различными проблемами, связанными с Интернет – WWW Conference. В России по вопросам информационного поиска ежегодно проводится конференция «Электронные библиотеки (RCDL)».

 

1. Основные принципы технологии поиска информации

1.1 Понятия и определения

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

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

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

С понятием документа тесно связаны метаданные и суррогаты. Метаданные (метаинформация) – это структурированная информация о документе, например, библиографические сведения, информация о качестве документа, отзывы других пользователей. Под суррогатом понимают представление документа в виде заголовка, имени автора, аннотации, ключевых слов и т. д.

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

На рис. 1 представлена общая схема работы информационно-поисковой системы.

Рис. 1. Информационно-поисковые системы

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

1.2 Информационная потребность пользователя

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

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

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

Выделяют четыре этапа представления информационной потребности:

−реальная информационная потребность – это неосознанная истинная информационная потребность пользователя (потребность в некоторой новой информации при решении стоящей перед пользователем задачи);

−осознанная информационная потребность – появляется после осознания пользователем стоящей перед ним проблемы (осознанная потребность отличается от реальной, более того, пользователь может понимать имеющуюся проблему неправильно);

−выраженная информационная потребность – результат описания осознанной информационной потребности с помощью естественного языка;

−формализованная информационная потребность – это результат представления выраженной потребности средствами формального поискового языка ИПС.

На рис. 2 показана эволюция представлений информационной потребности. По мере переходов от одного представления к другому отличие от первоначальной реальной потребности увеличивается.

Информационная потребность, сформулированная на информационно-поисковом языке, называется запросом.

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

Релевантность – это фундаментальное понятие теории информационного поиска. Тем не менее, оно не является специфичным для информационно-поисковых систем, и изучается многими направлениями науки: философией, психологией, теорией искусственного интеллекта, теорией обработки естественных языков и т. д.

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

 

Рис.2. Информационные потребности.

 

1.3 Релевантность

Наиболее часто используются следующие виды релевантности:

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

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

3.Ситуационная релевантность – определяет полезность информационного ресурса для задачи, решаемой пользователем, с точки зрения временных затрат, способа взаимодействия пользователя с системой и т. п.

4.Системная (алгоритмическая) релевантность – характеризует степень близости между формализованной информационной потребностью (запросом) и найденным поисковой системой документом.

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

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

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

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

Релевантность не является статичной величиной и может со временем меняться. Например, знания пользователя могут измениться после прочтения найденного документа, что в свою очередь может привести к составлению нового запроса, то есть к изменению формализованной информационной потребности. Это иллюстрирует интерактивную природу информационного поиска.

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

Нерелевантные документы, которые сравниваются с релевантными, иногда называются шумом, по аналогии с теорией передачи информации К. Шеннона. Релевантные документы в таком случае можно называть сигналом, а эффективность поиска оценивать по соотношению "сигнал - шум".

Слишком большой шум затрудняет выделение пертинентных документов из множества найденных, а слишком малый не даёт уверенности в достаточной полноте поиска. Практика показывает, что пользователь, который ищет информацию, полагает число найденных документов удовлетворительным, когда количество непертинентных документов лежит в интервале 10–30% от общего числа найденных.

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

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

1.4 Общая схема процесса поиска

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

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

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

Независимо от типа поисковой системы, все операции информационного поиска можно разбить на четыре группы:

−информационный анализ,

−хранение информации,

−поисковые операции,

−выдача информации.

Общая схема процесса поиска в информационно-поисковой системе представлена на рис. 3.

Рис.3. Процесс поиска документа

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

Наряду с отбором из документов определенных терминов существуют и другие способы их описания. Они подробно рассматриваются в следующих разделах. Здесь же важно отметить, что основа любого описания документа – это термины, входящие в его состав.

 

2. Представление информации в ИПС

2.1. Индексирование документов

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

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

Любой метод индексирования основан на текстах исходных документов, или же на определенных фрагментах этих текстов (заглавия, рефераты и др.).

Обычный процесс индексирования состоит из следующих операций:

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

−приписывание этим терминам некоторого веса, который отражает предполагаемую важность терминов.

−отнесение каждого термина к некоторому типу (например, к классу действий, свойств или объектов);

−определение отношений (синонимических, иерархических, ассоциативных и т. д.) между терминами.

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

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

Тем не менее, современные способы индексирования не ограничиваются анализом частотных параметров текста, предоставляя возможность весьма подробного описания документов. Коэффициенты значимости терминов определяются с учетом положения термина внутри документа (например, в заголовке) и взаимного расположения терминов в тексте.

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

2.2. Векторная модель текста

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

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

Словарь – это упорядоченное множество терминов. Мощность словаря обозначается как D.

Поисковый образ документа – это вектор размерности D. Самый простой поисковый образ документа – двоичный вектор. Если термин входит в документ, то в соответствующем разряде этого двоичного вектора проставляется 1, в противном же случае – 0. Более сложные поисковые образы документов связаны с понятием относительного веса терминов или частоты встречаемости терминов .

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

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

Матрица информационного массива изображена на рис. 4, где W_ij – вес термина t_j в документе d_i.

Рис. 4. Матрица "термин-документ" информационного массива

 

Процедура обращения к информационно-поисковой системе может быть определена следующим образом: L x q = R.

Здесь q – вектор запроса, R – вектор отклика системы на запрос.

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

2.3. Статистический анализ текстов. Закон Ципфа

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

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

Наиболее известный гиперболический закон, относящийся к статистической обработке текстов, сформулирован Дж. Ципфом. Он касается распределения слов в достаточно больших выборках текста и используется для решения задачи выделения ключевых слов (терминов) произвольного документа. Основываясь на общем "принципе наименьшего усилия", Дж. Ципф вывел универсальный закон, который применим ко всем созданным человеком текстам [, , ].

Рассмотрим некоторый текст, количество слов в котором обозначим как T , а число вхождений каждого слова t_i в этот текст обозначим как n_i . Частота появления слова t_i в таком случае будет определяться формулой:

(TF)_i = n_i/T.

Если расположить слова текста в порядке убывания частоты их появления, начиная с наиболее часто встречающихся, то произведение частоты слова (TF)_Iна порядковый номер частоты будет постоянным для любого данного слова t_i:

(TF)_i* r_i = C, (1)

где C – некоторая константа, r_i – порядковый номер (ранг) частоты слова.

Наиболее часто встречающиеся слова будут иметь ранг 1, следующие за ними – 2 и т. д. Если несколько слов имеет одинаковую частоту, то ранг присваивается только одному значению из каждой группы.

Выражение (1) описывает функцию вида y = k \ x и её график – гипербола, или прямая в логарифмических координатах (рис. 5).

Рис. 5. Закон Ципфа.

Эксперименты показывают, что частота (TF)_i и количество слов n_i , входящих в текст с этой частотой (другими словами, количество слов, имеющих одинаковый ранг частоты), также связаны между собой. Обозначим это количество как . Форма кривой зависимости сохраняет свои параметры для всех текстов в пределах одного языка. Вид такой зависимости представлен на рис.6 .

Рис.6. Зависимость числа слов от каждого ранга от частоты их встречаемости.

Вероятность P_i встретить произвольно выбранное слово t_i , очевидно, будет равна частоте встречаемости этого слова в тексте:

Таким образом, согласно закону Ципфа, если самое распространенное слово встречается в тексте, например 50 раз, то следующее по частоте слово с высокой долей вероятности встретится 25 раз.

Связь, задаваемая зависимостью (2.2), описывает реальные данные приближенно. Более точное совпадение с экспериментом дает несколько измененное уравнение

(2)

Здесь C и s – параметры распределения, а B – малая константа, называемая поправкой Мандельброта. Она улучшает совпадение для общеупотребительных слов, имеющих низкий ранг, а параметр s – для слов, имеющих высокий ранг. Значение константы C в разных языках различно, но внутри одной языковой группы оно остается неизменным вне зависимости от анализируемого текста.

Выражение (2) называется каноническим законом Ципфа . Оно используется для составления поискового образа документа, то есть для извлечения из текста документа слов, наиболее адекватно отражающих его смысл.

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

Рис.7. Выделение ключевых слов по закону Ципфа.

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

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

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

Число служебных слов в отрицательном словаре составляет обычно несколько сотен, в зависимости от системы.

2.4. Анализ информационных массивов

2.4.1. Понятие относительной частоты

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

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

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

Определим документную частоту термина t_i как число документов массива, в которых встречается этот термин, и обозначим ее (DF)_i.

Тогда взвешивающую функцию, обратную документной частоте (IDF – Inversed Document Frequency – обратная документная частота), можно определить следующим образом:

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

2. Несколько иной подход применяется при использовании методов оценки различительной силы термина. Здесь хорошим для индексации считается такой термин, который делает документы максимально непохожими друг на друга. Тем самым обеспечивается максимальное удаление одного документа от другого в пространстве индексирования. Плохим считается такой термин, который делает документы более похожими друг на друга, вследствие чего различить их становится труднее.

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

Значимость термина t_i измеряется его различительной силой (DF)_i. Она определяется как разность между средним попарным подобием документов, когда термин t_i отсутствует в векторах документов массива, и средним попарным подобием, когда термин t_i присутствует.

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

2.4.2 Распределение частоты встречаемости терминов

Практика показывает, что хорошие, средние и плохие индексационные термины можно характеризовать по распределению их документной частоты (DF)_iи распределению частоты встречаемости F_i

Суммарная частота встречаемости термина t_i в массиве документов определяется следующей формулой:

1. Лучшими для индексации терминами с наивысшими значениями различительной силы являются термины со средними значениями суммарной частоты встречаемости F_iи документной частотой, составляющей менее половины его частоты как термина (суммарной частоты в массиве).

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

3. Худшими терминами, имеющими отрицательные значения различительной силы, являются те термины, которые имеют высокую документную частоту (порядка объема всего массива документов) и суммарную частоту термина большую, чем число документов в массиве.

Рис.8 Характеристика терминов по распределению документной частоты

Рис. 8 иллюстрирует вышеописанное разделение терминов. Если расположить термины в порядке увеличения документной частоты (DF)_i, то индексационные термины должны, насколько это возможно, попадать в средний интервал значений.

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

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

Термины с распределениями (рис. 9 б) повышают точность, но резко снижают полноту поиска, а с распределениями (рис. Рис. 9 в) – наоборот, увеличивают полноту, но уменьшают точность.

Наконец, равномерное распределение частоты (рис. 9 г) свойственно общеупотребительным терминам, которые не обеспечивают ни надлежащей точности поиска, ни его полноты.

Рис.9. Распределение частот терминов в документе

2.4.3 Определение весов терминов

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

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

Чем больше вес термина в документе, тем более релевантным оказывается этот документ, и тем более высокую позицию этот документ занимает в списке результатов поиска. Особенно актуальным такое упорядочение представляется для крупных информационных массивов.

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

Наиболее простая и самая распространенная модель поиска – булева модель – использует двоичную систему взвешивания терминов. Этот метод реализуется на стадии отбора индексационных терминов, и заключается в том, что терминам, вошедшим в поисковый образ, приписывается единичный вес, а остальным терминам – нулевой вес. Таким образом, все термины из поискового образа документа считаются равнозначными .

Недостатки булевой модели широко известны:

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

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

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

1. частотная модель

2. вероятностная модель

3. латентно-семантический анализ.

Остановимся на них более подробно.

2.4.4 Частотная модель

Частотная модель взвешивания терминов тесно связана с частотным методом индексирования. Одна из наиболее известных весовых функций записывается следующим образом :

Здесь W_i– вес, приписываемый термину термина t_i,

(TF)_i – частота термина в документе,

(IDF)_i – обратная документная частота.

Также на практике широко применяется весовая функция

где (TF)_max – максимальная частота термина в k -ом документе, то есть частота термина, который встречается в документе чаще всего. Весовой коэффициент W_iотражает значимость термина t_i в k -ом документе.

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

где (DV)_i– значение различительной силы термина t_i/

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

2.4.5 Вероятностная модель

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

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

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

Обозначим вероятность такого события как

гдеw₁ – событие, которое состоит в том, что документ d является релевантным по отношению к запросу q . Аналогично, предположим, что – вероятность того, что документ d окажется нерелевантным.

Для определения вероятности воспользуемся теоремой Байеса:

Здесь P(w₁₎ – вероятность того, что случайно выбранный документ является релевантным, P(d) – вероятность того, что из всего множества документов для рассмотрения выбран документ P(d | w₁) – вероятность того, что документ d выбран из множества релевантных документов.

2.4.6 Латентно-семантический анализ

Основное предназначение взвешивания терминов, как отмечалось выше, заключается в определении того, насколько полно они отражают содержание документа. Как показывает практика, частотные методы оценки весов имеют ряд недостатков. Следствием этого является получение в результате поиска нерелевантных и отсутствие истинно релевантных документов.

Во-первых, описанные методы не учитывают тот факт, что частоты встречаемости различных терминов зависят друг от друга. Термины не появляются в документе независимо от остальных терминов, они могут быть, например, объединены в словосочетания, устоявшиеся обороты и т.п.

Другой проблемой является синонимия и полисемия (многозначность) . Под синонимией понимается тот факт, что любое явление или предмет могут быть выражены различными способами. В зависимости от контекста, знаний человека, манеры письма одни и те же сведения описываются разными терминами (синонимами). Например, синонимы «дисплей» и «монитор» определяют один и тот же предмет.

Полисемия, напротив, заключается в том, что большинство слов в языке имеет несколько значений. Один и тот же термин может обозначать абсолютно разные понятия. Соответственно, наличие того или иного термина в некотором документе не означает того, что документ является релевантным запросу, в котором содержится Описанные проблемы решает латентное семантическое индексирование (ЛСИ) .

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

Анализ такой структуры (ЛСИ) позволяет описать каждый документ

- с точки зрения наличия или отсутствия каких-либо терминов,

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

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

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

Математически латентно-семантическое индексирование реализуется с помощью одного из методов линейной алгебры – сингулярного разложения матрицы [,]. Современные алгоритмы используют также аппарат теории вероятностей (вероятностное латентное семантическое индексирование) .

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

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

Главное достоинство межязыкового ЛСИ – отсутствие необходимости перевода (ручного или машинного) запроса на другой язык. Это особенно актуально для поиска в сети Интернет, когда запросы являются неспециализированными, и их адекватный перевод вызывает значительные трудности [, , ].

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

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

2.5 Хранение индексированных документов

Организация хранения массива поисковых образов документов – одна из критических частей технологии поиска информации.

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

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

Часть данных необходима для облегчения работы пользователя с результатами поиска (заголовки и аннотации документов и др.). Обычно информация о терминах и документах, которая находится в базах данных ИПС, может быть использована одновременно для нескольких алгоритмов поиска.

Рассмотрим общую структуру базы данных поисковых образов интернет-документов (гипертекстовых страниц) [, , , ].

База данных (рис. Рис. 10) состоит из таблицы адресов страниц, таблицы ключевых слов, таблицы заголовков страниц, таблицы с датами изменения страниц, таблицы гиперссылок, а также двух таблиц-списков – прямого и инвертированного.

Таблица адресов страниц содержит уникальные идентификаторы (pageID) и адреса страниц (URL).

Таблица ключевых слов содержит термины и их уникальные идентификаторы (kwdID).

Таблица с заголовками страниц ставит в соответствие каждому идентификатору страниц pageID название этой страницы.

Таблица с датами изменения страниц фиксирует для каждой страницы pageID дату последнего посещения этой страницы индексационным роботом (т. е. дату индексации этой страницы). Она используется при обновлении базы данных: если содержание страницы изменилось со времени последней индексации, ее следует проиндексировать заново. В этой таблице также хранятся даты модификации стра ниц. Эта информация используется при ранжировании результатов поиска не по релевантности, а по дате.

 

Рис.10. Структура базы данных поисковых образов

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

Таблицы, содержащие информацию о ссылках, необходимы по двум причинам:

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

Интернет;

- документы, объединенные гиперссылками, содержат также и много одинаковых индексационных терминов.

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

Таблица, называемая прямым списком, содержит список ключевых слов (kwdID) для каждой страницы (pageID). Эта таблица используется для вычисления частоты встречаемости термина в документе (TF)_i и определения весов терминов, а также в алгоритмах обратной связи по релевантности и в функциях поддержки и актуализации массива индексированных документов.

Таблица – инвертированный список содержит для каждого ключевого слова (kwdID) список страниц (pageID), в которых это слово встречается. Кроме того, здесь указывается позиция (порядковый номер) данного термина в странице. Эта информация используется в тех запросах, где важным является взаимное расположение слов (контекстный поиск). Например, когда идет поиск по запросу «операционная система», важно получить не просто все документы, в тексте которых присутствуют термины «операционная» и «система», а только те, в которых эти два слова расположены друг за другом, т. е. объединены во фразу.

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

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

Для ускорения доступа к базе данных поисковых образов веб-документов применяются механизмы индексации и хеширования.

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

Хеширование – алгоритм, в ходе выполнения которого для сохраняемых объектов генерируется специальный указатель (хеш-код), используемый впоследствии для индексации массива указателей.

Часто для хранения и обработки писаний документов используются системы управления базами данных (СУБД). В таких случаях поиск по базе данных осуществляется с использованием встроенных средств СУБД.

3 Модели поиска информации

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

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

Любая модель поиска тесно связана с информационно-поисковым языком. Информационно-поисковый язык (ИПЯ) – это специальный язык для формирования запросов к ИПС. Необходимость создания ИПЯ вызвана трудностями интерпретации естественного языка в компьютерной системе. Однако синтаксис информационно-поисковых языков обычно довольно прост и внешне они часто похожи на естественные.

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

Рассмотрим основные модели поиска информации, применяемые в ИПС.

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

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

Поисковые образы запросов связывают термины с помощью булевых операторов ("И" – "AND", "ИЛИ" – "OR", "И НЕ" – "AND NOT"). Эти операции производятся над множествами документов, содержащих тот или иной термин, определенный запросом.

Для обозначения объединения множеств ("ИЛИ" в запросе) применяется символ , пересечения множеств ("И" в запросе) – , разности множеств ("И НЕ" в запросе) – \ .

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

Одно из них содержит первый термин запроса, а другое – второй. Затем определяется общая часть (пересечение) этих подмножеств, то есть те документы, в состав которых одновременно входят и первый, и второй термины из запроса.

Рассмотрим, например, такой запрос:

(((Microsoft and Word) or (Microsoft and Excel)) and Macintosh) and not Windows

В данном случае выражение на ИПЯ означает следующее:

нужно найти все документы, которые одновременно содержат либо сочетание "Microsoft Word", либо сочетание "Microsoft Excel", а также содержат слово "Macintosh", но не содержат слово "Windows".

Этот запрос можно разбить на две части:

1. Microsoft and Word and Macintosh and not Windows

2. Microsoft and Excel and Macintosh and not Windows

Выполнение первого запроса происходит в два этапа. Сначала находятся все документы, содержащие термины "Microsoft", "Word" и "Macintosh". Затем из найденных документов отсеиваются те, которые содержат слово "Windows".

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

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

В некоторых поисковых системах вместо булевых операторов язык запросов позволяет использовать различные знаки. Так, знак "+" эквивалентен оператору "И", знак "-" – оператору "И-НЕ" и т. д.

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

Несколько типичных булевых стратегий поиска изображено в табл.1.

Здесьe d c b a , , , , – термины, из которых состоят запросы, аE D C B A , , , , – множества документов, содержащих эти термины (например, A - это множество документов, содержащих термин a , и т. д.).

ИПС, работающие с булевой моделью поиска, имеют ряд недостатков .

1.Обычные булевы запросы затрудняют варьирование глубины поиска с целью выдачи большего или меньшего количества документов в зависимости от требований пользователя. Для получения желаемого уровня эффективности необходимо найти правильную формулировку запроса: не слишком широкую и не слишком узкую.

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

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

3.Еще одним минусом является тот факт, что множество выданных документов не может быть представлено пользователю в ранжированном виде (ранжирование – упорядочение результатов поиска по некоторому критерию соответствия их информационной потребности пользователя), например в порядке уменьшения сходства между документом и запросом. Документ либо полностью соответствует запросу, либо не соответствует совсем. Эта проблема может быть решена с помощью взвешенного булева поиска, при котором производится частичное ранжирование с использованием весов терминов W_i. Результаты поиска располагаются в порядке уменьшения весов совпавших терминов [, , ].

Несмотря на описанные недостатки, булева модель поиска широко применяется в современных ИПС из-за простоты ее реализации.

 

3.2 Функции подобия "документ-запрос"

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

Многие современные ИПС реализуют модели поиска информации, основанные на вычислении мер близости документов и запросов . ИПЯ, используемые в таких моделях, называются языками типа "найти похожее" (языки типа "Like This"). В этих языках необязательно формулировать запросы с помощью булевых операторов.

Для вычисления меры подобия документов и запросов существует более тридцати различных алгоритмов[,].Мы рассмотрим четыре алгоритма :

- расширенного булевого поиска,

- наибольшего цитирования,

- IDF TF × алгоритм,

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

Алгоритмы расширенного булевого поиска и наибольшего цитирования основаны на метаинформации гипертекстовых страниц.

IDF TF × алгоритм использует статистические частотные оценки встречаемости терминов.

Расширенный векторный алгоритм работает как с частотными оценками, так и с гипертекстами.

Введем некоторые обозначения:

Для повышения качества поиска в приведенном выражении вместо единицы можно также использовать вес термина в документе W _{j, i}

IL– англ. Incoming Hyperlink – входящая гиперссылка.

 

3.2.1 Алгоритм расширенного булевого поиска

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

Релевантность документа P_iпо отношению запроса q рассчитывается как:

 

P

Представленный алгоритм расширенного булевого поиска использует модель не только для данного документа, но и для соседних с ним, учитывая частоту появления в них слов запроса. Такое становится возможным в среде гипертекстовых документов. Предполагается, что если два документа связаны гиперссылкой, то между ними должна существовать и некоторая семантическая (смысловая) связь. Практически это выглядит следующим образом. Если документ P_i не содержит термина запроса Q_j , но связан с другими документом P_k, в который этот термин входит, то полагают, что документ P_iсодержит термин Q_j. Однако при этом во время ранжирования документу P_iприписывается меньший вес, чем если бы он на самом деле содержал термин Q_j.

Алгоритм определения релевантности документа P_iи запроса q принимает вид

Здесь c₁ и c₂ – положительные константы, причем c_{1 >} c_2.

3.2.2 Алгоритм наибольшего цитирования

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

Цель данного алгоритма – приписать большие веса тем документам в множестве найденных, которые цитируются (на которые ссылаются другие документы) чаще всего. Аналогичный подход применяется также в ряде других алгоритмов, в частности, в алгоритме PageRank, который используется в информационно-поисковой системе Интернет Google .

3.2.3 Векторный алгоритм поиска

Векторный алгоритм поиска, называемый IDF TF × -алгоритмом, является одним из самых распространенных. Он основан на векторной модели информационного массива, в которой для определения меры близости документов и запросов используется значение косинуса угла между их векторами в многомерном пространстве информационного массива .

Запросы и документы в векторной модели представляют множествами наборов взвешенных терминов. Вектор запроса q в таком случае будет выглядеть так: