Что такое поисковой индекс

Поисковый индекс

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

Что такое индексация

Процесс добавления роботами собранной информации в базу называется индексацией. Затем данные определенным образом обрабатываются и создается индекс – выжимка из документов. Процесс заполнения индекса осуществляется одним из двух способов: вручную или автоматически. В первом случае владелец ресурса должен самостоятельно добавить URL веб-ресурса в специальную форму, которая есть у «Яндекса», Google и других поисковых систем. Во втором робот сам находит сайт, планомерно переходя по внешним ссылкам с других площадок или сканируя файл-карту sitemap.xml.

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

Зачем индекс поисковым системам

Индексация страниц сайта – неотъемлемая часть работы поисковых систем (не только Google и «Яндекса», но и всех остальных). База, полученная в процессе сканирования веб-ресурсов, используется для формирования релевантной выдачи. Основные роботы поисковых систем:

Также существуют роботы для индексации rss-ленты, картинок и др.

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

Скорость индексации страниц

Чем быстрее происходит добавление страницы в индекс, тем лучше для веб-ресурса. Однако поисковые роботы не могут выполнять такой большой объем работы так же часто, как обновляется наполнение сайтов. Индексация в «Яндекс» в среднем занимает одну-две недели, а в Google – несколько дней. С целью ускорения индексации ресурсов, для которых очень важно быстрое попадание информации в базу (новостные порталы и т. д.), применяется специальный робот, посещающий такие сайты от одного до нескольких раз в день.

Как проверить индексацию в «Яндексе» и Google

Воспользоваться информацией из панели веб-мастеров. В списке сервисов Google откройте Search Console, а затем перейдите в раздел «Индекс Google». Нужная информация будет находиться в блоке «Статус индексирования». В «Яндекс.Вебмастер» необходимо перейти по следующей цепочке: «Индексирование сайта» — «Страницы в поиске». Еще один вариант: «Индексирование сайта» — «История» — «Страницы в поиске».

Задать поиск по сайту с использованием специальных операторов. Для этого используйте запрос с конструкцией «site:», указав далее адрес вашего ресурса в полном формате. Так вы узнаете количество проиндексированных страниц. Серьезные расхождения в значениях (до 80 %), полученных в разных поисковых системах, говорят о наличии проблем (например, веб-ресурс может находиться под фильтром).

Установить специальные плагины и букмарклеты. Это небольшие дополнения для браузера, которые позволяют выполнить проверку индексации страниц сайта. Одним из самых популярных среди них является RDS Bar.

Как ускорить индексацию

На скорость индексации сайта прямо влияют несколько факторов:

Чтобы ускорить индексацию сайта, выполните ряд правил:

Дополнительно рекомендуем оценить объем flash-элементов с точки зрения их влияния на продвижение. Наличие визуальных объектов этого типа значительно снижает долю поискового трафика, так как не дает роботам выполнить индексацию в полной мере. Также не желательно размещения ключевой информации в PDF-файлах, сохраненных определенным образом (сканироваться может только текстовое содержимое документа).

Источник

Поисковый индекс

Что такое поисковый индекс и для чего он необходим поисковым системам? Что такое индексация и как ее проверить в Гугле и Яндексе? Разбираем ответы на все эти вопросы — кликайте по ссылке ниже и переходите на соответствующую WIKI-страницу на нашем сайте.

Что такое поисковый индекс

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

Что такое индексация

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

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

Для чего поисковым система нужен индекс

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

Конечно, в реальности и поисковых систем есть массу других роботов, которые отвечают за индексацию какого-либо определенного контента (RSS-ленты, графики, аудио, видеоконтента и т.д.).

Когда робот впервые посещает сайт, он сравнивает его с правилами поисковой системы и, если ресурс соответствует им, он будет внесен в индекс. При повторном посещении сайта роботы будут лишь обновлять новые данные, которые на нем появились.

С какой скоростью индексируются страницы

