1. Введение

Как инструмент поиска Apache с открытым исходным кодом, Lucene всегда был волшебным оружием для реализации поисковых функций.Сегодняшние популярные Solr и Elasticsearch разработаны на основе этого набора инструментов.Наша команда отзыва поиска также реализовала набор построения индекса на основе Lucene.Механизм , используется для поиска отелей, поиска билетов, поиска и других связанных с поиском операций.

А Lucene может сыграть жизненно важную роль в поиске именно благодаря инвертированному индексу.

Поэтому в этой статье будет представлена ​​концепция инвертированного индекса и реализация инвертированного индекса в Lucene.

2 Основные принципы

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

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

select * from hotel_table where hotel_name like '%公寓%';

На самом деле с этой реализацией много проблем:

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

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

Инвертированный индекс — это концепция, которая отличается от прямого индекса:

• Положительный индекс: в качестве индекса используется уникальный идентификатор объекта документа, а в качестве структуры записи используется содержимое документа.
• Инвертированный индекс: инвертированный индекс относится к структуре использования слова в содержимом документа в качестве индекса и идентификатора документа, содержащего слово, в качестве записи.

Ниже приведен пример, иллюстрирующий процесс генерации нижнего инвертированного индекса.
Предположим, что в настоящее время имеется два содержимого документа:

Улица Сучжоу через здание

Orange Hotel Suzhou Street Branch

Шаги обработки следующие:

1. Положительный индекс нумерует каждый документ как его уникальный идентификатор.

2. Создайте инвертированный индекс:

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

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

Например, если вам нужно запросить два вышеуказанных документаАпельсины улицы Сучжоу, которое может быть передано после причастияулица Сучжоунашел1,2,пройти черезапельсиннашел2, а затем перейдите кбери бери иПодождите, пока операция даст окончательный результат.

2.2 Структура инвертированного индекса

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

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

Таблица записей состоит из всех данных (Публикации), соответствующих термину, Это не только информация об идентификаторе документа, но может содержать следующую информацию:

• ID документа (DOCID, ID документа), все документы, содержащие слово уникальный идентификатор для пересылки индекса для запроса исходных данных.
• Частота терминов (TF, Частота терминов), которая записывает количество вхождений термина в каждом документе для последующих оценок релевантности.
• Позиция (Position), запись позиции сегментации слова (несколько) Термина в каждом документе, используемом для поиска слова (Phrase Query).
• Смещение, которое записывает начальную и конечную позицию термина в каждом документе, для выделения и т. д.
  

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

В случае массивных данных полнотекстовым поисковым системам необходимо хранить большой объем текста, поэтому они сталкиваются со следующими проблемами:

• Словарь относительно большой (например, поле в нашем поиске может содержать десятки миллионов терминов)
• Сообщения могут занимать много места (у термина миллионы документов)

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

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

С этой целью Lucene представляет множество продуманных структур данных и алгоритмов. Его реализация инвертированного индекса имеет следующие особенности:

• Хранить на диске с низкой стоимостью хранения (размер индекса составляет около 20-30% индексируемого текста).
• Быстро читать и писать

Далее будет проанализирована реализация в Lucene в соответствии со структурой инвертированного индекса с точки зрения списка публикаций и словаря терминов.

3.1 Реализация списка сообщений

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

• Файл суффикса .doc: запишите информацию docId для проводок и частоту слова для термина.
• Файл суффикса .pay: запись информации о полезной нагрузке и информации о смещении
• Файл суффикса .pos: запись информации о местоположении

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

Общая реализация трех файлов не слишком велика.Здесь файл .doc используется в качестве примера для анализа его реализации.

В файле .doc хранится идентификатор документа и частота терминов, соответствующие каждому термину. Каждый термин содержит пару структур TermFreqs и SkipData.

Среди них TermFreqs хранит информацию о docId и частоте слов, а SkipData — это информация таблицы пропусков, которая используется для реализации быстрого перехода внутри TermFreqs.

3.1.1 TermFreqs

TermFreqs хранит номер документа и частоту соответствующего термина, которые представляют собой два значения int во взаимно однозначном соответствии. Чтобы максимально сжать данные, Lucene использует гибридное хранилище, состоящее из PackedBlock и VIntBlocks.

PackedBlock

