Введение в инвертированные индексы

Понимание перевернутых Индексов (Серия из 3 частей)

Вы можете ознакомиться с первым постом этой серии здесь. Чтобы знать обо всех предстоящих статьях серии.

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

Темы, на которые следует обратить внимание в этой статье:

    * Introduction to Information Retrieval
    * What is an Inverted Index ?
    * Traditional database vs Search Engine
    * Components of Inverted Index
    * Dictionary
    * Posting Lists

Введение в поиск информации Предположим, вы хотели определить, что все новостные статьи Washington Post содержат слова “окружающая среда” и “здоровье” с момента ее создания. Один из подходов состоит в том, чтобы начать с самого начала и прочитать весь текст, записывая каждую статью, содержащую упомянутые слова. Этот метод обычно называют grepping сквозным текстом. И этот процесс займет полжизни, чтобы завершить его, довольно грустно, не так ли? Так что же нам делать? Одним из наиболее популярных способов избежать такого линейного сканирования для каждого запроса является индексирование документов заранее. При правильном индексировании вы можете выполнить вышеупомянутую задачу за несколько секунд/минут на современных машинах. Одним из таких индексов, который широко используется при индексировании большого набора данных, являются Инвертированные индексы . Все ваши популярные поисковые системы, такие как Elasticsearch/Lucene/Solr, активно используют инвертированные индексы, чтобы предоставить вам удивительно быстрые поисковые системы.

Что такое Перевернутый индекс ? Как это делает поиск информации таким быстрым?

Выражаясь предельно простыми словами – “Обратный/инвертированный индекс обеспечивает сопоставление терминов и их местоположения в текстовой коллекции”. Поэтому вам не нужно сканировать всю коллекцию текстов для извлечения информации, что в конечном итоге сокращает время поиска. Множество других функций, таких как ранжированное извлечение , исправление орфографии , могут быть реализованы в этой системе перевернутых индексов, чтобы обеспечить гораздо больше функциональных возможностей.(Эти темы будут рассмотрены позже в этой серии)

Традиционная база данных (Прямые индексы) против поисковых систем (Инвертированный индекс)

Давайте предположим, что нашей системе нужна коллекция, состоящая из 4 документов: Doc1, Doc2, Doc3, Doc4 Doc1 :: Добро пожаловать в отель Калифорния, Такое прекрасное место Док 2 : Она покупает лестницу на Небеса Документ3 : Эй, Джуд, не делай все плохо Документ4 : Забери меня на небеса

В традиционной базе данных SQL данные будут выглядеть примерно так:

И совершенно очевидно, что для любых данных/информации поиск на основе Содержимого документа столбца будет сложным и сложным. Производительность в традиционных базах данных SQL повышается за счет запросов по первичному ключу или создания эффективных “индексов” для обхода этих таблиц БД. Вы можете использовать инвертированные индексы в SQL Db, таких как postgresql, но они не так эффективны, как в поисковых системах, таких как elasticsearch/lucene и т. Д. Индексы, используемые в SQL, такие как индекс B-дерева (по умолчанию), хэш-индексы являются своего рода прямыми индексами , как правило, сопоставляются с документом (он же идентификатор документа) для всей строки данных.

Принимая во внимание, что та же самая операция с поисковой системой значительно упрощена. Благодаря использованию обратных индексов поиск информации по огромному количеству документов сравнительно очень прост и эффективен по сравнению с традиционными базами данных. В Обратных индексах сопоставление происходит от “терминов” к документам (как показано в таблице ниже)

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

Чтобы узнать больше о различиях между прямыми и инвертированными индексами, вы можете прочитать эту статью: Прямые и перевернутые индексы- различия, основанные на требованиях

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

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

Словарь

Словарь работает как структура данных поиска поверх списков публикации. Учитывая перевернутый индекс и запрос, наша первая задача состоит в том, чтобы определить, существует ли каждый термин запроса в словаре. Как и в примере с Washington Post, нам сначала нужно определить, действительно ли слово “окружающая среда” присутствует в нашем словаре, то есть в перевернутом индексе, и если да, то определить соответствующие публикации. Эта операция поиска использует классическую структуру данных, называемую словарем. В нем есть два широких раздела решений: хеширование и деревья поиска . Мы рассмотрим их в следующих статьях.

Список публикаций

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

Вот диаграмма, которая показывает очень упрощенную структуру перевернутого индекса

)

Стоп-слова : Некоторые чрезвычайно распространенные слова, которые, по-видимому, не имеют большого значения для выбора документов, соответствующих требованиям запроса, полностью исключены из словаря | . Как a, an, и, являются, как и т. Д.

Термины в левом столбце перевернутой индексной таблицы содержит весь словарь нашей коллекции, который мы получили в результате анализа N документов.

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

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

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

Спасибо. Оставайся В Безопасности, Оставайся Сильным.

Понимание перевернутых Индексов (Серия из 3 частей)

Оригинал: “https://dev.to/im_bhatman/introduction-to-inverted-indexes-l04”