Любая поисковая система содержит три базовых части: • Робот — краулер, спайдер, индексатор .. «Червяк» (crawler). • Программа, способная найти на web-странице все ссылки на другие страницы.


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте его и откройте на своем компьютере.


алгоритмы
I


А.В. Цыганов 2008

65%
startup
компаний приходится на создание поисковых систем

Виды поиска в
WWW

поиск по

известным адресам

Тематические


каталоги

Поисковые машины

Специализированный поиск в базах данных

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

организациях …)

Wikipedia,

arXiv
,

Math World,

Planet Math, Science World,


Physics.org,

The Math Forum,

S.O.S. Mathematics,

www.springerlink.com
,

www.iop.org

и.т.д.


Критерии профессионального поиска
:


контроль
полноты

охвата ресурсов͖


контроль достоверности информации, полученной из Сети (
точность
);


высокая
скорость

проведения поиска
;


удобство, понятность и пр.
субъективные критерии

нтность

(
relevant
)

-

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


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


Релевантным

называется

документ

или

страница

в

интернете,

которая

формально

соответствует

сути

сделанного

через

поисковую

систему

запроса
.



При

оценке

релевантности

информации,

найденной

в

интернете,

оценивается



полнота

информации,

означающая,

что

ничего

из

имеющегося

в

интернете

не

потеряно



точность
,

показывающая,

что

не

найдено

ничего

лишнего

из

имеющейся

в

сети

информации
.


ито влияет на
нтность
?

head&#xh5ea;&#x-2d3;

&#xtitl;title
ито такое релевантность и
пертинентность
, как сделать
релевантный сайт
, как оценить
релевантность сайта
,
определение релевантности
/
titl�e

meta http
-
equiv
="Content
-
Type" content="text/html; charset=windows
-
1251" �/

meta http
-
equiv
="pragma" content="no
-
cache" �/

meta name="
Keywords
" content="
ревалентность
,
пертинентность
, релевантность информации,
релевантность сайта, определение релевантности" />


meta name="robots" content="
index,follow
" �/

/
head


͙͙
h1&#xh513;
ито

такое релевантность
/h1


͙..

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

Семантические
показатели
-

основаны
на оценке релевантности
между



документами
и запросами



Полнота выдачи (ПВ
)


ПВ
=


+




а



множество релевантных и выданных системой документов


b



множество релевантных, но не выданных системой документов



Потери
информации (ПИ)



ПИ
=


+





а


множество релевантных и выданных системой
документов


b



множество релевантных, но не выданных системой
документов


Точность выдачи (ТВ)



ТВ
=


+




а



множество релевантных и выданных системой документов


c



множество нерелевантных, но выданных системой документов



Информационный шум (ИШ)



ИШ
=


+





а



множество релевантных и выданных системой
документов


c



множество нерелевантных, но выданных системой документов


Пертинентность

Пертинентность

(
р
ertinence
)



субъективно

оцениваемое

соответствие

полученной

информации

информационной

потребности

пользователя
.


Шрубо

говоря

это

отношение

объема

полезной

для

пользователя

информации

к

объему

информации

полученной

по

запросу
,

т
.
е
.

КПД

поиска
.


Можно

улучшить,

используя

учёт

прошлых

интересов

данного

пользователя,

учёт

поведения

пользователей

на

поисковике,

уточнение

формулировок

запросов,

ранжирование

по

весовым

критериям,

ограничение

числа

выданных

в

результате

поиска

документов
͙͙


В

свое

время

Google

реализовала

новые

алгоритмы

достижения

неформальной

релевантности

(пертинентности)

и

благодаря

этому

стала

самой

популярной

ПС

в

интернете
͙
..


При

создании


сайтов,

кроме

решения

важных

вопросов

дизайна

сайта

и

его

наполненности,

необходимо

оценивать

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

и

пертинентность

сайта
,

с

точки

зрения

отношения

к

нему


существующих

поисковых

систем
.


