Поисковые технологии *

Это не шутка, действительно, разработчики сервиса Google Analytics добавили новый инструмент для отслеживания посещаемости любого ресурса в режиме реального времени. Новый инструмент получил собственное название — Google Analytics Real-Time. Сервис доступен только в новой версии интерфейса, так что если вы еще работаете в старом, меняйте привычки. Конечно, если вам нужно отслеживание в режиме реального времени.

В мае 2011 года Google запустил поиск авиарейсов в виде текстовой подсказки при поисковом запросе (работает в том числе на русском языке для местных авиамаршрутов). Уже тогда стало ясно, что компания серьёзно работает в данном направлении и скоро турагентам придётся искать новую работу¹.

И продолжение не заставило долго ждать. Вчера открылся полноценный поиск авиабилетов с нормальным интерфейсом Google Flights. Он пока ограничен территорией США.

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

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

Теперь же «пробоину» нашли в Google: например, такой запрос [9999999..99999999999999999999999] блокируется Гуглом. Вместо девяток могут быть и другие числа.

Это специфический формат запроса X..Y, который включает все числа в диапазоне от X до Y. Версию о том, что диапазон чисел слишком велик и поэтому система не справляется с запросом, можно отбросить.

Путешествовать — это не всегда дорого, и многие знают это на личном опыте. Способы сэкономить существуют разные, но один из самых популярных сейчас — если вы не готовы жертвовать сервисом, путешествуя «дикарём» или скоростью, отправляясь в путь на машине, — является так называемый «чип трип» (от cheap trip – «недорогое путешествие»). Даже самые лучшие курорты редко бывают заполнены круглый год: серьезный поток посетителей приходится на праздники и сезон отпусков, в остальное же время в отелях остается много незанятых мест. В этот период номера сдаются со значительными скидками, и турагентства не упускают возможности предоставить своим клиентам «горячие» путевки по сильно сниженным ценам. Разумеется, это никак не сказывается на качестве предлагаемого сервиса. Отдых по таким путевкам и называется чип трипом. Спецификой таких туров являются ограниченные сроки, но, чем ближе дата отправления, тем дешевле обойдется путевка, поэтому клиент всегда остается в выигрыше.

Клуб путешественников

Запущенный буквально на днях, в начале августа, проект FAN TRIP представляет собой агрегатор дешёвых путёвок. Схема работы проекта проста: вы находите для себя интересный вариант, выкупаете турпакет и отправляетесь в поездку. Однако создатели проекта хотят выйти за рамки интернет-магазина путешествий, и позиционируют себя как клуб любителей дешёвых туров, в котором вокруг собственно поиска и продажи путёвок выстраивается целая инфраструктура: возможность поиска попутчиков, партнерская программа, оффлайновые клубные мероприятия, накопительная и бонусная система.


Отдых — он на самом деле рядом, только руку протяни

Апорт — один из старейших поисковиков Рунета, теперь (как и Рамблер) тоже использует поиск Яндекса.



Даже немного жаль… В свое время он был весьма и весьма неплох — я лично некоторое время использовал его в качестве основного поиска.

Вчера в Санкт-Петербурге открылась 5-я юбилейная летняя школа по информационному поиску — RuSSIR'2011 при поддержке СпбГУ и РОМИП.

В этом году мы не только выступили «Золотым спонсором», но и наш эксперт — Андрей Калинин, руководитель разработки Поиска@Mail.Ru прочитает практическую лекцию на тему борьбы с поисковым спамом.

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

От проекта Поиск@Mail.Ru каждый участник получит набор открыток со смешными и понятными зачастую только профильным специалистам задачками по информационному поиску.

Смотрите, какие прикольные задачки:

Пользователи сообщают, что по некоторым запросам Bing выдаёт что-то вроде «синего экрана смерти». Результат выглядит примерно так:



В кэше Гугла можно найти массу таких нечитаемых сообщений об ошибке Bing. Что это такое?

Поиск по картинкам Google Image Search дополнился новой функцией: меню с расширенной информацией об изображении. Теперь, если файл содержит метаданные EXIF, то некоторые из них демонстрируются прямо в окне с поисковыми результатами, в том числе дата съёмки, модель фотоаппарата и параметры съёмки (выдержка, диафрагма, ISO, фокусное расстояние, использование вспышки, настройки экспокоррекции).

К сожалению или к счастью, Google не показывает остальные метаданные (например, координаты GPS и идентификационный номер фотоаппарата) и не позволяет искать фотографии по этим параметрам. Хотя это было бы удобно — можно было бы посмотреть все фотографии, сделанные в данном конкретном месте или конкретным фотоаппаратом. Вся эта информация наверняка есть в кэше Google, но такую функцию уже можно было назвать нарушением приватности.

Полное содержание и список моих статей по поисковой машине будет обновлятся здесь.

В предыдущих статьях я рассказывал про работу поисковой машины, вот и дошел до сложного технически момента. Напомню что разделяют 2 типа индексов – прямой и обратный. Прямой – сопоставление документу списка слов в нем встреченного. Обратный – слову сопоставляется список документов, в которых оно есть. Логично, что для быстрого поиска лучше всего подходит обратный индекс. Интересный вопрос и про то, в каком порядке в списке хранить документы.

На предыдущем шаге DataFlow от модуля-индексатора мы получили кусочек данных в виде прямого индекса, ссылочной информации и информации о страницах. Обычно у меня он составляет около 200-300mb и содержит примерно 100 тысяч страниц. Со временем я отказался от стратегии хранения цельного прямого индекса, и храню только все эти кусочки + полный обратный индекс в нескольких версиях, чтобы можно было откатиться назад.

Устройство обратного индекса с виду, простое, – храним файл, в нем в начале таблица адресов начала данных по каждому слову, потом собственно данные. Это я утрировано. Так получается самый выгодный для оптимизации скорости поиска формат — не надо прыгать по страницам — как писали Брин и Пейдж, — 1 seek, 1 read. На каждой итерации перестроения, я использую 20-50 кусочков информации описанных выше, очевидно загрузить всю инфу из них в память я не могу, тем более что там полезно хранить еще кучу служебных данных об индексе.

Ну вот одна из самых вкусных частей БД – она хранит миллиарды разных ссылок, и производит доступ к ним в произвольном порядке.

Сначала очевидно можно заметить что все URL сгруппированы в рамках сайта, т.е. все ссылки внутри 1 сайта можно хранить вместе для скорости. Я выделил URL сайта, и стал хранить список сайтов отдельно – сейчас их 600 тыс и отдельная таблица БД описанной раньше легко с ними справляется. В памяти постоянно находится AVL дерево с CRC всех известных сайтов, и проверяя первым делом существование URL я получаю ID сайта ему соответствующего, если он уже есть в базе.

Остальную часть ссылки – кроме названия сайта я отрезаю, и считаю CRC для нее, назовем ее Hash. Таким образом любая ссылка относительно однозначно имеет индекс (ID сайта, Hash). Все ссылки можно отсортировать по Hash в рамках отдельного сайта, и тогда можно легко искать существующую или нет – пробегать по списку все ссылок данного сайта пока не встретим с нужным Hash или не встретим больший Hash – значит ссылки нет. Ускорение не очень большое, но в 2 раза, все таки, в среднем.

Решил немного описать на мой взгляд самую полезную древовидную структуру. AVL дерево это бинарное дерево (у каждой вершины не более 2 сыновей), в котором каждой вершине присвоен идентификатор (как раз его и хранит дерево), идентификаторы подчиняются следующему правилу: ID левого сына<ID родителя<ID правого сына.
Т.е. если обходить дерево рекурсивно слева направо получим отсортированный по возрастанию список ID, справа налево – по убыванию.
Причем дерево максимально сбалансировано: высота левого поддерева отличается от высоты правого максимум на 1.

Интересно в нем то, что тогда на проверку существования элемента в дереве уходит log(N) N – количество ID. Ведь надо пройти от корня вниз, а поскольку дерево максимально симметрично то его высота — log(N)+1
Хорошая новость – нам никто не запрещает прикрепить к вершине еще какие-то полезные данные и тогда выборка произвольных данных по ID будет занимать log(N) времени
Плохая новость – одинаковые ID как следует из определения в нем существовать не могут. Придется делать финт ушами, один способ сделать вместо каждой вершины список вершин с одинаковым ID, другой – изменить алгоритм балансировки.

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

