Pull to refresh

Как устроено ранжирование

Reading time 9 min
Views 26K
Со временем Sphinx оброс большой кучей режимов поиска и ранжирования. Регулярно возникают вопросы про разное (от «как вытащить документ на 1е место» до «как рисовать от 1 до 5 звездочек в зависимости от степени совпадения»), которые на самом деле суть вопросы про внутреннее устройство тех режимов. В этом посте расскажу все, что вспомню: как устроены режимы поиска и режимы ранжирования, какие есть факторы ранжирования, как в точности рассчитываются факторы, как финальный вес, все такое. И, конечно, про звездочки!


Про режимы поиска и ранжирования


Прежде всего, разберемся, что вообще делают те режимы. Через API про них сейчас доступны 2 разных метода, SetMatchMode() и SetRankingMode(). Казалось бы, разные; но на самом деле, внутри там теперь одно и то же. Ранее, вплоть до версии 0.9.8 включительно, были доступны только режимы поиска, те. SetMatchMode(). Все они были реализованы разными ветками кода. Каждая из веток кода сама делала и поиск документов, и их ранжирование. Причем, понятно, по-разному. В версии 0.9.8 была начата разработка нового унифицированного движка поиска документов. Однако, чтобы не ломать совместимость, этот движок был доступен только в режиме SPH_MATCH_EXTENDED2. Начиная с 0.9.9 стало видно, что новый движок уже в целом достаточно стабильный и быстрый (а на всякий особый случай, если недоглядели, есть версия 0.9.8). Это позволило убрать кучу старого кода, и начиная с 0.9.9 все режимы поиска обрабатываются новым движком. Для совместимости, при использовании устаревших режимов поиска используется упрощенный код разбора запросов (который игнорирует операторы языка полнотекстовых запросов), и автоматически выставляется правильный (соответствующий режиму поиска) ранкер, но на этом все отличия и заканчиваются. Поэтому фактически вес документа ( weight) зависит только от режима ранжирования (ranker). Поэтому два нижеследующих запроса дадут одинаковые веса:

// 1й вариант
$cl->SetMatchMode ( SPH_MATCH_ALL );
$cl->Query ( "hello world" );

// 2й вариант
$cl->SetMatchMode ( SPH_MATCH_EXTENDED2 );
$cl->SetRankingMode ( SPH_RANK_PROXIMITY );
$cl->Query ( "hello world" ); 


Во втором варианте при этом можно написать @title hello (см. язык запросов). В первом нельзя (см. совместимость).

Ранкеры рассчитывают вес документа по нескольким доступным им (и только им) внутренним факторам. Можно сказать, что разные ранкеры просто по-разному собирают факторы в конечный вес. Два наиболее важных фактора это 1) классический статистический фактор BM25, используемый большинством (если не всеми) поисковыми системами с 80х годов, и 2) специфичный для Sphinx фактор веса фразы.

Про BM25


BM25 представляет собой вещественное число в диапазоне от 0 до 1, которое зависит от частот ключевых слов в текущем документе с одной стороны и общем наборе документов (коллекции) с другой, и только от частот. Текущая реализация BM25 в Sphinx рассчитывается исходя из общей частоты слова в документе, а не только частоты фактических совпадений с запросом. Например, для запроса title hello (который матчит 1 копию слова hello в заголовке) фактор BM25 будет рассчитан такой же, как и для запроса @(title,content) keyword. Упрощенная реализация сделана намеренно: в стандартном режиме ранжирования фактор BM25 вторичен, отличия в ранжировании при тестировании получались несущественные, а вот скорость отличалась вполне себе измеримо. Точный алгоритм расчета выглядит так:

BM25 = 0
foreach ( keyword in matching_keywords )
{
    n = total_matching_documents ( keyword )
    N = total_documents_in_collection
    k1 = 1.2

    TF = current_document_occurrence_count ( keyword )
    IDF = log((N-n+1)/n) / log(1+N)
    BM25 = BM25 + TF*IDF/(TF+k1)
}
BM25 = 0.5 + BM25 / ( 2*num_keywords ( query ) )


TF означает Term Frequency (частота ключевого слова, в ранжируемом документе). IDF означает Inverse Document Frequency (обратная частота документов, во всей коллекции). IDF для часто встречающихся в коллекции ключевых слов получается меньше, для редких слов побольше. Пиковые значения выходят IDF=1 для слова, которое встречается ровно в одном документе, и IDF~=-1 для слова, которое есть в каждом документе. TF теоретически варьируется от 0 до 1, в зависимости от k1; при выбранном k1=1.2 оно фактически варьируется от 0.4545… до 1.

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

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

Про вес фразы


