Ранжирование в Sphinx

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

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

// так
$mysphinx->SetMatchMode ( SPH_MATCH_ALL );
$mysphinx->Query ( "welcome" );

// или так
$mysphinx->SetMatchMode ( SPH_MATCH_EXTENDED2 );
$mysphinx->SetRankingMode ( SPH_RANK_PROXIMITY );
$mysphinx->Query ( "welcome" );
В последнем же варианте мы могли бы использовать @title hello, а в первом – нет.

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

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

Алгоритм точного расчета:

BM25 = 0

for ( i=0; i < matching_keywords.length; i++)
{
k1 = 1.2
TF = document_occurrence_count ( matching_keywords[i] )
IDF = log((total_documents_in_collection-total_matching_documents(matching_keywords[i])+1)/total_matching_documents(matching_keywords[i])) / log(1+total_documents_in_collection)
BM25 = BM25 + TF*IDF/(TF+k1)
}

// нормализовать до диапазона 0..1
BM25 = 0.5 + BM25 / ( 2*keywords_count ( query ) )
TF здесь есть ни что иное, как Term Frequency (частота нашего ключевого слова в документе). IDF - Inverse Document Frequency - это уже обратная частота самих документов. Этот показатель для часто употребляемых ключевых слов выходит обычно поменьше, а для редких слов – наоборот.

Фактор BM25 увеличивается в значении, когда мы ищем редкие ключевые слова, но в документе они встречаются часто. Значение падает, когда ключевые слова часто употребляются. Максимум достигается тогда, когда с документом совпали все, причем сверх редкие, ключевые слова, которые входят в документ много раз. И наоборот.

Слишком частые слова катастрофически уменьшают BM25.

Вес фразы, в свою очередь, определяет степень близости с запросом и называется еще query proximity. Он считается совсем по-другому. Здесь частоты не учитываются, зато берется в расчет взаимное расположение введенных ключевых слов и таких же слов в документе. То есть, Sphinx производит анализ позиции слов, ищет самое большое непрерывное точное совпадение с запросом, причем измеряет длину совпадения в ключевых словах. Другими словами, находится самая большая общая «подпоследовательность» ключевых слов между обрабатываемым полем и запросом, она же (Longest Common Subsequence, LCS). Вес фазы при этом приравнивается к длине LCS.

Примеры:

1) keyword = save our souls, text value = save and heating our souls
phrase weight = 2 (совпала подфраза "our souls", длиной 2 ключевых слова)
2) keyword = save our souls, text value = save and heating our unfortunate souls
phrase weight = 1 (отдельные слова совпадают, но подфразы нет)
3) keyword = save our souls, text value = в данном тексте не совпало ни одно слово
phrase weight = 0
Метод SetFieldWeights() позволяет найти окончательный вес фразы документа:

$phraseWeight = 0
for ($i=0;$i<$matchingFields.length;$i++)
{
$fieldWeight = maxSubsequenceLength ( $keyword, $matchingFields[$i] )
$phraseWeight += userWeight ( $matchingFields[$i] ) * $fieldWeight
}
Например:

$title = "save our souls";
$body = "In popular usage, SOS became associated with phrases such as 'save our ship'";

$keyword = "save our souls"
$keywordTitleWeight = 5;
$keywordBodyWeight = 3;

$titleWeight = 3
$bodyWeight = 2
$docWeight = 3*5+2*3 = 21
Описанные факторы можно назвать основными, но никак не единственными. Можно рассчитывать и другие текстовые факторы.

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

По умолчанию ранкер называется в режимах extended и extended2 как SPH_RANK_PROXIMITY_BM25 и комбинирует вес фразы с BM25. Существуют среди них два связанных, ранкеры SPH_RANK_BM25 и SPH_RANK_PROXIMITY, первый считает по-честному только BM25, а второй возвращает фактор веса самой фразы в качестве веса.

// ранкер SPH_RANK_PROXIMITY_BM25 (стоит по умолчанию)
$weight = $phraseWeight*1000 + integer(doc_bm25*999)

// ранкер SPH_RANK_PROXIMITY (форсируется режимом SPH_MATCH_ALL)
$weight = $docPhraseWeight;

