Использование расширяемого языка разметки xml для обеспечения обмена данными о таксономии животных между группами исследователей


[english version here]

А.И. Иванов, А.К. Багачанова, Н.К. Потапова
Институт биологических проблем криолитозоны СО РАН, г. Якутск
Якутский государственный университет, г. Якутск

Доклад на 2-ой республиканской научно-практической конференции 25 - 28 ноября 2003 г. Тезисы докладов. Часть I. Якутск 2003. /Сборник тезисов докладов. Типография ЯГУ, 2003. УДК 517.9; 681.3; 523.165

Тезисы

Информационные технологии активно используются в разных областях знаний, в частности и в биологии для унификации сведений о животных, растениях, а также для обмена информацией между специалистами. Нами сделана попытка составить базу данных для 300 видов некоторых семейств двукрылых насекомых (Insecta, Diptera).
Рассматривается модель документов (DOM - document object model) по спецификации WorldWide Web Consortium (W3C) xml для представления сведений о систематике и классификации таксонов животных, их типах ареалов и распространении в Якутии, библиографии.
DOM позволяет производить свободный унифицированный обмен информации между исследователями независимо от применяемых в различных местах ССУЗ и СУБД, а также между приложениями в программных комплексах. Другие группы могут расширять модель применительно к своим потребностям, фиксируя изменения в определении типа документа (dtd), DTD в xml является элементом системы для самодокументирования данных.
Побочным недостатком является избыточность описания (ненормализованность в терминах реляционных СУБД) и вытекающие из этого проблемы. Например, в систематике таксонов, авторы и годы описания видов, а также типы их ареалов и пункты географического распространения могут многократно повторяться, как и в самом документе, так и в разных документах, что при использовании неизбежно приведет к разнообразным ошибкам и трудности при поддержании актуальности информации.
Для разрешения этого в документе вместо информации может быть поставлена ссылка на другой документ, документ в спецификации Open eBook Foundation , содержащий библиографическое описание в дублинском ядре (DC - Dublin Core) и запись в стандарте межмашинного обмена записями us marc (unimarc, rusmarc).
В рассматриваемой программной реализации редактора документов с описанием таксонов есть возможность создания таких документов, а также необходимых для работы документов OpenEbook - пакетов описания электронных книг и их текстов в формате xhtml.
Предполагается, что с развитием технологии XPATH, xslt, uiml будет эффективно происходить поиск и обмен таксономической информацией в интернет.

e-mail: a.k.bag@ibpc.ysn.ru, n.k.potapova@ibpc.ysn.ru,  ibpc[NO_SPAM]2003@yahoo.com 

Введение

Использование расширяемого языка разметки xml для обеспечения обмена данными о таксономии животных между группами исследователей
А.И. Иванов, А.К. Багачанова, Н.К. Потапова
Институт биологических проблем криолитозоны СО РАН, г. Якутск
Якутский государственный университет, г. Якутск
Сегодня состояние окружающей нас среды настолько изменилось, что это вызывает обеспокоенность не только биологов, экологов, но и людей наблюдательных и не равнодушных к природе. Эта обеспокоенность подвигла биологов всего мира на создание банка данных о видах, которые существуют в настоящее время. Но это касается не только простого перечня видов, но и тех основных биологических параметров, и тех механизмов адаптации, которые позволяют успешно существовать виду в той или иной природной зоне.
Цель нашей работы – обобщить накопленные нами данные о двукрылых насекомых. Отряд двукрылые насекомые один из самых богатых по числу видов и насчитывает примерно 80 тысяч видов в мире, а в Якутии – 680 (Винокуров, 2002). Эта цифра не отражает реального богатства фауны и составляет приблизительно только 30% от ожидаемого его состава. Это связано со слабой его изученностью в Якутии. Нашей задачей настоящего времени стало обобщение собственных и литературных сведений для видов трех семейств Syrphidae (журчалки), Chloropidae (злаковые мухи), Culucidae (кровососущие комары). 
Для составления сводки имеющегося материала, который отражает разные параметры жизни этих насекомых трудно использовать традиционные способы публикации. Для решения поставленных задач нами использованы современные информационные технологии, которые активно используются в разных областях знаний, в частности и в биологии для унификации сведений о животных, растениях, а также для обмена информацией между специалистами. 

