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

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

Фактори злиття

Як дані входять до індексу? Як слова та підлеглі функції додаються до індексу під час текстового корпусного обходу? І чи можуть кілька пошукових роботів працювати асинхронно? Пошуковий робот повинен спочатку перевірити, оновлює він старий зміст або додає новий. Злиття індексу^[⇨] пошукової системи подібно SQL Merge та іншим алгоритмам злиття[5].

Методи зберігання

Як зберігати індексовані дані? Тобто визначають вид інформації, що зберігається: стиснутий або відфільтрований.

Розмір індексу

Скільки необхідно пам'яті комп'ютера, аби підтримувати індекс.

Швидкість пошуку

Як швидко можна знайти слово в інвертованому індексі. Важливим для інформатики є порівняння швидкості знаходження запису в структурі даних та швидкості оновлення/видалення індексу.

Зберігання

Як зберігається індекс протягом тривалого часу[6].

Відмовостійкість

Для пошукової служби важливо бути надійною. Запитання відмовостійкості містять проблему ушкодження індексу, визначаючи, чи можна окремо розглядати некоректні дані, пов'язані з поганими апаратними засобами, секціюванням та схемами на основі геш-функцій та композитного секціювання[7], а також реплікації.

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

Суфіксне дерево

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

Інвертований індекс

Сховище списку входжень кожного критерію пошуку[10], зазвичай у формі геш-таблиць або бінарного дерева[11][12].

Індекс цитування

Сховище цитат або гіперпосилань між документами для підтримки аналізу цитування, предмет бібліометрії.

N-грами

Сховище послідовностей довжин, даних для підтримки інших типів пошуку або аналізу тексту[13].

Матриця термів документа

Використовується в латентно-семантичному аналізі (ЛСА), зберігає входження слів у документах двовимірної розрідженої матриці.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Неоднозначність меж слова

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

Неоднозначність мови

Для більш точного ранжування документів пошукові системи можуть враховувати додаткову інформацію про слово, наприклад, до якої мови або частини мови воно відноситься. Ці методи залежать від мови, оскільки синтаксис між мовами різниться. При токенізації деякі пошукові системи намагаються автоматично визначити мову документа.

Різні формати файлів

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

Помилки пам'яті

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

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

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

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

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

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

• HTML
• ASCII текстові файли (текстові документи без спеціального форматування)
• Adobe-формат електронних документів (PDF)
• PostScript (PS)
• LaTeX
• Usenet формат новинних інтернет-серверів
• XML і похідні, наприклад, RSS
• SGML
• Формати мультимедійних метаданих, як ID3
• Microsoft Word
• Microsoft Excel
• Microsoft PowerPoint
• IBM Lotus Notes

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

• ZIP — формат стиснення даних та архівації файлів
• RAR — формат стиснення даних та умовно-безкоштовна програма-архіватор
• CAB — Microsoft Windows Cabinet File
• Gzip — формат стисненого файлу gzip
• BZIP — формат стисненого файлу bzip
• Tape ARchive (TAR), стиснений файл Unix
• TAR.Z, TAR.GZ or TAR.BZ2 — Unix-архів файлів стиснутих в Compress, GZIP або BZIP2

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

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

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

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

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

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

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

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