Пошуко́вий і́ндекс — структура даних, яка містить інформацію про документи та використовується в пошукових системах. Індексування, що здійснюється пошуковою машиною, — процес збору, сортування та зберігання даних з метою забезпечення швидкого та точного пошуку інформації. Створення індексу включає міждисциплінарні поняття з лінгвістики, когнітивної психології, математики, інформатики та фізики. Вебіндексуванням називають процес індексування в контексті пошукових машин, розроблених для пошуку вебсторінок в Інтернеті.
Популярні пошукові машини зосереджуються на повнотекстовій індексації документів, написаних природною мовою. Мультимедійні документи, такі як відео та аудіо і графіка, також можуть брати участь у пошуку.
Метапошукові машини використовують індекси інших пошукових сервісів і не зберігають локальний індекс, тоді як пошукові машини, засновані на кеш сторінках, довго зберігають як індекс, так і текстові корпуси. На відміну від повнотекстових індексів, частково-текстові сервіси обмежують глибину індексації, щоб зменшити розмір індексу. Великі сервіси, зазвичай, виконують індексацію в заданому часовому інтервалі через необхідність часу і витрат на обробку, у той час як пошукові машини, засновані на агентах, будують індекс у масштабі реального часу.
Індексація Мета використання індексу — підвищення швидкості пошуку релевантних документів за пошуковим запитом. Без індексу пошукова машина повинна була б сканувати кожен документ в корпусі, що вимагало б великої кількості часу і обчислювальної потужності. Наприклад, у той час, як індекс 10 000 документів може бути опитано в межах мілісекунд, послідовний перегляд кожного слова в 10 000 великих документів міг би зайняти години. Додаткова пам'ять, що виділяється для зберігання індексу, і збільшення часу, необхідного для поновлення індексу, компенсується зменшенням часу на пошук інформації.
Фактори, що впливають на проектування пошукових систем При розробці пошукової системи необхідно враховувати такі фактори: Фактори злиття Як дані входять до індексу? Як слова та підлеглі функції додаються до індексу під час текстового корпусного обходу? І чи можуть кілька пошукових роботів працювати асинхронно? Пошуковий робот повинен спочатку перевірити, оновлює він старий зміст або додає новий. Злиття індексу пошукової системи подібно SQL Merge та іншим алгоритмам злиття. Методи зберігання Як зберігати індексовані дані? Тобто визначають вид інформації, що зберігається: стиснутий або відфільтрований. Розмір індексу Скільки необхідно пам'яті комп'ютера, аби підтримувати індекс. Швидкість пошуку Як швидко можна знайти слово в інвертованому індексі. Важливим для інформатики є порівняння швидкості знаходження запису в структурі даних та швидкості оновлення/видалення індексу. Зберігання Як зберігається індекс протягом тривалого часу. Відмовостійкість Для пошукової служби важливо бути надійною. Запитання відмовостійкості містять проблему ушкодження індексу, визначаючи, чи можна окремо розглядати некоректні дані, пов'язані з поганими апаратними засобами, секціюванням та схемами на основі геш-функцій та композитного секціювання, а також реплікації.
Індексні структури даних Архітектура пошукової системи розрізняється за способами індексування і за методами зберігання індексів, задовольняючи чинники. Індекси бувають наступних типів: Суфіксне дерево Образно структуроване як дерево, підтримує лінійний час пошуку. Побудовано на зберіганні суфіксів слів. Дерева підтримують розширене гешування, яке важливо для індексації пошукової системи. Використовується для пошуку за шаблоном в послідовностях ДНК та кластеризації. Основним недоліком є те, що зберігання слова в дереві може потребувати простір більший, ніж необхідно для зберігання самого слова. Альтернативний запис — суфіксний масив. Вважається, що він вимагає менше віртуальної пам'яті та підтримує блочно-сортувальний стиск даних. Інвертований індекс Сховище списку входжень кожного критерію пошуку, зазвичай у формі геш-таблиць або бінарного дерева. Індекс цитування Сховище цитат або гіперпосилань між документами для підтримки аналізу цитування, предмет бібліометрії. N-грами Сховище послідовностей довжин, даних для підтримки інших типів пошуку або аналізу тексту. Матриця термів документа Використовується в латентно-семантичному аналізі (ЛСА), зберігає входження слів у документах двовимірної розрідженої матриці.
Проблеми паралельного індексування Однією з основних задач при проектуванні пошукових систем є управління послідовними обчислювальними процесами. Існують ситуації, у яких можливе створення стану гонитви та когерентних відмов. Наприклад, новий документ доданий до корпусу, і індекс повинен бути оновленим, але в той же час індекс повинен продовжувати відповідати на пошукові запити. Це колізія між двома конкуруючими завданнями. Вважається, що автори є виробниками інформації, а пошуковий робот — споживачем цієї інформації, який захоплює текст та зберігає його в кеші (або корпусі). Прямий індекс є споживачем інформації, виробленої корпусом, а інвертований індекс — споживачем інформації, виробленої прямим індексом. Це зазвичай згадується як модель виробника-споживача. Індексатор є виробником доступної для пошуку інформації, а користувачі, які її шукають, — споживачами. Проблема посилюється при розподіленому зберіганні та розподіленій обробці. Щоб масштабувати великі обсяги індексованої інформації, пошукова система може ґрунтуватися на архітектурі розподілених обчислень, при цьому пошукова система складається з декількох машин, що працюють узгоджено. Це збільшує ймовірність нелогічності та робить складнішою підтримку повністю синхронізованої, розподіленої, паралельної архітектури.
Прямий індекс Прямий індекс зберігає список слів для кожного документа. Нижче наведена спрощена форма прямого індексу: + Прямий індекс Документ СловаДокумент 1Любіть, Україну, у, сні, й, наявуДокумент 2вишневу, свою, УкраїнуДокумент 3красу, її, вічно, живу, і, новуДокумент 4і, мову, її, солов'їну Необхідність розробки прямого індексу пояснюється тим, що найкраще одразу зберігати слова за документами, оскільки їх надалі аналізують для створення пошукового індексу. Формування прямого індексу включає асинхронну системну обробку, яка частково обходить вузьке місце оновлення інвертованого індексу. Прямий індекс сортують, щоб перетворити в інвертований. Прямий індекс власне являє собою список пар, які складаються з документів та слів, відсортованих за документами. Перетворення прямого індексу у інвертований є лише питанням сортування пар за словами. У цьому плані інвертований індекс — відсортований за словами прямий індекс.
Інвертований індекс
Багато пошукових систем використовують інвертований індекс при оцінюванні пошукового запиту, щоб швидко визначити місце розташування документів, що містять слова запиту, а потім ранжувати ці документи по релевантності. Оскільки інвертований індекс зберігає список документів, що містять кожне слово, пошукова система може використовувати прямий доступ, аби знайти документи, пов'язані з кожним словом в запиті, і швидко отримати їх. Нижче наведено спрощене уявлення інвертованого індексу: + Інвертований індекс Слово ДокументивічноДокумент 3вишневуДокумент 2живуДокумент 3іДокумент 3,Документ 4їїДокумент 3, Документ 4йДокумент 1красуДокумент 3любітьДокумент 1мовуДокумент 4наявуДокумент 1новуДокумент 3своюДокумент 2сніДокумент 1солов'їнуДокумент 4уДокумент 1УкраїнуДокумент 1,Документ 2 Інвертований індекс може лише визначити, чи існує слово в межах конкретного документа, оскільки не зберігає жодної інформації щодо частоти та позиції слова, і тому його вважають логічним індексом. Він визначає, які документи відповідають запиту, але не оцінює їх. У деяких випадках індекс містить додаткову інформацію, таку як частота кожного слова в кожному документі або позиція слова в документі. Інформація про позицію слова дозволяє пошуковому алгоритму ідентифікувати близькість слова, щоб підтримувати пошук фраз. Частота може використовуватися, щоб допомогти в ранжуванні документів за запитом. Такі теми в центрі уваги досліджень інформаційного пошуку.
Інвертований індекс представлений розрідженою матрицею, оскільки не всі слова присутні в кожному документі. Індекс подібний матриці термів документа, що використовується в ЛСА. Інвертований індекс можна вважати формою геш-таблиці. В деяких випадках індекс представлений у формі двійкового дерева, яка вимагає додаткової пам'яті, але може зменшити час пошуку. У великих індексах архітектура, зазвичай, представлена розподіленою геш-таблицею.
Злиття індексу Інвертований індекс заповнюється шляхом злиття або відновлення. Архітектура може бути спроектована так, щоб підтримувати інкрементну індексацію, у якій злиття визначає документ або документи, які будуть додані або оновлені, а потім аналізує кожний документ в слова. Для технічної точності, злиття об'єднує недавно індексовані документи, які зазвичай перебувають у віртуальній пам'яті, з індексним кешем, який розташований на одному або декількох твердих дисках комп'ютера.
Після синтаксичного аналізу індексатор додає вказаний документ в список документів для відповідних слів. У більш великих пошукових системах процес знаходження кожного слова для інвертованого індексу може потребувати великого обсягу роботи, тому його, зазвичай, поділяють на дві частини: розробка прямого індексу, сортування прямого індексу в інвертований індекс. Інвертований індекс називається так через те, що він є інверсією прямого індексу.
Стиснення Створення та підтримка великомасштабного пошукового індексу потребує значної пам'яті та виконання завдань обробки. Багато пошукових систем використовують ту чи іншу форму стиснення, щоб зменшити розмір індексів на диску. Розглянемо таку ситуацію для повнотекстового механізму пошуку в Інтернеті: Потрібно 8 бітів (1 байт) для зберігання одного символу. Деякі кодування використовують 2 байта на символ. Середнім числом символів в будь-якому слові на сторінці візьмемо 5. Враховуючи цей сценарій, не стислий індекс для 2 мільярдів вебсторінок мав би зберігати 500 мільярдів записів слів. 1 байт за символ або 5 байтів за слово — було б потрібно 2500 гігабайт одного лише простору пам'яті. Це більше, ніж середній вільний простір на диску 2 персональних комп'ютерів. Для відмовостійкій розподіленої архітектури потрібно ще більше пам'яті. Залежно від обраного методу стиснення індекс може бути зменшений до частини такого розміру. Компроміс часу і обчислювальної потужності, необхідної для виконання стиснення та розпакування.
Цікаво, що великомасштабні проекти пошукових систем містять витрати на зберігання, а також на електроенергію для здійснення зберігання.
Синтаксичний аналіз документа Синтаксичний аналіз (або парсинг) документа передбачає його розбір на компоненти (слова) для вставки в прямий та інвертований індекси. Знайдені слова називають токенами (), і в контексті індексації пошукових систем та обробки природної мови парсинг часто називають токенізацією (тобто розбиттям на токени). Синтаксичний аналіз іноді називають розміткою частин мови, морфологічним аналізом, контент-аналізом, текстовим аналізом, аналізом тексту, генерацією узгодження, сегментацією промови, лексичним аналізом. Терміни «індексація», «парсинг» та «токенізація» взаємозамінні в корпоративному сленгу.
Обробка природної мови постійно досліджується і покращується. Токенізація має проблеми з отриманням необхідної інформації з документів для індексації, для підтримання якісного пошуку. Токенізація для індексації включає в себе кілька технологій, реалізація яких може бути комерційною таємницею.
Проблеми при обробці природної мови