книги хакеры / журнал хакер / 166_Optimized

ХАКЕР 11/166/2012

019

Мой любимый пример из той эпохи — на-

лагается, что данные у тебя уже есть, и откуда

вручную в Microsoft Word! После этого мы

звание песни Depeche Mode «I feel you». Про-

ты их взял — из базы данных или откуда-то

достаточно быстро сумеем бинарным поиском

сто классика. Каждое из этих слов встречается

еще, — уже не важно. Может быть, ты за меня

найти нужное слово, прочитать эту строчку,

более чем в половине всей коллекции песен.

сходил по интернету и накачал документы.

где через запятую записан список номеров

За счет этого стандартный статистический ал-

Зато я умею их проиндексировать и быстро по

документов, и вот — мы их нашли. Это и есть

горитм ранжирования такую песню, в которой

ним искать.

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

есть точная цитата — идеальное соответствие

С масштабированием тоже полный по-

Однако нужно хранить не только номера

поисковой фразе, но повторяется она нечасто,

рядок. У нас есть две части: часть, которую я

документов, но еще и позиции слов в них. По-

заранжирует глубоко вниз. То есть идеальное

все еще считаю простой, и часть, которая куда

зицию при этом можно записывать по-разному.

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

сложнее. Когда нужно разложить данные на

То есть это может быть не просто номер слова

выдачи. Зато песня, в которой все три слова

много серверов, возникают две проблемы. Как

от начала документа, но также номер поля,

повторяются оч-чень уж много раз, окажется

разложить и потом собрать их вместе?

номер зоны. Для веб-поиска возможны еще

на самом верху.

Разложить — в нашей модели проблем нет.

атрибуты: скажем, не подкрашено ли слово

Еще одно ключевое дизайн-решение

На один сервер положил конфигурацию, на

жирным шрифтом или красным цветом. В слу-

заключалось в том, что близкие совпадения

которой написано «этот сервер тянет докумен-

чае с языками с развитой морфологией (типа

фраз нужно вытягивать вверх. Ранжировать

ты с номерами от 1 до 1 000 000». На второй

русского) может оказаться неплохой идеей

выше, чем просто россыпь слов по документу.

сервер положил конфигурацию от 1 000 000

также указать и форму слова.

Это подсказал простой здравый смысл, когда я

до 2 000 000. Все, задача индексации решена.

Потом возникает и чисто технический

решал свои личные задачи. Я хотел, чтобы точ-

Конечно, у тебя возникает зоопарк конфигов

вопрос — не будешь же ты, в самом деле,

ная цитата из песни была вверху, и была там

на разных серверах — их возможно как-то

вордовый документ читать? Данные нужно

гарантированно. Стандартный, статистический

автоматизировать или положить под контроль

сохранить бинарно, хорошо пожать, чтобы они

метод ранжирования мне этого не давал — он

версий… но это понятные и легкие техни-

жрали поменьше места, а поиск работал бы-

смотрел только на частоты, но не смотрел на

ческие трудности. А вот если бы поисковая

стрее. Получается вот такая структура данных.

позиции слов.

система понятия не имела о слиянии резуль-

Есть также два принципиально конфлик-

Такпоявилсяновыйпоиск,который…не-

татов поиска, тебе пришлось бы в приложе-

тующих параметра: скорость и качество. Тре-

скольколетпролежалвстоле.Я использовал

нии писать массу идиотского кода: а давайте

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

его для личных целей, раздавал друзьям и зна-

сходим ко всем серверам, соберем с каждого

результат» — это одно. А качество поиска —

комым, по их запросам вносил какие-то правки.

отклик, вместе их сольем, пересортируем по

это уже другое требование. Качество поис-

Одинизтакихпользователейоказался

нужному условию сортировки... Из десяти сер-

ка — это штука, которой серьезно на данный

оченьактивныммолодымчеловеком.Его зовут

веров два не ответили? Давайте сходим опять.

момент занимаются только веб-поисковики.

Петр Зайцев, он хорошо известен в узких кругах

Естественно, это сделано в Sphinx, ведь мы

Google, Yandex и так далее. Нам, конечно, тоже

как основатель компании Percona, но в тот

должны помогать пользователю делать поиск,

хочется этим заниматься, но силенок пока не

момент еще работал в MySQL. Он фактически за-

а не головную боль ему создавать. В какой-то

очень хватает.

ставил меня выйти из тени, сделать сайт, начать

момент это было хорошим отличием Sphinx от

Что нужно, чтобы сделать мегаскорость?

светиться на конференциях. В общем, рассказал