Конечно, чем быстрее сайт попадет в индекс поисковика, тем лучше для его владельца. Но поисковые роботы не смогу обработать тот огромный объем данных, который создается в процессе запуска новых сайтов и обновления старых. Поэтому если вы запускаете новый сайт, то рассчитывайте на то, что Яндекс проиндексирует его примерно через 7-14 дней, а Google «справится» за пару-тройку дней.

Если необходимо ускорить процесс индексации на сайте, который обновляется ежедневно (например, новостной портал), поисковая система будет отправлять на него быстрого робота. В таком случае обновление контента может происходить хоть каждый день.

Как проверить индексацию сайта в Google и Яндекс

Для проверки индексации сайта в поисковой системе можно воспользоваться одним из трех следующих методов:

Как ускорить индексацию сайта

Для ускорения индексации сайта в первую очередь нужно позаботиться о том, чтобы сайт:

Непосредственно для ускорения процесса индексации нужно следовать таким правилам:

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

Источник

Что такое поисковый индекс

28 ноября 2017 Опубликовано в разделах: Азбука терминов. 9915

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

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

Что значит индексация

Это процесс, в ходе которого роботы включают имеющиеся данные в единую базу. Далее они обрабатываются. Сбор данных, формирование индекса может происходить автоматически или вручную. В первом случае робот ищет сайты, для этого он сканирует файл формата sitemap.xml или переходит по внешним ссылкам с других сайтов. Во втором варианте владелец сайта сам добавляет URL сайта в специализированные формы-заявки систем Гугл, Яндекс и так далее.

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

Для чего нужен индекс поисковой системы

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

Индексирование делают роботы, которые бывают двух типов:

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

Чем быстрее сайт добавляется в индекс, тем скорее вы увидите первых посетителей. Индексация Гуглом занимает несколько дней, а индексация Яндексом — несколько недель.

Проверить индексацию в системах Гугл и Яндекс

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

Ускорение индексации

Скорость индексации зависит от факторов:

Если вы желаете увеличить скорость индексации и быстрее войти в поисковую систему, сделайте следующее:

С момента занесения сайта в индекс начинается отсчет возраста сайта.

Источник

Устройство поисковых систем: базовый поиск и инвертированный индекс

Под капотом почти каждой поисковой строки бьется одно и то же пламенное сердце — инвертированный индекс. Именно инвертированный индекс принимает текстовые запросы и возвращает пользователю список документов, а пользователь смотрит на всё это дело и радуется котиками, ответам с StackOverflow и страничкам на вики.

В статье описано устройство поиска, инвертированного индекса и его оптимизаций с отсылками к теории. В качестве подопытного кролика взят Tantivy — реализация архитектуры Lucene на Rust. Статья получилась концентрированной, математикосодержащей и несовместимой с расслабленным чтением хабра за чашкой кофе, осторожно!

Формальная постановка задачи: есть набор текстовых документов, хотим быстро находить в этом наборе наиболее подходящие документы по поисковому запросу и добавлять в набор новые документы для последующего поиска.

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

Определение релевантности

На человеческом языке «релевантность» — это смысловая близость документа к запросу. На языке математики близость может выражаться через близость векторов. Поэтому для математического выражения релевантности необходимо документам и запросам из мира людей сопоставить вектора в некотором пространстве из мира математики. Тогда документ будет считаться релевантным запросу, если документ-вектор и запрос-вектор в нашем пространстве находятся близко. Поисковая модель с таким определением близости зовётся векторной моделью поиска.

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

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

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

NB.: Здесь и далее «слова» в контексте документов и запросов будут называться «термами» с целью избежания путаницы

Запишем релевантность в виде двух математических функций и далее будем наполнять их содержанием:

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

Наиболее известные аддитивные функции релевантности — TF-IDF и BM25. Они используются в большинстве поисковых систем как основные метрики релевантности.

Откуда взялись TF-IDF и BM25

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

