Поисковый индекс

Поиско́вый и́ндекс — структура данных, которая содержит информацию о документах и используется в поисковых системах. Индекси́рование➤, совершаемое поисковой машиной, — процесс сбора, сортировки и хранения данных с целью обеспечить быстрый и точный поиск информации. Создание индекса включает междисциплинарные понятия из лингвистики, когнитивной психологии, математики, информатики и физики. Веб-индексированием называют процесс индексирования в контексте поисковых машин, разработанных, чтобы искать веб-страницы в Интернете.

Популярные поисковые машины сосредотачиваются на полнотекстовой индексации документов, написанных на естественных языках[1]➤. Мультимедийные документы, такие как видео и аудио[2] и графика[3][4], также могут участвовать в поиске.

Метапоисковые машины используют индексы других поисковых сервисов и не хранят локальный индекс, в то время как поисковые машины, основанные на кешированных страницах, долго хранят как индекс, так и текстовые корпусы. В отличие от полнотекстовых индексов, частично-текстовые сервисы ограничивают глубину индексации, чтобы уменьшить размер индекса. Большие сервисы, как правило, выполняют индексацию в заданном временно́м интервале из-за необходимого времени и затрат на обработку, в то время как поисковые машины, основанные на агентах, строят индекс в масштабе реального времени.

Индексация

[править | править код]

Цель использования индекса — повышение скорости поиска релевантных документов по поисковому запросу. Без индекса поисковая машина должна была бы сканировать каждый документ в корпусе, что потребовало бы большого количества времени и вычислительной мощности. Например, в то время, как индекс 10 000 документов может быть опрошен в пределах миллисекунд, последовательный просмотр каждого слова в 10 000 больших документов мог бы занять часы. Дополнительная память, выделяемая для хранения индекса, и увеличение времени, требуемое для обновления индекса, компенсируется уменьшением времени на поиск информации.

Факторы, влияющие на проектирование поисковых систем

[править | править код]

При разработке поисковой системы необходимо учитывать следующие факторы:

Факторы слияния
Как данные входят в индекс? Как слова и подчиненные функции добавляются в индекс во время текстового корпусного обхода? И могут ли несколько поисковых роботов работать асинхронно? Поисковый робот должен сначала проверить, обновляет он старое содержание или добавляет новое. Слияние индекса➤ поисковой системы подобно SQL Merge и другим алгоритмам слияния[5].
Методы хранения
Как хранить индексируемые данные? То есть определяют вид хранимой информации: сжатый или отфильтрованный.
Размер индекса
Сколько памяти компьютера необходимо, чтобы поддерживать индекс.
Скорость поиска
Как быстро можно найти слово в инвертированном индексе. Важным для информатики является сравнение скорости нахождения записи в структуре данных и скорости обновления/удаления индекса.
Хранение
Как хранится индекс в течение длительного времени[6].
Отказоустойчивость
Для поисковой службы важно быть надежной. Вопросы отказоустойчивости включают проблему повреждения индекса, определяя, можно ли отдельно рассматривать некорректные данные, связанные с плохими аппаратными средствами, секционированием и схемами на основе хеш-функций и композитного секционирования[7], а также репликации.

Индексные структуры данных

[править | править код]

Архитектура поисковой системы различается по способам индексирования и по методам хранения индексов, удовлетворяя факторы➤. Индексы бывают следующих типов:

Суффиксное дерево
Образно структурировано как дерево, поддерживает линейное время поиска. Построено на хранении суффиксов слов. Деревья поддерживают расширенное хеширование, которое важно для индексации поисковой системы[8]. Используется для поиска по шаблону в последовательностях ДНК и кластеризации. Основным недостатком является то, что хранение слова в дереве может потребовать пространство за пределами необходимого для хранения самого слова[9]. Альтернативное представление — суффиксный массив. Считается, что он требует меньше виртуальной памяти и поддерживает блочно-сортирующее сжатие данных.
Инвертированный индекс
Хранилище списка вхождений каждого критерия поиска[10], обычно в форме хеш-таблиц или бинарного дерева[11][12].
Индекс цитирования
Хранилище цитат или гиперссылок между документами для поддержки анализа цитирования, предмет библиометрии.
N-грамма
Хранилище последовательностей длин данных для поддержки других типов поиска или анализа текста[13].
Матрица термов документа
Используется в латентно-семантическом анализе (ЛСА), хранит вхождения слов в документах в двумерной разреженной матрице.

