Организация инвертированных индексов

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

По бинарному поисковому методу поиск в последовательно организованном файле проводится при первичном определении среднего элемента и сравнивании его с искомым элементом. Если средний элемент в файле не является искомым термином, то „верхняя" или „нижняя" часть файла игнорируется в зависимости от соотношения среднего и искомого элементов. То же повторяется с оставшейся половиной, и таким образом та часть, в которой проводится поиск, каждый раз уменьшается вдвое. При данной системе поиска файл, содержащий 65000 элементов, при поиске подвергнется не более чем 16 сравнениям, в то время как при прямом последовательном сканировании потребуется 65000 сравнений.

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

Типичный файл инвертированных индексов, приведенный выше, обычно включает в себя номер доступа каждой записи, которая содержит термин, а также имя поля, в котором содержится данный термин и его положение в этом поле (например, пятое слово в поле „название" пятьсот первой записи).

При использовании инвертированного индексирования система вначале выдает цифру - количество записей, содержащих искомый термин (так называемые hits или postings). Номера доступа тех записей, которые удовлетворяют данному поисковому запросу, заносятся в отдельный пронумерованный список, называемый set (набор).

Sets создаются для каждого искомого термина или запроса. Номера доступа в наборе используются для быстрого доступа к записям, расположенным в линейном файле, когда пользователь дает системе команду просмотреть найденные записи.