И TF-IDF, и BM25 показывают степень релевантности документа запросу одним числом. Чем выше значение метрик, тем более релевантен документ. Сами по себе значения не имеют какой-либо значимой интерпретации. Важно только сравнение значений функций для различных документов. Один документ более релевантен данному запросу, чем другой, если значение его функции релевантности выше.

Попробуем повторить рассуждения авторов формул и воспроизвести этапы построения TF-IDF и BM25. Обозначим размер корпуса проиндексированных документов как . Самое простое, что можно сделать — это определить релевантность равной количеству вхождений терма (termFrequency или ) в документ:

Что делать, если у нас не один терм , а запрос , состоящий из нескольких термов, и мы хотим посчитать запроса для этого документа? Вспоминаем про ограничение аддитивности и просто суммируем все отдельные по термам из запроса:

В формуле выше есть проблема — мы не учитываем различную «важность» разных термов. Если у нас будет запрос «cat and dog», то наиболее релевантными окажутся документы, в которых есть 100500 вхождений терма «and». Вряд ли это то, что хотел бы получить пользователь.

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

— это количество документов в корпусе, содержащих терм . Получается, что чем чаще терм встречается, тем менее он важен и тем меньше будет . Термы вроде «and» будут иметь огромный и соответственно маленький .

Вроде уже лучше, но теперь есть другая проблема — сам по себе мало о чём говорит. Если , и размер корпуса проиндексированных текстов — 100 документов, то терм «жираф» в этом случае считается очень частым. А если размер корпуса 100 000, то уже редким.

Зависимость от может быть убрана превращением в относительную частоту путем деления на :

Теперь представим следующее — у нас 100 документов, в одном из них есть терм «слон», в двух — «жираф». в первом случае будет равно 100, а во-втором — 50. Терм «жираф» получит в два раза меньше очков, чем терм «слон» только лишь потому, что документов с жирафом на один больше, чем со слоном. Исправим эту ситуацию, сгладив функцию .

Сглаживание можно произвести различными способами, мы сделаем это логарифмированием:

Мы только что получили TF-IDF. Едем дальше к BM25.

Вряд ли документ, содержащий терм «жираф» 200 раз в два раза лучше, чем документ, содержащий терм «жираф» 100 раз. Поэтому и тут проедемся сглаживанием, только теперь сделаем это не логарифмированием, а чуть иначе. Заменим на С каждым увеличением числа вхождения терма на единицу, значение прирастает все меньше и меньше — функция сглажена. А параметром мы можем контролировать кривизну этого сглаживания. Говоря по-умному, параметр контролирует степень сатурации функции.

Рис. 0: Чем выше значение , тем сильнее будут учитываться последующие вхождения одного и того же терма.

У есть два замечательных побочных эффекта.

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

Во-вторых, значение функции ограничено сверху. Остальная часть тоже ограничена сверху, поэтому и вся функций имеет ограничение сверху (далее — upper bound). Более того, в нашем случае очень просто посчитать.

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

Последний шаг — начнем учитывать длину документов в . В длинных документах терм «жираф» может встретится просто по-случайности и его наличие в тексте ничего не скажет о реальной теме документа. А вот если документ состоит из одного терма и это терм «жираф», то можно совершенно точно утверждать, что документ о жирафах.

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

Найдем теперь место для длины документа в нашей формуле. Когда растет, то значение падает. Если мы будем умножать на , то получится, что более длинные документы будут получать меньший . То что нужно!

Можно еще дополнительно параметризовать силу, с которой мы учитываем длину документа, для контроля поведения формулы в разных ситуациях. Заменим на и получим:

При формула вырождается в , а при формула принимает вид .

Ещё раз: — сила влияния повторяющихся термов на релевантность, а — сила влияния длины документа на релевантность.

Подставим в :

У нас получилась формула BM25 с небольшим нюансом. В каноничной формуле (этот член называется ) заменен на . Замена не имеет простых эвристик под собой и основана на подгонке под теоретически более чистую форму RSJ модели. Такая форма дает меньший вес слишком часто встречающимся термам: артиклям, союзам и прочим сочетаниям букв, несущим малое количество информации.

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

