Алгоритмы поиска, обратный индекс — Часть 1 / Habr

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

Что вы узнаете?

Алгоритмы поиска. Что представляет из себя индексация, инвертированный индекс. Математические модели, используемые современными поисковыми системами.

Алгоритмы поиска

1. Прямой поиск — последовательный перебор всех данных;
2. Инвертированных индексов — список слов (индекс-файл) документированные в алфавитном порядке с указание позиции и других параметров вхождения слова документа.

Обратный индекс

Как вы наверное догадались поисковиками используется алгоритм инвертированных индексов, т. к. использование прямого поиска гораздо более ресурсоемко. Восстановление из обратного индекса произойдет с потерями (падежи, дефисы, запятые, и т. п.). Поэтому также хранится прямой индекс документа для отображения сниппета (фрагмент найденного текста документа отображаемый в поиске).

Документ

Жил-был поп,
Толоконный лоб.
Пошел поп по базару
Посмотреть кой-какого товару.

Обратный индекс документа

базар  (3,4)
был     (1,2)
жил     (1,1)
какой  (1,1)
кой     (4,2)
лоб     (2,1)
поп     (1,3) (3,2)

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

Математическая модель

При поиске используется 3 типа математических моделей, вот они:

1. Булевские (логические) — есть слово — найден, нет — не найден;
2. Векторные (используются всеми ПС) — вес слова = TF * IDF;

   TF — частота слова в документе
   IDF — редкость слова в коллекции (корпус слов)
3. Вероятностная — подбор выдачи в ручную (с помощью асессоров) — самостоятельное определение релевантности страниц.

Главное

Релевантность — степень отношения к делу. Продвигайте только релевантные документы.

Как работают поисковые системы Сегалович И.В.

П.С. Продолжение следует…

Построение индекса для поисковой машины / Habr

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

В предыдущих статьях я рассказывал про работу поисковой машины, вот и дошел до сложного технически момента. Напомню что разделяют 2 типа индексов – прямой и обратный. Прямой – сопоставление документу списка слов в нем встреченного. Обратный – слову сопоставляется список документов, в которых оно есть. Логично, что для быстрого поиска лучше всего подходит обратный индекс. Интересный вопрос и про то, в каком порядке в списке хранить документы.

На предыдущем шаге DataFlow от модуля-индексатора мы получили кусочек данных в виде прямого индекса, ссылочной информации и информации о страницах. Обычно у меня он составляет около 200-300mb и содержит примерно 100 тысяч страниц. Со временем я отказался от стратегии хранения цельного прямого индекса, и храню только все эти кусочки + полный обратный индекс в нескольких версиях, чтобы можно было откатиться назад.

Устройство обратного индекса с виду, простое, – храним файл, в нем в начале таблица адресов начала данных по каждому слову, потом собственно данные. Это я утрировано. Так получается самый выгодный для оптимизации скорости поиска формат — не надо прыгать по страницам — как писали Брин и Пейдж, — 1 seek, 1 read. На каждой итерации перестроения, я использую 20-50 кусочков информации описанных выше, очевидно загрузить всю инфу из них в память я не могу, тем более что там полезно хранить еще кучу служебных данных об индексе.

Чтобы решить и эту, и много других проблем связанных с ограничениями ФС, диска, параллельным доступом к нескольким спискам страниц, я разбил весь индекс на 256 частей. В часть I попадают списки страниц для слов WORD_ID%256=I

Таким образом делим индекс на примерно равные части. Кроме того вся обработка на очередной итерации перестроения индекса связана только в рамках одной части. Т.е. из 20-50 кусков БД по 200-300 Mb необходимо загрузить только те данные, которые связаны со словами, попадающими в обрабатываемую часть.

Итого: делаем 256 повторений одной и той же процедуры:

1. читаем нужные данные из входных кусков БД, предварительно загрузив всю информацию о словах, страницах и Url страниц. В памяти сортируем, делаем списки правильной структуры. Упаковываем инфу о странице и добавляем ее ID, HASH и другие данные.
2. открываем баррель (я обозвал так куски индекса) обратного индекса «крайней версии» для чтения. Открываем пустой баррель «новой версии» индекса для записи.
3. Для каждого слова по порядку сливаем 2 списка – один построенный сортированный в памяти, а другой читаемый и уже отсортированный в файле.
4. Закрываем, дописываем все что надо, радуемся.

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

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

