Теория поиска информации

Это также означает, что самое популярное слово в английском языке (the) употребляется в 10 раз чаще, чем слово, стоящее на десятом месте, в 100 раз чаще, чем сотое, и в 1000 раз чаще, чем тысячное.

Значение вышеупомянутой постоянной в разных языках различно, но внутри одной языковой группы она остается неизменной. Так, например, для английских текстов постоянная Зипфа равна приблизительно 0,1. Для русского языка постоянная Зипфа равна примерно 0,06-0,07.

Второй  закон Зипфа констатирует, что частота и количество слов, входящих в текст с этой частотой, связаны между собой. Если построить график, отложив по одной оси (оси X) частоту вхождения слова, а по другой (оси Y) — количество слов, входящих в текст с данной частотой, то получившаяся кривая будет сохранять свои параметры для всех без исключения созданных человеком текстов.

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

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

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

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

Чтобы испытать свою разработку, ученый решил проанализировать тексты всех президентских докладов о положении в США (State of the Union addresses) начиная с 1790 года. В итоге получилось, что в период Войны за независимость американских колоний часто употреблялись слова militia («ополчение») и British («британский»), а в период с 1947 по 1959 годы наблюдался «скачок» в использовании слова atomic («атомный»). Таким образом, ученому удалось доказать работоспособность системы.

1.3 Как поисковые машины могут использовать законы Зипфа?

Для того чтобы ответить на этот вопрос, воспользуемся первым законом Зипфа и построим график зависимости ранга от частоты. Как уже упоминалось, его форма всегда примерно одинакова.

Можно предположить, что  наиболее значимые для текста слова  лежат в средней части представленного графика. Оно и понятно: слова, которые встречаются слишком часто, — это предлоги, местоимения и т.д. (в английском, немецком и некоторых других языках — еще и артикли). Редко встречающиеся слова также в большинстве случаев не несут особого смыслового значения, хотя иногда, наоборот, весьма важны для текста (об этом будет сказано чуть ниже). Каждая поисковая система решает, какие слова отнести к наиболее значимым, по-своему, руководствуясь общим объемом текста, частотными словарями и т.п. Если к числу значимых слов будут отнесены слишком многие, важные термины будут забиты «шумом» случайных слов. Если диапазон значимых слов будет установлен слишком узким, за его пределами окажутся термины, несущие основную смысловую нагрузку.

Для того чтобы безошибочно  сузить диапазон значимых слов, создается словарь «бесполезных» слов, так называемых стоп-слов (а словарь, соответственно, называется стоп-лист). Например, для английского текста стоп-словами станут артикли и предлоги the, a, an, in, to, of, and, that... и др. Для русского текста в стоп-лист могли бы быть включены все предлоги, частицы и личные местоимения: на, не, для, это, я, ты, он, она и др.Исключение стоп-слов из индекса ведет к его существенному сокращению и повышению эффективности работы. Однако некоторые запросы, состоящие только из стоп-слов (типа «to be or not to be»), в этих случаях уже не пройдут. Неудобство вызывают и некоторые случаи полисемии (многозначности слова в зависимости от контекста). Например, в одних случаях английское слово «can» как вспомогательный глагол должно быть включено в список стоп-слов, однако как существительное оно часто несет большую содержательную нагрузку.

Но поисковая машина оперирует не с одним документом, а с их огромным количеством. Допустим, нас интересуют статьи Шопенгауэра. Если бы поисковая машина оценивала частоту вхождения слова «Шопенгауэр» по вышеописанному алгоритму, эта частота была бы близка к нулю, названное слово не вошло бы в число значимых и документы, содержащие это слово, упоминались бы в конце результатов поиска. Чтобы такого не произошло, поисковые машины используют параметр, который называется инверсная частота термина. Значение этого параметра тем меньше, чем чаще слово встречается в документах базы данных. На основе этого параметра вычисляют весовой коэффициент, отражающий значимость того или иного термина.

Инверсная частота  термина i = log (количество документов в  базе данных / количество документов с  термином i).    Формула 3

Вес термина i в документе j = частота термина i в документе j * инверсная частота термина i.                                    Формула 4

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

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

Пример индексирования см. в Приложении

2.Представление базы данных

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

2.1 Матричное представление базы данных

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

Предположим, база данных имеет 8 документов (Д1, Д2… Д8), в которых содержатся 12 терминов. Если термин входит в документ, в соответствующей клеточке ставится единица, в противном случае -- ноль (в реальной системе все сложнее: помимо прочего, учитываются еще и весовые коэффициенты терминов).

Составим, например, такой  запрос: корабли в бутылках(см.Таблицу 2.1.1). Система обработает запрос: удалит стоп-слова и, возможно, проведет морфологический анализ. Останется два термина: корабль и бутылка. Система будет искать все документы, где встречается хотя бы один из терминов. Посмотрим на матрицу. Указанные в запросе термины есть в документах: Д1, Д2, Д4, Д7, Д8. Они и будут выданы в ответ на запрос. Однако нетрудно заметить, что документы Д2, Д4 и Д7 не удовлетворяют нашим чаяниям -- они из области виноделия и никакого отношения к постройке моделей кораблей в бутылках не имеют. Впрочем, система все сделала правильно, ведь, с ее точки зрения, термины корабль и бутылка равноценны.

Однако этот метод  применяется крайне редко в современных  поисковых системах, поэтому следует  перейти к пространственно-векторной  модели.

Таблица 2.1.1

	Д1	Д2	Д3	Д4	Д5	Д6	Д7	Д8
Алкоголизм	0	1	0	0	1	0	0	0
Бутылка	1	1	0	1	0	0	1	0
Вино	0	1	0	1	0	0	1	0
Корабль	1	0	0	0	0	0	0	1
Модель	1	0	0	0	0	1	0	1
Море	0	1	1	0	0	1	0	0
Парус	0	0	1	0	0	1	0	1
Пиво	0	0	0	1	1	0	0	0
Судо-  моделизм	0	0	1	0	0	0	0	0
Урожай	0	0	0	1	1	0	1	0
Хобби	0	0	1	0	0	0	0	1

2.2 Пространственно-векторная модель ПС

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

Предположим, мы хотим  найти документы, касающиеся постройки  моделей кораблей в бутылках(см.Рисунок 2.2.1). Составим запрос, например, такой: корабли в бутылках. Получив его, поисковая система удалит лишние слова, выделит термины и вычислит вектор запроса в пространстве документов (стрелочка на рисунке). Установив некоторый диапазон соответствия, система выдаст документы, попавшие в заштрихованную область на рисунке. Эта область непременно захватит документы, повествующие о необычных увлечениях - хобби, классическом судомоделизме и т.п. В них может вовсе не оказаться некоторых слов запроса, однако документы останутся достаточно релевантными. Термины, относящиеся к вину, будут группироваться в другой точке пространства, и запрос их не затронет. В пространственно-векторной модели термины взаимодействуют друг с другом, что повышает релевантность документов. Понятно, что пространственно-векторная модель лучше воспринимает запросы, составленные на естественном языке, чем матричная.

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

Рисунок 2.2.1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2.3 Полнота и точность поиска

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

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

Итак, релевантным (от англ. relevant подходящий, относящийся к делу) называется документ, имеющий отношение  к сделанному вами запросу, т.е. содержащий нужную нам информацию.

Полнота (ничего не потеряно) и точность (не найдено ничего лишнего) являются составляющими релевантности.

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

 

Коэф.полноты  поиска = Полученные релевантные документы / Общее количество релевантных документов в базе данных ПС