«врагов» типа Apache Solr (он тогда вообще не

Грубо говоря — максимально ловко пожать

мне о том, что проект по большому счету вышел

распределялся на несколько серверов).

список документов, так чтобы можно было

годный, людям нужный, и практически принудил

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

КАКУСТРОЕНПОИСК?

меня его выложить. За что ему большое спасибо,

тать и выплюнуть в программу. Все. Это одно

он сыграл немалую роль.

Последние несколько лекций

на эту тему

требование. А второе требование, противо-

Благодаря ему я начал пилить Sphinx для

я начинал со слов: «Кто читал Библию, тот

речащее этому первому, — не просто «найти»

проектов большего масштаба. Тут важно по-

умеет делать поиск». Есть такая штука в

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

нимать: одно дело, когда индексируешь сто

массе разных изданий Библии, называется

наиболее качественно.

мегабайт на личном сайте или полгигабайта

конкорданс: в самом конце для каждого сло-

Представь, что тебе нужно не просто

сообщений форума на «Тупичке» (oper.ru).

ва, за исключением предлогов и междометий,

максимально быстро обработать этот список,

И совсем другой вопрос, когда тебе запилива-

написано как минимум, на какой странице оно

но обработать его осмысленно. Нужно вы-

ют 50 Гб в 50 миллионах сообщений из блогов,

находится, а как максимум — дана и более

плюнуть не 3000 результатов поиска в произ-

которые откуда-то накраулили.

точная позиционная информация (например,

вольном порядке (или, например, в порядке

Десять лет назад 99% поисковиков были

в каком стихе встречается). Это отличная

возрастающего идентификатора документа),

написаны исходя из следующего предпо-

ментальная модель поискового индекса. Он

а в том порядке, какой пользователь счи-

ложения: клиент хочет купить готовый набор

именно так и устроен.

тает релевантным. Отдельный фокус здесь

скриптов, которые позволяли бы прицепить

Приведу пример: берем текст и строим

заключается в том, что нет единого понятия

поиск на свой сайт. И чтобы робот дальше сде-

так называемый инвертированный индекс.

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

лал за него все — обошел сайт, все документы

Что это такое? Это большой сортированный

Для одной и той же пары «запрос и до-

выкачал, сложил в полнотекстовый индекс.

по алфавиту словарь, где для каждого слова

кументы» разные люди могут сказать разное.

Sphinx не про это. Он не будет за тебя

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

Когда лично я ищу слово «sphinx», меня, ско-

ходить по сайтам, он чисто про поиск. Предпо-

встречается. Можно реализовать его даже

рее всего, интересует мой собственный веб-

сайт. А если я «руссо туристо облико морале»

и я захожу на страницу Google с египетского

IP-адреса, то вряд ли меня волнует поисковый

ПОСЛЕДНИЕ НЕСКОЛЬКО ЛЕКЦИЙ

сервер. Вероятнее всего, мне нужно узнать,

когда ближайший тур на песчаном багги до

ОБ УСТРОЙСТВЕ ПОИСКА Я НАЧИНАЛ

этого самого сфинкса отходит из моего отеля.

Казалосьбы—одинитотжедокумент,

СО СЛОВ: «КТО ЧИТАЛ БИБЛИЮ, ТОТ УМЕЕТ

одинзапрос,нодлядвухразныхлюдейони

имеюточеньразныйвес. Запрос может быть

ДЕЛАТЬ ПОИСК»

одинаковым, но так называемая информацион-

ная потребность — разная. Поэтому товарищам,

020

ХАКЕР 11 /166/ 2012

фразу, не отличаются вообще никак. И десять

лет назад это не устраивало даже меня.

Думаю, даже большинство коммерческих

поисковиков использует ее до сих пор. Несмо-

тря на полное игнорирование позиций, фор-

мула достаточно качественная. Тем не менее

в коммерческих проектах неустанно работают

над новыми технологиями, заодно продвигая

науку. Если незатейливую реализацию BM25

сравнить с теми сложными формулами ранжи-

рования, которые там крутятся, естественно,

она даст худшие результаты. Но она достаточ-

но неплоха.

По сути, BM25 — это сумма частоты слова

(TF), умноженной на IDF — относительную

частоту слова в коллекции, для каждого слова

в запросе. Это опять на пальцах, потому что

на самом деле там запрятано еще несколько

передаточных коэффициентов, которые демп-

фируют, сглаживают частоты и смотрят на дли-

ну документа. Скажем, у тебя есть документ,

в котором слово встретилось один раз, и есть

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

