Поисковый индекс: Поисковый индекс – Поисковый индекс — Википедия

Содержание

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

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

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

Что такое индексирование?

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

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

Индексирование новых сайтов в Google происходит за 1-7 дней, а в Яндексе — примерно за 7-30 дней.

Как происходит индексирование?

Объемы опубликованной информации измеряются миллиардами миллиардов байтов. Поисковая система не в состоянии обойти весь Интернет, когда какой-либо пользователь сформулирует свой вопрос. Поэтому она подготавливается заранее.

Поиск в Сети проходит в 2 этапа. На первом этапе поисковые системы сканируют Интернет и сохраняют его отражение в базе данных на своих серверах. На втором – поисковики извлекают из базы данных ответы на вопросы пользователей.

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

Индекс напоминает предметный указатель в энциклопедии или адресный справочник. Только предметный указатель структурирует термины, а поисковый индекс – все общеупотребительные и узкоспециальные слова. В адресном справочнике слово имеет одно «место прописки», а в поисковом индексе – множество таких мест.

Поисковые боты постоянно исследуют Интернет, скачивают и обрабатывают веб-страницы. Слепок Сети хранится на серверах поисковой системы и обновляется вслед за каждым обходом.

Яндексе есть основной поисковый робот и быстро-робот Orange. Основной робот занимается индексированием всего Интернета по заданному графику. Благодаря Orange в поиске появляются самые свежие страницы, опубликованные несколько минуты или секунд назад.

Роботы путешествуют по Интернету по маршруту, составленному программой-планировщиком. Обнаружив неизвестную ссылку, роботы добавляют их в свой список подлежащих посещению адресов. Очередность посещения веб-страниц устанавливается с учетом тИЦ, частоты обновления сайтов и других ценных характеристик. Построенный маршрут планировщик передает «пауку». Миссия паука – скачивание запланированных документов, определение их типа (HTML, SWF, PDF  и т.д.), языка и кодировки, отправка собранных данных в хранилище. В хранилище производится очищение текста от HTML-разметки, отмечаются сведения о местоположении каждого слова. Отсюда все данные отправляются в индекс.

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

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

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

Как добавить сайт/страницу в индекс поисковой системы?

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

Аддурилка Яндекса: https://webmaster.yandex.ru/site/indexing/reindex/

Аддурилка Google: https://www.google.com/webmasters/tools/submit-url

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

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

Что делать для облегчения индексации всех страниц сайта в поисковиках?

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

  1. 1. На сайте должен размещаться уникальный и качественный контент. Большое количество плагиата может заставить поисковых роботов потерять интерес к сайту.
  2. 2. Нельзя использовать «черные» и «серые» методы оптимизации. Подобные нарушения могут привести к запрету индексации доменного имени.
  3. 3. Не стоит спешить сообщать поисковым системам о сайте сразу после его появлении на сервере. Желательно еще раз проверить качество представления контента, валидность кода, целостность внутренней перелинковки страниц. Поисковые роботы при индексировании отделяют текст от  HTML-кода, поэтому индексация сайта во многом зависит от корректности кода страницы. Информацию о внешнем виде страниц лучше выносить в каскадные таблицы стилей CSS.
  4. 4. На каждой странице должны быть верно прописаны мета-теги (тайтлы, ключевые слова и описания) и альты изображений.
  5. 5. Некоторые типы данных индексируются с ограничениями. В частности поисковики плохо обрабатывают документы с Flash и Javascript. Стоит отказаться от красиво раскрывающихся меню и других спецэффектов в пользу простой текстовой навигации по сайту.
  6. 6. Улучшает индексацию карта сайта. Исследуя карту сайта,  поисковые роботы могут легко и быстро добраться до всех страниц проекта. 
  7. 7. Служебные страницы, неуникальный и дублированный контент нужно скрывать от индексации. Повлиять на индексацию страниц поисковыми роботами можно через инструкцию в файле robots.txt, создаваемую директивами Allow, Disallow, User-agent, Crawl-delay. Запретить индексацию конкретного контента можно через мета-тег Robots, теги и атрибут .

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

Поисковый индекс — Википедия

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

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