Проблемы параллельного индексирования

[править | править код]

Одной из основных задач при проектировании поисковых систем является управление последовательными вычислительными процессами. Существует ситуации, в которых возможно создание состояния гонки и когерентных отказов. Например, новый документ добавлен к корпусу, и индекс должен быть обновлен, но в то же время индекс должен продолжать отвечать на поисковые запросы. Это коллизия между двумя конкурирующими задачами. Считается, что авторы являются производителями информации, а поисковый робот — потребителем этой информации, захватывая текст и сохраняя его в кэше (или корпусе). Прямой индекс является потребителем информации, произведенной корпусом, а инвертированный индекс — потребителем информации, произведенной прямым индексом. Это обычно упоминается как модель производителя-потребителя. Индексатор является производителем доступной для поиска информации, а пользователи, которые её ищут, — потребителями. Проблема усиливается при распределенном хранении и распределенной обработке. Чтобы масштабировать большие объемы индексированной информации, поисковая система может основываться на архитектуре распределенных вычислений, при этом поисковая система состоит из нескольких машин, работающих согласованно. Это увеличивает вероятность нелогичности и делает сложнее поддержку полностью синхронизируемой, распределенной, параллельной архитектуры[14].

Прямой индекс

[править | править код]

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

Прямой индекс
Документ Слова
Документ 1 наша, Таня, громко, плачет
Документ 2 уронила, в, речку, мячик
Документ 3 тише, Танечка, не, плачь,
Документ 4 не, утонет, в, речке, мяч

Необходимость разработки прямого индекса объясняется тем, что лучше сразу сохранять слова за документами, поскольку их в дальнейшем анализируют для создания поискового индекса. Формирование прямого индекса включает асинхронную системную обработку, которая частично обходит узкое место обновления инвертированного индекса[15]. Прямой индекс сортируют, чтобы преобразовать в инвертированный. Прямой индекс по сути представляет собой список пар, состоящих из документов и слов, отсортированный по документам. Преобразование прямого индекса к инвертированному является только вопросом сортировки пар по словам. В этом отношении инвертированный индекс — отсортированный по словам прямой индекс.

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

[править | править код]
Основная статья: Инвертированный индекс

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

Инвертированный индекс
Слово Документы
в Документ 2, Документ 4
громко Документ 1
мяч Документ 2, Документ 4
наша Документ 1
не Документ 3, Документ 4
плакать Документ 1, Документ 3
речка Документ 2, Документ 4
Таня Документ 1, Документ 3
тише Документ 3
уронить Документ 2
утонуть Документ 4

Инвертированный индекс может только определить, существует ли слово в пределах конкретного документа, так как не хранит никакой информации относительно частоты и позиции слова, и поэтому его считают логическим индексом. Инвертированный индекс определяет, какие документы соответствуют запросу, но не оценивает соответствующие документы. В некоторых случаях индекс включает дополнительную информацию, такую как частота каждого слова в каждом документе или позиция слова в документе[16]. Информация о позиции слова позволяет поисковому алгоритму идентифицировать близость слова, чтобы поддерживать поиск фраз. Частота может использоваться, чтобы помочь в ранжировании документов по запросу. Такие темы в центре внимания исследований информационного поиска.

Инвертированный индекс представлен разреженной матрицей, так как не все слова присутствуют в каждом документе. Индекс подобен матрице термов документа, используемом в ЛСА. Инвертированный индекс можно считать формой хеш-таблицы. В некоторых случаях индекс представлен в форме двоичного дерева, которая требует дополнительной памяти, но может уменьшить время поиска. В больших индексах архитектура, как правило, представлена распределенной хеш-таблицей[17].

