Текст книги "Яндекс для всех"
Автор книги: М. Абрамзон
Жанр:
Интернет
сообщить о нарушении
Текущая страница: 2 (всего у книги 37 страниц) [доступный отрывок для чтения: 14 страниц]
В статье, посвященной поисковой машине Rambler (http://www.rambler.ru/ doc/architecture.shtml), называются основные характеристики, которые могут быть применены к любым поисковикам:
□ полнота;
□ точность;
□ актуальность;
□ скорость;
□ наглядность.
Полнотапоиска характеризуется отношением количества найденных по запросу документов к общему количеству документов в Интернете, соответствующих данному запросу. Если по запросу «кристаллическая решетка» будет найдено 150 документов, а общее количество документов в Интернете, соответствующее этому запросу, составляет 1000, то полнота поиска составит 0,15. (Эта величина приблизительная, поскольку неизвестно точно, сколько же на самом деле существует в Интернете страниц, отвечающих условию поиска.) Чем более полно проанализированы и занесены в Индекс документы, тем выше будет показатель полноты поиска.
Точностьпоиска определяется как степень соответствия найденных документов запросу пользователя. Допустим, мы хотим найти документы, в которых встречается выражение «сын знахаря». В результатах поиска мы увидим документы, в которых встречается точно такое выражение. Но присутствуют и документы, содержащие искомые слова, но не выражения, например: "родители привозят сынав небольшой городок на Адриатическом побережье, к местному знахарю". И если всего найдено 200 документов, из которых только в 80 встречается именно искомое словосочетание, то точность поиска будет оценена как 80/200 (0,4). Чем точнее поиск, тем выше вероятность, что пользователь найдет нужные документы, тем меньше будет избыточной, лишней информации.
Для повышения точности результата в различных поисковых системах применяются различные способы. Каждый поисковик использует свои решения, в целом предназначенные для выполнения близких по сути задач. К примеру, вот что по этому поводу сказано на сайте Рамблера:
Повышение точности в поисковой машине Рамблер достигается за счет использования различных технологий на всех этапах обработки и поиска информации. Одним из наиболее интересных процессов является распознавание грамматических омонимов. Омонимы– это слова, которые имеют одинаковое написание, но различный смысл. Различают лексические и грамматические омонимы. Лексические омонимы относятся к одной части речи, как, например, существительное «бор»: хвойный лес, стальное сверло и химический элемент. Грамматические омонимы относятся к разным частям речи, поэтому по написанию у них обычно совпадают только отдельные формы. Примерами грамматических омонимов могут служить слова «печь» (существительное русская печьи глагол печьпирожки) и «рядовой» (прилагательное рядовойсотрудник и существительное рядовойИванов).
Омонимы не только увеличивают размер индексной базы (так как для каждого такого слова приходится хранить все его возможные значения), но и отрицательно сказываются на точности поиска. Если пользователь ищет слово "данные", ему неинтересно получить в найденном все документы, которые содержат слово "дать". Для того чтобы результаты поиска были точнее, модуль синтаксического анализа проводит разбор окружения слов-омонимов с целью установления их наиболее вероятных значений. Например, если рядом со словом "печь" стоит существительное ("пирожки", "картошка"), то с высокой вероятностью "печь" в данном контексте является глаголом. На сегодняшний день анализатор способен распознавать значения только грамматических омонимов.
Синтаксический анализ позволяет также с определенной вероятностью распознавать некоторые имена собственные. Например, если в тексте несколько слов подряд написано с большой буквы, они чаще всего представляют собой имя собственное (Петр Петрович, Московский Государственный Университет). Данные о таких конструкциях учитываются при индексации и обработке запроса.
Еще один способ повышения точности поиска – это выделение устойчивых обозначений и поиск их как отдельных лексических единиц. На сегодняшний день в Рамблере реализована система распознавания таких конструкций, как, например C++, б/у, п/п-к. Если по запросу С++ поднимать все тексты, в которых присутствуют латинская буква С, а также знак +, то получится огромное количество документов, далеко не все из которых соответствуют запросу; кроме того, это большая работа, значительно увеличивающая время поиска.
Источник: «Принципы работы поисковой машины Рамблер» (http://www.rambler.ru/doc/architecture.shtml).
А вот что на эту же тему пару лет назад сказал И. Сегалович, директор Яндекса по технологиям и разработке:
Алгоритм поиска учитывает социальную структуру Интернета. Он умеет отличать мнение людей от технической, вспомогательной и рекламной информации, то есть лучше распознавать, какой ресурс является авторитетным в своей области. Также введена дополнительная очистка результатов поиска от дубликатов. Теперь пользователь избавлен от повторения в списке найденного почти одинаковой информации. Поиск в Интернете – это серьезная наука, поэтому для повышения качества сервиса в Яндексе проводятся регулярные исследования. В прошлом году мы организовали отдел асессоров– пользователей, которые систематически по заданной методике оценивают релевантность результатов. Обратная связь от асессоров дает нам возможность настраивать параметры алгоритма ранжирования и увеличивать точность поиска. Стало удобнее работать с региональной информацией. Теперь Яндекс автоматически определяет, в каком городе находится компьютер, с которого поступил запрос, и, если уточнение по региону имеет смысл, предлагает повторить поиск, ограничив его сайтами данного региона. Поиск поддерживает шесть языков – к русскому и английскому добавились украинский, белорусский, французский и немецкий. Язык документов и сайтов определяется автоматически, а ограничить область поиска нужным языком можно в настройках или расширенном поиске. Расширенный поиск стал проще и функциональней, заданные с его помощью ограничения теперь видны на странице найденных результатов. Благодаря «умной подсказке» пользователи расширенного поиска смогут увидеть сформированный запрос, как если бы он был задан на русском языке.
Какова психология того, кто ищет информацию? Считается, что наиболее подходящие (релевантные) документы должны быть на первой-второй страницах результатов поиска. Если количество полученных результатов больше, человек вряд ли будет просматривать остальные страницы. И даже если в числе найденных есть документ, полностью отвечающий заданным условиям, но находится он на странице из второго десятка, ищущий этот документ не увидит – он просто не дойдет до этой страницы. Поэтому громадное значение приобретает и ранжированиедокументов в результатах поиска по их релевантности запросу.
По поводу релевантности Яндекс говорит, что это "соответствие ответа вопросу", но при этом важны две составляющие – полнота (ничто не забыто) и точность (отсутствие лишнего).
Релевантность различают как содержательную и формальную. Воспользовавшись словарями, представленными в Яндексе, предложу определения этих понятий:
□ содержательнаярелевантность – соответствие документа информационному запросу, определяемое неформальным путем;
□ формальнаярелевантность – соответствие, определяемое алгоритмически путем сравнения поискового предписания и поискового образа документа на основании применяемого в информационно-поисковой системе критерия выдачи.
В простейшем случае, релевантность текста определенному запросу – это процент вхождения запроса к общему объему текста. Для поисковых систем высокорелевантным текстом считается такой, где вхождение запроса в текст примерно равно 4–7 % – меньшего может не хватить, большее чревато тем, что система сочтет текст за поисковый спам и наложит на страницу некий понижающий фильтр или может вообще убрать страницу из результатов выдачи по искомому запросу.
Конечно, каждая поисковая система использует гораздо более сложные способы вычисления релевантности документов запросу пользователя. Тем не менее, несмотря на то что алгоритмы у всех поисковых машин разные, они построены на общих принципах – основные отличия результатов выдачи заключаются не в алгоритмах определения релевантности, а в конкретных способах реализации этих алгоритмов.
Какие же факторы, помимо вхождения слов запроса в текст документа, оказывают дополнительное влияние на его место среди других документов? Каждая поисковая машина, стремясь привлечь качеством выдачи запрашиваемой информации, разрабатывает собственные критерии подсчета релевантности. Это и плотность ключевых слов на странице, и разделы страниц, где находятся эти слова, объем содержания, тексты заголовков и ссылок и многое другое. Учитываются и такие рассчитываемые показатели сайтов, как индекс цитирования, тематический индекс цитирования, Page Rank. И при этом происходит постоянное изменение степени влияния на результаты тех или иных параметров, их состав и принцип расчета.
1.2. Как устроена поисковая машина Яndex
Поисковая машина Яndex относится ко второму рассмотренному ранее типу поисковых машин. У Яndexа есть свои пауки-агенты, есть свой Индекс и поисковый механизм. Эта поисковая машина ориентирована в первую очередь на российскую часть всемирного Интернета, т. е. индексируются в ней русскоязычные сайты, расположенные в доменах ru и su. Сделаны небольшие исключения для наиболее авторитетных зарубежных сайтов. Сложнее с русскоязычными сайтами, которые зарегистрированы в международных или региональных (государственных) доменах других стран – com, org, de, us и других, но они все же попадают в Индекс и учитываются при поиске.
Большинство значимых зарубежных нерусскоязычных сайтов может быть найдено по ссылке, при этом, в отличие от русскоязычных сайтов, в Индекс они не попадают. Упрощается ситуация в том случае, когда у компаний, таких как BMW, IBM и многих других, появляются русскоязычные версии сайтов, без проблем индексируемые Яндексом.
Поисковая машина – самый востребованный ресурс Яндекса. Ежедневно его посещают около четырех с половиной миллионов посетителей, при этом количество просмотренных поисковых страниц приближается к сорока миллионам. При этом пользователи, выполняющие на нем поиск, этого не замечают – складывается впечатление, что Яндекс работает индивидуально для каждого из них.
Так, при запросе средней "тяжести", то есть при поиске не очень частотного слова, время отклика системы (без учета времени передачи данных по каналу от поисковой системы к пользовательскому компьютеру) исчисляется десятыми долями секунды.
В условиях постоянного роста количества пользователей и их запросов главной задачей поисковой машины является сохранение приемлемых с точки зрения пользователей скорости и полноты выполнения запросов. Эта задача решается несколькими способами, каждый из которых является необходимым, но не достаточным в отрыве от других. Способы достижения высоких результатов на сегодня применяются следующие:
□ оптимизация базовых поисковых алгоритмов и архитектуры поиска;
□ регулярное увеличение мощностей вычислительных ресурсов поисковой системы;
□ использование архитектурной возможности масштабирования системы.
Оптимизация поисковых алгоритмов проводится постоянно. Результаты таких работ вводятся в действие до двух раз в год. Сказывается их внедрение на уменьшении нагрузки на поисковую машину (в год эта величина составляет 20–30 %), а также на уменьшении времени отклика.
Увеличение мощности – это постоянное обновление используемого оборудования. Сюда входит и переход на более мощные процессоры, увеличение оперативной памяти, увеличение объемов дисковых хранилищ. Способ хотя и необходимый, но крайне затратный. Результативность выполненного апгрейда можно косвенно оценить увеличением объема поисковой базы, находящейся в его распоряжении.
Третий способ – использование мастшабируемости системы. В двух словах суть его заключается в том, что каждый уровень системы распараллеливается на несколько одинаковых узлов. Например, при наличии десяти поисковых серверов, обрабатывающих поступающие запросы, очередной запрос будет направляться на тот из них, которых в данный момент времени будет свободен.
Аналогично обстоит дело и со сбором информации. Этим занимается робот-паук, который обходит страницы с заданными URL и скачивает их в базу данных, а затем архивирует и перекладывает в хранилище суточными порциями. Робот размещается на нескольких машинах, и каждая из них выполняет свое задание. Так, робот на одной машине может качать новые страницы, которые еще не были известны поисковой системе, а на другой – страницы, которые ранее уже были скачаны не менее месяца, но и не более года назад.
Хранилище у всех машин едино.
При необходимости работу можно распределить другим способом, например, просто распределив между роботами всю работу, учитывая лишь ее объемные показатели. Параллельная работа программы позволяет легко выдерживать дополнительную нагрузку – при увеличении количества страниц, которые нужно обойти роботу, достаточно просто распределить задачу на большее число машин.
В хранилище информация в сжатом виде собирается и разбивается на части. Эти части постепенно распределяются между множеством машин, на которых запущена программа-индексатор. Как только индексатор на одной из машин заканчивает обработку очередной части страниц, он обращается за следующей порцией. В результате на первом этапе формируется много маленьких индексных баз, каждая из которых содержит информацию о некоторой части Интернета. При увеличении нагрузки на машины, занимающиеся индексированием, проблема может быть решена простым добавлением машин в систему.
После того как все части информации обработаны, начинается объединение (слияние) результатов. Основная база участвует в анализе как одна из частей нового индекса. Так, если объединяются 70 новых частей, то в анализе участвует 71 фрагмент (70 новых + основная база предыдущей редакции). Специальная программа ("сливатор") составляет таблицы перенумерации документов базы. Содержимое всех частей объединяется. Среди страниц с одинаковыми адресами выбирается наиболее свежая версия; если при скачивании URL последней информацией была ошибка 404 (запрашиваемая страница не существует), она временно удаляется из индексной базы. Параллельно осуществляется склейка дублей – страницы, которые имеют одинаковое содержимое, но различные URL, объединяются в один документ.
Сборка единой базы из частичных индексных баз представляет собой простой и быстрый процесс. Сопоставление страниц не требует никакой интеллектуальной обработки и происходит со скоростью чтения данных с диска. Если информации, которая генерируется на машинах-индексаторах, получается слишком много, то процедура "сливания" частей проходит в несколько этапов. Вначале частичные индексы объединяются в несколько промежуточных баз, а затем промежуточные базы и основная база предыдущей редакции пересекаются. Таких этапов может быть сколько угодно. Промежуточные базы могут сливаться в другие промежуточные базы, а уже потом объединяться окончательно. Поэтапная работа незначительно замедляет формирование единого индекса и не отражается на качестве результатов.
Источник: «Принципы работы поисковой машины Рамблер» (http://www.rambler.ru/doc/architecture.shtml).
А вот что рассказывали о решении аналогичных задач на Яндексе.
1.2.1. «Пауки»Если применить к поиску на Яндексе традиционные термины Distributed Information Retrieval, то можно выделить следующие приемы распараллеливания.
1. Разделение коллекции документов– начиная с весны 2000 года, в Яндексе используется «параллельный поиск» в нескольких поисковых источниках. Параллельный поиск– это одновременный поиск в специализированных базах (коллекциях), предлагаемых поисковой системой. Обычно, источник – это отдельная база небольшого размера, отличная от «большой» базы документов. Подразумевается, что документы, индексируемые в такой базе, имеют некоторую регулярную структуру. Если при поиске по обычной базе находятся и документы из базы параллельного поиска, точно соответствующие запросу, то одновременно (параллельно) с обычным результатами поиска выдается список из нескольких найденных документов. База параллельных источников имеет существенно меньший размер, чем база веб-поиска. Обход и индексация документов в ней осуществляется отдельным роботом, поэтому обновление базы может происходить очень быстро (вплоть до ежеминутного).
В "Яндексе" есть четыре базы параллельного поиска:
• по новостям (обновление каждые 10 минут, ежедневно около 3000 новостей);
• по товарным предложениям интернет-магазинов (ежедневное обновление, примерно 300 000 товаров);
• по заголовкам статей энциклопедий (обновление раз в месяц, около 200 000 статей);
• по каталогу ("ручному" описанию веб-ресурсов).
Особый интерес с точки зрения традиционных поисковых технологий представляет техника разделения большой базы документов, то есть собственно базы веб-страниц. По состоянию на 2002 год она состояла из 60 млн документов и была разделена на 30 частей.
Среди особенностей текущей реализации разделения веб-коллекции в Яндексе можно отметить следующее:
• есть центр контроля и распределения URL;
• отсутствует репликация коллекции по машинам;
• распределение документов по коллекциям случайно.
2. Первая фаза обработки запроса: выбор коллекции, трансформации запроса– пользователь может явно указать, в какой коллекции следует искать. Если этого не сделано, то на основе лингвистического (точнее, эвристического) анализа запроса Яндекс может сделать допущение о приоритете специализированной коллекции или подходящей к характеру запроса рубрики каталога.
3. Вторая фаза обработки запроса: раздача запроса по коллекциям– обычно используются все коллекции. Собирающий сервер раздает в коллекции модифицированные запросы, в которых для каждого термина сообщается глобальное значение его обратной частоты(IDf в терминах традиционного IR). Для этого на всех «собирающих» серверах хранится глобальная статистика терминов. Она изменяется медленно, поэтому обновляется относительно редко. Статистика подсчитывается по считающейся наиболее универсальной – вебовской – коллекции. Таким образом, каждая поисковая машина ищет ответ на запрос с назначенными «сверху» глобальными частотами, и значения релевантности, вычисляемые в разных коллекциях, можно считать последовательными и вычисляемыми «в одной системе координат». Модификации запросов этим не ограничиваются, и для специализированных коллекций (например, «энциклопедии») могут быть и другими, в том числе и очень специфическими.
4. Третья фаза обработки запроса: исполнение и ранжирование запроса в коллекциях– запрос выполняется паралельно для всех коллекций.
Следует отметить, что веб-коллекции документов распределены по машинам произвольно и, вообще говоря, могут быть расположены все вместе на одной машине. Слияние результатов производится на том из собирающих (метапоисковых) веб-серверов, на который попадал пользователь при заходе по адресу www.yandex.ru. Процесс раздачи запроса, описанный здесь, позволяет корректно ранжировать слитый результат. При этом не требуется переранжирование результатов, полученных из разных неоднородных коллекций с использованием локальных IDF, а также не нужен динамический обмен данными между источниками для вычисления глобальнойIDF.
Мы ищем в Яндексе информацию и новости, картинки и значения слов, товары и услуги. На сегодняшний день в базе данных накоплена информация о миллионах документов и сайтов, огромном количестве новостей, графических изображений, сотнях тысяч предлагаемых товаров и услуг. За обновление информации в ней отвечают различные роботы.
Вот они, те роботы, которые выполняют основную работу по поиску и индексированию информации:
□ Yandex/1.01.001 (compatible; Win16; I) – основной индексирующий робот;
□ Yandex/1.01.001 (compatible; Win16; P) – индексатор картинок;
□ Yandex/1.01.001 (compatible; Win16; H) – робот, определяющий зеркала сайтов;
□ Yandex/1.02.000 (compatible; Win16; F) – робот, индексирующий пиктограммы сайтов (favicons);
□ Yandex/1.03.003 (compatible; Win16; D) – робот, обращающийся к странице при добавлении ее через форму "Добавить URL";
□ Yandex/1.03.000 (compatible; Win16; M) – робот, обращающийся при открытии страницы по ссылке "Найденные слова";
□ YaDirectBot/1.0 (compatible; Win16; I) – робот, индексирующий страницы сайтов, участвующих в рекламной сети Яндекса.
А кроме них есть и несколько агентов, которые занимаются проверкой доступности сайта или документа, на который стоит ссылка в соответствующем сервисе. Их тоже несколько:
□ Yandex/2.01.000 (compatible; Win16; Dyatel; C) – "простукивалка" Яндекс. Каталога. Если сайт недоступен в течение нескольких дней, он снимается с публикации. Как только сайт начинает отвечать, он автоматически появляется в Каталоге.;
□ Yandex/2.01.000 (compatible; Win16; Dyatel; Z) – "простукивалка" Яндекс. Закладок. Ссылки на недоступные сайты помечаются серым цветом;
□ Yandex/2.01.000 (compatible; Win16; Dyatel; D) – "простукивалка" Яндекс. Директа. Она проверяет корректность ссылок из объявлений перед модерацией. Никаких автоматических действий не предпринимается;
□ Yandex/2.01.000 (compatible; Win16; Dyatel; N) – "простукивалка" Яндекс. Новостей. Она формирует отчет для контент-менеджера, который оценивает масштаб проблем и, при необходимости, связывается с партнером.
Если о наименованиях роботов информация не является закрытой (в любом случае, ее можно обнаружить в логах сайтов, которые эти роботы посещали), то сведения о том, на каком сетевом адресе работает тот или иной робот, закрыты. Связано это с необходимостью уменьшить вероятность некорректного использования этой информации в целях продвижения сайтов. С этой же целью сетевые адреса время от времени изменяются.
Зачем эта информация нужна вам? Если вы являетесь владельцем сайта, и у вас установлен механизм, собирающий информацию о ваших посетителях, в эти данные попадет и информация о посетивших ваш проект роботах. Вы будете в курсе, какие роботы и когда вас посещали и какие страницы просматривали.