Зато какое-то другое, в десять раз более ред-

кое слово, встретилось там чаще. Если просто

перемножать такие метрики — будет плохо.

Слишком большое количество вхождений

более плохого (менее редкого) слова сильно

заспамит результат. Поэтому TF засовывается

под логарифм.

Что за TF, IDF? IDF значит inverse document

frequency, обратная частота документа — ме-

трика того, насколько слово редкое. Если оно

максимально редкое — встречается всего раз

на всю коллекцию, то метрика максимизиру-

ется и стремится к единице. Если наоборот —

встречается в каждом документе, метрика

минимизируется и стремится к нулю. Чем реже

слово, тем лучше его IDF. Когда всего один

документ на всю твою коллекцию из миллиона

или миллиарда — это хорошо. Есть еще одна

тупая метрика — TF (term frequency). Частота

слов в текущем документе, который ты об-

рабатываешь. То есть сколько вхождений этого

слова вообще есть. Просто посчитать.

Но давай разберем, как работает запрос

из двух слов. Что он должен делать, чтобы

исполниться и отранжировать результаты,

у которых эта информация есть (то есть веб-

много. Но Open Source поисковики обычно

при помощи классической частотной функ-

гигантам вроде Google или Яндекс), приходит-

анализируют крайне мало.

ции BM25? Это работает так: берем список

ся угадывать информационную потребность

Некоторое время назад у меня вообще

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

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

была присказка — мол, типичный Open Source

по возрастанию номера документа. Берем

IP-адресу, языку в браузере, истории поис-

поисковик (да и не только Open Source) для

второй список. Бежим по обоим спискам

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

ранжирования использует всего один фактор.

одновременно и выбираем те документы, у ко-

сайтов и так далее. В той мере, в какой они до

Общепринятую статистическую функцию

торых номер совпал. Просто пересекаем два

таких данных могут дотянуться, конечно.

BM25, которая смотрит на частоты слов в кол-

списка. Получаем третий список — это все до-

лекции (настолько они частые или редкие) и на

кументы, в которых есть два наших ключевых

ФОРМУЛА BM25

частоты слов в конкретном документе.

слова. Осталось их отранжировать. То есть

Качество поиска, если говорить очень

Формулу BM25 придумали где-то в 80-х, а в

посчитать ту или иную функцию ранжирова-

упрощая, — это усредненная степень счастья

начале 2000-х довольно тривиальным образом

ния, например BM25.

каждого отдельного пользователя. В идеале:

расширили, чтобы уметь взвешивать доку-

Как это сделать? Для этого нужно заранее,

я коряво формулирую свою информационную

менты о многих полях и назначать этим полям

в момент построения индекса, рядом с каждым

потребность, а поисковая машина «делает

разный вес.

номером документа, в списке документов (на

магию» — угадывает по всем явным и не очень

Но есть проблема: BM25 вообще не смотрит

который из словаря есть указатель), положить

сигналам, какой же именно документ мне

на взаимные позиции слов. То есть три слова,

не только номер, но и число вхождений этого

дико нужен, и возвращает именно его. Таких

как угодно размазанные по документу, и три

слова в этот документ, TF. А в самом словари-

сигналов приходится анализировать довольно

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

ке положить не только слово и указатель на

ХАКЕР 11/166/ 2012

021

список документов, но еще и сравнительную

когда в документе есть точное совпадение

стовые. Текстовые — мы обнюхиваем позиции

частоту этого слова во всей коллекции, IDF.

для нашего запроса. Дефолтная формула

и привязанную к ним информацию и по этим

Она тоже рассчитывается в момент индекса-

ранжирования до сих пор такая, но с тех пор

позициям делаем всякие выводы. На самом

ции текста. Мы читаем с диска вдвое больше

ситуация у нас еще немного улучшилась и

деле — считаем всякие статистические штуч-

данных, когда бежим по двум спискам и пере-

будет улучшаться дальше.

ки. Типа что такое TF? Это просто сумма числа

секаем их. При пересечении мы не смотрим на

Фактор близости работает немного слож-

позиций. Что такое IDF? Это тоже статистиче-

TF (частоты), но после того, как у документов

нее, чем ВМ25. Чтобы его посчитать, не отде-

ская штука, но только заранее посчитанная по

совпали номера, — у нас и частоты есть. У нас

лаешься предрассчитанным числом слов. Тут

всей коллекции. Можно еще всякий смешной

есть TF — из списка документов, и есть IDF —

нужно не просто хранить список документов,

фарш смотреть — на близость смотреть, что