Слияние индекса

[править | править код]

Инвертированный индекс заполняется путём слияния или восстановления. Архитектура может быть спроектирована так, чтобы поддерживать инкрементную индексацию[18][19], где слияние определяет документ или документы, которые будут добавлены или обновлены, а затем анализирует каждый документ в слова. Для технической точности, слияние объединяет недавно индексированные документы, обычно находящиеся в виртуальной памяти, с индексным кэшем, который находится на одном или нескольких жестких дисках компьютера.

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

  • разработка прямого индекса,
  • сортировка прямого индекса в инвертированный индекс.

Инвертированный индекс называется так из-за того, что он является инверсией прямого индекса.

Сжатие

[править | править код]

Создание и поддержка крупномасштабного поискового индекса требует значительной памяти и выполнения задач обработки. Многие поисковые системы используют ту или иную форму сжатия, чтобы уменьшить размер индексов на диске[6]. Рассмотрим следующий сценарий для полнотекстового механизма поиска в Интернете:

  • Требуется 8 битов (1 байт) для хранения одного символа. Некоторые кодировки используют 2 байта на символ[20].
  • Среднее число символов в любом слове на странице примем за 5.

Учитывая этот сценарий, несжатый индекс для 2 миллиардов веб-страниц должен был бы хранить 500 миллиардов записей слов. 1 байт за символ или 5 байт за слово — потребовалось бы 2500 гигабайт одного только пространства памяти. Это больше, чем среднее свободное пространство на диске 2 персональных компьютеров. Для отказоустойчивой распределенной архитектуры требуется еще больше памяти. В зависимости от выбранного метода сжатия индекс может быть уменьшен до части такого размера. Компромисс времени и вычислительной мощности, требуемой для выполнения сжатия и распаковки.

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

Синтаксический анализ документа

[править | править код]

Синтаксический анализ (или парсинг) документа предполагает разбор документа на компоненты (слова) для вставки в прямой и инвертированный индексы. Найденные слова называют токенами (англ. token), и в контексте индексации поисковых систем и обработки естественного языка парсинг часто называют токенизацией (то есть разбиением на токены). Синтаксический анализ иногда называют частеречной разметкой, морфологическим анализом, контент-анализом, текстовым анализом, анализом текста, генерацией согласования, сегментацией речи, лексическим анализом. Термины «индексация», «парсинг» и «токенизация» взаимозаменяемы в корпоративном сленге.

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

Проблемы при обработке естественного языка

[править | править код]
Неоднозначность границ слова
На первый взгляд может показаться, что токенизация является простой задачей, но это не так, особенно при разработке многоязычного индексатора. В цифровой форме тексты некоторых языков, таких, как китайский или японский, представляют сложную задачу, так как слова четко не разделены пробелом. Цель токенизации в том, чтобы распознать слова, которые будут искать пользователи. Специфичная для каждого языка логика используется, чтобы правильно распознать границы слов, что необходимо для разработки синтаксического анализатора для каждого поддерживаемого языка (или для групп языков с похожими границами и синтаксисом).
Неоднозначность языка
Для более точного ранжирования документов поисковые системы могут учитывать дополнительную информацию о слове, например, к какому языку или части речи оно относится. Эти методы зависят от языка, поскольку синтаксис между языками различается. При токенизации некоторые поисковые системы пытаются автоматически определить язык документа.
Различные форматы файлов
Для того, чтобы правильно определить, какие байты представляют символы документа, формат файла должен быть правильно обработан. Поисковые системы, которые поддерживают различные форматы файлов, должны правильно открывать документ, получать доступ к документу и токенизировать его символы.
Ошибки памяти
Качество данных естественного языка не всегда может быть совершенным. Уязвимость существует из-за неизвестного количества документов, в частности, в Интернете, которые не подчиняются соответствующему протоколу файла. Двоичные символы могут быть ошибочно закодированы в различных частях документа. Без распознавания этих символов и соответствующей обработки может ухудшиться качество индекса или индексирования.