Реализация инвертированного индекса

С учетом ограниченной памяти, медленных дисков и процессоров нам теперь нужно придумать структуру данных, способную выдавать top-K релевантных по BM25 документов.

Есть у нас набор документов, по которым необходимо вести поиск. Всем документам присваивается document ID или DID. Каждый документ разбивается на термы, термы при желании обрезаются или приводятся к каноничной форме. Для каждого обработанного терма составляется список DID документов, содержащих этот терм — постинг-лист.

Рис. 1: Постинг-листы

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

Вторая часть инвертированного индекса — словарь всех термов. Под словарь используется KV-хранилище, где термы являются ключами, а значения — адреса постинг-листов в RAM или на диске. Обычно для KV-хранилища в оперативной памяти используются хеш-таблицы и деревья. Однако для словаря термов могут оказаться более подходящими другие структуры, например, префиксные деревья.

Рис. 2: Словарь термов (префиксное дерево)

В Tantivy для хранения термов вообще использованы finite-state transducers через crate fst. Если совсем упрощать, то можно считать, что префиксные деревья организуют словарь путем выделения общих префиксов у ключей, а трансдюсеры ещё могут и общие суффиксы выделять. Поэтому сжатие словаря происходит эффективнее, только в итоге получается уже не дерево, а ациклический орграф.

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

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

Используя словарь термов и постинг-листы можно для запроса из одного одного терма определить список документов, в котором этот терм появляется. Затем останется посчитать для каждого документа из постинг-листа и взять top-K документов.

Для этого перенесем из области математики в реальный мир. В Tantivy используется BM25, как один из вариантов функции релевантности:

Поэтому при обходе постинг-листа от начала и до конца первые документов кладутся в кучу (далее top-K heap) безусловно. А затем каждый последующий документ сначала оценивается и кладется в кучу только если его выше минимального из кучи. Текущий минимум в top-K heap далее будет обозначен как .

Операции над постинг-листами для запросов из нескольких термов

Что сделает инвертированный индекс с запросом «скачать OR котики»? Он заведет два итератора по постинг-листам для термов «скачать» и «котики», начнет итерирование по обоим листам, попутно рассчитывая и поддерживая top-K heap.

Аналогичным образом реализуется AND-запрос, однако тут итерирование позволяет пропускать значительные части постинг-листов без расчета для них.

Более важными для поисковиков общего назначения являются OR-запросы. А всё потому, что они покрывают больше документов и потому, что ранжирование запросов метриками TF-IDF или BM25 всё равно поднимает в топ документы с бОльшим количеством совпавших слов. Это сделает top-K документов больше похожим на результат работы AND-запроса.

Наивный алгоритм реализации OR-запроса следующий:

Рис. 3: Итерации OR-алгоритма. Чуть ниже есть псевдокод алгоритма

В п.4 сбор итераторов осуществляется быстро, так как список итераторов отсортирован по DID. Пересортировку итераторов в п.3 тоже можно оптимизировать, если мы знаем какие итераторы были продвинуты в п.6.

Некоторые оптимизации инвертированного индекса

В обычной задаче поиска ищутся не вообще все релевантные документы, а только K наиболее релевантных. Это открывает путь для важных оптимизаций. Причина простая — большая часть документов станет ненужной и мы избежим накладных вычислений над ней. Такая постановка задачи ещё известна как Top-K queries.

Посмотрим внимательнее на псевдокод OR-алгоритма Bortnikov, 2017:

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

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

Сжатие постинг-листов

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

Вспомним, что постинг-лист — это возрастающий список DID, сами DID — обычно 64-битные беззнаковые числа. Числа в постинг-листе не сильно отличаются друг от друга и лежат в достаточно ограниченной области значений от 0 до некоторого числа, сопоставимого с количеством документов в корпусе.

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

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

