Индексирование и обработка запросов
Индексирование и обработка запросов включают структуры данных и алгоритмы, которые позволяют поисковой системе быстро отвечать на запросы по большим текстовым коллекциям, главным образом с помощью инвертированного индекса.
Definition
Индексирование — это построение структур данных, главным образом инвертированного индекса, сопоставляющего термины с содержащими их документами, что обеспечивает эффективный поиск, в то время как обработка запросов — это набор алгоритмов, которые обходят эти структуры для вычисления документов, соответствующих запросу или наилучшим образом ранжированных для него.
Scope
Эта область охватывает то, как текстовые коллекции преобразуются в структуры, доступные для поиска, и как запросы оцениваются по ним: построение инвертированного индекса, решения по токенизации и терминологическому словарю, сжатие списков вхождений для экономии места и ускорения доступа, эффективная обработка запросов, включая ранжированный поиск и раннее завершение, а также методы толерантного поиска, такие как поиск по шаблону (wildcard), исправление орфографии и фонетическое сопоставление. Она затрагивает системную инженерию быстрого поиска, отличную от моделей поиска, которые определяют ранжирование, и методов оценки, которые измеряют качество.
Sub-topics
Core questions
- Как строится и обновляется инвертированный индекс для большой, изменяющейся коллекции?
- Как можно сжимать списки вхождений без замедления оценки запросов?
- Как эффективно оцениваются запросы, особенно ранжированные запросы по миллионам документов?
- Как система может получать хорошие результаты, не оценивая каждый документ?
- Как система обрабатывает опечатки, подстановочные знаки и приблизительные совпадения?
Key concepts
- инвертированный индекс
- список вхождений
- токенизация и терминологический словарь
- построение индекса (BSBI, SPIMI)
- сжатие индекса
- подокументная и пословная оценка
- динамическая обрезка и раннее завершение
- толерантный поиск
Key theories
- Инвертированный индекс как основная структура данных
- Сопоставление каждого термина со списком вхождений документов (и позиций), где он встречается, позволяет поиску затрагивать только документы, содержащие термины запроса, что делает его фундаментальной структурой для масштабируемого текстового поиска.
- Компромисс между сжатием и эффективностью
- Кодирование промежутков идентификаторов документов и частот терминов с помощью компактных целочисленных кодов значительно уменьшает размер индекса и, за счет сокращения операций ввода/вывода и улучшения поведения кэша, также может ускорить обработку запросов.
- Эффективная оценка ранжированных запросов
- Стратегии подокументной и пословной оценки в сочетании с методами динамической обрезки и раннего завершения позволяют системам возвращать наиболее релевантные результаты без полной оценки всей коллекции.
Clinical relevance
Инвертированные индексы и эффективная обработка запросов являются основой каждой производственной поисковой системы, от веб-поисковых систем и поисковых платформ с открытым исходным кодом до полнотекстового поиска в корпоративных системах и базах данных. Их эффективность напрямую определяет задержку запросов, стоимость оборудования и масштаб коллекций, которые могут быть интерактивно просмотрены.
History
Инвертированные файлы использовались для текстового поиска с самых ранних информационных систем, но современная теория построения индекса, сжатия и эффективной оценки была консолидирована в 1990-х годах, в частности, в работе Уиттена, Моффата и Белла «Managing Gigabytes». Обзор Зобеля и Моффата 2006 года синтезировал два десятилетия исследований инвертированных индексов, поскольку веб-масштабный поиск сделал эффективность первостепенной задачей.
Key figures
- Justin Zobel
- Alistair Moffat
- Ian H. Witten
- W. Bruce Croft
Related topics
Seminal works
- zobel2006
- wittenmgb1999
- manning2008
Frequently asked questions
- Почему инвертированный индекс предпочтительнее сканирования документов?
- Сканирование каждого документа для каждого запроса слишком медленно в масштабе. Инвертированный индекс позволяет системе сразу переходить к небольшому набору документов, которые содержат термины запроса, поэтому время запроса зависит от задействованных списков вхождений, а не от размера всей коллекции.
- Замедляет ли сжатие индекса поиск?
- Обычно наоборот. Меньший индекс уменьшает трафик диска и памяти, а современные целочисленные коды очень быстро декомпрессируются, поэтому время, сэкономленное на вводе/выводе и улучшенном поведении кэша, обычно перевешивает затраты на декодирование, делая сжатые индексы как меньше, так и быстрее.