Токенизация

[править | править код]

В отличие от большинства людей, компьютеры не понимают структуру документа естественного языка и не могут автоматически распознавать слова и предложения. Для компьютера документ — это только последовательность байтов. Компьютер не «знает», что символ пробела является разделителем слов в документе. Человек должен запрограммировать компьютер так, чтобы определить, что является отдельным словом, называемым токеном. Такую программу обычно называют токенизатором или синтаксическим анализатором (парсером), а также лексическим анализатором[21]. Некоторые поисковые системы и другое ПО для обработки естественного языка поддерживают специализированные программы, удобные для осуществления синтаксического анализа, например, YACC или Лекс[22].

Во время токенизации синтаксический анализатор определяет последовательность символов, которые представляют слова и другие элементы, например, пунктуация, представленная числовыми кодами, некоторые из которых являются непечатаемыми управляющими символами. Синтаксический анализатор может распознать некоторые объекты, например, адреса электронной почты, телефонные номера и URL. При распознавании каждого токена могут быть сохранены некоторые характеристики, например, язык или кодировка, часть речи, позиция, число предложения, позиция в предложении, длина и номер строки[21].

Распознавание языка

[править | править код]

Если поисковая система поддерживает несколько языков, то первым шагом во время токенизации будет определение языка каждого документа, поскольку многие последующие шаги зависят от этого (например, стемминг и определение части речи). Распознавание языка — это процесс, при котором компьютерная программа пытается автоматически определить или классифицировать язык документа. Автоматическое распознавание языка является предметом исследований в обработке естественного языка[23].

Анализ формата документа

[править | править код]

Если поисковая система поддерживает множество форматов документов, то документы должны быть подготовлены для токенизации. Проблема состоит в том, что некоторые форматы документов содержат информацию о форматировании в дополнение к текстовому содержанию. Например, документы HTML содержат HTML-теги[24]. Если бы поисковая система игнорировала различие между содержанием и разметкой текста, то посторонняя информация включалась бы в индекс, что привело бы к плохим результатам поиска. Анализ формата — выявление и обработка языка разметки, встроенного в документ. Анализ формата также упоминается как структурный анализ, разделение тегов, текстовая нормализация.

Задача анализа формата осложняется тонкостями различных форматов файлов. Некоторые форматы файлов защищаются правом интеллектуальной собственности, о них мало информации, а другие — наоборот, хорошо документированы. Распространенные, хорошо задокументированные форматы файлов, которые поддерживают поисковые системы[25][26]:

Некоторые поисковики поддерживают файлы, которые хранятся в сжатом или зашифрованном формате[27][28][29]. При работе со сжатым форматом индексатор сначала распаковывает документ. Этот шаг может привести к получению одного или нескольких файлов, каждый из которых должен быть индексирован отдельно. Бывают следующие поддерживаемые форматы сжатого файла:

Анализ формата может включать методы повышения качества, чтобы избежать включения ненужной информации в индекс. Контент может управлять информацией о форматировании, чтобы включать дополнительные сведения. Примеры злоупотребления форматированием документа в случае веб-спама:

  • Включение сотен или тысяч слов в раздел, который скрыт от представления на мониторе, но является видимым индексатору, при помощи тегов форматирования (например, в скрытый тег div в HTML можно включить использование CSS или JavaScript).
  • Установка цвета шрифта слов таким же, как цвет фона, что делает невидимыми слова для человека при просмотре документа, но слова остаются видимыми для индексатора.

Распознавание раздела

[править | править код]