Постинг-листы хорошо сжимаются varint’ом в несколько раз, но теперь у нас связаны руки — прыгнуть вперед в постинг-листе через N чисел нельзя, ведь непонятно где границы каждого элемента постинг-листа. Получается, что читать постинг-лист мы можем только последовательно, ни о какой параллельности речи не идет.

Для возможности параллельного чтения изобрели компромиссные схемы, похожие на varint, но не совсем. В таких схемах числа разбиваются на группы по N чисел и каждое число в группе кодируются одинаковым количеством бит, а вся группа предваряется дескриптором, описывающим что в группе находится и как это распаковать. Одинаковая длина запакованных чисел в группе позволяет использовать SIMD-инструкции (SSE3 в Intel) для распаковки групп, что кратно ускоряет время работы.

Tantivy упаковывает DID в блоки по 128 чисел, а затем пишет блок из 128 частот термов, используя bitpack-кодировку.

Varint хорошо сжимает малые числа и хуже сжимает большие числа. Так как в постинг-листе находятся возрастающие числа, то с добавлением новых документов качество сжатия будет становиться хуже. Простое изменение — в постинг-листе будем хранить не сами DID, а разницу между соседними DID. Например, вместо [2, 4, 6, 9, 13] мы будем сохранять [2, 2, 2, 3, 4].

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

Скип-листы для итерирования по постинг-листам

Как уже было сказано выше, после сжатия постинг-листов массив чисел превращается в связанный список. Всё, что мы теперь можем сделать — это последовательно обходить список от начала к концу. Хотя до сих пор нам большего и не требовалось, описанные в следующих секциях схемы оптимизации нуждаются в возможности продвигать итераторы на произвольное число DID вперед.

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

Точность прыжка зависит от объема памяти, который мы можем выделить под скип-лист — типичный компромисс в алгоритмах. В Tantivy перемещение вдоль постинг-листа реализовано именно скип-листами. Известна lock-free реализация скип-листа, но на момент написания статьи (март 2021) библиотека выглядит не слишком поддерживаемой.

В нашей реализации скип-листа нужно ещё хранить частичные суммы до того места, куда мы собираемся прыгнуть. Иначе ничего не получится, потому что для постинг-листа мы использовали Delta-encoding.

Оптимизации OR-запросов

Все оптимизации обхода постинг-листов делятся на безопасные и небезопасные. В результате применения безопасных оптимизаций top-K документов остается без изменений по сравнению с наивным OR-алгоритмом. Небезопасные оптимизации могут дать большой выигрыш по скорости, но они меняют top-K и могут пропустить некоторые документы.

MaxScore одна из первых известных попыток ускорить выполнение OR-запросов. Оптимизация относится к безопасным, описана в Turtle, 1995.

Суть оптимизации в разбиении термов запроса на два непересекающихся множества: «обязательных» и «необязательных». Документы, содержащие термы только из «необязательного» множества, не могут войти в top-K и поэтому их постинг-листы могут быть промотаны вперед до первого документа, который содержит хотя бы один «обязательный» терм.

Помните терма, введеный в разделе про TF-IDF и BM25? Напоминаю, что это условная «важность» терма. Общераспространенные слова имеют малую важность, а специфичные — высокую. является функцией от частоты встречаемости терма и может быть рассчитан на лету по размеру постинг-листа.

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

Имеет смысл рассматривать только те документы, которые содержат хотя бы один терм из «обязательного» множества термов. Поэтому мы можем промотать постинг-листы «необязательных» термов до наименьшего из DID‘ов, на которые указывают итераторы «обязательных» термов. Тут-то нам и нужны скип-листы, без них пришлось бы бежать по постинг-листам последовательно и никакого выигрыша в скорости не получилось бы.

Рис. 4: Промотка итераторов в MaxScore

После каждого обновления top-K heap производится перестроение двух множеств и алгоритм завершает работу в момент, когда все термы оказываются в «необязательном» множестве.

WAND также является безопасным методом оптимизации поиска, описанным в Broder, 2003. В чем-то он похож на MaxScore: также анализирует частичные суммы и .

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

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

После этого, мы возвращаемся на первый шаг алгоритма

