Пошуковий індекс

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

Пошуко́вий і́ндекс — структура даних, яка містить інформацію про документи та використовується в пошукових системах. Індексування, що здійснюється пошуковою машиною, — процес збору, сортування та зберігання даних з метою забезпечення швидкого та точного пошуку інформації. Створення індексу включає міждисциплінарні поняття з лінгвістики, когнітивної психології, математики, інформатики та фізики. Веб-індексуванням називають процес індексування в контексті пошукових машин, розроблених для пошуку веб-сторінок в Інтернеті.

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

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

Індексація[ред. | ред. код]

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

Фактори, що впливають на проектування пошукових систем[ред. | ред. код]

При розробці пошукової системи необхідно враховувати такі фактори:

Фактори злиття
Як дані входять до індексу? Як слова та підлеглі функції додаються до індексу під час текстового корпусного обходу? І чи можуть кілька пошукових роботів працювати асинхронно? Пошуковий робот повинен спочатку перевірити, оновлює він старий зміст або додає новий. Злиття індексу[⇨] пошукової системи подібно SQL Merge та іншим алгоритмам злиття[5].
Методи зберігання
Як зберігати індексовані дані? Тобто визначають вид інформації, що зберігається: стиснутий або відфільтрований.
Розмір індексу
Скільки необхідно пам'яті комп'ютера, аби підтримувати індекс.
Швидкість пошуку
Як швидко можна знайти слово в інвертованому індексі. Важливим для інформатики є порівняння швидкості знаходження запису в структурі даних та швидкості оновлення/видалення індексу.
Зберігання
Як зберігається індекс протягом тривалого часу[6].
Відмовостійкість
Для пошукової служби важливо бути надійною. Запитання відмовостійкості містять проблему ушкодження індексу, визначаючи, чи можна окремо розглядати некоректні дані, пов'язані з поганими апаратними засобами, секціонуванням та схемами на основі хеш-функцій та композитного секціонування[7], а також реплікації.

Індексні структури даних[ред. | ред. код]

Архітектура пошукової системи розрізняється за способами індексування і за методами зберігання індексів, задовольняючи чинники[⇨]. Індекси бувають наступних типів:

Суфіксне дерево
Образно структуроване як дерево, підтримує лінійний час пошуку. Побудовано на зберіганні суфіксів слів. Дерева підтримують розширене хешування, яке важливо для індексації пошукової системи[8]. Використовується для пошуку за шаблоном в послідовностях ДНК та кластеризації. Основним недоліком є те, що зберігання слова в дереві може потребувати простір більший, ніж необхідно для зберігання самого слова[9]. Альтернативний запис — суфіксний масив[ru]. Вважається, що він вимагає менше віртуальної пам'яті та підтримує блочно-сортувальний стиск даних.
Інвертований індекс
Сховище списку входжень кожного критерію пошуку[10], зазвичай у формі хеш-таблиць або бінарного дерева[11][12].
Індекс цитування
Сховище цитат або гіперпосилань між документами для підтримки аналізу цитування, предмет бібліометрії.
N-грами
Сховище послідовностей довжин, даних для підтримки інших типів пошуку або аналізу тексту[13].
Матриця термів документа
Використовується в латентно-семантичному аналізі (ЛСА), зберігає входження слів у документах двовимірної розрідженої матриці.

Проблеми паралельного індексування[ред. | ред. код]

Однією з основних задач при проектуванні пошукових систем є управління послідовними обчислювальними процесами. Існують ситуації, у яких можливе створення стану гонитви та когерентних відмов. Наприклад, новий документ доданий до корпусу, і індекс повинен бути оновленим, але в той же час індекс повинен продовжувати відповідати на пошукові запити. Це колізія між двома конкуруючими завданнями. Вважається, що автори є виробниками інформації, а пошуковий робот — споживачем цієї інформації, який захоплює текст та зберігає його в кеші (або корпусі). Прямий індекс є споживачем інформації, виробленої корпусом, а інвертований індекс — споживачем інформації, виробленої прямим індексом. Це зазвичай згадується як модель виробника-споживача. Індексатор є виробником доступної для пошуку інформації, а користувачі, які її шукають, — споживачами. Проблема посилюється при розподіленому зберіганні та розподіленій обробці. Щоб масштабувати великі обсяги індексованої інформації, пошукова система може ґрунтуватися на архітектурі розподілених обчислень, при цьому пошукова система складається з декількох машин, що працюють узгоджено. Це збільшує ймовірність нелогічності та робить складнішою підтримку повністю синхронізованої, розподіленої, паралельної архітектури[14].

Прямий індекс[ред. | ред. код]

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

Прямий індекс
Документ Слова
Документ 1 Любіть, Україну, у, сні, й, наяву
Документ 2 вишневу, свою, Україну
Документ 3 красу, її, вічно, живу, і, нову
Документ 4 і, мову, її, солов'їну

Необхідність розробки прямого індексу пояснюється тим, що найкраще одразу зберігати слова за документами, оскільки їх надалі аналізують для створення пошукового індексу. Формування прямого індексу включає асинхронну системну обробку, яка частково обходить вузьке місце оновлення інвертованого індексу[15]. Прямий індекс сортують, щоб перетворити в інвертований. Прямий індекс власне являє собою список пар, які складаються з документів та слів, відсортованих за документами. Перетворення прямого індексу у інвертований є лише питанням сортування пар за словами. У цьому плані інвертований індекс — відсортований за словами прямий індекс.

Інвертований індекс[ред. | ред. код]

Багато пошукових систем використовують інвертований індекс при оцінюванні пошукового запиту, щоб швидко визначити місце розташування документів, що містять слова запиту, а потім ранжувати ці документи по релевантності. Оскільки інвертований індекс зберігає список документів, що містять кожне слово, пошукова система може використовувати прямий доступ, аби знайти документи, пов'язані з кожним словом в запиті, і швидко отримати їх. Нижче наведено спрощене уявлення інвертованого індексу:

Інвертований індекс
Слово Документи
вічно Документ 3
вишневу Документ 2
живу Документ 3
і Документ 3,Документ 4
її Документ 3, Документ 4
й Документ 1
красу Документ 3
любіть Документ 1
мову Документ 4
наяву Документ 1
нову Документ 3
свою Документ 2
сні Документ 1
солов'їну Документ 4
у Документ 1
Україну Документ 1,Документ 2

Інвертований індекс може лише визначити, чи існує слово в межах конкретного документа, оскільки не зберігає жодної інформації щодо частоти та позиції слова, і тому його вважають логічним індексом. Він визначає, які документи відповідають запиту, але не оцінює їх. У деяких випадках індекс містить додаткову інформацію, таку як частота кожного слова в кожному документі або позиція слова в документі[16]. Інформація про позицію слова дозволяє пошуковому алгоритму ідентифікувати близькість слова, щоб підтримувати пошук фраз. Частота може використовуватися, щоб допомогти в ранжируванні документів за запитом. Такі теми в центрі уваги досліджень інформаційного пошуку.

Інвертований індекс представлений розрідженою матрицею, оскільки не всі слова присутні в кожному документі. Індекс подібний матриці термів документа, використовуваному в ЛСА. Інвертований індекс можна вважати формою хеш-таблиці. В деяких випадках індекс представлений у формі двійкового дерева, яка вимагає додаткової пам'яті, але може зменшити час пошуку. У великих індексах архітектура, зазвичай, представлена розподіленою хеш-таблицею[17].

Злиття індексу[ред. | ред. код]

Інвертований індекс заповнюється шляхом злиття або відновлення. Архітектура може бути спроектована так, щоб підтримувати інкрементну індексацію[18][19], у якій злиття визначає документ або документи, які будуть додані або оновлені, а потім аналізує кожний документ в слова. Для технічної точності, злиття об'єднує недавно індексовані документи, які зазвичай перебувають у віртуальній пам'яті, з індексним кешем, який розташований на одному або декількох твердих дисках комп'ютера.

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

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

Інвертований індекс називається так через те, що він є інверсією прямого індексу.

Стиснення[ред. | ред. код]

Створення та підтримка великомасштабного пошукового індексу потребує значної пам'яті та виконання завдань обробки. Багато пошукових систем використовують ту чи іншу форму стиснення, щоб зменшити розмір індексів на диску[6]. Розглянемо таку ситуацію для повнотекстового механізму пошуку в Інтернеті:

  • Потрібно 8 бітів (1 байт) для зберігання одного символу. Деякі кодування використовують 2 байта на символ[20].
  • Середнім числом символів в будь-якому слові на сторінці візьмемо 5.

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

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

Синтаксичний аналіз документа[ред. | ред. код]

Синтаксичний аналіз (або парсинг) документа передбачає його розбір на компоненти (слова) для вставки в прямий та інвертований індекси. Знайдені слова називають токенами (англ. token), і в контексті індексації пошукових систем та обробки природної мови парсинг часто називають токенізацією (тобто розбиттям на токени). Синтаксичний аналіз іноді називають розміткою частин мови, морфологічним аналізом, контент-аналізом, текстовим аналізом, аналізом тексту, генерацією узгодження, сегментацією промови, лексичним аналізом. Терміни «індексація», «парсинг» та «токенізація» взаємозамінні в корпоративному сленгу.

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