Некоторые поисковые системы включают распознавание раздела, определяют основные части документа до токенизации. Не все документы в корпусе читаются как правильно написанная книга, разделенная на главы и страницы. Некоторые документы в Интернете, такие как новостные рассылки и корпоративные отчеты, содержат ошибочное содержание и боковые блоки, в которых нет основного материала. Например, эта статья отображает в левом меню ссылки на другие веб-страницы. Некоторые форматы файлов, как HTML или PDF, допускают содержание, которое будет отображаться в колонках. Хотя содержимое документа представлено на экране в различных областях, исходный текст хранит эту информацию последовательно. Слова, которые появляются последовательно в исходном тексте, индексируются последовательно, несмотря на то, что предложения и абзацы отображаются в различных частях монитора. Если поисковые системы индексируют весь контент, как будто это основное содержание документа, то качество индекса и поиска может ухудшиться. Отмечают две основные проблемы:

  • Содержание в различных разделах рассматривают как связанное с индексом, хотя в действительности это не так.
  • Дополнительное содержание «боковой панели» включено в индекс, но оно не способствует реальной значимости документа, поэтому индекс заполнен плохим представлением о документе.

Для анализа раздела может потребоваться, чтобы поисковая система реализовала логику визуализации каждого документа, то есть абстрактное представление самого документа, и затем проиндексировала представление вместо документа. Например, иногда для вывода контента на страницу в Интернете используют JavaScript. Если поисковая система «не видит» JavaScript, то индексация страниц происходит некорректно, поскольку часть контента не индексируется. Учитывая, что некоторые поисковые системы не беспокоятся о проблемах с визуализацией, веб-разработчики стараются не представлять контент через JavaScript или используют тег NoScript, чтобы убедиться, что веб-страница индексируется должным образом[30]. В то же время этот факт можно использовать, чтобы «заставить» индексатор поисковой системы «видеть» различное скрытое содержание.

Индексация метатегов

[править | править код]

Определенные документы часто содержат встроенные метаданные, такие как автор, ключевые слова, описание и язык. В HTML-страницах метатеги содержат ключевые слова, которые также включены в индекс. В более ранних технологиях поиска в Интернете индексировались ключевые слова в метатегах для прямого индекса, а полный текст документа не анализировался. В то время еще не было полнотекстовой индексации, и аппаратное обеспечение компьютера было не в состоянии поддерживать такую технологию. Язык разметки HTML первоначально включал поддержку метатегов для того, чтобы правильно и легко индексировать, без использования токенизации[31].

В процессе развития Интернета в 1990-х, многие корпорации создали корпоративные веб-сайты. Ключевые слова, используемые для описания веб-страниц стали больше ориентироваться на маркетинг и разрабатывались, чтобы управлять продажами, помещая веб-страницу в начало страницы результатов поиска для определенных поисковых запросов. Факт, что эти ключевые слова были определены субъективно, приводил к спаму, что вынудило поисковые системы принять полнотекстовую индексацию. Разработчики поисковой системы могли поместить много «маркетинговых ключевых слов» в содержание веб-страницы до того, как наполнят её интересной и полезной информацией. Однако целью проектирования веб-сайтов являлось привлечение клиентов, поэтому разработчики были заинтересованы в том, чтобы включить больше полезного контента на сайт, чтобы сохранить посетителей. В этом смысле полнотекстовая индексация была более объективной и увеличила качество результатов поисковой системы, что содействовало исследованиям технологий полнотекстовой индексации.

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

См. также

[править | править код]

Примечания

[править | править код]
  1. ↑ Clarke,Cormack, 1995.
  2. ↑ Rice,Bailey.
  3. ↑ Jacobs,Finkelstein,Salesin, 2006.
  4. ↑ Lee.
  5. ↑ Brown, 1996.
  6. ↑ 1 2 Cutting,Pedersen, 1990.
  7. ↑ mysql.
  8. ↑ trie.
  9. ↑ Gusfield, 1997.
  10. ↑ inverted index.
  11. ↑ Foster, 1965.
  12. ↑ Landauer, 1963.
  13. ↑ 5-gram.
  14. ↑ Dean,Ghemawat, 2004.
  15. ↑ Brin,Page, 2006.
  16. ↑ Grossman,Frieder,Goharian, 2002.
  17. ↑ Tang,Sandhya, 2004.
  18. ↑ Tomasic, 1994.
  19. ↑ Luk,Lam, 2007.
  20. ↑ unicode.
  21. ↑ 1 2 Tokenization Guidelines, 2011.
  22. ↑ Lex&Yacc, 1992.
  23. ↑ Automated language recognition, 2009.
  24. ↑ html, 2011.
  25. ↑ formats files.
  26. ↑ Типы файлов Google/Yandex.
  27. ↑ Программы индексации и поиска файлов.
  28. ↑ Индексирование архивов.
  29. ↑ Служба индексирования windows.
  30. ↑ JS indexing.
  31. ↑ Lee Hypertext, 1995.