BMW является расширением алгоритма WAND из предыдущего пункта, предложенным в Ding, 2011. Вместо использования глобальных для каждого терма, мы теперь разбиваем постинг-листы на блоки и сохраняем отдельно для каждого блока. Алгоритм повторяет WAND, но проверяет в дополнение еще и частичную сумму блоков, на которые сейчас указывают итераторы. В случае, если эта сумма ниже , то блоки пропускаются.

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

Для понимания разрыва между продакшеном инвертированных индексов и академическими исследованиями можно занырнуть в широко известный в узких кругах тикет LUCENE-4100.

TLDR: Реализация важной Block-max WAND-оптимизации молчаливо дожидалась смены TF-IDF на BM25, заняла 7 лет и была выкачена только в Lucene 7.

Block Upper Scoring

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

Автор статьи экспериментировал с поиском, в котором необходимы были только свежие документы-новости. BM25 была заменена на где — функция, накладывающая пенальти на устаревающие документы и принимающая значения от 0 до 1. Поменяв формулу для , удалось добиться пропуска 95% всех блоков с несвежими новостями, что сильно ускорило конкретно этот вид поиска. Сам подход с хранением поблочных метрик, а также вычислимым и конечным пределом функции релевантности располагает к экспериментам.

Предварительная обработка поискового запроса

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

Разбор поискового запроса

Рис. 5: Этапы обработки поискового запроса

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

Будут ли токены соединены по умолчанию оператором OR или AND зависит от настроек индекса. С одной стороны — соединение через AND иногда может дать более точный результат, с другой — есть риск вообще ничего не найти. Можно составить несколько запросов и после их выполнения на основе размера выдачи или внешних метрик выбрать лучший вариант.

Логическое дерево ложится в основу плана операций. В Tantivy соответствующая структура называется Scorer. Реализация Scorer является центром вселенной инвертированных индексов, так как эта структура ответственна за итерирование постинг-листов и за все возможные оптимизации этого процесса.

Этап расширения поискового запроса

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

Запрос разбавляется синонимами, термам добавляются веса, используется история предыдущих поисков, добавляются фильтры, контекст поиска и миллион других хаков, являющихся коммерческими секретами. Этот этап работы называется query extension, он невероятно важен для улучшения качества поиска.

На этапе расширения поисковых запросов дешево проводить эксперименты. Представьте, что вы хотите выяснить, даст ли вам какой-либо профит использование морфологии при поиске. Морфология в этом контексте — приведение разных словоформ к каноничной форме (лемме).

У вас есть несколько вариантов:

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

В архитектуре Lucene инвертированный индекс нарезан на сегменты. Сегмент хранит свою часть документов и является неизменяемым. Для добавления документов мы собираем в RAM новые документы, делаем commit и в этот момент документы из RAM сохраняются в новый сегмент.

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

Сегменты могут обрабатывать запросы одновременно, поэтому сегмент является естественной единицей распараллеливания нагрузки. Сложность здесь возникает только в слиянии результатов из разных сегментов, так как нужно выполнять N-Way Merge потоков документов от каждого сегмента.

Тем не менее, много маленьких сегментов — плохо. А такое иногда случается, когда запись ведется небольшими порциями. В таких ситуациях Tantivy запускает процедуру слияния сегментов, превращая много маленьких сегментиков в один большой сегмент.

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

Шардирование

Существует два способа распараллеливания нагрузки на инвертированный индекс: по документам или по термам.

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

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

Поскольку в инвертированном индексе перестроение сегментов является сложной операцией, лучше сразу начать использовать схемы типа Ring или Jump Consistent Hashing для снижения объемов перешардируемых документов при открытии нового шарда.

Многофазовые поиски и ранжирование

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

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

Первая фаза двухфазовых (или даже многофазовых) поисков делает всё тоже самое. А вот на второй фазе происходит переранжирование top-K документов из первой фазы с использованием более тяжелых для вычисления метрик. Такое деление оправдано, поскольку отделяет быструю первую фазу на всем множестве документов от тяжелой второй фазы на ограниченном множестве документов.

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

