Продвижение сайтов, которое работает
Обратный звонок

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

Инвертированный индекс  это одна из простейших и основополагающих структур данных. Она используется для построения списка релевантных документов при поиске.

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

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

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

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

  • t0 = «Самого главного глазами не увидишь»;
  • t1 = «Не все увидишь глазами»;
  • t2 = «Главного не увидишь только глазами»;
  • t3 = «Сложно увидеть главное»;
  • 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    

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