Он использует структуру PackedInts для сжатия int[] в компактный блок. Его метод сжатия состоит в том, чтобы взять битовую длину, занимаемую максимальным значением в массиве, в качестве длины бюджета, а затем усечь каждый элемент массива в соответствии с этой длиной для достижения цели сжатия.

Например: максимальное значение в массиве int, содержащем 128 элементов — 2, тогда длина бюджета — 2 бита, длина PackedInts — всего 2 * 128/8 = 32 байта, и тогда его можно хранить 4 длинными значениями.

VIntBlock

VIntBlock использует VInt для сжатия значений int.Для большинства языков тип int занимает 4 байта, независимо от того, являются ли данные 1, 100, 1000 или 1000 000. VInt принимает байты переменной длины для представления целого числа. Число с большим значением представлено большим количеством байтов, а число с меньшим значением представлено меньшим количеством байтов. Каждый байт использует только биты с 1-го по 7-й (всего 7 бит) для хранения данных, а 8-й бит используется в качестве флага, указывающего, следует ли продолжать чтение следующего байта.

Например:

Когда целое число 130 имеет тип int, ему требуется 4 байта.После преобразования в VInt используются только 2 байта.8-й бит первого байта равен 1, указывая на то, что необходимо прочитать второй байт.

В соответствии с характеристиками двух вышеуказанных блоков Lucene будет обрабатывать каждые 128 документов, содержащих Term, а соответствующие массивы DocId и TermFreq будут преобразованы в структуры PackedInt PackedDocDeltaBlock и PackedFreqBlock соответственно. Используйте VIntBlock для хранения.

3.1.2 SkipData

При поиске выполняется операция пересечения наборов DocId, соответствующих каждому термину, то есть оценка того, существует ли DocId одного термина в TermFreqs другого термина. DocId в каждом блоке в TermFreqs упорядочены и могут быть запрошены путем последовательного сканирования, но если имеется слишком много документов, соответствующих термину, эффективность поиска будет очень низкой, а поскольку размер блока не фиксирован, мы не можем использовать Это дихотомический способ запроса. Поэтому, чтобы уменьшить количество сканирований и сравнений, Lucene использует SkipData, структуру таблицы пропуска, для достижения быстрого пропуска.

пропустить стол

Список пропуска предназначен для добавления многоуровневого индекса к исходному упорядоченному связанному списку и реализации быстрого поиска по индексу.

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

Структура SkipData

Каждый раз, когда блок генерируется в TermFreqs, узел будет генерироваться на 0-м уровне SkipData, а затем узел верхнего уровня будет генерироваться через каждые N узлов выше 0-го уровня.

Каждый узел связан с узлами более низкого уровня через атрибут Child.Атрибут DocSkip в узле хранит максимальное значение DocId блока.DocBlockFP, PosBlockFP и PayBlockFP указывают, что данные блока соответствуют расположению .pay, . pos и файлы .doc.

3.1.3 Размещение окончательных данных

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

• SkipOffset: используется для описания начальной позиции информации о текущем термине в информации таблицы пропуска файла .doc.
• DocStartFP: начальная позиция идентификатора документа и информации о частоте терминов для информации о текущем термине в файле .doc.
• PosStartFP: начальная позиция информации о текущем термине в файле .pos.
• PayStartFP: начальная позиция информации о текущем термине в файле .pay.

3.2 Реализация словаря терминов

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

3.2.1 Хранение данных

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

На приведенном выше рисунке вы можете видеть, что Блок также содержит Блок, Это необходимо для обработки внутренней части набора терминов, содержащего тот же префикс.Терм содержит тот же префикс.

Например, на рисунке ниже представлен набор Term с общим префиксом a, а внутренняя часть Term содержит такой же префикс ab, то эта часть Term будет обрабатываться как вложенный Блок.

3.2.2 Поиск данных

Словарь терминов хранится в файле .tim с помощью NodeBlock. С увеличением количества документов будет увеличиваться и количество терминов в Словаре, а эффективность запросов неизбежно будет постепенно снижаться.

Поэтому для создания индекса для словаря необходима хорошая структура данных, которая представляет собой индекс терминов (хранилище файлов .tip). Lucene использует структуру данных FST для реализации этого индекса.

FST

FST, полное название преобразователя конечного состояния (Finite State Transducer).