Влияние абиатических факторов на развитие двукрылых

В сообщении рассматривается модель документов DOM (document object model) по спецификации World Wide Web Consortium (W3C) xml для представления сведений о систематике и классификации животных, их типах ареалов и распространении в Якутии, библиографии.

Таксономия

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

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

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

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

Обзор существующих технологий

В докладе рабочей группы по базам данных таксономии Alex Chapman [1] сказано, что “реально компьютерная таксономия берет начало в 70-х с проекта DELTA…DELTA – устаревший стандарт, требующий обновления. В смежных областях можно найти примеры, что может быть сделано. Например, STAR (Structure Text Archive descriptive standard) в кристаллографии.”

Позднее в России группа разработчиков ZooInt сделала попытку по интеграции разрозненных РСУБД, в результате чего и была получена данная система.

В статье разработчиков российской программы ZOOInt говорится что: “Разработка машинных банков данных по зоологии наталкивается на специфические трудности, связанные с огромным числом таксонов животных (более миллиона) и характерной, пожалуй, только для зоологии чрезвычайно разветвленной многоуровневой иерархией таксонов (более 40 таксономических категорий или рангов), постоянно изменяющейся как на низших, так и на самых высоких уровнях. Многие научные названия имеют синонимы, число которых у некоторых таксонов достигает десятков. Кроме того, в каждый момент времени для каждой естественной группы таксонов существуют, как правило, параллельно несколько альтернативных систем - несколько разных представлений о числе этих таксонов и о структуре их иерархических связей.”[2]

Так или иначе реализация РСУБД или использование другой модели данных для хранения не должно накладывать ограничения на полноту информации; а именно это и происходит из за нечеткости информации. Можно считать, что банки данных должны быть информационно-поисковыми системами с возможностью нечеткого (fuzzy) поиска.

Создание в последние годы целого класса связанных с xml программных средств позволяет говорить о возникновении XML-технологии, которая содержит в себе полноценные возможности представления и манипулирования данными, могущие уже сами по себе быть вполнеконкурентоспособными возможностям реляционных систем управления базами данных. Кроме того, в современных версиях вовсю используется поддержка xml технологий.

Технологии xml сейчас достаточно развиты, и с xml документами сейчас можно производить манипуляции с использованием DOM, XPATH, XSLT, SAX и разных других языков и технологий.

Ron Gilmour опубликовал первое определение документа описания вида животных (XML DTD)[3].

Есть также другие специальные определения [4] [5].

В настоящее время международная рабочая группа таксономических баз данных ведет работы по созданию XDELTA, языке разметки, основанного на xml [6]

В Республике Саха есть опыт создания БД «Кадастр интродуцентов Якутии», «Декоративные растения Якутии», с использованием программ Microsoft Access и Microsoft Visual FoxPro (Егоров, Данилова, 2003, Ильин и др., 2003). В данном сообщении приводятся сведения о БД «Биоразнообразие модельных семейств двукрылых насекомых (Insecta, Diptera) Центральной Якутии» составленные с помощью xml технологий.
Информационная структура БД «Биоразнообразие модельных семейств двукрылых насекомых (Insecta, Diptera) Центральной Якутии» следующая:
А. Систематика и фауна двукрылых
Таксономическое положение двукрылых - содержит латинские и русские названия семейств, родов, видов, подвидов и латинские названия синонимов, составленные на основе современных таксономических сводок;
Б. Распространение видов
Включает сведения о местах их нахождения в Якутии, России и за ее пределами;
В. Зоогеографическое положение видов и типы их ареалов
Г. Экологические сведения о двукрылых насекомых
1. Фенология двукрылых - указаны сроки развития преимагинальных фаз и имаго;
2. Биотопическая приуроченность двукрылых;
Трофические связи преимагинальных фаз и имаго;

DTD

DTD текст

Хранение информации

xml документы могут храниться как в ординарных файловых системах, IFS хранилищах, так и в базах данных, как Oracle. Для выборки кортежей могут применяться как XPATH выражения, так и собственные средства СУБД, например, SQL расширения или через различные API (ldap, isapi/nsapi, web DAV).

Sleepycat выпустила также в этом году новую версию Db xml (раньше называемой Berkeley DB)–native-xml менеджер для хранения и извлечения xml – данных, надстраиваемый над Berkeley db, представляющий собой библиотеки c++ и java для доступа посредством XPath 1.0, фактически хранилище данных.

В большинстве unix систем Berkeley DB широко применяется в различныхслужбах, например, NIS, реестре и использует хешированные файлы (с произвольной записью в любое место). Очевидно, следует ожидать увеличения предложения сетевых устройств для хранения xml документов.

SleepyCat занимается продажей лицензий на встраивание СУБД в операционные системы и сетевое оборудование, его главные партнеры Sun и Cicso.

Часто в реализациях используют собственные бинарные представления xml документов для ускорения поиска и для уменьшения объема занимаемого пространства, из которого затем при запросе документа идет его восстановление. Xml документ в сравнении с текстом более структурирован, так что бинарное представление дает известные преимущества в скорости поиска перед контекстным поиском в полнотекстовой БД.

В частности, в случае полнотекстовой БД требуется перестроение всего индекса для всех документов; в случае xml индекс может обновляться динамически.

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

На рисунке внизу показано основное окно программы.

Элементы управления редактора xml документов

  1. поиск документа
  2. список найденных документов
  3. окно сообщений (ошибки, поиск) 
  4. дерево элементов xml документа
  5. атрибуты выделенного элемента
  6. открытые документы
  7. окно редактора
  8. страницы редактора, предварительного просмотра и формы ввода
  9. строка статуса

Редактирование документов

На следующих рисунках показан один из способов визуального редактирования xml документа. Программа реализует режим two-way editing, как в окне кода, так и с помощью дерева элементов, палитры новых элементов и редактора атрибутов.

Выделить редактируемый элемент. В окне атрибутов внести изменения, если требуется.

 

В окне сообщений отображается список найденных ошибок в документе. xml документ должен быть валидным, в отличие от, например, html, поэтому  нужно своевременно делать исправления. Добавляемый элемент, в частности, может иметь список обязательных атрибутов, что и отображается.

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

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

Внешние хранилища документов

В качестве примера настройки программы показан диалог добавления ldap соединения в дерево документов (дерево видно слева, внизу под корзиной- элементы ftp sites и ldap sites).

ldap и ftp соединения введены в дерево документов для удобства, обычно вполне можно использовать сетевые соединения windows для совместной работы над документами, используя, например, webDAV соединение (расширение контроля версий (cvs) HTTP/1.1).

Поиск информации

Для обеспечения поиска используется построение неполного инвертированного индекса, а использование XPATH в программе ограничено операциями, применяемыми в редких случаях.

Во время проектирования программы были поставлены следующие цели, которые нужно было достичь:

  • Быстрое время отклика поиска,
  • Обеспечение возможности обслуживания большого числа запросов в момент пиковой нагрузки и, как следствие, нетребовательность к ресурсам – с учетом последующей многопользовательской работы библиотеки функций,
  • Обеспечение возможно более простого интерфейса пользователя в сочетании с возможностью поиска как по двум - трем, так и по большему числу атрибутов,
  • Достижение приемлемого времени построения индексов

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

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

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

Если в случае точного поиска широко используются древовидные структуры и хэш-индексы, а учет грамматических форм и синонимов осуществляется с помощью расширения выборки, то уже для «поиска по подстроке» можно использовать суффиксные деревья.

Поиск на неточное равенство фактически приводит к full-scan, поэтому он сознательно не реализован в программе.

Ожидается что словарь будет из за специальности терминов весьма ограничен, поэтому реализован алгоритм последовательного перебора терминов словаря.

Впоследствии можно будет реализовать:

  • частичный поиск с использованием хэш-функции на множестве слов, инвариантной относительно определенного класса ошибок наподобие известной функции soundex или
  • метод расширения выборки (spell-checking), заключающийся в умышленной модификации поисковых терминов с учетом наиболее вероятных изменений.
  • метод n-грамм, метод триад, также являющийся методом расширения выборки путем выделения подстрок и нахождения слов с общими подстроками.

Кроме того, есть модификация метода n-грамм Вилбура-Ховайко, которую сами авторы называют методом триад (используются 3-граммы или «триады»), была разработана для минимизации числа обращений к словарю. Авторы метода предложили строить полное множество терминов, имеющих общие триады с ключевыми словами запроса, но затем – с помощью весового «коэффициента похожести» терминов словаря и запроса – на этапе чтения инвертированных списков «отсекать» малоперспективные варианты (для которых коэффициент похожести будет меньше заданного порогового значения). При этом какие-то термины могут быть пропущены; налицо компромисс между эффективностью поиска и его полнотой.

  • Trie-деревья.