Вес фразы (он же степень близости с запросом, он же query proximity) считается совершенно иначе. Этот фактор совсем не учитывает частоты, зато учитывает взаимное расположение ключевых слов запросе и документе. Для его расчета, Sphinx анализирует позиции ключевых слов в каждом поле документа, находит самое длинное непрерывное совпадение с запросом, и считает его, совпадения, длину в ключевых словах. Формально говоря, находит наибольшую общую подпоследовательность (Longest Common Subsequence, LCS) ключевых слов между запросом и обрабатываемым полем, и назначает вес фразы для этого поля равным длине LCS. В переводе обратно на русский, вес (под)фразы — это число ключевых слов, которые в поле появились ровно в таком же порядке, как и в запросе. Вот несколько примеров:

1) query = one two three, field = one and two three
field_phrase_weight = 2 (совпала подфраза "two three", длиной 2 ключевых слова)

2) query = one two three, field = one and two and three
field_phrase_weight = 1 (отдельные слова совпадают, но подфразы нет)

3) query = one two three, field = nothing matches at all
field_phrase_weight = 0

Чтобы получить окончательный вес фразы для документа, веса фразы в каждом поле перемножаются на указанные пользователем веса полей (см. метод SetFieldWeights()) и результаты умножения складываются вместе. (Кстати, по умолчанию веса полей равны 1, и не могут быть выставлены ниже 1.) Псевдокод выглядит так:

doc_phrase_weight = 0
foreach ( field in matching_fields )
{
   field_phrase_weight = max_common_subsequence_length ( query, field )
   doc_phrase_weight += user_weight ( field ) * field_phrase_weight
}

Например:

doc_title = hello world
doc_body = the world is a wonderful place

query = hello world
query_title_weight = 5
query_body_weight = 3

title_phrase_weight = 2
body_phrase_weight = 1
doc_phrase_weight = 2*5+3*1 = 13

Про светлое будущее


Описанные два фактора на сегодня основные, но вообще говоря не единственные. Технически вполне возможно считать другие текстовые факторы. Например, считать «правильный» BM25 с учетом фактических совпадений; считать веса подфраз похитрее, с учетом частот входящих слов; дополнительно учитывать количество совпавших в поле слов; итд итп. Еще можно учитывать всякие внетекстовые факторы на уровне самого ранкера; иными словами, использовать какие-то атрибуты в процессе расчета weight, а не вдобавок к расчету.

Про ранкеры


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

Ранкер по умолчанию (в режимах extended/extended2) называется SPH_RANK_PROXIMITY_BM25 и комбинирует вес фразы с BM25. Фактор BM25 располагается в нижних 3 десятичных знаках, вес фразы начиная с 4го и выше. Есть два связанных ранкера, SPH_RANK_PROXIMITY и SPH_RANK_BM25. Первый возвращает в качестве веса просто сам фактор веса фразы. Второй честно считает только BM25, а веса фразы в каждом совпавшем поле вместо долгих расчетов быстро принимает равными единице.

// ранкер SPH_RANK_PROXIMITY_BM25 (по умолчанию)
rank_proximity_bm25 = doc_phrase_weight*1000 + doc_bm25*999

// ранкер SPH_RANK_PROXIMITY (форсируется в режиме SPH_MATCH_ALL)
rank_proximity = doc_phrase_weight

// ранкер SPH_RANK_BM25 (быстрый, тк. не нужно считать дорогие веса подфраз)
rank_bm25 = sum ( matching_field_weight )*1000 + doc_bm25*999

SPH_RANK_PROXIMITY_BM25 выбран по умолчанию, тк. есть мнение, что из имеющихся именно он дает наиболее релевантный результат. Умолчание в будущем может и поменяться; планы делать более умные и в целом более хорошие ранкеры вполне себе есть. Ранкер SPH_RANK_PROXIMITY как бы эмулирует режим SPH_MATCH_ALL (самый, кстати, первый, с которого в 2001-м году все начиналось). SPH_RANK_BM25 нужно использовать, если вес фразы по каким-либо причинам не важен; либо просто если хочется подускорить запросы. Кстати говоря, выбор ранкера существенно влияет на скорость запроса! Типично наиболее дорогая часть вычислений это анализ позиций слов внутри документа. Поэтому SPH_RANK_PROXIMITY_BM25 всегда будет медленнее SPH_RANK_BM25, а тот в свою очередь всегда медленнее SPH_RANK_NONE (который вообще ничего не считает).