Алгоритм + Структура данных = Поисковая система


Как

и

любая

программа,

поисковая

система

оперирует

со

структурами

данных

и

исполняет

алгоритм
.



В

настоящее

время

есть

четыре

класса

поисковых

алгоритмов
.



ари

алгоритма

из

четырех

требуют

«
индексирования
»,

предварительной

обработки

документов,

при

котором

создаются

вспомогательный

файл,

сиречь

«
индекс
»,

призванный

упростить

и

ускорить

сам

поиск
.



ото

алгоритмы

инвертированных

файлов,

суффиксных

деревьев

и

сигнатур
.


иетвертый

класс

алгоритмов

прямого

поиска

не

требует

индексирования
.

Анатомия поисковой системы

Любая поисковая система содержит три базовых части
:



Робот

-

краулер, спайдер, индексатор ͙..

Извлечение
и накопление данных документов.



Базы данных
-

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



Клиент



обработка запросов (поиск
по созданным
данным).



Существует

масса

других

частей,

однако

их

назначение

заключается

главным

образом

именно

в

эффективной

поддержке

этих

трёх

базовых
.


Анатомия поисковой
системы (
2
)

Анатомия поисковой
системы (
3
)

Web

spider

или

Web

scraper



это

разновидности

программных

роботов

или

агентов



терминологии,

предложенной

Аланом

Кеем

(Alan

Kay)

в

начале

1980
-
х

годов)
.



Программный

агент

должен

действовать

в

качестве

посредника

(proxy)

между

пользователем

и

компьютерным

миром
.

аакой

агент

может

иметь

определённую

цель

и

должен

работать

над

достижением

этой

цели

в

отведённой

ему

области
.



Цель

может

состоять

в

сборе

информации

или

в

понимании

структуры

какого
-
либо

Web
-
сайта

и

его

полезности
.

аакие

пауки

автоматически

извлекают

данные

из

Web
-
сайта

(

например

HTML
-
код

документа
)

и

передают

их

другим

приложениям,

которые

индексируют

контент

этого

Web
-
сайта

с

целью

формирования

наилучшего

набора

поисковых

терминов
.

«Паук» (
spider
)

"
Web
-
скребок
"

(
Web

scraper
)



это

агент,

который

действует

аналогично

Web
-
паукам,

но

более

интересен

с

юридической

точки

зрения
.



Scraper



это

разновидность

паука,

которая

нацелена

на

работу

с

определённым

Интернет
-
контентом,

например,

с

данными

о

стоимости

продуктов

или

услуг
.


Один

из

вариантов

применения

scraper
-
агентов




конкурентное

ценообразование,

т
.

е
.

выявление

существующих

на

рынке

цен

на

определённую

категорию

товаров

с

целью

установления

соответствующих

цен

на

собственную

продукцию
.



Кроме

того,

scraper

способен

объединять

данные

из

нескольких

источников

в

Интернете

и

предоставлять

эту

итоговую

информацию

пользователю

и

т
.
д
.

Шлаза и ноги паука


Основными органами зрения и перемещения
Web
-
паука в Интернете является
HTTP



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


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


Протокол
HTTP

поддерживает запросы
трех

основных типов.


Запрос
типа
HEAD

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

сервера.


Запрос
типа
GET

запрашивает сам актив, например, файл или
изображение.


Запрос
типа
POST

разрешает клиенту взаимодействовать с сервером через
Web
-
страницу (обычно через
Web
-
форму).

Простой
агент типа
Web

scraper

(другое название


screen

scraper
) для сбора
информации о котировках
акций
-

приведен

сценарий на языке
Ruby
.

#!/
usr
/local/bin/ruby

require 'net/http'

host
= "www.smartmoney.com"

link = "/
eqsnaps
/
index.cfm?story
=
snapshot&symbol
="+ARGV[
0
]

begin



# Create a new HTTP connection


httpCon

= Net::
HTTP.new
( host,
80
)



# Perform a HEAD request


resp

=
httpCon.get
( link, nil )



stroffset

=
resp.body

=~ /class="price"�/



resp.body.slice
14
,
10
)



limit =
('')



print ARGV[
0
0
..limit
-
1
] +


" (from stockmoney.com)
\
n"


end

«иервяк» (
crawler)


Программа, способная найти на
web
-
странице
все ссылки

на другие
страницы.



Ее задача


определить, куда дальше должен «ползти» «паук»,

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


Каждую

найденную

ссылку

в

документе

crawler

должен

проверить

на

правильность,

с

точки

зрения

интернет
-
имени

сервера
.



Для

этих

целей

используется

стандартный

механизм

DNS



однако

если

рассматриваемая

страница

содержит

массу

ссылок

на

другие

страницы

и

при

этом

первичный

сервер

зоны,

в

которой

располагаются

данные

страницы

в

данный

момент

по

каким
-
либо

причинам

не

доступен,

то

возникают

огромные

потери

времени

на

попытках

установления

соответствия


-

в

итоге

ваша

страничка

не

индексируется!!!!

Web
-
пауки

и

краулеры

минимизируют

порождаемую

ими

нагрузку

на

Интернет

с

помощью

набора

политик
.



итобы

представить

масштабы

проблемы,

необходимо

учесть,

что

Google

индексирует

более

8

млрд
.

Web
-
страниц
.

Поиск

в

Интернете

весьма

дорог,

как

с

точки

зрения

пропускной

способности,

необходимой

для

передачи

Web
-
контента

индексатору,

так

и

с

точки

зрения

вычислительных

затрат

на

индексирование

результатов
.


Политики

поведения

определяют,

какие

страницы

Web
-
краулер

должен

вводить

в

индексатор

и

как

часто

Web
-
краулер

должен

возвращаться

на

какой
-
либо

Web
-
сайт

для

повторной

проверки,

а

также

т
.
н
.

"политику

вежливости"
.



Web
-
серверы

могут

запрещать

работу

краулеров

с

помощью

стандартного

файла

robot
.
txt
,

который

сообщает

краулерам

о

том,

что

можно,

а

что

нельзя

просматривать

на

данном

сервере

+

такие

директивы

как

Disallow,

Allow,

User
-
agent,

Crawl
-
delay

и

другие
.

Индексатор (
Indexer)


Программа, которая
«разбирает»
web
-
страницу на составные
части

и анализирует их.



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



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










( вспомните про
алгебраический тип данных
)


База данных
(database)


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



аребует огромных ресурсов

как для хранения, так и для последующей
обработки.

Data center Google in US

В
2008
году


63
,
272
Machines


126
,
544
Processors


253
,
088
GHz
Proccessing

ability


126
,
544
GB
Memory


5
,
062
TB Hard Drive Space

Система выдачи результатов поиска (
Search Engine
Results Engine
-

клиент
)

Индексация и индекс


Процесс

загрузки

информации

из

интернета

и

предварительного

анализа

ее

поисковой

машиной

называют

индексацией
.



База

данных

ПС,

в

которой

храниться

вся

информация



это

и

есть

индекс

,

грубо

говоря
.




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

глава, вторая
-

стих)














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

Вопрос, что индексировать


волк или волка или волку.


ЗАмок

или
заМОК

( ударение)


Большие
/
маленькие буквы
-

General Motors


Пунктуация
-

C
.Ш. А. или США (сокращение, аббревиатура).


иисла (в каком формате
?
)
3/12/91, Март 12,1991

55 В.С,
В
-
55


Как обрабатывать
синонимы и омонимы, индексировать
эквивалентные слова
или расширять
/
уточнять запрос
?


Классы эквивалентности
:

автомашина и автомобиль

опушка


край леса или меховая обшивка одежды
?




Пример

-

выделение корня


Сокращаем слова к их корню до их индексирования

-
языковая зависимость

-
например,
бегун, побег, пробежка

все сокращаются к
бег.



Для примера,

слова
бег
ун

и
бег
унок предполагаются


относящимися к
слову
бег


Так как корни
бег

и
бег


совпадают с корнем
бег
.

"алгоритм
стемминга
", от слова
стем

-

"корень".

Пример
-

алгоритм Портера


Обычный алгоритм для выделения корня в англоязычных текстах


Соглашения +
5
-
фазное сокращение


фазы применяют последовательно


каждая фаза состоит из набора команд


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


аипичные правила Портера


Прилагательное существительное


Множественное число единичное

число

The
Porter Stemming Algorithm


Porter’s homepage. (
англ.)

The
Porter Stemming Algorithm


Project «Snowball» (
англ.)

The
English (Porter2) stemming algorithm (
улучшенная версия алгоритма)


Project
«Snowball» (
англ.)

Каждая

поисковая

система

использует

свой

алгоритм

поиска

и

его

детали

представляют

собой

ноу
-
хау

разработчиков

поисковика
.


(
есть

классификация

алгоритмов

и

систем
)


Алгоритм

поиска



метод,

руководствуясь

которым

поисковая

система

принимает

решение,

включать

или

не

включать

ссылку

на

web
-
страницу

в

результаты

поиска
.

Механизмы и алгоритмы поиска

П
C

осуществляет отбор на основании постоянно меняющихся критериев
-

например
:


Title

(заголовок):

Имеется ли ключевое слово в заголовке?


Domain
/URL (Домен/адрес):

Имеется ли ключевое слово в имени домена
/

в
адресе страницы?


Style

(стиль):

(STRONG или B), Курсив (EM или I), Заголовки :EAD.


Density

(плотность): Количество ключевых слов относительно всего текста
страницы называется плотностью ключевого слова.


MetaInformation

(мета данные):

-

мета ключевые слова (
meta

keywords
) и
мета описания (
meta

description
).



Outbound

Links

(ссылки наружу):

Какие ссылки есть на странице и содержит
ли они и ключевое слово?


Inbound

Links

(внешние ссылки):

Имеются ли в Интернет ссылки на данный
сайт? Каков текст ссылки? «
внестраничный
» критерий (автор страницы не
всегда может им управлять).


Insite

Links

(ссылки внутри страницы):

Какие ссылки на страницы данного
сайта содержит эта страница?

Закономерности поиска


Правило Парето


Правило
S


Законы
Зипфа
-
Мандельброта


Закономерность
Брэдфорда



Закономерность

еипса



Правило
Парето
80
/
20

Анализируя

общественные

процессы,

Парето

рассматривал

социальную

среду

как

пирамиду
.



В

результате

кропотливых

исследований

ученый

сформулировал

математическую

зависимость

между

величиной

дохода

и

количеством

получающих

его

лиц
.



Ученый

в

1906

году

установил,

что

80

процентов

земли

в

Италии

принадлежит

лишь

20

процентам

ее

жителей
.



Парето

пришел

к

выводу,

что

параметры

полученного

им

распределения

примерно

одинаковы

и

не

различаются

принципиально

в

разных

странах

и

в

разное

время
.


Вильфредо


Парето


Распределение Парето

Распределение

доходов

по

Парето

описывается

уравнением
:


N = A /е
p+
1
,


где

е



величина

дохода,

N

-

численность

людей

с

доходом,

равным

или

выше

е
,

A

и

p

-

коэффициенты

уравнения

-

е


1
,

p



0
.



Распределение

Парето

обладает

свойством

устойчивости,

т
.
е
.

сумма

двух

случайных

переменных,

имеющих

распределение

Парето,

также

будет

иметь

это

распределение
.


W
iki

При

информационном

поиске

достаточно

определить

20
%

необходимых

ключевых

слов,

позволяющих

найти

80
%

требуемых

документов
.



80
%

посещений

Web
-
сайта

приходится

лишь

на

20
%

его

Web
-
страниц
.



При

создании

(программировании)

необходимо

учитывать

то,

что

наиболее

сложным

функциональным

возможностям

системы,

на

реализацию

которых

ушло



80
%

трудозатрат

будут

использоваться

не

более,

чем

20
%

пользователей

данной

системы
.



Если

предположить,

что

идеальная

система

имеет

100
%

необходимых

функций,

а

систему,

которая

реализует

90
%

функций

можно

создать

за

10

человеко
-
лет,

то

для

доведения

функциональности

системы

до

уровня

95
%

потребуется

еще

не

менее

10
-
ти

человеко
-
лет
.



ааким

образом,

цена

последних

5
-
ти

процентов

равна

цене

всей

системы,

работающей

с

функциональностью

90
%
.



О переходе количества в качество

Если

система

достигла

99
%

своей

идеальной

функциональности,

то

дальнейшие

попытки

ее

совершенствования

ведут,

в

лучшем

случае,

к

повышению

качества

сопровождения

реализованных

уже

функций,

и,

если

изобразить

график,

отмечая

по

оси

абсцисс

затраченные

ресурсы

на

развитие

системы,

а

по

оси

ординат

-

уровень

функциональности,

то

график

будет

иметь

вид

кривой
,












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


распределение Парето.


Буква
S
те
хнологического

прогресса

В

реальной

жизни

бывают

случаи,

когда

после

длительного

процесса

стабилизации

происходит

резкий

взлет

этой

кривой

выше

уровня

100
%
,

т
.
е
.

график

принимает

вид

перевернутой

буквы

S
.













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

Законы
Зипфа

(Ципфа)



Мандельброта


Зипф

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



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



На основе этого наблюдения
Зипф

вывел
два закона
.

Первый закон
Зипфа


Первый закон связывает
частоту появления (вхождения)

того или иного слова с
рангом

этой частоты.



Наиболее часто встречающимся словам присваивается ранг, равный
единице
.



аем словам, что встречаются реже


ранг, равный
двойке

и т.п.



Зипф

обнаружил, что произведение
частоты вхождения слова

и его
ранга

является постоянной величиной.



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



Значение константы
Зипфа

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

неизменным
.


Для русского и украинского языков коэффициенты
Зипфа

составляют
приблизительно 0,06
-
0,07.


Первый закон
Зипфа

Второй закон
Зипфа


иастота вхождения слов

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


Получившая

кривая

будет

сохранять

свои

параметры

для

всех

текстов

в

пределах

одного

языка
.


С

другой

стороны,

на

каком

бы

языке

текст

ни

был

написан,

форма

кривой

Зипфа

останется

неизменной
.

Отличаться

будут

лишь

коэффициенты
.


частота вхождения слов

количество слов

Следствия законов
Зипфа


Законы
Зипфа

универсальны
. Они применимы не только к текстам.



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

и
числом проживающих

в них жителей.



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

отвечают законам
Зипфа
.



В

законах

Зипфа

отражается

«человеческое»

происхождение

объектов



т
.
е
.

можно

отличать

искусственное

от

природного



например

распределение

кратеров

на

Луне
.



Известный

математик

Бенуа

Мандельброт

математическим

путѐм

пришѐл

к

аналогичной

первому

закону

Зипфа

зависимости

f*r
e

=

c

,

где

e

-

близкая

к

единице

переменная

величина,

которая

может

изменяться

в

зависимости

от

свойств

текста

и

языка



Как ПС используют законы
Зипфа


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

слова лежат в средней части графика.

Центральная часть графика

Центральная

зона

графика

содержит

термины

(слова),

наиболее

характерные

именно

для

данного

текста



по

правилу

Парето

их

будет

около

20
%
!
.


оти

значимые

или

ключевые

слова

в

совокупности

выражают

специфичность

текста
,

отличие

его

от

других

текстов,

охватывают

его

основное

содержание
.


Каждая ПС по
-
своему решает, какие слова отнести к наиболее значимым.