Кстати, при шардировании индекса удобно сервера второй фазы использовать для агрегирования документов от шардов первой фазы.

Первая фаза ранжирования

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

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

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

В веб-поиске роль члена обычно исполняет PageRank, рассчитываемый раз в N дней на больших кластерах MapReduce. Посчитанный PageRank записывается в быстрое KV-хранилище инвертированного индекса, такое как FastFields в случае Tantivy и используется при вычислении релевантности.

Документы из других источников могут иметь другие метрики. Например, для поиска по научным статьям имеет смысл использовать импакт-фактор или индекс цитирования.

Вторая фаза ранжирования

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

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

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

Качество поиска

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

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

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

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

Далее пара метрик, с которых вам стоит начать. Они просто формулируется даже в терминах SQL-запроса, особенно если у вас что-то типа Clickhouse для хранения логов.

Самое первое и очевидное — нашёл ли вообще пользователь у вас хоть что-нибудь в рамках сессии.

Хорошее введение в MAP@k, а также в несколько других learning-to-rank метрик есть на Хабре. Скорее всего первое, что вы посчитаете из серьезных метрик. Метрика характеризует насколько хороший у вас top-K документов, где K обычно берется равным количеству элементов на странице поисковой выдачи.

Вместо заключения: Google и их первый инвертированный индекс

Рис. 6: Вот что бывает, когда программистов заставляют рисовать схемы против их воли (воспроизведение оригинальной блок-схемы из Brin, 1998)

Студенты Сергей Брин и Ларри Пейдж создали первую версию Google и проиндексировали около 24 миллионов документов в 1998 году. Скачивание документов студенты реализовали на Python, всего они запускали по 3-4 процесса паука. Один паук объедал примерно по 50 документов в секунду. Полное заполнение базы занимало 9 дней, выкачивалось под сотню ГБ данных. Сам индекс исчислялся десятками ГБ.

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

Основа индекса — файлы в формате Barrel. Barrel — текстовый файл, хранящий четверки ⟨did, tid, offset, info⟩, отсортированные по ⟨did, offset⟩. В этой нотации did — id документа, tid — id терма, offset — позиция терма в документе.

В оригинальной системе было 64 таких Barrel файла, каждый из которых отвечал за свой диапазон термов (tid). Новый документ получал новый did и соответствующие четверки дописывались в конец Barrel файлов.

Набор таких Barrel файлов является прямым индексом, позволяющий достать список термов для заданного did бинарным поиском по did (файлы же отсортированы по did). Получить инвертированный индекс из прямого можно операцией обращения — берем и сортируем все файлы по ⟨tid, did⟩.

Рис. 7: Пересортировка Barrel-файлов

Всё! Ещё раз — мы пересортировываем одновременно 64 файла и получаем инвертированный индекс из прямого, так как теперь бинарным поиском можно искать уже по tid.

За форматом Barrel-файлов совершенно явно выглядывают уши MapReduce концепции, полноценно реализованной и задокументированной в работе J.Dean, 2004 позже.

О Google в общем доступе находится много вкусных материалов. Начать можно с оригинальной работы Brin, 1998 об архитектуре поиска, дальше потыкать в материалы Университета Нью-Джерси и шлифануть всё презентацией J.Dean о внутренней кухне первых версий индекса.

Представляете, приходите вы на работу, а вам говорят, что весь следующий год каждый месяц вам нужно будет ускорять код на 20%, чтобы дебит с кредитом сошлись. Так жил Google в начале нулевых годов. Разработчики в компании уже до того доигрались, что насильно переселяли файлы индекса на внешние цилиндры HDD — у них линейная скорость вращения выше была и файлы считывались быстрее.

К счастью, в 2021 году такие оптимизации уже не особо нужны. HDD практически вытеснены из оперативной работы, а индекс, начиная с середины 2010-ых, целиком размещается в RAM.

Источник