В сегодняшней статье мы продолжаем обсуждать поисковые системы и поговорим с вами о самой важной части поисковых систем -Перевернутый индекс.
Прежде чем представить инвертированный индекс, давайте посмотрим, что такое индекс. Индекс — это понятие в базе данных, как говорит Википедия.Индекс базы данных — это отсортированная структура данных в системе управления базой данных, помогающая быстро запрашивать и обновлять данные в таблицах базы данных."Указатель можно просто рассматривать как каталог поиска в словаре. Например, мы хотим найти слово под названием "указатель". С помощью каталога мы можем быстро найти позицию, где начинается буква я. Индекс тоже самое,но не ищем.Опять первая буква слова,но данные.
В предыдущей статье о поисковых системах мы говорили, что после того, как краулер поисковой системы просканирует текстовую информацию веб-страницы, он сначала произведет сегментацию слов, а затем сохранит ее. То есть хранитсяне полная документация, но в документацииИнформация о ключевом слове. Очевидно, что количество веб-страниц, содержащихся в поисковой системе, чрезвычайно велико, и для обеспечения эффективности мы должны использовать индекс.
Мы называем каждую веб-страницуДокументация(документ), подготовьтеидентификатор документа,ПотомОбъединение ключевых слов в документах через связанные спискиВстаньте. Тогда структура данных должна выглядеть так.
На этом рисунке мы используем идентификатор документа для запроса информации о ключевом слове, содержащейся в документе. Сначала мы проверяем соответствующий документ, а затем проверяем в нем идентификатор.Это запрос, который соответствует нашему повседневному мышлению, поэтому считается "переслать запросПоэтому такая индексная структура называетсяфорвардный индекс.
Но только прямой индексации недостаточно, например, если пользователь ищет «Пекинский университет», мы можем получить два ключевых слова «Пекин» и «Университет». Мы надеемся, что соответствующие документы можно будет найти с помощью этих двух ключевых слов.Мы не знаем идентификатор документа. То есть это обратный запрос, используя словарь в качестве аналогии, мы надеемся запросить его положение в словаре через слово.
Чтобы сделать это, когда у нас есть только прямой индекс, мы должны перебрать все документы и выбрать документы, содержащие ключевые слова «Пекин» и «Университет», один за другим. Мы снова можем легко увидеть, что это нежелательно. Итак, чтобы решить эту проблему, мы должны построить обратный индекс,Укажите на документ по ключевому слову. Таким образом, мы можем быстро отфильтровать соответствующую информацию о документе по ключевым словам.
Этот инвертированный индекс является инвертированным индексом.
С перевернутым индексом все остальное намного проще. Мы можем легко вызвать все документы, содержащие ключевые слова по ключевым словам, а затем пройти соответствующий алгоритм.Рассчитать корреляцию между каждым документом и ключевым словом, ты можешь сделатьПроверка релевантности. Это также фильтрация релевантности, упомянутая в предыдущем введении к поисковым системам.
Вся технология инвертированного индекса не должна быть трудной для понимания, но реальная работа более сложна и требует множества оптимизаций. Ниже представлена наиболее широко используемая из многих схем оптимизации.
Оптимизация в ElasticSearch
Говоря об инвертированных индексах, нельзя не упомянуть ElasticSearch. Можно сказать, что ElasticSearch является наиболее широко используемой поисковой системой с открытым исходным кодом в мире. ElasticSearch неотделим от Wikipedia, GitHub, Baidu, Tencent и бесчисленного множества малых и средних компаний. Он объединяет через системуПоисковая система, полнотекстовый поиск, структурированный анализи многие другие функции, а такжеПростая конфигурация, превосходная производительностьИ Т. Д.
Как распределенная поисковая система, ElasticSearch имеет множество оригинальных шаблонов проектирования, в сочетании со сложностью самой распределенной системы есть много вещей, которые можно изучить. В сегодняшней статье в основном речь пойдет об инвертированных индексах, поэтому я кратко расскажу об оптимизации инвертированных индексов.
Как упоминалось в предыдущей статье, мы достигаем цели поиска по ключевым словам, устанавливая инвертированный индекс для ключевых слов. По логике конечно проблем нет, но на самом деле проблема не маленькая. Самая большая проблема в том, что таких ключевых слов слишком много, и это нормально, и эти ключевые слова не по порядку.Если мы хотим найти одно из них, мы можем только пройтись по всем таблицам ключевых слов. Для нас это явно неприемлемо, и здесь необходимо проводить оптимизацию.
Одна из самых простых оптимизаций заключается в выполнении этихСортировать по ключевому слову, мы сортируем после созданияСловарь(Словарь). После того, как у нас есть словарь, мы можем пройтиБинарный поиск классаСделайте быстрый поиск сейчас. Вроде все идеально, но проблемы все же есть.
Со сложностью проблем нет, сложность O(logN) приемлема, неприемлемачтение с диска. Поскольку этот словарь слишком велик, нам нужны служебные данные для каждого поиска на диске, а каждое случайное чтение диска занимает 10 мс времени. Это также неприемлемо для высокопроизводительной системы.
Чтобы оптимизировать этот ответ, мы должныУменьшить количество случайных чтений с диска.
Лучший способ сократить использование диска — хранить данные в памяти. Но как мы уже говорили ранее, этот словарь слишком большой, и очень вероятно, что он не поместится в памяти. Поэтому нам нужно снова выполнить простую индексацию, например:
Ключевые слова, начинающиеся с буквы A, хранятся на странице x Ключевые слова, начинающиеся с буквы B, хранятся на странице y...
На самом деле это способ поиска в словаре, но проблема в том, что если все ключевые слова на английском языке, вы, конечно, можете это сделать. Однако поисковые системы поддерживают не только английский, ключевые слова могут быть на разных языках и даже с разными символами. И даже в английском языке количество индексов, соответствующих каждой букве, неодинаково. Например, есть много слов, начинающихся с буквы s, но очень мало слов, начинающихся с буквы z. Если эта простая операция, на самом деле, не обязательно повышает эффективность работы.
Итак, чтобы решить эту проблему, нам нужно ввести структуру данных, а именноПрефиксное дерево (дерево Trie).
Дерево префиксов выглядит так:
Принцип префиксного дерева не сложен, на самом деле он заключается в том, чтобы поставитьСтроки с одинаковым префиксом сопоставляются с одной и той же веткой дерева.среди. В конце каждой вилки записывается расположение контента, соответствующего этому префиксу. Фактически это означает, что исходный индекс плоского хранилища отображается на дерево. Однако не все индексы хранятся в дереве префиксов, сохраняются только некоторые префиксы ключевых слов. Через префикс мы можем найти определенную позицию в словаре, а затем выполнить поиск в обратном направлении от этой позиции, так чтоИзбегает чрезмерного использования случайной адресации жестких дисков, тем самым экономя время.
В качестве примера возьмем следующий рисунок:
Например, искомое ключевое слово «Access", через дерево префиксов мы сначала находим расположение словаря, соответствующее префиксу А, который является расположением Ады на рисунке. Затем мы начинаем с Адыпройти назад, пока не будет найден доступ. Разумно построив префиксное дерево, мыМожет контролировать накладные расходы на обход словаря, чтобы достичь цели оптимизации.
В дополнение к этому ElasticSearch также сделал некоторые оптимизации для совместного запроса индекса и слияния индексов. Из-за некоторых других задействованных технологий и структур данных, а также ограничений по объему я не буду здесь вдаваться в подробности. Я поделюсь им с вами в следующей статье.
Если вы чувствуете, что что-то приобрели, просто нажмитеобрати внимание набар~