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

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

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

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

Индексация

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

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

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

Факторы слияния

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

Методы хранения

Как хранить индексируемые данные, т.е. должна ли быть информация в виде сжатых или отфильтрованных данных.

Размер индекса

Сколько памяти компьютера необходимо, чтобы поддерживать индекс.

Скорость поиска

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

Хранение

Как хранится индекс в течение длительного времени.

Отказоустойчивость

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

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

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

Суффиксное дерево

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

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

Хранилище списка вхождений каждого атомного критерия поиска, обычно в форме хэш-таблиц или бинарного дерева.

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

Хранилище цитат или гиперссылок между документами для поддержки анализа цитирования, предмет библиометрии.

Индекс N-грамм

Хранилище последовательностей длины данных для поддержки других типов поиска или анализа текста.

Матрица термов документа

Используется в ЛСА, хранит вхождения слов в документах в двумерной разреженной матрице.

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

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

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

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

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

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

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

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

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

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

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

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

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

Индекс слияния

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

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

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

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

Сжатие

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

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

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

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

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

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

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

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

Неоднозначность границ слова

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

Неоднозначность языка

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

Различные форматы файлов

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

Ошибки памяти

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

Токенизация

В отличие от грамотных людей, компьютеры не понимают структуру документа естественного языка и не могут автоматически распознавать слова и предложения. Для компьютера документ — это только последовательность байтов. Компьютер не 'знает', что символ пробела является разделителем слов в документе. Человек должен запрограммировать компьютер так, чтобы определить, что является отдельным словом, называемым токеном. Такую программу обычно называют токенизатором или синтаксическим анализатором (парсером), а также лексическим анализатором. Многие поисковые системы и другое ПО для обработки естественного языка, включают специализированные программы для синтаксического анализа, например, YACC или Лекс.

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

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

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

См. также

• Вертикальный поиск
• Извлечение информации
• Индекс (базы данных)
• Контент-анализ
• Локальный поисковик
• Поисковая система
• Семантическая паутина

Литература

• Charles L. A. Clarke , Gordon V. Cormack. Dynamic Inverted Indexes for a Distributed Full-Text Retrieval System (англ.) // MultiText Pro ject Technical Report MT-95-01. — University of Waterloo, Waterloo, Ontario N2L 3G1, Canada, 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.

Ссылки

• James Lee. Software Learns to Tag Photos (англ.). MIT Technology Review 1-2 (9 ноября 2006). Дата обращения: декабрь 2006.

• Stephen V. Rice, Stephen M. Bailey. Searching for Sounds Comparisonics Searching for Sounds (англ.). © 2013 Comparisonics Corporation (май 2004).

• С. Брин, Л. Пейдж The Anatomy of a Large-Scale Hypertextual Web Search Engine  (неопр.). Дата обращения: 20 сентября 2009. Архивировано 30 марта 2012 года.

• MySQL 5.1 Reference Manual. 18.2.3.1 LINEAR HASH Partitioning (англ.). mysql.com. © Oracle and/or its affiliates 1997, 2013. Дата обращения: 24 октября 2013.
• Vreda Pieterse and Paul E. Black. "trie" in Dictionary of Algorithms and Data Structures (англ.). http://www.nist.gov (22 февраля 2011).
• Vreda Pieterse and Paul E. Black. "inverted index" in Dictionary of Algorithms and Data Structures (англ.). http://www.nist.gov U.S. National Institute of Standards and Technology (14 августа 2008).
• Thorsten Brants, Alex Franz. Web 1T 5-gram Version 1 (англ.). http://catalog.ldc.upenn.edu/ (19 сентября 2006).
• The Unicode Standard - Frequently Asked Questions (англ.) (декабрь 2006).