Однако, если к числу значимых будет отнесены слишком
много слов
, то
важные термины будут забиты «шумом» случайных слов.


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


Стоп
-
слова

Для того, чтобы безошибочно сузить диапазон значимых слов, создается словарь
«бесполезных» слов или
«стоп
-
слов».


Словарь

этих

слов

(«стоп
-
лист»)

содержит,

например,

артикли

и

предлоги,

частицы

и

личные

местоимения

(
а,

без,

более,

бы,

был,

была,

были,

было,

быть,

в,

вам,

вас,

весь,

во,

вот,

все,

всего,

всех,

вы,

где,

да,

даже,

для,

до,

его,

ее
,

если,

есть,

ещё,

же,

за,

здесь,

и,

из,

из
-
за,

или,

им,

их,

к,

как,

как
-
то,

ко,

когда,

кто,

ли,

либо,

мне,

может,

мы,

на,

надо,

наш,

не,

него,

неё,

нет,

ни,

них,

но,

ну,

о,

об,

однако,

он,

она,

они,

оно,

от,

очень,

по,

под,

при,

с,

со,

так,

также,

такой,

там,

те,

тем,

то,

того,

тоже,

той,

только,

том,

ты,

у,

уже,

хотя,

чего,

чей,

чем,

что,

чтобы,

чьё,

чья,

эта,

эти,

это,

я
),


а

также

целый

ряд

других

слов
.

Их

конкретный

перечень

может

состоять

от

нескольких

сот

до

нескольких

тысяч

слов

и

различен

для

разных

поисковых

машин
.
.


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



Весовой коэффициент

При определении значимых слов применяется и т.н.
«весовой коэффициент».


иасто встречаемое
на всех сайтах слово
-

имеет весовой коэффициент,
близкий к нулю.


Слово встречаемое редко

на всех сайтах
-

может иметь весьма высокий
коэффициент.


Параметр, определяющий «весовой коэффициент», называется
инверсная
частота термина
.


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

Необходимо

например

для

того,

чтобы

ПС

могла

игнорировать

некоторые

часто

встречающиеся

слова

-

прайс,

сайт,

Интернет
,

и

т
.
д

Закономерность
Брэдфорда


Основной

смысл

закономерности

С
.

Брэдфорда

заключается

в

следующем
:

если

научные

журналы

расположить

в

порядке

убывания

числа

помещенных

в

них

статей

по

конкретному

предмету,

то

полученный

список

можно

разбить

на

три

зоны

таким

образом,

чтобы

количество

статей

в

каждой

зоне

по

заданному

предмету

было

одинаковым
.



оти

три

зоны

составляли
:

профильные

журналы,

посвященные

рассматриваемой

тематике,

журналы,

частично

посвященные

заданной

области,

и

журналы,

тематика

которых

весьма

далека

от

рассматриваемого

предмета
.


С.
Брэдфорд

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



P
3
: P
2
= P
2
: P
1
= N
,


где

P
1

-

число

журналов

в

1
-
й

зоне,

P
2

-

во

2
-
й,

P
3

-

число

журналов

в

3
-
й

зоне
.




Исходя

из

реалий

развития

сети

Интернет,

ее

можно

рассматривать

как

закономерность,

относящуюся

к

ранговому

распределению

Web
-
сайтов,

относительно

вхождения

в

них

Web
-
страниц,

релевантных

некоторой

области

знаний
.


Закон
еипса


В компьютерной лингвистике эмпирический закон
еипса

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

v
(
n
) =
Kn
ъ
,

где
v



это объем словаря уникальных слов, составленный из текста, который
состоит из
n

уникальных слов.
K

и
ъ



обусловленные эмпирически параметры.
Для европейских языков
K


принимает значение от 10 до100, а
ъ

-

от 0.4 до 0.6
.










Закон
еипса

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

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

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



теоретико
-
множественные

(булевская,
нечётких
множеств,
расширенная булевская),


алгебраические

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


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

Большинство

поисковых

систем

функционируют

безо

всяких

математических

моделей,

так

как

их

разработчики

не

ставят

перед

собой

задачу

реализовывать

абстрактную

модель
.



Как

только

речь

заходит

о

повышении

качества

поиска,

о

большом

объёме

информации,

о

потоке

пользовательских

запросов,

кроме

эмпирически

проставленных

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

полезным

оказывается

оперировать

каким
-
нибудь

пусть

и

несложным

теоретическим

аппаратом
.



Модель

поиска



это

некоторое

упрощение

реальности,

на

основании

которого

получается

формула

(сама

по

себе

никому

не

нужная),

позволяющая

программе

принять

решение
:

какой

документ

считать

найденным

и

как

его

ранжировать
.



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

Булевская модель

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

ИЛИ
,

НЕ
.

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


Недостатки




1.
недостаточно
возможностей для описания сложных
запросов

2.
результатов запроса либо слишком много либо слишком мало

3.
проблематичность
при ранжирования
результатов

53




Матрица документ
-
термин
C(
d,t
)

показывает какие встречаются
слова
t

и в
каких документах

d

C(
d,t
)

1

0

0

1

1

0

1

0

1

0

1

0

1

1

1

Запрос
:


q

=

a


И (
b

ИЛИ

(
НЕ

c
) )

Булевская модель


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

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


Компоненты

вектора
соответствуют
N

терминам,
образующим
пространство.


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


Как выбирать размерность
пространства терминов

N

?


Как вычислять весовые
коэффициенты

w
t
?

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

Релевантность в векторной модели

Пример



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

Достоинства
:

1.
Учет

весов повышает эффективность поиска

2.
Позволяет оценить степень соответствия документа запросу

3.
Косинусная метрика удобна при ранжировании


Недостатки

1.

Нет
достаточного теоретического обоснования для построения
пространства
терминов

2.

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

Вектор
слово
-
документной

встречаемости



ари
поро
-
сенка

Красная
Шапочка

Колобок

аеремок

медведь

0

0

1

1

волк

1

1

1

1

поросенок

1

0

0

0

мышь

0

0

0

1

бабушка

0

1

1

0

0
,

если
слова нет

в документе
,

1
если есть

Итак мы имеем
вектора из 0/1
для каждого слова размерности равной
количеству документов
.


Запрос
:


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


Ответ
:



возьмем

вектора
для

медведя

(дополнение),

волка

и
поросенка
(дополнение)


и
выполним между ними побитное умножение


11
00&
1111
&0
1
11

= 0
1
00


второй документ!

61

Вероятностные модели

Заключаются в оценке вероятности того, что документ
d

является
релевантным по отношению к запросу
q


Вероятность вычисляется на основе теоремы Байеса
:





P(R)



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

является
релевантным


P(
d|R
)



вероятность случайного выбора документа
d

из множества
релевантных
документов


P(d)



вероятность случайного выбора

документа
d

из коллекции
D


Google Page Rank





Все

его

используют,

но

мало

кто

знает,

как

он

работает

и

как

его

вычисляют
.



Поиск

среди

миллиардов

существующих

и

миллионов

создаваемых

каждый

день

страниц,

задача

более

сложная,

чем

вы

можете

сразу

представить
.

PageRank
,

только

один

из

сотен

факторов,

используемых

Google

для

улучшения

качества

поиска
.



Но

как

он

работает,

и

какие

факторы

на

него

влияют,

а

какие

нет,

и,

что

мы

знаем

о

PageRank
?

Алгебраическое определение


Рассмотрим восемь
web
-
страниц связанных соответствующими
гиперссылками и найдем
PageRank

этих страниц











Начнем

с

построения

матрицы

гиперссылок

H



элемент

которой

в

i
th

строке

и

j
th

столбце

определяется

по

правилу




࢏࢐
=




















если












в

противном

случае



Здесь




-