Проблеми при обробці природної мови[ред. | ред. код]

Неоднозначність кордонів слова
На перший погляд може здатися, що токенізація є простим завданням, але це не так, особливо при розробці багатомовного індексатора. У цифровій формі тексти деяких мов таких як китайська, японська або арабська являють собою складну задачу, оскільки слова чітко не розділені пропуском. Мета токенізації в тому, щоб розпізнати слова, які шукатимуть користувачі. Специфічна для кожної мови логіка використовується, щоб правильно розпізнати межі слів, що необхідно для розробки синтаксичного аналізатора для кожної підтримуваної мови (або для груп мов зі схожими кордонами та синтаксисом).
Неоднозначність мови
Для більш точного ранжування документів пошукові системи можуть враховувати додаткову інформацію про слово, наприклад, до якої мови або частини мови воно відноситься. Ці методи залежать від мови, оскільки синтаксис між мовами різниться. При токенізації деякі пошукові системи намагаються автоматично визначити мову документа.
Різні формати файлів
Для того щоб правильно визначити, які байти представляють символи документа, формат файлу повинен бути правильно оброблений. Пошукові системи, які підтримують різні формати файлів повинні правильно відкривати документ, отримувати доступ до документа та токенізувати його символи.
Помилки пам'яті
Якість даних природної мови не завжди може бути досконалим. Уразливість існує через невідому кількість документів, зокрема в Інтернеті, які не підпорядковуються відповідному протоколу файлу. Двійкові символи можуть бути помилково закодовані в різних частинах документа. Без розпізнавання цих символів та відповідної обробки може погіршитися якість індексу або індексування.

Токенізація[ред. | ред. код]

На відміну від більшості людей, комп'ютери не розуміють структуру документа природної мови і не можуть автоматично розпізнавати слова та пропозиції. Для комп'ютера документ — це лише послідовність байтів. Комп'ютер не «знає», що символ пробілу є роздільником слів в документі. Людина повинна запрограмувати комп'ютер так, щоб визначити, що є окремим словом, званим токеном. Таку програму зазвичай називають токенізатором або синтаксичним аналізатором (парсером), а також лексичним аналізатором[21]. Деякі пошукові системи та інше ПО для обробки природної мови, підтримують спеціалізовані програми зручні для здійснення синтаксичного аналізу, наприклад, YACC або Лекс[ru][22].

Під час токенізації синтаксичний аналізатор визначає послідовність символів, які представляють слова та інші елементи, наприклад, пунктуація, представлена ​​числовими кодами, деякі з яких є недрукованими керуючими символами. Синтаксичний аналізатор може розпізнати деякі об'єкти, наприклад, адреси електронної пошти, телефонні номери та URL. При розпізнаванні кожного токена можуть бути збережені деякі характеристики, наприклад, мова або кодування, частина мови, позиція, число пропозиції, позиція в реченні, довжина та номер рядка[21].

Визначення мови[ред. | ред. код]

Якщо пошукова система підтримує декілька мов, то першим кроком під час токенізації буде визначення мови кожного документа, оскільки багато таких кроків залежать від цього (наприклад, Стемінг та визначення частини мови). Визначення мови[en] — це процес, при якому комп'ютерна програма намагається автоматично визначити чи класифікувати мову документа. Автоматичне розпізнавання мови є предметом досліджень в обробці природної мови[23].

Аналіз формату документа[ред. | ред. код]

Якщо пошукова система підтримує безліч форматів документів, то документи мають бути підготовлені для токенізації. Проблема полягає в тому, що деякі формати документів містять інформацію про форматування на додаток до текстового змісту. Наприклад, документи HTML містять HTML-теги[24]. Якби пошукова система ігнорувала відмінність між змістом та розміткою тексту, то стороння інформація включалася б в індекс, що привело б до поганих результатів пошуку. Аналіз формату — виявлення та обробка мови розмітки, вбудованої в документ. Аналіз формату також згадується як структурний аналіз, поділ тегів, текстова нормалізація.

Задача аналізу формату ускладнюється тонкощами різних форматів файлів. Деякі з них захищаються правом інтелектуальної власності, про них мало інформації, а інші навпаки добре документовані. Поширені, добре задокументовані формати файлів, які підтримують пошукові системи[25][26]:

Деякі пошукові системи підтримують файли, які зберігаються в стислому або зашифрованому форматі[27][28][29]. При роботі зі стисненим форматом індексатор спочатку розпаковує документ. Цей крок може привести до одного або декількох файлів, кожний з яких повинен бути індексований окремо. Бувають такі підтримувані формати стисненого файлу:

