\documentclass{article}
\usepackage[russian]{babel}
\usepackage{wrapfig}
\usepackage[dvips]{epsfig}

\title{Введение в поисковые системы}
\author{Ю. Лифшиц\thanks{Законспектировал Д. Кочелаев.}.}

\begin{document}
\maketitle

\section*{План лекции}
\begin{enumerate}
\item Архитектура поисковых систем
\item Алгоритмы поисковых систем
\item Поисковая оптимизация
\end{enumerate}
\par

\section{Архитектура поисковых систем}
\subsection{Анатомия поисковой системы}
В любой поисковой системе можно выделить три базовых части:
\begin{enumerate}
\item Робот (краулер, спайдер, индексатор). Робот отвечает за сбор
ин\-фор\-ма\-ции. То есть робот эмулирует работу пользователя,
загружая стра\-ни\-цы и сохраняя их в базе данных.
\item База данных. В базе данных хранится и сортируется собранная
ро\-бо\-том информация.
\item Клиент. В этой части обрабатываются пользоватльские запросы. В
действительности клиент может быть разнесен по нескольким
фи\-зи\-чес\-ки несвязанным компьютерам. Однако, чтоит отметить, что
все эти ком\-пью\-те\-ры должны иметь доступ к базе данных.
\end{enumerate}
Рассмотрим описанную выше структуру на примере поисковой системы Google.

\begin{center}
\includegraphics[scale=0.4]{ov.eps}
\end{center}

\begin{enumerate}
\item URL Server --- список всех адресов.
\item Crawler --- робот, который загружает страницы из списка адресов и
передает в Store Server.
\item Store Server сохраняет страницы в Repository, чаще всего в виде
HTML документа. При этом вся дополнительная информация, такая как
кар\-тин\-ки, flash-анимация и прочее, не сохраняется.
\item Indexer разбирает сохраненные в Repository HTML-документы в
пос\-ле\-до\-ва\-тель\-нос\-ти слов и сохраняет их в Barrles (база данных).
\item Lexicon --- список всех слов. Чаще всего слова храняться в таблице с 
двумя полями ``номер'' и ``слово''. Таким образом достигается эко\-но\-мия места в
базе данных, так как длинные слова заменяются дос\-та\-точ\-но коротким номером.
\item Anchors --- выделенные компонентом Indexer ссылки (URL).
\item URL Resolver --- обработчик URL. Если находятся новые ссылки, то они 
передаются в URL Server.
\item Links определяет какие сайт на какие ссылаются и передает это в PageRank.
\item PageRank --- определяет рейтинг сайта, основным критерием является
количество ссылок на этот сайт (подробнее смотрите раздел про Page\-Rank).
\item Searcher --- клиент. Чаще всего клиент пользуется статической базой
данных, которая обновляется примерно раз в сутки.
\end{enumerate} 

\subsection{Прямой и обратный индекс}
\parРассмотрим варианты хранения записей в базе данных, то есть параметр, по
которому они отсортированы, и какая дополнительная информация хра\-нить\-ся
для каждой записи. В связи с этим появляются два поняти прямой и обратный
индексы.
\par В случае прямого индекса записи отсортированы по номеру документа. Для
каждой записи хранится отсортированный по номеру список слов. Для каждого
слова хранятся первые несколько (например восемь) позиций вхождения слова в
докумен, количество вхождений и формат вхождения. Под форматом вхождения
подразумевается вхождение слова в тексте ссыл\-ки, в описании к картинке, в
загаловке и т.д., такие слова будут иметь приоритет при поиске. Прямой
индекс обновляется постоянно при работе робота, соот\-ветствен\-но возникает
вопрос: ``Как часто надо индексировать одну стра\-ни\-цу?''. Для каждой страницы
в базе данных харнится частота предполагаемого об\-нов\-ле\-ния, которая
считается следующим образом: при очередном заходе робота на эту страницу в
случае отсутствия обновлений частота уве\-ли\-чи\-вает\-ся в два раза, а если 
страница за этот период времени менялась, то умень\-шает\-ся. Также стоит отметить,
что чаще всегоробот индексирует не все слова из документа (например только
первую тясячу слов) и не все документы с одного сайта.
\par Обратный индекс используется клиентом при поиске. В этом случае для
записи отсортированы по словам. Для каждой записи хранится номер слова,
список документов, в которые входт это слово, и полная информация о вхождении.
Отметим, что обратный индекс обновляется не так часто как прямой, а примерно
раз в сутки.