страничка

с

номером

j

,

которая

имеет







гиперссылок

на

другие

страницы,






множество

страниц

на

которые

ведут




гиперссылки

с

i

-

той

страницы




По определению матрица гиперссылок будет

матрицей с
положительными
элементами,
сумма

которых в каждом столбце
равна
1


такие матрицы
называют
стохастическими
.

аеперь найдем
стационарный вектор
матрицы гиперссылок

(
т.е. вектор
отвечающий единичному собственному значению
)




H I = I


олементы этого вектора и есть значения
PageRank


соответствующей
страницы
.


ием больше эти значение


тем выше

качество


данной страницы.



Метод простых итераций
:













I
0


I
1


I
2


I
3


I
4


...

I
60


I
61


1

0

0

0

0.0278

...

0.06

0.06

0

0.5

0.25

0.1667

0.0833

...

0.0675

0.0675

0

0.5

0

0

0

...

0.03

0.03

0

0

0.5

0.25

0.1667

...

0.0675

0.0675

0

0

0.25

0.1667

0.1111

...

0.0975

0.0975

0

0

0

0.25

0.1806

...

0.2025

0.2025

0

0

0

0.0833

0.0972

...

0.18

0.18

0

0

0

0.0833

0.3333

...

0.295

0.295

Теоретическое решение
n→∞

Будущие поисковые машины


Каталоги сайтов:

регистрация сайтов сообществами


Каталоги запросов:

регистрация и разметка запросов
вебмастерами


Структурированная выдача:
по теме и типам
документов.


иитаемость выдачи:

названия, аннотации, тэги от
сообществ


Понимание запроса:

запросы на Ес, распознавание
темы, уточнение запроса


Новые виды заработка на поиске:

регистрация
запросов, сайтов, ранжирование, хостинг поиска

Отдельный разговор
:


Мобильный поиск (борьба за смартфон)


Локальный поиск и
геотаргетинг

(борьба за
кофе
-

Nokia
)


Блогопоиск

и новостные поисковики (борьба за
аффтара
)


Многоязыковый поиск и перевод (борьба с языковым барьером)


Национальные проекты (борьба против
Шугла
)


Ну и так далее .................


Источники
:

1.
ррий
Лифшиц
-

курс "
Алгоритмы для Интернета
"

2.
Шаврилова а.А.,
еорошевский
В.Ф. Базы знаний интеллектуальных систем.
-

СПб.: Питер, 2000
.

3.
Добрынин В. аеория информационно
-
логических систем. Информационный поиск
.
-

СПб.,
2002.

4.
Леонт
ь
ева
Н.Н. Автоматическое понимание текстов: системы, модели, ресурсы.
-

М.:
Издательский центр "Академия", 2006
.

5.
Пенроуз

Р. Новый ум короля: О компьютерах, мышлении и законах физики.


М.: УРСС, 2003
.

6.
Библиотека

на
www.nigma.ru

7.
Страница
Леонида
Бойцова

8.
Русский национальный корпус,
http://www.ruscorpora.ru


9.
иастотный
словарь Сергея
Шарова
,
http://www.artint.ru/projects/frqlist.asp


10.
Поисковые
машины и поисковая оптимизация,
http://searchengines.ru

РОМИП,
http://romip.narod.ru


11.
Список
стоп
-
слов,
http://forum.searchengines.ru/showthread.php?postid=7670


12.
Страница
Андрея Коваленко,
http://linguist.nm.ru


13.
Cайт

"Автоматическая Обработка аекста",
http://www.aot.ru


14.
Шусев
В.С.
Google
: эффективный поиск. Краткое руководство.


М.: «Вильямс»,
2006.

15.
Ландэ

Д.В. Поиск знаний в INTERNET. Профессиональная работа.: Пер. с англ.


М.:
«Вильямс», 2005.



Приложенные файлы

  • pdf 7709141
    Размер файла: 2 MB Загрузок: 0

Добавить комментарий