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

Массивов в ИПС

 

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

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

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

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

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

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

 

Адрес документа	Ключевые слова
D1	S2, S3
D2	S1, S3, S5
D3	S1, S3
D4	S3, S6
D5	S3, S4, S5
D6	S3, S4
D7	S1, S2, S4, S5
D8	S1, S3
D9	S2, S3, S4, S5

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

 

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

 

 

Слова	Адреса документов
S1	D2, D3, 07, D8
S2	D1, 02, D3, D4, D5, D6, D8,D9
S3	D1, D2, D3. D4, D5, Dб, 08,D9
S4	D5, D6, D7, D8, D9
S5	D2, D5, D7, D9
S6	D4

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

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

Автор	Вид документа	Дата издания	Название
Правительство РФ	Постановление №1172	7.11.96	Об утверждении Положения о порядке контроля за вывозом из РФ товаров и технологий двойного назначения, экспорт которых контролируется
Центральный банк РФ	Приказ № 02-368	27.09.97	О введении в действие Инструк­ции № 49 «0 порядке регистра­ции кредитных организаций и лицензирования банковской деятельности»
ГТКРФ	Письмо № 01-14/1104	1.10.96	0 применении Положения о таможенном перевозчике

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

 

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