В данной статье будет проанализирован принцип полнотекстового поиска (На основе Люсен), проанализируйте, как он создает индексы, как запрашиваются индексы и почему он такой быстрый! Это быстрее, чем вы?
Описание принципа полнотекстового поиска
Существует два основных метода поиска неструктурированных данных, то есть полнотекстовых данных:
одинСерийное сканирование: Так называемое последовательное сканирование, такое как поиск файла, содержащего определенную строку, заключается в просмотре одного документа по одному документу, для каждого документа, от начала до конца, если документ содержит эту строку, то этот документ - это то, что мы ищем файл, затем переходим к следующему файлу, пока все файлы не будут отсканированы.
Например, использование поиска Windows также может искать содержимое файла, но довольно медленно. Если у вас есть жесткий диск 80G, если вы хотите найти на нем файл, содержащий определенную строку, вы не сможете сделать это, не потратив несколько часов.
Команда grep под Linux работает так же. Вы можете подумать, что этот метод относительно примитивен, но для файлов с небольшим объемом данных этот метод по-прежнему является наиболее прямым и удобным. Но для большого количества файлов этот способ медленный.
Некоторые люди могут сказать, что последовательный просмотр неструктурированных данных очень медленный, но поиск структурированных данных относительно быстрый (поскольку структурированные данные имеют определенную структуру, для ускорения скорости можно использовать определенный алгоритм поиска), тогда возьмем наш неструктурированные данные Разве недостаточно преобразовать данные в способ иметь определенную структуру?
Эта идея очень естественна, но она составляет основную идею полнотекстового поиска, т. е.Извлеките часть информации из неструктурированных данных, реорганизуйте ее так, чтобы она имела определенную структуру, а затем выполните поиск данных с определенной структурой, чтобы достичь цели относительно быстрого поиска..
Эту часть информации, извлеченную из неструктурированных данных и затем реорганизованную, мы называемпоказатель.
Это утверждение относительно абстрактно. Его легко понять на нескольких примерах. Например, словарь, таблица пиньинь и таблица корневых контрольных слов словаря эквивалентны индексу словаря. Интерпретация каждого слова неструктурирована. , Если в словаре нет Таблицы слогов и корней, проверьте таблицу слов, чтобы найти слово в огромном море слов, вы можете только просмотреть его последовательно. Тем не менее, некоторая информация о слове может быть извлечена для структурированной обработки, например, произношение, которое более структурировано.Есть только несколько типов инициалей и финалей, которые можно перечислить один за другим, поэтому произношения вынимаются и располагаются в Произношение указывает на количество страниц, на которых слово подробно объясняется. Когда мы ищем по структурированному пиньинь, чтобы получить произношение, а затем по количеству страниц, на которые он указывает, мы можем найти наши неструктурированные данные, то есть объяснение слова.
Этот процесс сначала построения индекса, а затем поиска по индексу называется полнотекстовым поиском..
Полнотекстовый поиск можно условно разделить на два процесса: создание индекса (индексирование) и поисковый индекс (поиск).
создание индекса: процесс извлечения информации из всех структурированных и неструктурированных данных в реальном мире и создания индекса.
индекс поиска: это процесс получения запроса пользователя, поиска в созданном индексе и возврата результата.
Таким образом, при полнотекстовом поиске возникают три важные проблемы:
-
Что именно хранится в индексе? (Показатель)
-
Как создать индекс? (Индексирование)
-
Как искать индекс? (Поиск)
Ниже мы рассмотрим каждый вопрос по порядку.
Что в индексе?
Что именно нужно хранить в индексе?
Сначала давайте посмотрим, почему последовательное сканирование работает медленно: ФактическиИз-за несоответствия между информацией, которую мы хотим найти, и информацией, хранящейся в неструктурированных данных.. Информация, хранящаяся в неструктурированных данных, — это строки, которые содержит каждый файл, то есть известные файлы, и сравнительно легко получить строки, то есть отображение файлов в строки. И информацию, которую мы хотим искать, это какие файлы содержат эту строку, то есть известную строку, и нужный файл, то есть отображение из строки в файл. Эти двое совершенно противоположны. Поэтому, если индекс всегда может сохранять отображение строк в файлы, это значительно улучшит скорость поиска. Поскольку отображение строк в файлы является обратным преобразованию файлов в строки, индекс, который содержит эту информацию, называетсяобратный индекс.
Информация, хранящаяся в обратном индексе, обычно выглядит следующим образом: Предполагая, что в моей коллекции документов 100 документов, для удобства изложения пронумеруем документы от 1 до 100, и получим следующую структуру:
Слева находится ряд строк, называемыхСловарь.
Каждая строка указывает на связанный список документов (Документ), содержащий эту строку, и этот связанный список документов называетсяПеревернутый стол(Список рассылки). Благодаря индексу сохраненная информация согласуется с искомой информацией, что может значительно ускорить поиск.
Например, чтобы найти документы, содержащие как строку «lucene», так и строку «solr», нам нужны только следующие шаги:
- Получить связанный список документов, содержащих строку «lucene».
- Получить связанный список документов, содержащих строку «solr».
- Найдите файлы, содержащие как «lucene», так и «solr», объединив связанные списки.
Увидев это место, некоторые люди могут сказать, что полнотекстовый поиск действительно ускоряет поиск, но с добавлением процесса индексации их комбинация не обязательно намного быстрее, чем последовательное сканирование. Действительно, с добавлением процесса индексации полнотекстовый поиск не обязательно быстрее, чем последовательное сканирование, особенно когда объем данных невелик. И индексация очень большого объема данных тоже очень медленный процесс.
Однако между ними все же есть различия: последовательное сканирование требует сканирования каждый раз, в то время как процесс создания индекса нужно выполнить только один раз, и в дальнейшем он будет выполнен раз и навсегда. процесс создания индекса проходить не нужно, достаточно поискать созданный индекс.
Это также одно из преимуществ полнотекстового поиска перед последовательным сканированием:Индексируйте один раз, используйте много раз.
Как создать индекс?
Процесс создания индекса полнотекстового поиска обычно состоит из следующих шагов:
Шаг 1: Некоторые исходные документы для индексации (Документ).
为了方便说明索引创建过程，这里特意用两个文件为例：
文件一：Students should be allowed to go out with their friends, but not allowed to drink beer.
文件二：My friend Jerry went to school to see his students but found them drunk which is not allowed.
Шаг 2: Передайте исходный документ в подкомпонент (Tokenizer).
Токенизатор сделает следующее (этот процесс называется Tokenize):
-
Разделите документ на отдельные слова.
-
Удалить знаки препинания.
-
Удалить стоп-слова.
Так называемые стоп-слова являются одними из самых распространенных слов в языке.Поскольку они не имеют специального значения, в большинстве случаев их нельзя искать по ключевым словам.Поэтому при создании индекса такие слова будут удалены, а индекс будет уменьшенный размер.
Стоп-слова в английском языке, такие как «the», «a», «this» и так далее.
Для токенизатора каждого языка существует набор стоп-слов.
Результат, полученный после токенизатора, называется токеном.
在我们的例子中，便得到以下词元(Token)：
“Students”，“allowed”，“go”，“their”，“friends”，“allowed”，“drink”，“beer”，“My”，“friend”，“Jerry”，“went”，“school”，“see”，“his”，“students”，“found”，“them”，“drunk”，“allowed”。
Шаг 3: Передайте полученный токен (Token) компоненту обработки языка (Linguistic Processor).
Компонент обработки языка (лингвистический процессор) в основном выполняет некоторую языковую обработку полученного токена (Token).
Для английского языка лингвистический процессор обычно делает следующее:
-
Изменить на нижний регистр.
-
Сократите слова до их корневых форм, например, «автомобили» до «автомобиль» и т. д. Эта операция называется: стемминг.
-
Преобразование слов в корневые формы, например, «возил» в «возить» и т. д. Эта операция называется: лемматизация.
Stemming 和 lemmatization的异同： 相同之处：Stemming和lemmatization都要使词汇成为词根形式。 两者的方式不同： Stemming采用的是“缩减”的方式：“cars”到“car”，“driving”到“drive”。 Lemmatization采用的是“转变”的方式：“drove”到“drove”，“driving”到“drive”。 两者的算法不同： Stemming主要是采取某种固定的算法来做这种缩减，如去除“s”，去除“ing”加“e”，将“ational”变为“ate”，将“tional”变为“tion”。 Lemmatization主要是采用保存某种字典的方式做这种转变。比如字典中有“driving”到“drive”，“drove”到“drive”，“am, is, are”到“be”的映射，做转变时，只要查字典就可以了。 Stemming和lemmatization不是互斥关系，是有交集的，有的词利用这两种方式都能达到相同的转换。
Результат работы лингвистического процессора называется термом.
在我们的例子中，经过语言处理，得到的词(Term)如下：
“student”，“allow”，“go”，“their”，“friend”，“allow”，“drink”，“beer”，“my”，“friend”，“jerry”，“go”，“school”，“see”，“his”，“student”，“find”，“them”，“drink”，“allow”。
Именно из-за шагов языковой обработки поиск водил и драйва тоже можно искать.
Шаг 4: Передайте полученное слово (термин) компоненту индекса (индексатору).
Компонент индекса (индексатор) в основном выполняет следующие функции:
-
Создайте словарь с полученными словами (Term).
在我们的例子中字典如下： -
Отсортируйте словарь по алфавиту.
3. Объедините одно и то же слово (термин) в связанный список списка публикации документа.
В этой таблице есть несколько определений:
Document FrequencyТо есть частота документа, указывающая, сколько документов содержит этот термин (Term).
FrequencyТо есть частотность слова, а это значит, что этот файл содержит несколько терминов (Term).
Таким образом, для слова (Термин) «разрешить» имеется всего два документа, которые содержат слово (Термин), поэтому в связанном списке есть два документа после слова (Термин), и первый элемент представляет первый документ. содержащий "разрешить". Документ, документ № 1, в этом документе "разрешить" встречается дважды, второй пункт указывает на второй документ, содержащий "разрешить", который является документом № 2, в этом документе "разрешить" появляется один раз .
На данный момент индекс создан, и мы можем быстро найти через него нужные нам документы.
И в процессе мы были приятно удивлены, обнаружив, что по запросу «ездить», «водить», «водить» и «водить» также можно найти. Потому что в нашем индексе "за рулем", "за рулем" и "за рулем" после языковой обработки будут преобразованы в "привод", а при поиске, если ввести "за рулем", введенный запрос также пройдет через наш один из на третьем этапе он становится запросом «диск», чтобы можно было найти нужный документ.
Как искать индекс?
В этот момент, кажется, мы можем объявить: «Мы нашли документ, который искали».
Но на этом дело не закончилось, обнаружение всего лишь одного аспекта полнотекстового поиска. не так ли?
Если только один или десять документов содержали нашу строку запроса, мы ее находили. Но что, если есть тысяча или даже тысячи результатов? Какой файл вам нужен больше всего?
Шаг 1: Пользователь вводит оператор запроса.
Оператор запроса, как и наш обычный язык, также имеет определенный синтаксис.
举个例子，用户输入语句：lucene AND learned NOT hadoop。
说明用户想找一个包含lucene和learned然而不包括hadoop的文档。
Шаг 2. Выполните лексический анализ, синтаксический анализ и языковую обработку оператора запроса..
Поскольку оператор запроса имеет грамматику, он также должен выполнять синтаксический анализ, анализ синтаксиса и языковую обработку.
Шаг 3. Найдите в индексе документы, соответствующие синтаксическому дереву..
Этот шаг состоит из нескольких небольших шагов:
1. Сначала в таблице обратного индекса найдите связанный список документов, содержащий lucene, Learn и Hadoop соответственно.
2. Во-вторых, объедините связанные списки, содержащие lucene и Learn, чтобы получить связанный список документов, содержащих как lucene, так и Learn.
3. Затем выполните операцию разности между этим связанным списком и связанным списком документов Hadoop, чтобы удалить документы, содержащие hadoop, чтобы получить связанный список документов, который содержит как lucene, так и Learn, но не содержит Hadoop.
4. Этот список документов является документом, который мы ищем.
Шаг 4: Отсортируйте результаты по релевантности полученных документов и запросов..
Хотя на предыдущем шаге мы получили искомый документ, результат запроса должен соответствовать оператору запросаКорреляцияСортировка, чем актуальнее, тем выше приоритет.
Суммировать
1) Есть ряд проиндексированных файлов.
2) Проиндексированные файлы подвергаются грамматическому анализу и языковой обработке для формирования ряда терминов (Term).
3) Словари и таблицы обратного индекса формируются путем создания индекса.
4) Запишите индекс на жесткий диск через хранилище индексов.
2. Процесс поиска:
а) Пользователь вводит оператор запроса.
б) Ряд слов (Термин) получают путем грамматического анализа и языкового анализа оператора запроса.
c) Получить дерево запросов с помощью синтаксического анализа.
г) Считайте индекс в память через хранилище индексов.
e) Используйте дерево запросов для поиска в индексе, чтобы получить связанный список документов каждого термина (термин), пересечь и различать связанный список документов и получить результирующий документ.
f) Сортировать документы результатов поиска по релевантности запроса.
ж) вернуть результат запроса пользователю.
Ссылаться на:Lucene: основы полнотекстового поиска
В следующей статье будет представлен выбор solr и elasticsearch.