Инвертированный индекс

Более точное определение

«Инвертированный индекс (или как его еще называют "список словопозиций") - это такая структура данных, в которой для каждого термина во всех имеющихся коллекциях документов указаны все коллекции документов в которых этот термин встречается.

Рассмотрим пример

Предположим что у нас есть коллекция из 5 текстов:

1. t0 = «Самого главного глазами не увидишь»;
2. Не все увидишь глазами»;
   
3. t2 = «Главного не увидишь только глазами»;
4. t3 = «Сложно увидеть главное»;
5. t4 = «Увидеть глазами главное».

Для того что бы построить инвертированный список для данной коллекции документов, нам необходимо:

1. Составить таблицу последовательности терминов в каждом документе в сопровождении соответствующих идентификаторов документов;
2. Отсортировать данную таблицу по алфавиту (по возрастанию);
3. Сгруппировать одинаковые термины по слову и отделить идентификаторы документов;
4. Упорядочить идентификаторы документов (в нашем случаи подойдет любой вариант сортировки).

Немного таблиц

Идентификаторы и термины
Термины	docID
самого	0
главного	0
глазами	0
не	0
увидишь	0
не	1
все	1
увидишь	1
глазами	1
главного	2
не	2
увидишь	2
только	2
глазами	2
сложно	3
увидеть	3
главное	3
увидеть	4
глазами	4
главное	4

Сортировка  по алфавиту
Термины	docID
все	1
главного	0
главного	2
главное	3
главное	4
глазами	0
глазами	1
глазами	2
глазами	4
не	0
не	1
не	2
самого	0
сложно	3
только	2
увидеть	3
увидеть	4
увидишь	0
увидишь	1
увидишь	2

Результат
Термины	docID
все	1
главного	0	2
главное	3	4
глазами	0	1	2	3
не	0	1	2
самого	0
сложно	3
только	2
увидеть	3	4
увидишь	0	1	2

Все просто) Помимо идентификаторов терминов, поисковые системы так же хранят и другие данные используемые при ранжировании. Подробнее об этом читайте в следующих постах.