С 7 апреля по 13 мая проходил очередной учебный курс от ТопЭксперт.РФ – Полный курс SEO – 150 часов.

Курс вели признанные эксперты и аналитики, имеющие большой практический опыт и выдающиеся достижения в области поискового продвижения и информационного поиска – Андрей Калинин (Mail.ru), Михаил Сливинский (Wikimart.ru), Алексей Чекушин (Wikimart.ru), Станислав Поломарь (Web-IT) и Леонид Гроховский, руководитель учебного центра ТопЭксперт.РФ. Слушателями курса были начинающие и опытные оптимизаторы, желающие приобрести или значительно повысить свою квалификацию.

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

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

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

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

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

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

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

- Машинный перевод

- Извлечение мнений

- Распознавание речи

- Синтез речи

- Организация диалога с пользователем

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

И здесь далеко не все так просто. У человека есть задача – попасть в клуб RAЙ. Он думает, что его информационная потребность заключается в том, чтобы узнать месторасположение этого клуба. Он формулирует эту потребность словесно: «Где находится клуб Рай?», а затем вводит в поисковую строку запрос [рай]. Вопрос: удовлетворит ли полученный результат его информационную потребность, поможет ли решить задачу? Ответ: нет.

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

Булевский поиск.

Булевский поиск – это самая первая модель поиска, которая оставалась популярной на протяжении более 30 лет. Ее принципы заключаются в следующем:

- Запросы, которые задает пользователь = булевские выражения, предикаты

Например, Brutus и Caesar, но не Calpurnia

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

Результаты булевского поиска по запросу будут такими:

Возникает вопрос: Google, Яндекс, Поиск@Mail.ru – булевские?

В современном поиске может быть так, что запрос [w1 w2 … wn] интерпретируется как w1 AND w2 AND … AND wn , но можно получить документ и без wi – когда в строку запроса вводятся ссылки, разные варианты wi (морфология, опечатки, синонимы), слишком длинные запросы… В этих случаях булевский поиск вернет мало документов, поэтому современные поисковики позволяют себе уход от четко заданной булевской формулы предиката. Но самое главное отличие современного поиска – это то, что он ранжированный. Какое бы количество документов не было найдено по запросу, всегда наиболее важны только первые 10, то, что помещается на страницу, то, что увидит пользователь.

Обратный индекс.

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

Слева на слайде представлен словарь корпуса документов, а справа – координатные блоки, отсортированные по docID:

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

1. Извлечение текста из документа

2. Токенизация (последовательность пар - термин, DocID)

3. Сортировка (по терминам и по DocID)

4. Лингвистическая обработка (морфологический механизм, который из разных токенов делает один термин)

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

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

Но это не означает, что булевский поиск лучше.

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

Токен – выделенная строка символов, как они появляются в тексте.

Термин – «нормализованный» токен (регистр, морфология, исправленные ошибки и т.п.)

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

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

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

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

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

Простейшее дерево – бинарное:

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

Особое внимание Андрей уделил рассказу об исправлении орфографии в документах и запросах.

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

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

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

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

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

Алгоритм Soundex:

- Превратить каждый токен в 4-х символьную сокращенную форму.

- То же самое сделать для терминов запроса.

- Построить и использовать отдельный индекс сокращенных форм.

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

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

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

Анализ встречающихся в запросах ошибок показал, что 33,7% из них – орфографические, 10% - опечатки, 18% - транслитерация, 12% - неправильно написанные фамилии или бренды, 8,9% - иностранные слова и т.д.

Общая идея исправления опечаток такова:

1. Разбить запрос на части

2. Для каждой части составить список вариантов замен.

3. Оценить вес каждой замены.

4. Составить граф слов.

5. Найти оптимальный путь в графе.

Примеры графов слов:

Следующая часть лекции была посвящена алгоритмам индексирования. Андрей Калинин рассказал о двух алгоритмах индексирования: BSBI (наивном) и SPIMI (лучше масштабируемом). А также подробно остановился на распределенном индексировании – MapReduce.

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

Индекс можно разделить на части:

- По терминам.

- По документам.

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

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

Андрей привел в пример Google, дата-центры которого распределены по всему миру. Дата-центры Google – это 1 млн серверов и 3 млн процессоров/ядер. Это 10% вычислительной мощности всего мира.

Как же это все поддерживает стабильности поиска? Если в системе с 1000 узлами каждый узел имеет 99.9% рабочего времени, сколько рабочего времени будет иметь вся система?

Ответ: 63%

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

Ответ: меньше двух минут.

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

Модель параллельных вычислений MapReduce – это надежная и простая модель для распределенных вычислений, без необходимости писать много кода для параллелизма. Индексатор Google (образца 2002) состоял из нескольких фаз, каждая из которых была реализована в модели MapReduce.

После демонстрации студентам фотографий Google образца 1997 года и дата-центра образца 2000-го, Андрей перешел к самой интересной и долгожданной части лекционного курса – рассказу о ранжированном поиске.

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

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

Далее разговор пошел о текстовом ранжировании документов, об учете количества термина в документе и в массиве документов. Было подробно рассмотрено ранжирование tf-idf, его достоинства и недостатки, а также модификации tf-idf.

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

Как происходит классификация поисковых запросов? Каковы требования и рекомендации к поведению роботов-«пауков»? Что такое ссылочное ранжирование и какую роль играют алгоритмы PageRank и HITS?... На эти и на многие другие вопросы (например, дает ли наличие сайта в каталоге Mail.ru преимущество в ранжировании?) в течение лекций студенты получили исчерпывающие ответы от Андрея Калинина.

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

О том, чему учили студентов курса Михаил Сливинский, Алексей Чекушин и Станислав Поломарь, как происходила подготовка и защита диплома – читайте в наших следующих обзорах.