Итак как минимум будет нужна БД обслуживающая обычные «плоские» («2D») данные – т.е. некоторому идентификатору ID ставится в соответствие поле данных.
Почему поле данных я рассматриваю одно? Потому что:

• выборка производится только по полю ID – поиск по данным не производится. Для этого есть специализированные индексы – иначе с такими количествами информации толку будет мало
• любое количество полей можно упаковать в одно, для этого я «на коленке» создал набор небольших прикладных библиотек, в частности при упаковке сохраняется CRC данных, чтобы не использовать не дай бог битые

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

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

Думаю нет особой причины останавливаться на алгоритме разбора HTML в дерево, тем более, что в обобщенном виде такие парсеры учат писать курсе на 3-4 ВУЗа. Обычный стек, немного фишечек по пропуску аргументов (кроме тех что потом понадобятся), и выходное дерево как результат разбора. Текст разбивается на слова прямо в процессе разбора, и слова отправляются в отдельный список, где запомнены кроме общей информации и все позиции слова в документе. Понятное дело слова в списке уже в 1-й нормальной форме, про морфологию уже писал, здесь просто скопирую из предыдущей статьи.

В продолжение статьи С чего начинается поисковик, или несколько мыслей про crawler

В предыдущей статье я немного порассказал про эксперименты с интенсивностью загрузки и работой Crawler’а, в общих чертах опишу DataFlow проекта до построения индекса, чтобы было понятно о чем я пишу. Каждый шаг я постараюсь описать подробно в соответствующей статье

Итак, скачанная страница первым делом попадает на выделение ссылок. Новые ссылки с текущего сайта попадают в локальную очередь для загрузки в текущей сессии, а на все другие сайты добавляются в общую очередь Crawler’а. В этой очереди содержаться только главные страницы сайтов.

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

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

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

Надо сказать что задача поиска в общем виде не решается – для любого документа имеющего наибольшую релевантность например по слову «работа», можно создать модифицированную копию, которая будет иметь еще лучшую, с точки зрения поисковой машины, релевантность, однако будет полным бредом с точки зрения человека. Вопрос цены и времени, конечно. Из-за обширности Интернета на сегодняшний день таких страниц, мягко говоря, много. Разные системы борются с ними по-разному и с переменным успехом, когда-нибудь искусственный интеллект победит всех нас…

В продолжение начатой темы про собственную поисковую машину

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

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

Когда-то давно взбрела мне в голову идея: написать свой собственный поисковик. Было это очень давно, тогда я еще учился в ВУЗе, мало чего знал про технологии разработки больших проектов, зато отлично владел парой десятков языков программирования и протоколов, да и сайтов своих к тому времени было понаделано много.

Ну есть у меня тяга к монструозным проектам, да…

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

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

Одним движением Google удалил из поискового индекса 11,4 млн сайтов на «бесплатном хостинге» http://co.cc. Пожалуй, это самый крупный массовой бан в истории Google, хотя формально исключён только один домен.

По статистике CO.CC, сейчас у них зарегистрировано 11 393 121 поддоменов, принадлежащих корпоративным и частным клиентам.

И, надо сказать, как раз вовремя — очень многим веб-мастерам приходилось придумывать всякие «костыли» для получения информации о том, сколько же посетителей заходит на сайт из социальных сетей. А теперь разработчики из Google создали интересный инструмент (насколько он удобный и эффективный — покажет время), позволяющий все это отслеживать без всяких проблем.

Корпорация Google получила очередной судебный иск (интересно, сколько их всего, этих исков, подано в отношении корпорации?) от небольшого ирландского отеля. Отель действительно не самый крупный и известный, но администрация была неприятно удивлена, когда заметила, что при вводе названия отеля в поисковую строку, выводится несколько поисковых подсказок, одна из которых показывает слово «receivership» рядом с названием отеля. Это слово довольно сложно перевести на русский, но термин буквально означает «управление имуществом банкрота». То есть потенциальный клиент, вводя название отеля, мог видеть это слово, и решить, что отель стал банкротом. Понятно, что в такой отель никто не поедет.