Литература

[править | править код]
  • Charles E. Jacobs, Adam Finkelstein, David H. Salesin. Fast Multiresolution Image Querying (англ.) // Department of Computer Science and Engineering. — University of Washington, Seattle, Washington 98195, 2006.
  • Cutting, D., Pedersen, J. Optimizations for dynamic inverted index maintenance (англ.) / Jean-Luc Vidick. — NY, USA: ACM New York, 1990. — P. 405-411. — ISBN 0-89791-408-2.
  • Eric W. Brown. Execution Performance Issues in Full-Text Information Retrieval. — University of Massachusetts Amherst: Computer Science Department, 1996. — 179 с. — (Technical Report 95-81).
  • Dan Gusfield. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. — USA: Cambridge University Press, 1997. — 326 с. — ISBN 0-521-58519-8.
  • Caxton Croxford Foster. Information retrieval: information storage and retrieval using AVL trees (англ.) // ACM '65 Proceedings of the 1965 20th national conference. — NY, USA, 1965. — P. 192-205. — doi:10.1145/800197.806043.
  • Landauer, W. I. The balanced tree and its utilization in information retrieval (англ.) // IEEE Trans. on Electronic Computers. — USA, 1963. — No. 6. — P. 12.
  • Jeffrey Dean, Sanjay Ghemawat. MapReduce: Simplified Data Processing on Large Clusters (англ.). — Google, Inc, 2004.
  • Sergey Brin, Lawrence Page. The Anatomy of a Large-Scale Hypertextual Web Search Engine (англ.). — Stanford University, Stanford: Computer Science Department, 2006.
  • Grossman, Frieder, Goharian. IR Basics of Inverted Index (англ.). — 2002.
  • Tang Hunqiang, Sandhya Dwarkadas. Hybrid Global Local Indexing for Efficient Peer to Peer Information Retrieval (англ.). — University of Rochester: Computer Science Department, 2004.
  • Anthony Tomasic. Incremental Updates of Inverted Lists for Text Document Retrieval (англ.) : Conference Proceeding. — Stanford University, 1994.
  • Robert W.P. Luk, Wai Lam. Efficient in-memory extensible inverted file (англ.) // Information Systems. — 2007. — No. 32 (5). — P. 733-754. — doi:10.1016/j.is.2006.06.001.
  • Radim Řehůřek, Milan Kolkus. Language Identification on the Web: Extending the Dictionary Method (англ.) // Lecture Notes in Computer Science Volume. — Mexico, 2009. — No. 5449. — P. 357-368. — ISBN 978-3-642-00382-0. (недоступная ссылка)
  • Scoping SIG, Tokenization Taskforce PCI Security Standards Council. Info Supplement:PCI DSS Tokenization Guidelines. — 2011. — С. 23.
  • Б. Лоусон, Р. Шарп. Изучаем HTML5 = Introducing HTML5. — Питер, 2011. — 272 с. — (Библиотека специалиста). — 2000 экз. — ISBN 978-5-459-00269-0, 978-0321687296.
  • T. Berners-Lee. Hypertext Markup Language - 2.0 (англ.). — Network Working Group, 1995.
  • Levine JR, Mason T, Brown D. Lex & Yacc. — Sebastopol: O'Reilly & Associates, 1992. — P. 387. — ISBN 1565920007.

Ссылки

[править | править код]
  • James Lee. Software Learns to Tag Photos (англ.). MIT Technology Review 1-2 (9 ноября 2006). Дата обращения: декабрь 2013. Архивировано из оригинала 20 октября 2013 года.