Geum.ru

Общая характеристика работы

Вид материалаЗакон
1.3 Как поисковые машины могут использовать законы Зипфа?
Инверсная частота термина i = log (количество документов в базе данных / количество документов с термином i).
2.Представление базы данных
2.1 Матричное представление базы данных
Подобный материал:
1   2   3   4   5   6   7   8   9

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