индекс поисковой системы
1. Матрица Word-документ
Матрица слово-документ представляет собой концептуальную модель, которая выражает инклюзивную связь между ними. Рисунок 3-1 показывает ее значение. Каждый столбец на рис. 3-1 представляет собой документ, каждая строка представляет слово, а позиция галочки представляет отношение включения.
Рисунок 3-1 Матрица Word-Document
В вертикальном измерении документа каждый столбец представляет, какие слова содержит документ.Например, документ 1 содержит словарь 1 и словарь 4, но не другие слова. В горизонтальном измерении слов каждая строка представляет, какие документы содержат определенное слово. Например, для слова 1 слово 1 появляется в документе 1 и документе 4, а в других документах слово 1 отсутствует. Таким же образом можно интерпретировать и другие строки и столбцы матрицы.
Индекс поисковой системы на самом деле представляет собой определенную структуру данных, реализующую «матрицу слово-документ». Существуют различные способы реализации вышеуказанной концептуальной модели, такие как «инвертированный индекс», «файл подписи», «суффиксное дерево» и т.д. Тем не менее, различные экспериментальные данные показывают, что «инвертированный индекс» — это лучший способ реализации отношения отображения между словами и документами, поэтому в этой главе в основном представлены технические детали «инвертированного индекса».
2. Основные понятия инвертированного индекса
Документ (Документ):Как правило, объектами обработки поисковых систем являются веб-страницы Интернета, а понятие документов более широкое, представляя объекты хранения в виде текста, по сравнению с веб-страницами оно охватывает больше форм, таких как Word, PDF, html, XML, и т.д. Файл в формате можно назвать документом. Другой пример — электронная почта, короткое сообщение или Weibo, которые также можно назвать документом. В оставшейся части этой книги документы во многих случаях используются для представления текстовой информации.
Коллекция документов:Коллекция, состоящая из нескольких документов, называется коллекцией документов. Например, большое количество веб-страниц в Интернете или большое количество сообщений электронной почты являются конкретными примерами коллекций документов.
Идентификатор документа:Внутри поисковой системы каждому документу в коллекции документов присваивается уникальный внутренний номер, и этот номер используется как уникальный идентификатор документа, что удобно для внутренней обработки. Внутренний номер каждого документа называется «номер документа». ". DocID иногда используется позже для удобного представления номера документа.
Идентификатор слова (Word ID):Подобно номеру документа, поисковая система использует уникальный номер для представления слова, а номер слова может использоваться как уникальное представление слова.
Перевернутый индекс:Инвертированный индекс представляет собой особую форму хранения для реализации «матрицы слово-документ».Благодаря инвертированному индексу можно быстро получить список документов, содержащих это слово, по слову. Перевернутый индекс в основном состоит из двух частей:«Словарь Word» и «Перевернутый файл».
Словарь слов (лексикон):Обычной единицей индекса поисковой системы является слово. Словарь слов представляет собой набор строк, состоящий из всех слов, встречающихся в наборе документов. Каждая запись индекса в словаре слов записывает некоторую информацию о самом слове и указатель на «перевернутый список».
Список сообщений:В инвертированном списке записывается список всех документов, в которых встречается определенное слово, и информация о положении слова в документе, и каждая запись называется инвертированным элементом (проводка). Из перевернутого списка видно, в каких документах содержится определенное слово.
Перевернутый файл:Инвертированный список всех слов часто хранится последовательно в файле на диске, который называется инвертированным файлом, а инвертированный файл — это физический файл, в котором хранится инвертированный индекс.
Взаимосвязь между этими понятиями хорошо видна на рис. 3-2.
Рисунок 3-2 Схематическая диаграмма базовой концепции инвертированного индекса
3. Простой пример инвертированного индекса
Перевернутый индекс очень прост с точки зрения логической структуры и основных идей. Ниже мы иллюстрируем на конкретных примерах, чтобы читатели могли составить представление об инвертированном индексе.
Предположим, что коллекция документов содержит пять документов, содержимое каждого документа показано на рис. 3.3, а самый левый столбец на рисунке — это номер документа, соответствующий каждому документу. Наша задача — построить инвертированный индекс по этой коллекции документов.
Рисунок 3-3 Сбор документов
Такие языки, как китайский и английский, разные, и между словами нет четкого разделения, поэтому в первую очередь используется система сегментации слов для автоматического разделения документа на последовательности слов. Таким образом, каждый документ преобразуется в поток данных, составленный из последовательностей слов.Для удобства последующей обработки системой необходимо присвоить каждому отдельному слову уникальный номер слова, и при этом зафиксировать, какие документы содержат Это слово После такой обработки можно получить простейший инвертированный индекс (см. рис. 3-4). На рисунке 3-4 в столбце «Идентификатор слова» записан номер слова для каждого слова, во втором столбце — соответствующее слово, а в третьем столбце — инвертированный список, соответствующий каждому слову. Например, слово «Google», номер слова — 1, а перевернутый список — {1, 2, 3, 4, 5}, что указывает на то, что каждый документ в коллекции документов содержит это слово.
Рисунок 3-4 Простой инвертированный индекс
Причина, по которой инвертированный индекс, показанный на рис. 3-4, является самым простым, заключается в том, что индексная система записывает только те документы, которые содержат определенное слово, и может записывать больше информации. Рисунок 3-5 представляет собой относительно сложный инвертированный индекс По сравнению с базовой системой индексов на рисунке 3-4 инвертированный список, соответствующий слову, записывает не только номер документа, но также записывает информацию о частоте слов (TF), т. е. Количество вхождений этого слова в определенный документ записывается, потому что информация о частоте слов является очень важным расчетным фактором при расчете сходства между запросом и документом при сортировке результатов поиска, поэтому она записывается в инвертированный список. для облегчения подсчета баллов при последующей сортировке. В примере на рис. 3-5 номер слова слова «основатель» равен 7, а соответствующее содержимое перевернутого списка: (3:1), где 3 означает, что документ с номером документа 3 содержит это слово, а число 1 представляет информацию о частоте слов, то есть это слово появляется только один раз в документе № 3, и перевернутый список, соответствующий другим словам, имеет такое же значение.
Рисунок 3-5 Инвертированный индекс с информацией о частоте слов
Практичный перевернутый индекс также может записывать больше информации.Помимо записи номера документа и информации о частоте слов, индексная система, показанная на рисунке 3-6, записывает два дополнительных типа информации, то есть «информацию о частоте документа», соответствующую каждому слово (соответствует третьему столбцу рис. 3-6) и записать информацию о положении слова в определенном документе в инвертированный список.
Рисунок 3-6 Инвертированный индекс с частотой слов, частотой документов и информацией о встречаемости
"Информация о частоте встречаемости документов" показывает, сколько документов в коллекции документов содержит определенное слово. Причина записи этой информации та же, что и информация о частоте встречаемости слов. Эта информация является очень важным фактором при ранжировании результатов поиска. Информация о расположении слов, появляющихся в определенном документе, не обязательно фиксируется системой индексирования.В реальной системе индексирования эта информация может быть включена или не включена.Причина этого заключается в том, что эта информация не нужна поисковой системе. Да, информация о местоположении полезна только тогда, когда поддерживаются «фразовые запросы».
Возьмем в качестве примера слово «Las», номер слова равен 8, а частота документа равна 2, что означает, что во всем наборе документов есть два документа, содержащих это слово, и соответствующий инвертированный список: {(3;1 ;) , (5;1;)}, что означает, что слово появилось в документе 3 и документе 5, частота слова равна 1, а позиция появления слова "Las" в обоих документах равно 4, т.е. четвертое слово в документе - "las".
Перевернутый индекс, показанный на рисунке 3-6, уже представляет собой очень полную систему индексов.Структура индекса реальной поисковой системы в основном такая же.Единственная разница заключается в том, какая конкретная структура данных используется для реализации вышеуказанной логической структуры.
С помощью этой системы индексации поисковая система может легко ответить на запрос пользователя.Например, когда пользователь вводит запросное слово «Facebook», поисковая система ищет инвертированный индекс, из которого можно прочитать документы, содержащие это слово. , и эти документы предоставляются пользователю. Результаты поиска и использование информации о частоте слов и информации о частоте документов для сортировки этих результатов поиска кандидатов, расчета сходства между документом и запросом и сортировки вывода в соответствии с оценкой сходства из от высокого к низкому, что является частью внутреннего процесса поисковой системы, конкретный план реализации будет подробно описан в главе 5 этой книги.
4. Словарь слов
Словарь слов является очень важной частью инвертированного указателя.Он используется для хранения релевантной информации обо всех словах, появившихся в коллекции документов, и используется для записи информации о позиции инвертированного списка, соответствующей слову в списке. инвертированный файл. Когда поиск поддерживается, по словам пользователя в запросе, перейдите в словарь слов для запроса, вы можете получить соответствующий инвертированный список и использовать его в качестве основы для последующей сортировки.
Для крупномасштабной коллекции документов, которая может содержать сотни тысяч или даже миллионы разных слов, возможность быстрого нахождения слова напрямую влияет на скорость отклика при поиске, поэтому для анализа слова требуется эффективная структура данных. и искомые, а часто используемые структуры данных включают структуру хеш-связанного списка и древовидную структуру словаря.
4.1 Хэш плюс связанный список
Рисунок 1-7 представляет собой схематическую диаграмму структуры этого словаря. Эта структура словаря в основном состоит из двух частей:
Основная часть представляет собой хэш-таблицу, каждая запись хэш-таблицы содержит указатель, а указатель указывает на конфликтующий связанный список.В конфликтующем связанном списке слова с одинаковым хеш-значением образуют структуру связанного списка. Причина, по которой существует конфликтующий связанный список, заключается в том, что два разных слова получают одно и то же хеш-значение.В этом случае это называется конфликтом в методе хеширования.Слова с одинаковым хэш-значением могут быть сохранены в связанном списке для для последующих поисков.
Рисунок 1-7 Структура словаря хэшей и связанных списков
В процессе индексации структура словаря будет построена соответствующим образом. Например, при синтаксическом анализе нового документа для слова T, которое появляется в документе, сначала используйте хеш-функцию для получения его хеш-значения, а затем считывайте хранящийся в нем указатель в соответствии с записью хеш-таблицы, соответствующей хэш-значению, затем найден соответствующий список конфликтов. Если слово уже существует в списке конфликтов, это означает, что слово появилось в ранее проанализированном документе. Если слово не найдено в списке конфликтов, это означает, что слово встречается впервые, и оно будет добавлено в список конфликтов. Таким образом, когда все документы в коллекции документов проанализированы, создается соответствующая структура словаря.
При ответе на запрос пользователя процесс аналогичен построению словаря, разница в том, что даже если слово не появляется в словаре, оно не будет добавлено в словарь. Возьмем в качестве примера рис. конфликтного списка, обнаруживается, что слово 3 находится в конфликтном списке, значит, слово найдено, и тогда для последующей работы может быть прочитан соответствующий данному слову перевернутый список, если слово не найдено, значит, есть нет набора документов Документ содержит слова, результаты поиска пусты.
4.2 Древовидная структура
B-дерево (или B+-дерево) — еще одна эффективная структура поиска Рисунок 1-8 представляет собой схематическую диаграмму структуры B-дерева. B-дерево отличается от хеш-поиска, который требует сортировки элементов словаря по размеру (число или порядок символов), в то время как хэш-метод не требует данных для удовлетворения этого требования.
B-дерево формирует иерархическую структуру поиска.Средний узел используется для указания того, в каком поддереве хранятся элементы словаря определенного диапазона порядка, и играет роль в навигации в соответствии с размером элементов словаря для сравнения.Самый нижний лист узел хранит информацию об адресе слова, в соответствии с этим адресом можно извлечь строку слова.
Рисунок 1-8 Структура поиска B-дерева
использованная литература:
«Это поисковая система: подробное объяснение базовой технологии», глава 3