Популярные поисковые машины сосредотачиваются на полнотекстовой индексации документов, написанных на естественных языках[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 (Ноябрь 09, 2006). Дата обращения 3 декабря 2013.

что это такое и как туда попасть сайту

Мы увеличиваем посещаемость и позиции в выдаче. Вы получаете продажи и платите только за реальный результат, только за целевые переходы из поисковых систем

Получи нашу книгу «Контент-маркетинг в социальных сетях: Как засесть в голову подписчиков и влюбить их в свой бренд».

Подпишись на рассылку и получи книгу в подарок!

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

Больше видео на нашем канале - изучайте интернет-маркетинг с SEMANTICA

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

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

Что значит индексация

Это процесс, в ходе которого роботы включают имеющиеся данные в единую базу. Далее они обрабатываются. Сбор данных, формирование индекса может происходить автоматически или вручную. В первом случае робот ищет сайты, для этого он сканирует файл формата sitemap.xml или переходит по внешним ссылкам с других сайтов. Во втором варианте владелец сайта сам добавляет URL сайта в специализированные формы-заявки систем Гугл, Яндекс и так далее.

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

Для чего нужен индекс поисковой системы

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

Индексирование делают роботы, которые бывают двух типов:

  1. Основные. Они анализируют содержимое страниц, представленных на них контент.
  2. Быстрые. Он анализируют и индексируют новые данные, которые прибавились после обновления интернет-ресурса.

Есть и другие роботы, которые различаются по предмету индексации: специальные механизмы для работы с изображениями, RSS-лентами и прочими материалами.

Чем быстрее сайт добавляется в индекс, тем скорее вы увидите первых посетителей. Индексация Гуглом занимает несколько дней, а индексация Яндексом — несколько недель.

Проверить индексацию в системах Гугл и Яндекс

Чтобы проверить, проиндексирован ли ваш ресурс, можно использовать несколько способов:

  • Проанализировать данные панели веб-мастера. Открываем сервисы системы Гугл, после — Search Console. Теперь заходим в раздел «Индекс Google». Данные, которые мы ищем, находятся в в блоке «Статус». Для Яндекса делаем следующее: «Индексирование сайта», затем «Страницы в поиске».
  • Направить запрос по интернет-ресурсу, используя особые операторы. С этой целью нужно сделать запрос типа «site:» и адрес вашего сайта полностью. Таким образом можно узнать число страниц, которые уже проиндексированы. Если имеются расхождения, 80% и выше, значит в поисковиках есть проблемы.
  • Загрузить особые плагины. С помощью данного расширения можно легко проверить индексацию. Наиболее востребованный плагин сегодня — RDS Bar.

Ускорение индексации

Скорость индексации зависит от факторов:

  • Полное отсутствие ошибок, которые могли бы снизить скорость сбора роботами данных.
  • Авторитет сайта.
  • Как часто публикуется новый контент.
  • Каков уровень вложенности страниц сайта.
  • Правильно ли заполнен файл формата sitemap.xml.

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

  • Поменяйте хостинг на более надежный.
  • Откорректируйте robots.txt, выполните установку правил индексации, снимите ненужные запреты.
  • Ликвидируйте ошибки в коде.
  • Сделайте sitemap.xml, сохраните его в корневой папке.
  • Продумайте навигацию, чтобы каждая из страниц сайта находилась не больше, чем в трех кликах от главной страницы.
  • Обязательно добавьте сайт в панели веб-мастеров Гугл и Яндекс.
  • Выполните внутреннюю перелинковку.
  • Выполните регистрацию сайта в рейтингах с хорошим авторитетом.
  • Следите за контентом, проверяйте его.

С момента занесения сайта в индекс начинается отсчет возраста сайта.

Поисковый индекс — Википедия

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

Популярные поисковые машины сосредотачиваются на полнотекстовой индексации документов, написанных на естественных языках[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 (Ноябрь 09, 2006). Проверено 3 декабря 2013.

Поисковый индекс — Википедия. Что такое Поисковый индекс

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

Популярные поисковые машины сосредотачиваются на полнотекстовой индексации документов, написанных на естественных языках[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 (Ноябрь 09, 2006). Проверено 3 декабря 2013.

Поисковый индекс Википедия

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

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

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

Индексация[ | ]

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

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

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

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

Поисковый индекс Википедия

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

Популярные поисковые машины сосредотачиваются на полнотекстовой индексации документов, написанных на естественных языках[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 (Ноябрь 09, 2006). Дата обращения 3 декабря 2013.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *