| Home page | Каталоги и базы данных |
|
Научные и технические библиотеки |
|
УДК 025.4.036 Вершинин М.И. Совершенствование формата Качество инвертированного файла как основы эффективного поиска в базах данных в формате CDS/ISIS несомненно играет важную, если не основную роль. Перечислим наиболее существенные, на наш взгляд, факторы, влияющие на эффективность применения инвертированных файлов. Представительность. Очевидно, что чем больше информации в инвертированном файле, тем он полезнее для поиска. Значительную роль также играют правильное структурирование и сегментация данных. Размер. Чем меньше размер, тем легче ориентироваться в словаре БД и тем быстрее идет поиск. Данный фактор противоречит предыдущему. Семантическая определенность. Повышается релевантность результатов поиска. Мультибазовость. Обеспечивается одновременный поиск в нескольких БД, что сокращает время поиска. Гибкость. Возможность пополнения инвертированного файла при расширении связанных с ним БД без полной реорганизации. Каким же образом можно влиять на эти факторы? Самое очевидное решение для повышения представительности - полное инвертирование всех полей БД. Разумеется, это не выход. Остается другое - выбор информативных полей и подполей и их инвертирование. Но и после этого в инвертированном файле немало "мусора" - неинформативной лексики (НИЛ). Это не только так называемые стоп-слова, но и термины не несущие информации в контексте той или иной базы данных. Например, термин археологический в контексте проблемно-ориентированной базы данных (ПОБД) по археологии не является информативным. Можно привести много подобных примеров. Следовательно, необходимо каким-либо образом "фильтровать" инвертированный файл при его создании. Аналогичные функции выполняет файл стоп-слов в ППП CDS/ISIS, но ограничения, накладываемые на его состав (длина терминов не выше 10, количество терминов не больше 799), сужают возможности использования данного файла. Поэтому необходимо формировать специальный файл НИЛ без подобных ограничений, применение которого позволит сократить объем инвертированного файла и повысить релевантность поиска. Семантическую неопределенность можно устранить, определив источник ее происхождения. Как правило, это совпадение терминов или аббревиатур из различных полей. Таким образом, разделение информации из различных полей позволяет во многом решить данную проблему. Использование индексов для разделения терминов, тем более в режиме ручного ввода, на наш взгляд, не является естественным решением. Формат инвертированного файла ППП CDS/ISIS не предусматривает каких-либо ссылок на совокупность БД, поэтому поиск по совокупности БД происходит последовательно. Объединение нескольких БД в одну часто непродуктивно как с точки зрения организации поиска, так и с точки зрения их сопровождения. Разделение терминов по длине на короткие (не длиннее 10 символов) и длинные (до 30 символов) также снижает эффективность инвертированного файла. Кроме того, сбалансированное двоичное дерево, используемое в инвертированном файле, с одной стороны, конечно, элегантная модель, но, с другой - t-арное несбалансированное дерево без листьев дает на порядок меньше веток и более приспособлено для инкрементального поиска, формирование его идет намного быстрее. Анализ состава создаваемых CD/ISIS инвертированных файлов с помощью разработанных средств
[1] показал неэффективность применения дисковой памяти. Так, для некоторых БД, созданных в БАН, неиспользуемые фрагменты инвертированного файла занимают до 30% всего инвертированного файла (файл*.ifp). В инвертированном файле ППП CDS/ISIS каждая ссылка (64 бита) содержит [2]:
Мы использовали следующий формат ссылки (64 бита):
Возникает закономерный вопрос: а где же идентификатор поля? В нашем формате инвертированный файл представляет собой набор инвертированных файлов полей совокупности как ПОБД, так и БД общего назначения. Инвертированный файл поля имеет простую структуру:
Файл перекрестных ссылок содержит смещения терминов в инвертированном файле по 4 байта на каждый термин. Для ускоренного позиционирования в инвертированном файле используется t-арное дерево без листьев. Очевидно, что для применения такого формата необходимы свои программные средства. Для создания и обслуживания инвертированных файлов предложенного формата разработана программа VerInvert. За несколько этапов она реализует следующую технологию создания инвертированных файлов:
Разъясним подробнее суть выполняемых действий. При создании локальных и общих инвертированных файлов пользователь должен выполнить ряд этапов, некоторые из них необязательные. Завершить работу и начать ее можно с любого этапа. По умолчанию загружается последний конфигурационный файл, который использовался в предыдущем сеансе. Настройка (обязательный этап). На этом этапе следует связать ЛБД в единую систему. Ссылки на ЛБД можно добавлять в список по мере перехода к новым БД. Загружая те или иные конфигурационные файлы, можно работать с разными сочетаниями ЛБД. Создание файла НИЛ (необязательный этап). На этом этапе пользователь на основе анализа частотного файла создает файл НИЛ, который в дальнейшем применяется при отбраковывании лексических единиц (ЛЕ) в процессе создания инвертированного файла. В общем случае каждое поле может иметь свой файл НИЛ, но можно создать единый файл НИЛ для всех ЛБД и всех полей. Для этого необходимо загрузить существующий файл НИЛ в таблицу НИЛ, скопировать неинформативные ЛЕ из частотной таблицы в таблицу НИЛ и сохранить ее в файле с тем же именем. В итоге файл может получиться громоздким, что заметно замедлит процесс инвертирования. На самом деле инвертирование может происходить и без файла НИЛ. Например, поля интеллектуальной ответственности, как правило, не содержат НИЛ. Как известно [3], наименее информативны высокочастотные и низкочастотные термины. Ранжирование всех терминов в частотной таблице помогает выделить неинформативные и таким образом создать файл НИЛ для последующего применения. В интерактивном режиме пользователь просматривает частотную таблицу и отмечает неинформативную, на его взгляд, лексику. Затем он переносит выделенные термины в таблицу НИЛ. Программа позволяет выводить таблицу, ранжированную по частоте, упорядоченную по алфавиту и по длине терминов. Последнее помогает собрать вместе короткие термины и определить их информативность. Следует отметить, что программа содержит предопределенный набор НИЛ, включающий большую часть стоп-слов и разделенный на классы: местоимения, предлоги, союзы, артикли. Любой из этих классов может быть добавлен к таблице НИЛ без внесения в частотную таблицу. Кроме того, можно установить ограничение на длину вносимых в частотную таблицу терминов. По умолчанию, термины, состоящие менее чем из 3 символов, не заносятся в частотную таблицу. Таким образом значительный массив НИЛ уже на первоначальном этапе не включается в частотную таблицу. Еще на этапе формирования таблицы НИЛ ощутимо проявляется преимущество раздельного формирования инвертированных файлов по отдельным полям, так как можно для любого поля сформировать свою таблицу НИЛ и использовать ее при инвертировании данного поля. Очевидно, что существуют термины, информативные в контексте одного поля и неинформативные в контексте другого, и разделение инвертированных файлов позволяет в одном случае не утратить полезную информацию, а в другом - исключить лишнюю. Учитывая то, что объем БД может быть весьма значителен, существует возможность создания частотной таблицы на основе выборки из БД. Выборка может быть как линейной, когда анализируется отрезок БД, так и случайной, когда заданный процент записей БД выбирается из заданного отрезка БД с помощью программного эмулятора равномерно распределенной случайной величины. Конечно, при случайном выборе происходит потеря части низкочастотной лексики, но высокочастотная сохраняется практически полностью. Здесь, естественно, необходим компромисс между желанием ускорить формирование частотной таблицы и необходимостью сделать ее максимально представительной. Опыт эксплуатации ПОБД в БАН показал, что для таких БД низкочастотная лексика по большей части неинформативна, поэтому можно ограничиться анализом высокочастотной. Теперь о том, каким образом происходит сегментация (разделение на ЛЕ) полей и подполей БД. Сначала необходимо задать набор разделителей ЛЕ. Это обычно знаки препинания, пробел и специальные символы (.,;!?-=+:<>[]{}()'''\/ и прямой пробел). Разумеется, для разных полей список может меняться - любые символы могут быть как добавлены в него, так и удалены. Пустой список приведет к тому, что подполе будет интерпретироваться как одна ЛЕ. Следовательно, если необходимо анализировать подполе целиком, то в набор не включается ни один символ. Например, подполе инициалов или их расшифровки лучше рассматривать как единое целое, если, конечно, не интересует частотность того или иного имени или отчества. Чтобы не потерять составные фамилии, при сегментации соответствующего поля необходимо исключать символы пробел и дефис и т.п. Конечно, это должен делать грамотный человек, ориентирующийся в специфике конкретной БД. Создав таблицу НИЛ и сохранив ее в обычном текстовом файле, можно переходить к основному этапу - созданию инвертированных файлов. Источниками формирования инвертированного файла являются выбранное поле ЛБД, файл НИЛ (необязательно) и условия, накладываемые на процесс сегментации поля, совпадающие с условиями формирования соответствующих полю частотной таблицы и таблицы НИЛ. Кроме того, можно задать объединение подполей и префиксы для каждого подполя. В этом случае подполе рассматривается как одна ЛЕ. Например, можно объединить через подполе фамилии и подполе инициалов, либо снабдить подполе префиксом. При этом одно и то же подполе можно отразить в инвертированном файле разными способами: как с помощью префиксов и объединения, так и путем задания разных наборов разделителей. Одно и то же поле инвертировать несколько раз с разными условиями, при этом вся информация накапливается в одном и том же файле. Инвертировать можно как одно поле, так и одновременно группу полей, если они имеют общую таблицу НИЛ. Процесс инвертирования происходит следующим образом:
Для придания большей гибкости процессу создания и улучшения качества инвертированных файлов программа VerInvert включает возможность их корректировки. С ее помощью можно удалить неактуальные ссылки и создать дополнительные термины с теми же ссылками или заменить термины, не меняя ссылок. Можно также создать новый термин и приписать ему ссылки нескольких других, что уменьшает объем инвертированного файла и облегчает работу с ним. Например, это можно сделать при нормализации разных форм какого-либо термина или для объединения ссылок по какому-либо другому признаку. Можно заменить разноалфавитные начертания одного и того же термина на кириллическое или латинское представление и объединить все ссылки. В качестве термина может выступать фамилия, наименование издания, любой многоязычный термин. В процессе корректировки можно одновременно просматривать поля или записи, на которые есть ссылки, что облегчает принятие правильного решения. Программа VerInvert позволяет автоматически исправить ошибку во всех записях базы данных, на которые ссылается термин инвертированного файла. В дальнейшем предполагается объединить эту функцию с функцией синтаксического контроля и, следовательно, автоматически устранять грамматические ошибки в ЛБД. Завершив корректировку, необходимо обновить инвертированный файл. При этом в нем произойдут следующие изменения: термины, помеченные как удаляемые, будут удалены из файла; файл будет отсортирован и будут выявлены одинаковые термины, появившиеся в результате корректировки, при этом их ссылки будут объединены. Таким образом, в инвертированном файле могут присутствовать термины, не совпадающие ни с одной ЛЕ в исходном файле данных, но отражающие семантику группы ссылок, связанных с разными ЛЕ. Это приблизительно соответствует процессу индексирования ЛБД, но проходит этот процесс непосредственно в инвертированном файле. Следующий этап - слияние инвертированных файлов ЛБД в единую систему общих инвертированных файлов - заключается в добавлении к общим инвертированным файлам инвертированных файлов ЛБД. Процесс автоматизирован, и пользователь должен только пометить в списке инвертированных файлов сливаемые файлы и запустить процесс слияния. Поиск в БД с использованием инвертированного файла такого формата обеспечивает поисковый интерфейс БАН - программа VerSearch. Программы VerInvert и VerSearch разработаны в среде Delphi 4, опробованы на БД, содержащих от 3 тыс. до 400 тыс. записей. Программы работают в среде Windows 9x с любыми БД в формате CDS/ISIS и требуют наличия только файла документов и таблицы определения полей. Дальнейшее развитие комплекса программ предполагает включение функций автоматического индексирования с привлечением уже имеющейся методики [4].
СПИСОК ЛИТЕРАТУРЫ 1. Вершинин М.И. Расширенный интерфейс ввода и редактирования данных для CDS/ISIS //Библиотеки и ассоциации в меняющемся мире: новые технологии и новые формы сотрудничества: Материалы конф./ 5-я юбил. междунар. конф. "Крым - 98", Судак, Автоном. Респ. Крым, Украина, 6-14 июня 1998. М., 1998. Т. 2. С. 588-589. |
|
Copyright © 1995-2001 ГПНТБ России |