// ранкер SPH_RANK_BM25 (он быстрый, потому что не нужно считать такие дорогие веса подфраз)
$totalFieldWeights = 0
for($i=0;$i<$matchingFields.length;$i++)
$totalFieldWeights += userWeight ( $matchingFields[$i] )
$weight = $totalFieldWeights*1000 + integer(doc_bm25*999)
Наш SPH_RANK_PROXIMITY_BM25 стоит по умолчанию не потому, что блатной, а потому, что считается самым релевантным по своему результату (кто знает, надолго ли он таким считается, но не будем загадывать). SPH_RANK_BM25 используем тогда, когда вес фразы роли не играет.

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

$k = 0
for ($i=0;$i<$allFields.length;$i++){
$k = $k + userWeight ($allFields[$i]) * keywordsCount($query)
}

$weight = 0
for ($z=0;$z<$matchingFields.length;$z++){
$fieldPhraseWeight = maxSubsequenceLength($keyword, $matchingFields[$z])
$fieldRankValue = ($fieldPhraseWeight * $k + matchingKeywordsCount ( $matchingFields[$z] ) )
$weight = $weight + userWeight ( $matchingFields[$z] ) * $fieldRankValue
}
А вот такой ранкер, как SPH_RANK_WORDCOUNT, просто складывает количество совпадающих по каждому полю вхождений, умноженное на вес самого поля. Проще, как видите, некуда.

$weight = 0;
for ($i=0;$i<$matchingFields.length;$i++ )
weight = weight + KeywordOccurrencesCount ($matchingFields[$i]);
Ну а SPH_RANK_FIELDMASK нам возвращает так называемую битовую маску полей, которые совпали с запросом.

$weight = 0;
for ($i=0;$i<$matchingFields.length;$i++ )
setBit ( $weight, indexOf ( $matchingFields[$i] ) )
// другими словами, $weight |= ( 1 << indexOf ( $matchingFields[$i] ) )
И наконец, о звездочках. К вопросу о том, чему должны быть равны все же максимально допустимые веса и как их пересчитывать в звездочки, или в проценты, а то и вовсе в баллы по шкале от единицы до 17. Получается так, что максимальный вес во многом зависит от запроса и от ранкера.

Пример с SPH_RANK_PROXIMITY_BM25:

$maxWeight = keywordsCount * sum ( userFieldWeights ) * 1000 + 999
Абсолютного максимума мы можем достигнуть, если все поля будут содержать совершенно точную копию введенного запроса. Если запрос был составлен с ограничением, то абсолютный максимум абсолютно невозможен. Поэтому, как видим, подсчет правильного максимума – не такая уж легкая задача. Но если все же позарез нужны звездочки, можно взять самый большой @weight по каждой выборке, и все нормализовать относительно него.

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

Тут как раз и вмешиваются ранкеры. Такие как proximity или proximity_bm25. Если запрос встретился полностью в поле, то ему присваивают максимальный вес, без учета длины поля.

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

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

SELECT *, @weight + IF(fieldcrc==$querycrc,1000,0) AS customweight ...
ORDER BY customweight DESC
Неудобно, но тоже своего рода выход из ситуации.

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

Оцени публикацию:
  • 0,0
Оценили человек: 0

Похожие статьи:

Справочники и учебники:


Предложения и пожелания:
Ваше имя:
Ваш E-mail:
Сколько будет Οдин + Τри
Главная
X

Новые заметки:

Про что мы забываем когда делаем оценку задачи по времени

Список вопросов для собеседования разработчика по телефону

Symfony2 авторизация без Doctrine2 для чайника

Phpstorm7 LiveEdit

Жесткий хабр или не хабр, тогда кто?

Яндекс.Деньги мошенничество

Как узнать какие страницы в поиске яндекса или это секрет

Последние комменты:

Yapro CMS:

Здравствуйте, Гость | Войти | Регистрация | Карта сайта | RSS ленты | Ошибка в тексте? Выделите её мышкой и нажмите: Ctrl + Enter

youtube.com/watch?v=7hFivbgIEqk

При полном или частичном использовании материалов данного сайта, ссылка на сайт "yapro.ru" обязательна как на источник информации.
Автоматический импорт материалов и информации с сайта запрещен.
Copyrights © 2007 - 2018 YaPro.Ru

Главная » Веб-мастеру » PHP »