В отличии от обычных сбалансированных деревьев, в trie-дереве все строки, имеющие общее начало, располагаются в одном поддереве. Каждое ребро помечено некоторой строкой. Терминальным вершинам («листьям») соответствуют слова списка.
Чтобы ни одно из слов не было префиксом другого слова (как в случае слов пол и половик), в конец каждого слова добавляется специальный символ $, отсутствующий в алфавите. Обычно trie-деревья используются для поиска по подстроке (в них заносятся все суффиксы или префиксы терминов). Тем не менее, trie-деревья можно использовать и для нечеткого поиска путем вычисления «расстояние редактирования между словами» - количество операций редактирования (замены, удаления, вставки, транспозиции символов), путем которых можно привести одно слово к другому.

На рисунке внизу показано окно программы построителя инвертированного списка xml документа.

Поиск информации с использованием Boyer-Moore (BM) и регулярных выражений (URE)

Так как XPath не имеет средств для модификации документа, в программе реализованы два варианта поиска и замены вхождений выражений в документах- как в открытых, так и рекурсивно в каталогах по типам документов. На рисунке внизу показано диалоговое окно поиска. Диалоговое окно замены выглядит примерно также.

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

На рисунке вверху зеленой линией внизу показано окно результатов поиска.

Передача информации

В Windows 2003 реализуется поддержка xml [7] для ввода форм; также как в ОС Apple, пакете Microsoft Office xml применяется как для хранения документов.

Получаемые данные могут быть трансформированы с использованием, например, XSLT.

Библиография

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

Кроме того, библиографические данные были использованы для тестирования производительности написанных библиотек подпрограмм поиска и построения индекса; так как имеются большие объемы библиографических записей в сравнении с таксономией.

Существующие форматы с небольшими вариациями являются разработанным Библиотекой Конгресса США в конце пятидесятых годов ленточном формате. Вкратце, файл данных библиографии состоит из непрерывно следующих друг за другом записей, разделенных ленточными маркерами записей. Каждая запись состоит из заголовка, называемого Лидером, таблицы смещений полей, называемой Справочником, и собственно данных - называемых полями и подполями.

Например, поле Автор имеет код 100 и включает подполя 1-Тип ФИО, a-ФИО, b- династический номер, c- титул, d- дата, e- роль лиц, q- полное имя, u- место работы. Некоторые поля, как и подполя, повторяются, длины полей и применяемые коды и сокращения также описаны в стандартах.

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

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

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

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