Я использую совмещенный коэффициент, построенный из общей информации о слове на странице (кол-во встреч; место встречи – title, meta, ссылки, текст; выделение, форматирование), из метрик тематичности (пока что они развиты у меня весьма слабо), из PR, из пословного PR (PR по каждому слову у меня тоже есть) и некоторых других.

Причем очевидно, что при высокочастотных запросах, нам реально нужны дай бог первая 1000-2000 результатов в списке, для верности будем считать 262 тысячи. Т.к. все популярные ответы очевидно попадут в них, а дальше на них можно запускать уже функцию ранжирования которая как следует их отсортирует.
При низкочастотных запросах, когда нам реально нужны 2-3-10 результатов, без полного прохождения индекса не обойтись, однако и общая длина списка страниц редко когда будет больше 100 тысяч.

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

1. запоминаем какие PR сильно изменились при пересчете
2. грузим первые N тысяч из списка+немного из остатка по критериям PR, метрики страницы и другой эвристике
3. туда же грузим из входных данных нужную порцию о словах текущего барреля
4. только для выделенных страниц уже обновляем все данные на корректные, новые – PR, метрики
5. сортируем сотню тысяч результатов, вместо пары десятков миллионов и уже в памяти
6. пишем отсортированное, а остальное просто копируем из предыдущего индекса удаляя дубли

Ну и конечно надо иметь функцию «обновить целиком» когда раз в месяц-полгода, к примеру, индекс будет перестраиваться весь самым простым прямым алгоритмом

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

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

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

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

Популярные поисковые машины сосредотачиваются на полнотекстовой индексации документов, написанных на естественных языках^[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.

Поисковый индекс: понятие и разновидности

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

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

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

Выделяют два различных способов индексации – автоматический и ручной

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

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

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

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

Похожее

Инвертированный индекс — Википедия

Материал из Википедии — свободной энциклопедии

Инвертированный индекс (англ. inverted index) — структура данных, в которой для каждого слова коллекции документов в соответствующем списке перечислены все документы в коллекции, в которых оно встретилось. Инвертированный индекс используется для поиска по текстам.

Есть два варианта инвертированного индекса:

• индекс, содержащий только список документов для каждого слова,
• индекс, дополнительно включающий позицию слова в каждом документе^[1].

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

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

Пусть у нас есть корпус из трёх текстов T0={\displaystyle T_{0}=}"it is what it is", T1={\displaystyle T_{1}=}"what is it" и T2={\displaystyle T_{2}=}"it is a banana", тогда инвертированный индекс будет выглядеть следующим образом:

"a":      {2}
"banana": {2}
"is":     {0, 1, 2}
"it":     {0, 1, 2}
"what":   {0, 1}

Здесь цифры обозначают номера текстов, в которых встретилось соответствующее слово. Тогда отработка поискового "what is it" запроса даст следующий результат {0,1}∩{0,1,2}∩{0,1,2}={0,1}{\displaystyle \{0,1\}\cap \{0,1,2\}\cap \{0,1,2\}=\{0,1\}}.

Особенности применения в реальных поисковых системах[править | править код]

В списке вхождений слова в документы, помимо id документов, обычно также указываются факторы (TF-IDF, бинарный фактор: «попало слово в заголовок или не попало», другие факторы), которые используются при ранжировании. Индекс может строиться не по всем словоформам, а по леммам (по каноническим формам слов). Стоп-слова можно исключить и не строить для них индекс, считая, что каждое из них встречается почти во всех документах корпуса. Для ускорения вычисления пересечений используют эвристику skip-pointer-ов. При обработке запросов, содержащих много слов, используют функцию кворума, которая пропускает на следующую стадию ранжирования часть документов, в которых встретились не все слова из запроса.

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

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

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

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

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

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

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

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

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

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

Как хранить индексируемые данные? То есть определяют вид хранимой информации: сжатый или отфильтрованный.

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

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

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

Как быстро можно найти слово в инвертированном индексе. Важным для информатики является сравнение скорости нахождения записи в структуре данных и скорости обновления/удаления индекса.

Хранение

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

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

Для поисковой службы важно быть надежной. Вопросы

Архитектура поисковой системы различается по способам индексирования и по методам хранения индексов, удовлетворяя факторы^[⇨]. Индексы б

Что такое поисковый индекс? | KV.by

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

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

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

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

Вадим СТАНКЕВИЧ,
[email protected]