\subsection{Релевантность и позиция документа в поиске}
\par Для начала дадим определение релевантности. Под релевантностью
по\-ни\-мает\-ся то, насколько слово (совокупность слов) соответствует
данному документу.
\par Рассмотрим теперь характеристики, которые могут влиять на
по\-зи\-цию документа в списке ответов:
\begin{enumerate}
\item Наличие слов в документе. Очевидно, что если слова в документе не
встречаются, то данный документ не подходит под условия поиска.
\item Частота вхождения слов. Чем чаще слова встречаются на странице, тем
выше документ окажется в списке поиска.
\item Форматирование слов. То есть если в документе слова встре\-чают\-ся
выделяющих тэгов, заголовков, описаний картинок, то такой до\-ку\-мент будет
иметь более высокий приоритет.
\item В случае набора слова значение также имеют расстояние между этиим 
словами в документе и их порядок.
\item В некоторых поисковых система (например Яндекс) значение имеет
морфологическое вхождение слов, то есть падеж (род, лицо), в ко\-то\-ром
слово входит в документ.
\item Количество и уважаемость ссылок (подробнее смотрите раздел про PageRank).
\item Регистрация в каталоге поисковой системы. Это очень важная
ха\-рак\-те\-рис\-ти\-ка, так как каталоги составляются вручную и в них уже
заданы разделы и тематика страницы.
\end{enumerate}

\subsection{Работа клиента}
\par Сначала запрос разбивается на слова. Далее удаляются так называемые ``стоп''
слова --- слова, которые встречаются почти во всех документах (пред\-ло\-ги,
союзы). На следующем шаге каждому слову сопоставляется его номер из ``лексикона''.
Для каждого слова из запроса находится в обратном ин\-дек\-се список документов,
которые содержат это слово. Из этих списков создается новый, содержащий те
и только те документы, которые входили в списки для всех слов. Затем, на основе
характеристик обозначеных в предыдущем разделе для каждого документв вычисляется
степень ре\-ле\-вант\-нос\-ти, и список сортируется по этому признаку. На этом шаге
для всех документов соз\-дают\-ся аннотации. Аннотацией может быть содержание тэга
``description'', контекст вхождения слов из запроса (наиболее близко стоящих или
первое вхож\-де\-ние), первое предложение или заголовок документа.

\subsection{Качество поиска}
\par Имея несколько поисковых систем, хочется определить какая же из них лучшая.
То есть оценить качество поиска. Как это сделать? На этот вопрос нет однозначного
ответа. Однако, можно привести некоторые возможные критерии определения качества
поиска:
\begin{enumerate}
\item Полота поиска, то есть насколька большая доля страниц, из удов\-лет\-во\-ряю\-щих
условиям поиска, была найдена. Обычно у современных поисковых машин с этим критерием
проблем не возникает. Хотя ко\-ли\-чест\-во документов в базе данных у поисковых машин
отличается, для сравнения база данных Google содержит около 8 миллиардов до\-ку\-мен\-тов,
а --- Яндекса только около 10 миллионов. Однако, в базе данных Яндекса есть до\-ку\-мен\-ты из
русскоязычного интернета, от\-сутст\-вую\-щие в базе данных Google.
\item Точность поиска, то есть доля релевантных документов из всех най\-ден\-ных.
\item Benchmarks: показатели системы на контрольных запросах и спе\-ци\-аль\-ных коллекциях
документов. С этим критерием у некоторых поис\-ко\-вых систем возникают проблемы, например
некоторое время назад из че\-ты\-рех крупных поисковых систем по своему имени себя находила
только одна (остальные безусловно выдавали ссылку на себя, но да\-ле\-ко не самой первой).
Также проводятся ежегодные соревнования поисковых алгоритмов.
\item Оценка экспертов.
\end{enumerate}
\par Также стоит отметить, важность производительности поисковых ал\-го\-рит\-мов, так например
Google, при убыстрении своих поисковых алгоритмов на 1\%, смог бы уменьшить свой парк
компьютеров на 100 штук (на данный момент у них около 10 тысяч компьютеров).

\section{PageRank}
\subsection{Постановка задачи}
\par При выборе из списка документов, найденных по некоторому запросу, хо\-те\-лось
бы выбрать наиболее подходящие. Таким образом встает задача о вы\-чис\-ле\-нии ``качества''
документа. Первые идеи, которые могут прийти в голову:
\begin{enumerate}
\item Учет частоты обновления страницы.
\item Учет количества посещений страницы.
\item Учет регистрации в каталоге данной поисковой системы.
\end{enumerate}
\par  К сожалению, эти характеристики легко подделать (пожалуй за ис\-клю\-че\-нием регистрации
в каталоге). Рассмотрим выдвинутую в 1998 году Брином идею определения рейтинга страницы
через количество ссы\-лаю\-щих\-ся страниц и их рейтинг. Как будет показано далее, ``накрутить''
данный показатель достаточно тяжело.

\subsection{Модель случайного блуждания}
\par Для определения PageRank для страниц промоделируем хождение поль\-зо\-ва\-те\-ля
по сети. Для этого воспользуемся моделью случайного блуждания. Представим
себе сеть в виде ориентированного графа, где вершины яв\-ляют\-ся докуентами, а
ребра --- ссылками. Пользователь начинает свое движение из случайной вершины. Далее
на каждом шаге он с вероятностью $\varepsilon$ (обычно $\varepsilon$ берется примерно 0.15) 
переходит в случайную вершину и с вероятностью $1-\varepsilon$ по одному из ребер ведущих
из данной вершины.
\begin{center}
\includegraphics[scale=0.35]{walk.eps}
\end{center}
\par Введем понятие предельной вероятности: $PR_k(i)$ --- это вероятность ока\-зать\-ся
в вершине i через k шагов.
\par\textbf{Утверждение:} $\lim_{k\to\infty}PR_k(i)=PR(i)$, то есть для каждой вершины
существует предельная вероятность находиться в ней.

\subsection{Основное уравнение PageRank}
Введем некоторые обозначения: $T_1,\dots,T_n$ --- вершины, из которых идут ребра в $i$,
$C(X)$ --- количество ребер исходящих из вершины $X$. Тогда имеет место следующее
утверждение.
\par\textbf{Утверждение:}
$PR(i)=\varepsilon/N + (1-\varepsilon)\sum_{i=1}^n \frac{PR(T_i)}{C(T_i)}$
\par\textbf{Доказательство.}
\par По определению $PR_k(i)$ верно следующее:
\par$PR_0(i)=1/N$
\par$PR_k(i)=\varepsilon/N + (1-\varepsilon)\sum_{i=1}^n \frac{PR_{k-1}(T_i)}{C(T_i)}$
\par Теперь переходим к пределу в обеих частях последнего равенства и получаем доказываемое
утверждение.
\par Доказательство завершено.
\par Разберемся откуда берутся оба слагаемых в правой части равенства: $\varepsilon/N$
--- вероятность того, что мы начнем с этой вершины, а сумма это сумма вероятностей
прихода с других страниц по ссылкам.
\par Практически предельный PageRank не используют, а вместо $PR(i)$ берут $PR_{50}(i)$.
После расчета PageRank нормализуется и округляется так, чтобы это было целое число от 1
до 10.

\subsection{Матричная интерпретация}
\par Рассмотрим матрицу $L$ для построенного в предыдущем пункте графа. Заполнять матрицу
будем по следующему принципу: $l_{ij}=\varepsilon/N$, если из вершины $i$ в вершину $j$ нет
ребра, и $l_{ij}=\varepsilon/N + (1-\varepsilon)1/C(i)$, если ребро есть.
Введем следующие обозначения:
\par $\overline{PR_k}=(PR_k(1),\dots,PR_k(N))$
\par $\overline{PR}=(PR(1),\dots,PR(N))$
\par Тогда будут верны следующие соотношения:
\par $PR_k=L^k\,PR_0$
\par $PR=L\,PR$
\par Последнее равенство является свойством PR, но если при умножении матрицы на вектор
получается исходный вектор, то он является соб\-ствен\-ным для данной матрицы. Таким образом,
PR можно также считать как соб\-ствен\-ный вектор для матрицы $L$.

\subsection{Векторная модель}
Рассотрим коллекцию документов, каждый из которых является списком слов. Пусть $TF_{ij}$ ---
частота терма, то есть относительная доля слова $i$ в тексте $j$; $IDF_i$ --- обратная
встречаемость в документах, то есть величина, обратная числу документов содержащих слово
$i$. Составим матрицу $M$ с элементами $m_{ij}=TF_{ij}\cdot IDF_i$. Элемент матрицы определяет
на сколько слово подходит документу, а благодаря множителю $IDF_i$ будут цениться редкие слова.

\subsection{Сингулярное разложение матриц}
\par Введем определение сингулярного разложения. Пусть $A$ --- матрица $m\times n$.
Разложение $A=USV$ называется сингулярным, если $U$ --- ортогональная матрица
$m\times m$, $V$ --- ортогональная матрица $n\times n$, а $S$ ---
диагональная матрица $m\times n$. Отметим несколько фактов касательно сингулярного
раз\-ло\-же\-ния.
\begin{enumerate}
\item Для каждой матрица $A$ можно вычислить сингулярное разложение, причем числа,
стоящие на диагонали $S$ --- корни из собственных чисел $AA^T$. Если же
матрица $A$ квадратная, то диагональ $S$ --- собствные числа $A$.
\item Если $S'$ --- матрица $S$, в которой оставили только $k$ наибольших чисел, 
то $US'V$ --- самое близкое приближение матрицы $A$ имеющее ранг $k$.
\end{enumerate}

\subsection{Применение сингулярного разложения}
\par Размер матрицы документы-слова имеет порядок $10^{10}\times 10^6$, однако,
эта матрица очень разряжена, поэтому для нее можно посчитать приближение ранга
100, используя сингулярное разложение. В получившейся матрице выделим 100
линейно-независимых строк, назовем их обобщенными сло\-ва\-ми; и 100 линейно-независимых
столбцов, назовем их обобщенными до\-ку\-мен\-та\-ми. Теперь любой документ можно представить
как линейную ком\-би\-на\-цию выбранных стобцов, тоже верно и для слов со строками. Таким
образом теперь мы перешли от базица из $10^6$ слов к базису. Обобщенные слова и документы
также называюь ``собственными смыслами''.
\par С помощью собственных смыслов можно решить следующие задачи:
\begin{itemize}
\item Поиск ``похожих'' слов и ``похожих'' документов, так как у них будет похожее
разложение по базису.
\item Учитывая предыдущий пункт, можно тематически классифицировать документы
исходя из разложения. Данную классификацию можно использовать при подсчете
PageRank.
\item Также можно организовать фильтрацию при выводе результатов поис\-ка, например введя поле
``spam''.
\end{itemize}

\section{Поисковая оптимизация}
\par Поисковая оптимизация --- это необходимый комплект действий над сайтом, направленный
на улучшение нахождения сайта поисковиками. Цель поис\-ко\-вой оптимизации ---
вывод сайта в первую десяку ответов поисковых запросов по ключевым запросам. Отметим, что
это не обязательно произой\-дет, а иногда оптимизационны действия могут быть воспирняты
поис\-ко\-ви\-ка\-ми как ``накрутка'' и приведут к обратному эффекту. Для крупных сайтов уда\-ле\-ние
из каталога (одно из возможных действий поисковика) может првести к огромным убыткам:
например, для сайта по торговле недвижимостью невывод в перво тройке запросов может
првести к убыткам измеряемым десятками тысяч долларов.