Еще один ранкер, используемый для обработки исторических режимов поиска, это SPH_RANK_MATCHANY. Он тоже считает веса подфраз, как и два других ранкера про proximity. Но этот вдобавок считает число совпавших ключевых слов в каждом поле, и комбинирует его с весами подфраз так, чтобы а) более длинная подфраза в любом поле отранжировала весь документ выше; б) при одинаковой длине подфразы, выше ранжировался документ с бОльшим количеством совпавших слов. На пальцах, если в документе A есть более точная (длинная) подфраза запроса, чем в документе B, надо выше ранжировать именно документ A. Иначе (если подфразы одинаковой длины) смотрим просто на число слов. Алгоритм такой:

k = 0
foreach ( field in all_fields )
   k += user_weight ( field ) * num_keywords ( query )

rank = 0
foreach ( field in matching_fields )
{
   field_phrase_weight = max_common_subsequence_length ( query, field )
   field_rank = ( field_phrase_weight * k + num_matching_keywords ( field ) )
   rank += user_weight ( field ) * field_rank
}

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

rank = 0
foreach ( field in matching_fields )
   rank += user_weight ( field ) * num_matching_occurrences ( field )

Наконец, SPH_RANK_FIELDMASK возвращает битовую маску полей, совпавших с запросом. (Тоже несложный, да...)

rank = 0
foreach ( field in matching_fields )
   rank |= ( 1<<index_of ( field ) )

Про звездочки


Регулярно всплывает вопрос, чему таки равны максимальные возможные веса, и как их правильно пересчитать в звездочки (обычно 5-конечные, но возможны варианты), проценты, или баллы по интуитивно понятной шкале от 1 до 17. Как видим, максимальный вес сильно зависит и от ранкера, и от запроса. Например, абсолютный максимум веса на выходе из SPH_RANK_PROXIMITY_BM25 зависит от числа ключевых слов и весов полей:

max_proximity_bm25 = num_keywords * sum ( field_weights ) * 1000 + 999

Но этот абсолютный максимум будет достигнут только когда все поля содержат точную копию запроса во-1х, плюс запрос ищет во всех полях во-2х. А если запрос составлен с ограничением по одному конкретному полю (например, title hello world)? Абсолютный максимум недостижим в принципе, для этого конкретного вида запроса максимальный практически возможный вес будет равен:

max_title_query_weight = num_keywords * title_field_weight * 1000 + 999

Так что точно аналитически посчитать «правильный» максимум веса довольно сложно. Если жизни нету без звездочек, можно либо сравнительно легко считать «абсолютный» максимум (который практически никогда не будет достигаться), либо вообще брать максимальный weight по каждой конкретной выборке, и нормализовать все относительно него. Через multi-query механизм это делается почти бесплатно, но это уже тема для отдельной статьи.

Про полные совпадения (update)


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

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

В текущем транке (версия 0.9.10) работы уже ведутся, добавлен экспериментальный ранкер SPH_RANK_SPH04, который как раз ранжирует полные совпадения поля выше. Техническая возможность появилась в 0.9.9, тк. в 0.9.8 формат индекса не предусматривает нужных данных (для любопытных, там у сохраненных позиций нет флажка «это был конец поля»).

Кое-что можно сделать и без нового ранкера.

Например, можно пробовать вручную увеличивать вес в случае полного совпадения. Для этого ручками убираем всю пунктуацию и верхний регистр из самого поля (при индексации) и из запроса, считаем crc32 от поля, сохраняем егов атрибут индекса. Затем при поиске рассчитываем выражение weight+if(fieldcrc==querycrc,1000,0) и сортируем результаты по этому выражению. Довольно криво, но в отдельных случаях может помочь.

Еще можно чуть изменить задачу, и учитывать не собственно факт полного совпадения, а длину документа (либо отдельного поля). Для этого при ндексации сохраняем LENGTH(myfield) в атрибут, при поиске ранжируем по выражению вида (это только пример!) weight+ln(max(len,1))*1000

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

Про пространство для напильника


Есть ли куда всю эту кухню дорихтовывать дальше? Еще как. Поняв, как устроены имеющиеся ранкеры, какие факторы они считают и как комбинируют, сразу можно немедля осознанно подправлять weight (точнее, задавать новое арифметическое выражение с участием weight, и сортировать выдачу по нему). Что интереснее, технически можно добавлять новые специализированные ранкеры (минута рекламы на первом: ранкеры SPH_RANK_WORDCOUNT и SPH_RANK_FIELDMASK придумал не я, запросили коммерческие пользователи). Из C++ кода ранкеров есть немедленный доступ к запросу, ключевым слова, ранжируемому документу, и (самое главное) списку всех совпадающих с запросом вхождений ключевых слов вместе с позициями в документе… да, из этих деталей советского паровоза вполне таки можно собрать советский истребитель; главное, мастерски применять магию напильника.
Tags:
Hubs:
+44
Comments 43
Comments Comments 43

Articles

Information

Website
sphinxsearch.com
Registered
Founded
Employees
Unknown
Location
Россия