Аналіз формату може включати методи підвищення якості, що дозволяють уникнути включення «непотрібної інформації» в індекс. Контент може керувати інформацією про форматування, щоб включати додаткові відомості. Приклади зловживання форматуванням документа в разі веб-спаму:

  • Включення сотні або тисячі слів в розділ, який прихований від подання на моніторі, але є видимим індексаторам, за допомогою тегів форматування (наприклад, в прихований тег div в HTML можна включити використання CSS або JavaScript).
  • Установка кольору шрифту слів таким самим, як колір фону, що робить невидимими слова для людини при перегляді документа, але слова залишаються видимими для індексатора.

Розпізнавання розділу[ред. | ред. код]

Деякі пошукові системи включають розпізнавання розділу, визначають основні частини документа до токенізації. Не всі документи в корпусі читаються як правильно написана книга, розділена на розділи та сторінки. Деякі документи в Інтернеті, такі як новинні розсилки[ru] та корпоративні звіти, містять помилковий зміст та бічні блоки, в яких немає основного матеріалу. Наприклад, ця стаття відображає в лівому меню посилання на інші веб-сторінки. Деякі формати файлів, як HTML або PDF, допускають зміст, який буде відображатися в колонках. Хоча вміст документа представлено на екрані в різних областях, вихідний текст зберігає цю інформацію послідовно. Слова з'являються та індексуються послідовно в початковому тексті, незважаючи на те, що пропозиції та абзаци відображуються в різних частинах монітора. Якщо пошукові системи індексують весь контент як основний зміст документа, то якість індексу та пошуку може погіршитися. Відзначають дві основні проблеми:

  • Вміст в різних розділах розглядають як пов'язане з індексом, хоча насправді це не так.
  • Додатковий вміст «бічної панелі» включено в індекс, але воно не сприяє реальній значущості документа, тому індекс заповнений поганим поданням про документ.

Для аналізу розділу може знадобитися, щоб пошукова система реалізувала логіку візуалізації кожного документа, тобто абстрактне уявлення самого документа, і потім проіндексувала уявлення замість документа. Наприклад, іноді для виведення контенту на сторінку в Інтернеті використовують JavaScript. Якщо пошукова система «не бачить» JavaScript, то індексація сторінок відбувається некоректно, оскільки частина контенту не індексується. Враховуючи, що деякі пошукові системи не турбуються про проблеми візуалізації, веб-розробники намагаються не представляти контент через JavaScript або використовують тег NoScript[ru], щоб переконатися, що веб-сторінка індексується належним чином[30]. Водночас цей факт можна використати, щоб «змусити» Індексатор пошукової системи «бачити» різний прихований зміст.

Індексація метатегів[ред. | ред. код]

Певні документи часто містять вбудовані метадані, такі як автор, ключові слова, опис і мову. В HTML-сторінках метатеги містять ключові слова, які також включені в індекс. У більш ранніх технологіях пошуку в Інтернеті індексувалися ключові слова в метатегах для прямого індексу, а повний текст документа не аналізувався. У той час ще не було повнотекстової індексації, і апаратне забезпечення комп'ютера було не в змозі підтримувати таку технологію. Мова розмітки HTML спочатку включала підтримку метатегів для того, щоб правильно та легко індексувати, без використання токенізації[31].

У процесі розвитку Інтернету в 1990-х, багато корпорацій створило корпоративні веб-сайти. Ключові слова, які використовуються для опису веб-сторінок, стали більше орієнтуватися на маркетинг та розроблялися, щоб керувати продажами, розміщуючи веб-сторінку в початок сторінки результатів пошуку для певних пошукових запитів. Факт, що ці ключові слова були визначені суб'єктивно, призводив до спаму. Це змусило пошукові системи прийняти повнотекстову індексацію. Розробники пошукової системи могли помістити багато «маркетингових ключових слів» у зміст веб-сторінки до того, як наповнять її цікавою та корисною інформацією. Однак метою проектування веб-сайтів було залучення клієнтів, тому розробники були зацікавлені в тому, щоб включити більше корисного контенту на сайт, аби зберегти відвідувачів[ru]. В цьому сенсі повнотекстова індексація була більш об'єктивною та збільшила якість результатів пошукової системи, що сприяло дослідженням технологій повнотекстової індексації.

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

Див. також[ред. | ред. код]

Примітки[ред. | ред. код]

Посилання[ред. | ред. код]

Джерела[ред. | ред. код]

Література[ред. | ред. код]

  • 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.