Он имеет следующие характеристики:

• Учитывая ввод, вы можете получить вывод, который эквивалентен HashMap.
• Общий префикс, экономия места суффикса, потребление памяти FST намного больше, чем HashMap
• Сложность поиска слов O(len(str))
• Неизменяемый после сборки

На следующем рисунке показан FST, сгенерированный mon/1, thrus/4 и tues/2.Вы можете видеть, что thrus и tues имеют общий префикс t и суффикс s.

Согласно FST, искомый термин может использоваться в качестве входных данных, а значения на краях пути могут быть накоплены для получения выходных данных Ниже приведена логика чтения с вводом в качестве сквозного:

• исходное состояние 0
• Вход T, FST от 0 -> 3, вывод = 2
• Вход h, FST от 3 -> 4, выход=2+2=4
• Вход r, FST от 4 -> 5, выход=4+0
• Вход u, FST от 5 -> 7, выход=4+0
• Вход s, FST достигает конечного узла, выход=4+0=4

Итак, каковы соответствующие входные и выходные данные FST, созданные Словарем терминов? Можно ошибиться, что на вход FST подается весь Термин в Словаре, так что данные Проводки, соответствующие конкретному Термину, можно найти через FST.

Фактически, FST формируется префиксом каждого NodeBlock в словаре, поэтому с помощью FST вы можете только напрямую найти конкретный указатель файла этого NodeBlock в файле .tim, а затем вам нужно пройти суффикс, соответствующий Entry, в NodeBlock. найти его.

Таким образом, в Lucene она действует как следующая функция:

1. Быстрый метод проб и ошибок, то есть, если вы не можете найти его на FST, вы можете перейти напрямую, не просматривая весь словарь, аналогично BloomFilter.
2. Чтобы быстро определить положение блока, положение блока в файле можно рассчитать напрямую с помощью FST.
3. FST также является Автоматизацией (автоматическим конечным автоматом). Это реализация регулярных выражений, поэтому FST может предоставлять возможности регулярных выражений. FST может значительно повысить производительность приближенных запросов, включая запросы с подстановочными знаками, SpanQuery, PrefixQuery и т. д.

3.3 Инвертированная логика запроса

После введения структуры индексной таблицы и таблицы записей можно получить шаги запроса инвертированного индекса Lucene:

• Получите FST указанного поля через StartFP в данных Term Index (файл .tip)
• Найдите блок, который может существовать в словаре терминов (файл .tim) для указанного термина с помощью FST.
• Загрузите соответствующий блок в память, просмотрите запись в блоке и определите, существует ли указанный термин через суффикс (суффикс)
• Если он существует, данные проводки получаются через FP каждого файла в данных TermStat записи.
• Если вам нужно получить все DocId, соответствующие термину, перейдите напрямую к TermFreqs.Если вы хотите получить указанные данные DocId, вы можете быстро перейти через SkipData.
  

4 Обработка числовых типов Lucene

Реализации вышеупомянутого словаря терминов и списка публикаций имеют дело с термином строкового типа, но для числового типа, если реализация реализована вышеописанным способом, возникнут следующие проблемы:

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

Поэтому Lucene представила BKDTree для поддержки эффективных числовых классов или многомерных запросов.

4.1 KDTree

BKDTree основан на KDTree, который реализован как двоичное дерево поиска. Основное отличие состоит в том, что KDTree использует разные значения размерности на разных слоях.

Ниже приведен пример двумерного дерева.Первый слой принимает x в качестве измерения сегментации, а узлы с x>30 передаются в правое поддерево, узлы с x

4.2 BKDTree

Дерево BKD представляет собой комбинацию дерева KD и дерева B+ и обладает следующими свойствами:

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

5 Резюме

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

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

использованная литература

Анализ исходного кода Lucene:www.amazingkoala.com.cn/Lucene/
Дерево Lucene BKD: https://www.shenyanchao.cn/blog/2018/12/04/lucene-bkd/
Принцип и анализ запросов Lucene:Woohoo.info Q.Can/article/Sister E…
Изучение инвертированного индекса Lucene: https://www.6aiq.com/article/1564413040138 Lucene
Словарь FST углубленного анализа:Woohoo, Шэнь Янчао, Talent/blog/2018/1…