\subsection{Этапы поисковой оптимизации}
\begin{itemize}
\item Предвартельный этап. На этом этапе идет анализ тематического сег\-мен\-та, сайта 
(обдумываем будующее содержание), поиск ниши по\-зи\-цио\-ни\-ро\-ва\-ния (как подать сайт),
составление семантического ядра запросов (определение основных запросов, при которых
хотим по\-па\-дать в первую десятку; стоит внимательно отнестись к синонимам --- это позволит
улучшить результаты поиска).
\item Оптимизация под аудиторию. Основную часть этого этапа составляет работа с
содержанием. Во-первых, необходимо обртить внимание на тексты, так как индексация идет
именно по словам. Во-вторых, на\-ли\-чие на сайте дополнительных сервисов привлечет
дополнтельную ауди\-то\-рию. В-третьих, можно привести к специальному виду --- текст
хорошо читается, но при этом содержит много слов из ключевых зап\-ро\-сов (SEO копирайтинг).
\item Оптимизация под поисковые запросы. На данном этапе сайт под\-го\-тов\-ка сайта к индексации.
Перечислим некоторые пункты.
\begin{itemize}
\item Запрет индексации некоторых страниц. Это делается для того, чтобы сайт не находился
по ненужным словам. В качестве при\-ме\-ра можно приведем большой сайт-каталог, в котором в том
числе было описание телефона Nokia, этот сайт находился именно по запросу про этот телефон.
Что явно не предусматривалось создателями сайта.
\item Корректировка архитектуры сайта с учетом юзабилити. Нап\-ри\-мер, добиться
того, чтобы с главной страницы до любой можно было дойти за три--четыре клика,
причем было бы легко до\-га\-дать\-ся, куда надо кликать.
\item Работа над внутренними факторами. Заполнить тэги ``description'', ``keywords'', ``title''. В
последнем тэге полезной может ока\-зать\-ся структура: ``название сатйа'' - ``название раздела'' -
``наз\-ва\-ние страницы''.
\item Визуальное и архитектурное (то есть выделение ``тэгами'') вы\-де\-ле\-ние ключевых слов. Напомним, что при
поиске слова вы\-де\-лен\-ные тэгами имеют более высокий приоритет по сравнению с обычными.
\item Корректировка текстов с точки зрения наличия ключевых слов и читаемости. С одной стороны,
нельзя допустить, чтобы тест из-за обилия ключевых слов стал нечитаемым. С другой, каким
бы замечательным с точи зрения литературы не был текст, но если в нем отсутствуют ключевые
слова, то проиндексируется он плохо.
\item Работа над описанием сайта для каталогов, обмена ссылками и прочего.
\item Работа над внешними факторами. Сюда входят: регистрация в посковиках, каталогах, повышение
тематической авторитетности сайта (например ссылка из новостной ленты сайта lenta.ru будет высоко
цениться поисковиками при подсчете PageRank).
\end{itemize}
\item Поддержка сайта. На этом этапе идет анализ достигнутых результатов и дальнейшая корректировка
сайта. Также имеет смысл разместить рекламу. При ее размещении стоит учесть аудиторию сайтов, где
рек\-ла\-ма будет размещена. Ведь если ваш сайт посвящен ``искусству бон\-сай'', то вряд ли имеет смысл
размещать рекламу на сайтах по\-свя\-щен\-ных ``спорту'', то есть тематика сайтов должна быть схожа. Ин\-те\-рес\-ным
примером продвижения сайта является премия учрежденная А. Лебедевым, когда он еще был никому не известен.
Он организовал премию и раздал ее всем крупнейшим сайтам вместе с баннером, на котором была надпись
``Лауреат премии лучший сайт'', и ссылочкой на сайт Лебедева. Как результат огромное количество ссылок
на сайт со страниц с высоким PageRank.
\end{itemize}

\section{Ссылки по SEO}

\textbf{Где учиться:}
\begin{itemize}
 \item SearchEngines.Ru
 \item SearchEngineWatch.Com
 \item http://seotext.ru
 \item SEO in Wikipedia.Org
 \item Ralph Wilson Checklist
 \item Энциклопедия Интернет Рекламы
\end{itemize}
\textbf{Эффективный поиск в интернете:}
\begin{itemize}
 \item http://logic.pdmi.ras.ru/\~{}yura/search.html
\end{itemize}

\end{document}






























