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

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

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

Визначення мови

Якщо пошукова система підтримує декілька мов, то першим кроком під час токенізації буде визначення мови кожного документа, оскільки багато таких кроків залежать від цього (наприклад, Стемінг та визначення частини мови). Визначення мови — це процес, при якому комп'ютерна програма намагається автоматично визначити чи класифікувати мову документа. Автоматичне розпізнавання мови є предметом досліджень в обробці природної мови^[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^[ru] — 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).
• Установка кольору шрифту слів таким самим, як колір фону, що робить невидимими слова для людини при перегляді документа, але слова залишаються видимими для індексатора.

Розпізнавання розділу

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

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

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

Індексація метатегів

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

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

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

Див. також

• Вертикальний пошук^[ru]
• Індекс (бази даних)
• Отримання інформації
• Семантичне павутиння

Примітки

1. Clarke,Cormack, 1995.
2. Rice,Bailey.
3. Jacobs,Finkelstein,Salesin, 2006.
4. Lee.
5. Браун"--, 1996.
6. 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. 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.

Посилання

• James Lee (Ноябрь 09, 2006). Software Learns to Tag Photos. MIT Technology Review (англ.). с. 1—2. Процитовано 2013-12-3.
• Stephen V. Rice, Stephen M. Bailey (Май 2004). Searching for Sounds Comparisonics Searching for Sounds (англ.). © 2013 Comparisonics Corporation.
• С. Брин, Л. Пейдж. The Anatomy of a Large-Scale Hypertextual Web Search Engine. Архів оригіналу за 30 березня 2012. Процитовано 2013-12-3.
• MySQL 5.1 Reference Manual. mysql.com (англ.). © Oracle and/or its affiliates 1997, 2013. Процитовано 24 жовтня 2013.
• Vreda Pieterse and Paul E. Black (22 Февраль 2011). "trie" in Dictionary of Algorithms and Data Structures. http://www.nist.gov (англ.).
• Vreda Pieterse and Paul E. Black (14 Серпня 2008). "inverted index" in Dictionary of Algorithms and Data Structures. http://www.nist.gov U.S. National Institute of Standards and Technology (англ.).
• Thorsten Brants, Alex Franz (Сентябрь 19, 2006). Web 1T 5-gram Version 1. http://catalog.ldc.upenn.edu/ (англ.).
• The Unicode Standard - Frequently Asked Questions (англ.). Грудень 2006.
• Файли яких форматів індексує Google?. http://www.seowords.ru. © 2008-2013 Немного о seo. 22 Февраль 2010. Процитовано 24 листопада 2013.
• rznasa (2010-09-21 22:42). Які типи файлів можуть індексувати Google и Yandex. http://excalibur.com.ua. © 2009-2010 Портал о создании и продвижении сайтов :: EXCALIBUR. Архів оригіналу за 4 грудня 2013. Процитовано 24 листопада 2013.
• ghosty (25 березня 2003). Програми індексації та пошуку файлів / Desktop Search. Процитовано 2013-12-1.
• Максим Захаров (11 Май 2010). Індексування архівів. Процитовано 2013-12-1.
• Служба індексування windows. 20 серпня 2013. Процитовано 2013-12-1.
• Чи підтримує Google Site Search індексування контента JavaScript на моїх сторінках?. ©2013 Google. Архів оригіналу за 10 грудня 2013. Процитовано 2013-12-1.

Література

• Charles L. A. Clarke , Gordon V. Cormack. Dynamic Inverted Indexes for a Distributed Full-Text Retrieval System : [англ.] // MultiText Pro ject Technical Report MT-95-01. — University of Waterloo, Waterloo, Ontario N2L 3G1, Canada, 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 : [англ.]. — NY, USA : ACM New York, 1990. — С. 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.^{[недоступне посилання з липня 2019]}
• Caxton Croxford Foster. Information retrieval: information storage and retrieval using AVL trees : [англ.] // ACM '65 Proceedings of the 1965 20th national conference. — NY, USA, 1965. — С. 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. — № 6. — С. 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 : [англ.]. — Stanford University, 1994.
• Robert W.P. Luk, Wai Lam. Efficient in-memory extensible inverted file : [англ.] // Information Systems. — 2007. — № 32 (5). — С. 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. — № 5449. — С. 357-368. — ISBN 978-3-642-00382-0.^{[недоступне посилання з червня 2019]}
• 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.

Портал «Програмування»