20.6. структуры информационно-поисковых массивов в ипс

20.6. структуры информационно-поисковых массивов в ипс

Центральной частью каждой ИПС является информационно-поисковый массив (ИПМ), который может быть организован различными способами. В ДИПС ИПМ подразделяется на две части: сами документы или их копии и ПОД с адресами номерами документов в поисковом массиве. Поиск осуществляется по второй части ИПМ.

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

В ИПС используют две принципиальные схемы информационного массива — прямую и инверсную.

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

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

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

Рис. 20.2. Прямая схема организации информационного массива

Инверсный способ организации поискового массива предусматривает создание инвертированной матрицы, в которой и происходит поиск (ее называют инвертированным матричным индексом) (см. рис. 20.3).

Рис. 20.3. Инверсная схема организации информационного массива

Простой индекс можно представить как бинарное отношение I(v,a), в котором «v» слово, взятое из текста, «а» список адресов документов, содержащих это слово. Каждый кортеж инвертированного индекса называется инвертированным списком.

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

Документальный поиск сводится к просмотру соответствующих записей файла инвертированного матричного индекса/Таким образом, отпадает необходимость в последовательном просмотре всего информационного массива и значительно сокращается время поиска.

При индексировании (инвертировании) текста документа возможны различные варианты.

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

При полном инвертировании все слова документа, в том числе и шумовые (незначащие), включаются в индекс.

В случае неполного инвертирования в индекс включаются все значимые слова текста документов, а незначимые удаляются. В качестве незначимых слов выступают союзы, предлоги и прочие служебные части речи.

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

При решении задач организации эффективного доступа к данным индексы больших размеров преобразуют в иерархию индексов небольших размеров. Один из способов реализации таких индексных структур состоит в использовании В-деревьев, листьями которых являются ссылки на документы.

Списки адресов {а} в ИПС значительно больше по размерам, чем в СУБД. Поэтому для организации эффективного доступа к данным индекс может храниться, например, в трех разных файлах, связанных указателями. Первый файл — индексный файл состоит из полей: слово; указатели пересылок. Второй файл пересылок, состоит из полей: номер документа; адрес документа. Третий файл содержит тексты документов.

В инвертированных матричных индексах может также храниться дополнительная информация. Например, данные о месте вхождения термина, статистические данные о термине, слова, связанные парадигматическими отношениями с данным термином, и др.

Информация о месте вхождения термина это — зона, абзац, предложение и номер слова в предложении. Эти данные могут указываться для каждого вхождения термина в документ и для каждого документа, содержащего данный термин. Данные о положении слова используются для реализации некоторых видов контекстного поиска.

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

Если в индексе присутствуют указатели на синонимы, то при обработке запроса происходит автоматическое связывание инвертированных списков всех терминов, синонимичных указанному в запросе. Это значительно повышает полноту поиска.

В дополнение к прямой и инвертированной схемам в ИПС используется так называемый атрибутный индекс. Он позволяет хранить данные о документе, не содержащиеся непосредственно в его тексте. Например, имя автора, дату создания, наименование темы и другие фактические данные. Данные могут автоматически извлекаться из документа либо вноситься вручную при вводе документа в систему. Структура атрибутного индекса соответствует стандарту представления структурированной информации — т.е. это таблица с заранее заданными полями. На рис. 20.4 представлен пример организации поискового файла — атрибутного индекса, в котором все документы характеризуются одним и тем же набором реквизитов-полей: автор документа, вид документа и его номер, дата издания, название. Поиск по атрибутному индексу осуществляется средствами обработки запросов СУБД — выдаются только те документы, значения атрибутов которых удовлетворяют условиям запроса.

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

Рис. 20.4. Пример атрибутного индекса

В современных ИПС реализованы как атрибутное индексирование, так и инвертированное матричное. Это позволяет, например, отыскать все документы, созданные за определенный период времени, и при этом содержащие конкретную фразу. Первая часть поиска — по дате выполняется с помощью атрибутного индекса, а вторая часть по заданному набору слов — на основе инвертированного матричного индекса. Разрешается и обратная последовательность отбора. Так, если пользователь из всей базы предварительно получил список документов, содержащих сведения о льготах по уплате подоходного налога, он может сузить этот список, ограничившись документами, принятыми каким-либо органом, или за определенный период (дату).