из словарика. Мы просто перемножаем их,

но хранить тот факт, что в документе номер

LCS (Longest Common Subsequence) хороший.

складываем и все. Задача решена.

123 слово «Вася» встретилось в позициях 10,

Можно и более умные факторы придумать,

Так вот, присказка раньше была такая:

20 и 30. А слово «Петров» в этом же документе

которые смотрят на близость слов. Все, что

если у многих поисковиков всего один ранжи-

встретилось в позициях 11, 48 и 92. И нужно

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

рующий фактор (та самая BM25), то у Sphinx

не только выяснить, что пара номеров 123 и

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

их целых два. Один — BM25, потому что куда

123 совпала для слов «Вася» и «Петров» и

методам обнюхивания позиций и прочей мета-

без нее? Второй — степень близости. Степень

поэтому оба слова есть в документе номер 123

информации, которую мы сохранили.

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

и он удовлетворяет запросу «Вася Петров».

Но еще есть внетекстовые факторы. Тот

Очень простая на самом деле штука. Сейчас

Еще после этого нужно пробежаться по всем

же page rank, который у всех на слуху. Что это

уже все посложнее и присказка уже невер-

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

такое? Это фактор, не имеющий ни малейшего

на — факторов куда больше двух. Но степень

кументе и посмотреть — о, а в этом месте они у

отношения к тексту запроса и документа. Это

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

нас стояли рядом. Ништяк. Это же совпадение

некий коэффициент, который показывает, на-

Берем запрос и считаем такое число:

фразы. Давайте этот факт у себя отметим и

сколько хорошо на этот сайт и на эту страницу

сколько слов мы можем оставить в запросе,

используем при ранжировании как одну из

ссылаются извне. Просто некий факт, который

чтобы выходить на отдельно взятый до-

переменных. В литературе это называется

привязан к номеру документа, к этому номеру

кумент. Понятно, что единицу мы насчитаем

факторами или сигналами.

123 в списках для слов «Вася» и к той же самой

всегда — хоть одно слово должно совпасть.

В принципе, все текстовые факторы

единичке, что привязана к слову «Петров».

А если у нас два слова стоят в запросе рядом

при ранжировании опираются на это. Они

Упорядочивание результатов может

и абсолютно такая же цитата встречается

всегда рассчитываются по позициям и прочей

опираться на посчитанную релевантность,

в документе, значит наш фактор близости

привязанной информации. Если слово было

а может на более сложные факторы. К при-

равен двум. Или, формально, длина наиболь-

написано жирным — теоретически поисковик

меру, сначала на новостном сайте идут все

шей общей подпоследовательности равна

может это использовать. Мы не используем, но

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

двум. Соответственно, чем больше это число,

теоретически — сделать можно.

плохими с точки зрения релевантности они ни

тем выше в выдаче будет стоять документ.

Для ранжирования существует ряд фак-

были, а после — все, что старше года, сортиру-

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

торов. Две категории — текстовые и внетек-

ется по релевантности. Вполне корректный и

разумный метод упорядочивания результатов,

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

У нас в Sphinx в один прекрасный момент

еще появилась такая штука — считалка выра-

жений. Можно написать произвольное ариф-

метическое выражение, и она его посчитает.

Она довольно быстрая по замерам — местами

в десятки раз быстрее той, что встроена в

MySQL. И возникла следующая чудная идея —

прикрутить ее тоже к ранжированию. Я на-

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

функцию ранжирования, которая считает не-

сколько всяких факторов по тексту запроса и

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

в твоей собственной формуле. С его помощью

можно тестировать собственные формулы

ранжирования, описывая их прямо в поиско-

вых запросах.

Формула ранжирования, которую можно

таким образом описать, — это комбинация

нескольких факторов, «кубиков». Один из

факторов — это бессмертная BM25 — как без

нее? Можно и просто учитывать количество

совпавших слов в каждом конкретном поле,

другие частотные факторы, типа минималь-

ной и максимальной IDF. Есть и еще более

хитрые факторы, типа позиции первого

наилучшего совпадения в данном поле, или

там максимума числа слова, совпавших в

скользящем окне заданной ширины. Мы сами

придумали считать примерно с полдесятка

факторов, и еще часть запросили пользо-

ватели. Итого сейчас там где-то 12 разных,

022

ХАКЕР 11 /166/ 2012

ХАКЕР 11/166/ 2012

023

024

ХАКЕР 11 /166/ 2012

ХАКЕР 11 /166/ 2012

025

026

ХАКЕР 11/166/2012