Из практики известно, что, например, в такой высокопроизводительной СУБД Btrieve (впоследствии Pervasive), работающей под управлением ОС Novell Netware перестроение индекса для одного поля в каталоге с 100 тыс. записей занимает более одного рабочего дня (ПО Mark компании Информсистема http://www.infromsystema.ru/ ). В случае SQL серверов время, требуемое для построения индекса еще выше.

Сравнение времен отклика

В качестве эксперимента было написано приложение, строящее индекс (инвертированный список) для около 10 полей в каталогах 3 тыс. записей и 100 тыс. записей, работающее через драйвер BDE с РСУБД Paradox, SQL серверами Interbase 5 и Oracle 8.

Время на создание инвертированного списка в случае небольшого количества записей составило на Pentium-II порядка нескольких или десятков минут, в случае нормального размера в 100 тыс. записей дождаться времени окончания процедуры в течение приемлемого интервала времени не удалось.

Поиск в полученных дал время отклика- в случае Paradox около секунды, и от минуты до нескольких десятков минут (в зависимости от сложности запроса)- в случае Oracle 8. В случае Interbase 5 сколько-нибудь приемлемого времени отклика получить не удалось (при поиске по нескольким полям) по причине того, что оптимизатор SQL запросов составлял неверные планы, в которых запрос скатывался к перебору записей (full-scan table), а сооружение планов вручную было бессмысленным - так как и в случае использования индексов время отклика было неудовлетворительным.

Причина этого достаточно ясна - если в случае поиска по одному полю СУБД производит только чтение, то в случае использования нескольких условий согласно Озкарахану (“Системы баз данных”) пересечение множеств наборов данных (оператор AND в реляционной алгебре) не может быть выполнено только операциями чтения, а создаются дополнительные временные кортежи данных.

Между тем операции записи имеют высокую стоимость выполнения, причем в случае многопользовательских РСУБД эти затраты за счет поддержки транзакции (для обеспечения возможности отката транзакция в случае ошибок) еще более высоки.

В ходе тестов также не обошлось без дополнительной настройки сервера Oracle, так как данные процедуры часто вызывали переполнение журналов отката. По умолчанию в рамках одной транзакции Oracle не позволяет вставить более 5 - 10 тыс. даже небольших записей, это самая, пожалуй, известная особенность SQL серверов с журналом транзакций, как DB2 и Oracle. Вторая особенность- это лавинообразное блокирование записей, последующее блокирование таблицы и отказ сервера. Поэтому поиск часто встречающихся атрибутов изданий скорее всего приводит к отказу в запросе, так как сервер баз данных не может создать временные наборы данных большой длины.

Interbase, в отличие от других промышленных РСУБД, использует запатентованную еще DEC архитектуру многоверсионных записей. Она была разработана в русле технологий для военных приложений, в частности, на ней реализована система информационной поддержки и автоматического выбора целей и наведения в групповом танковом бою с поддержкой с воздуха. Преимущество не только в отсутствии журналов для обеспечения транзакций, но и в том, что каждой транзакции создается как бы своя “виртуальная” база данных, временной слепок на момент начала транзакции; в результате достигается отсутствие блокировок. Однако производительность Interbase недостаточна. Чтобы обойти это с использованием промышленных решений, возможно было попробовать использовать сетевые СУБД, как Cache, Jasmine, построенные на основе MUMPS технологии, или dbm (ldap серверы), либо Z серверы (стандарт Z39.50), однако затраты на их эксплуатацию или слишком велики, либо достигаемое время отклика можно ожидать хотя и лучшее, но незначительно.

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

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

От построения b- дерева в словаре слов было решено отказаться, так как предполагалось, что словарь будет относительно небольшим, и эффекта от использования b- деревьев не будет. Это верно при допущении, что большинство записей сделано на одном - двум или трем языкам.

Построение инвертированного списка делается в три прохода.

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

Структура записи в словаре слов такая:

  • Начальное смещение в таблице полей
  • Конечное смещение в таблице полей
  • Длина слова (1..0xFF)
  • Слово

Как видно, размер записи может быть различным за счет строки с дескриптором длины (так называемые Macintosh string или ShortString)

Затем строится список указателей на поля и подполя. Этот список связывает слова в словаре с таблицей указателей на записи:

  • Номер поля (1..999) и подполя для формата MARC (USMARC ограничивает количество полей числом 999, количество подполей (теоретически) равно 256. Для XML документа это имя элемента (тега).
  • Начальное смещение в таблице указателей на записи
  • Конечное смещение в таблице указателей на записи

Затем заполняются пока еще не заполненные значения смещения в таблице словаря и формируется таблица ссылок на записи.

Описанные три таблицы составляют пирамиду:

                         комбинация слов/полей

                              /       \

                          Слово 1 .. Слово N

                           /             \

                    Поле1..Поле N  ...  Поле1..Поле L

                        /        \

                Запись1..Зап.R ...Запись1..Зап.D

                    /

              Записи

Эффективность

Простая структура данных позволяет осуществлять быстрый поиск. Поиск делается также в несколько этапов.

Сначала в таблице словаря ищется наиболее длинное слово. Предполагается, что в языке короткие слова используются чаще, а длинные- реже. Если это верно, достигается дополнительный выигрыш. По начальному и конечному смещению в таблице записей ищутся ссылки на поле (подполе), в котором это слово ищется. Получается список указателей на записи.

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

Из этого становится ясно, почему делается оценка по длине слова на первом этапе.

Так как число записей в худшем случае не будет превышать заданного предела для шумовых слов, вполне возможно нахождение в памяти процесса списка ссылок объемом в 60 тыс записей, или около 200 килобайт или в этих пределах без страничных сбоев.

После того, как поиск завершен, найденный кортеж дополнительно усекается до заданного предела (сейчас действует ограничение в 4096 записей), так как пользователь все равно не будет просматривать их все, а скорее всего уточнит параметры поиска.

Релизация

Реализован многопоточный ISAPI модуль для web сервера IIS. Записи хранятся в формате USMarc, инвертированный список находятся в трех файлах. Необходимости подгружать в память инвертированный список нет. Это позволяет легко подключать различные базы поиска.

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

Например, при количестве записей 80 тыс. размер файлов инвертированного списка- словарь- 3М, указатель полей- 2М, указатель записей- 8М (при количестве индексов 10).

В память подгружаются шаблоны страниц поиска, которые содержат псевдотеги такого вида:

<!--record ndx=ozon -->

<#100a|<font class=author>%s</font>>

<!--record-->

Для построения индекса, импорта данных (“Библиотека-4”, Озон, Колибри, Болеро, fotune, xml) созданы многопоточные приложения, внешний вид некоторых представлен ниже. Время построения инвертированного списка в среднем составляет 5 -7 минут.

Увеличение объемов

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

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

Поиск информации в интернет

Пример использования поиска записей видов показан на рисунке внизу и доступен по адресу: http://ensen.sitc.ru/taxon/

Для ввода слов можно использовать знак "*" для подстановки любых символов.

Поиск осуществляется динамически загружаемым в адресное пространство веб сервера модулем xmlndx (ISAPI/NSAPI). Модуль использует файлы инвертированного списка, создаваемые программой.

Для отображения в теле HTML документа модуль xmlndx ищет .xsl файл (документ xml, описывающий XSLT преобразование документа в html)

Также можно просматривать xml документ as is.

Офлайновая версия

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


Аналогичная программа была также написана для выполнения запросов для обеспечения динамического контента, записываемого на компакт диск и передаваемого третьим лицам.

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

Библиографический поиск, онлайновая и оффлайновая версии: http://ensen.sitc.ru/ldbndx/etc/

Ссылки

Программу можно скачать:

http://wap.commandus.com/download/apoosetup.exe

Этот документ также доступен по адресу:

http://ensen.sitc.ru/reports/itnoe.htm


[1] Alex Chapman “Directions for the structure of taxonomic descriptive data”, TAXONOMIC DATABASES WORKING GROUP 17th Annual Meeting 9 – 11 November, 2001 Friday, 9th http://www.tdwg.org/2001meet/AlexChapman.htm http://www.tdwg.org/2001meet/mins2001.htm

[2]Smirnov I.S., Lobanov A.L., Alimov A.F., Dianov M.B., Medvedev S.G. Development of information retrieval systems for zoology // ADBIS'96. Proceedings of the Third International Workshop on Advances in Databases and Information Systems. Moscow - September 10-13, 1996. Extended Abstracts. 1996. Vol. 2. P. 60-63.

 

[3]Ron Gilmour Gymnosperms of the Southeastern US - A Premature Sample of the Use of XML in Systematic Botany, Bioinformatics 2000, 16(4): 406-407.

 

[4]SysTax - a Database System for Systematics and Taxonomy http://www.biologie.uni-ulm.de/systax/documentation/interfaces/import_dtd.html

 

[5] 7) DTD for biological collection information, European Natural History Specimen Information Network (ENHSIN) Anton Güntsch, Botanic Garden and Botanical Museum Berlin-Dahlem http://www.bgbm.org/BioDivInf/Projects/ENHSIN/PilotCollectionDTD.htm

[6]Deriving an XML based format for Taxonomic Information DELTA (DEscription Language for TAxonomy) , International Taxonomic Databases Working Group http://biodiversity.uno.edu/delta/www/standard.htm

 

[7] http://msdn.microsoft.com/msdnmag/issues/03/09/InfoPath/default.aspx

Turn User Input into XML with Custom Forms Using Office InfoPath 2003 Aaron Skonnard


Скачать

http://wap.commandus.com/download/apoosetup.exe  

DTD
Онлайновый поиск http://ensen.sitc.ru/taxon/ 
Оффлайновая программа просмотра zip 1.23M
Другие отчеты и доклады
http://ensen.sitc.ru/ldbndx/etc/ 
is2sql e ldap report #1
eBook HRS
Abiturient form  Report #2
shareware
Copyright © Andrei Ivanov, 2003. All rights reserved.

[ Назад ]