автореферат диссертации по документальной информации, 05.25.05, диссертация на тему:Методы построения архивной малтигипертекстовой информационно-поисковой системы

РГВ од

1 1 НОЯ Í3S3

НАЦЮНАЛЬНА АКАДЕМ1Я НАУК УКРАТНИ Нацюмальна б1блютека УкраТни ¡m. 'B.I. Вернадського

На правах рукопису

СОХАНЬ Олег Васипьович

Методи побудови apxiBHoï малтиппертекстовсм ¡нформашйно-пошуковоУ системи

Спец1альн'|сть 05.25.05 - Системи ¡нформаци та обладнання apxiBiB, б1блютек i музеТо

Автореферат дисертац,1Т

на здобуття наукового ступбня кандидата техннних наук

КиТв 1996

Дисертац1ею с рукопис.

Роботу виконано в Нац1ональн1й б!бл1отец1 Укра'жи )м. 8.1. Вернадского.

Науков1 кер|'вники: доктор темйчних наук, професор

Гриша С. М. доктор 1сторичних наук

ДубровЫа Л. А.

Офадйш опокенти: доктор техшчних наук, професор

Кор)нний О. О. кандидат техннних наук

Костенко Л. й.

Пров!дна орган!зац1я: (нститут проблем ресстрацГШформацП' НАН УкраТни

Захист в1дбудеться 1996 р. о годит на

засщпнж спец'1ал!зованоТ ради Д 01.31.01 по захисту дисертаЫй на здобуття наукового ступени доктора наук (кандидата наук) в Нац1ональн!й б1бл!отец1 УкраТни ¡м. В.1. Вернадського за адресою: 252039, КиТв-39, проспект 40-р1ччя Жовтня, 3.

3 дисертацшю можна ознайошггися в Нац1ональн1й б!блютец1 УкраТни ¡м. 8.1. Вернадського (м. КиТв).

Автореферат розюлано

• (0_ • ЗеМекЯ^1996 р.

Вчвний секретар спец!ал°130ваноТ ради, кандидат ексномЫних наук

Актуалыпсть теми: Розвиток теорп шформацн, поява новнх ппертекстових шформацШннх систем 1 технолопй, масове використання аудюв^зуальних комп'югерних систем значною М1рою сприяло перегляду концепщй подання шформаци.

Орнпналып точки зору на гшертекст I г!пермед1а, сформульоваш В. Бушем1 в 1945 рощ, I вщповщно - Т. Нельсоном2 в 1964 рош, були занадто широкими та' всеосяжними. У вщповщносп до них в ппертекстгсшй техиолрги асощативш зв'язкн повинш охоплювати всю шформашю, до яко! будь-хто холв би мати доступ. При цьому користувачам шформаци повинна надаватися достатня свобода вибору навтгащйних маршрутов у представленому матер1ал1. В противному раэ1 - дат будуть эоргашзоваш в традицШному лшйному. видь що являе собою попередньо встановлену послщошисть елементгь гнформаци, а не наб1р факт1в 1 ¡дей, у яшй користувзч зможе достпджувати вар1анти, ям становлять для нього певнийЧйтерес.

Але э точки зору реально! практики, проблема достдження гшермформафйного простору д визначення в ньому яйй!гащйних марщрутпв була покладена на автор1в (розробнимв) ппертексту. Усталенню цього тюгляду виршальним чином сгфияла думка про те, що нав1гац1Иний маршрут мстжна розглядати як результат певного шформащйного пошукуабо мяожини пошумв.з наступннм особливим аранжувайням цих результате, в Якому ииб{р форми представления мформацп залежитъ вщ технологи н сприймання деякою групою користуВач1в. Деяк! спецгалкти в галуз1 ппертекстових технолопй ствержують, що досладйнки часттше

1 Bush V. As May Think? // Atlantic Monthly. - 1945. Vol. 176, № 1. P. 101-109.

2 Нельсон Т. Информационные системы будущего // Информационный поиск: Сб. материалов. -М.: Воениздат, 1970: С. 217-228.

бажають, щоб Jx направляли, не даючи вщхилятися занадго далеко вщ обраного 11aairauiИного маршруту3. Але при цьому вшшкають таю проблеми: .

1. Розробиикн ппертекстових документе повинш прийматн до уваги CTyninb знания предметно! ra/iysi i власного контролю за викорнстанням шформацн.

2. Гипертекст, що е зручним для одте! групп користувач1в, може бути незручним для iituioi або матн опосередковану структуру i бути за якимись ознаками однаково незручним для ecix груп користувач1в.

3. Класичний ппертекст дае певну множину ¡нформащйних траекторШ, але суттево тдкреслитн, що ця множима траекторШ е шдмножиною П0ВН01 множини TpaeKTopifl. До того ж остання мае експоненц1альну потужшсгь.

Inuii спещалюти виступають проги жорсткого визначення iiaeirauiflHHX маршрупв. Наприклад, М. Бернстайн стверджуе, що "ефектиишсть побудови ппертексту залеже вщ напруженого стану *пж систематизащею i величезною кшькштю шформаци, м1ж передбачувашстю i невизначешстю"4.

Без переб1льшення можна стверджувати, що останне десятир1ччя розвитку ceiTOBOi шформатики проходить шд знаком розвнтку глобальних комп'ютерних мереж Internet i найбшьш популярною ресурсу Word-Wide Web (WWW), який базуеться на технологи г1пертекст1в. Активна робота з ппертекс;говими

3 Grice R.A. Linking to hypertext: A hypercritical analysis // Proceedings of the 37lh International Technical Communication Conference (May 1990), P. P I 53-RT54. Washington, DC: Society for Technical Communication.

4 Bernstein M. DeepW intermingled hypertext: The navigation problem reconsidered // Technical Communication. - 1991. - Vol. 38, № 1. - P. 41-47, Washington, DC: Society for Technical Communication.

технологиями в глобальних мережах Internet приводить до 1х удосконалення як засобу подання шформаци, ochobhi напрямн розвитку яких сформульоваш М.М. Субботшим (Роайський державний науково-техшчний центр гшершформащйних технологий)5. Це, у свою чергу, внсувае перед спещалктами в галуз'г гшертекстових технолопй грунтовш завдання, В1Д вдалого розв'язання яких залежить як1сть швндкого i ефективного пощуку та доступу до шформаци в глобальних мережах, що зробнть миттевнм анонсування нових ушкалышх шформацМних pecypcia.

Об'скт цосл1иження; Об'ектом дослвдження е процеси задоволення жформащйних потреб користувач1в-дослщиик1в, як» опрацьовують велик! маснви apxiBHoi та б1блютечно! шформаци в ход1 наукових розробок.

Ппершформащйт технологи в цьому вщношенш виступають ефективним засобом, ям дозволяють розробку таких технолопй обробки шформаци, в яких науков1 абстракци, нав1ть найвнщого р1вня складнрсп, можливо трансформувати в реально вщчутт та зримо сприйнятлив!" образи, що дають можлиш'стъ користувачу комп'ютера при певннх умовах визначити нов» низки ¡манентного значения.

Предмет посл'ижашя: Предметом дослшження е методи оптимального та адаптивного в1зуалыгого подання даних у apxiBno-б1бл10течних ¡нформащйно-пошукових системах (1ПС) та реал|'зац1Я швидкого i сфектнвного пошуку потр»бно» шформаци як безпосередньо даних, так i конкретних факта, що стосуються даних.

5 Субботин ММ. Эвристический эффект гипертекста // НТИ. Сер. 1. - 1994. -№4. С. 9-14.

Завдапня досл!дження полягае у створенш комп'ютерннх технолопй штелектуа-шзованого шформашйного забезпечення користувач1в-дослщцик»в, а саме введения елементчв поточного управлшня структурою гипертексту до складу эасобге концевого користувача.

Конкретно завдання-дцсертацн полягали в тому.щаб:.'

1. Обгрунтовати ефектнвшсть застосування гшер-шформащйннхтсхнолопйв арх^вннх i б!блютечних шформацШно-пошукових системах.

2. Виконати ацал13 класичних ппертекстових технолопй та визначнти наявшсть целого ряду шформащйних проблем, пов'язаних 3 цими технологиями, як1 не позбавлеш недолтв.

3. Довести . актуадьшсть розробки ново! технолог!! оптимального та адаптивного гтертекстового подання шформацп.

4. Запропоновувати альтернативну (вщмшну вщ класично!) концепщю гшертекстового подання шформаци з можливютю управления структурою ппертексту з боку користувача та виконати дослщження П властивостей.

5. Застосувати певну технолопю структуризаци даних для динам1чно! побудови ппертекстових структур великих обсяпв шформаци.

6. Побудовати модел1 динам!чного синтезу гшер-шформащйного простору та розробити алгоритми адаптивно! оргашзацп ¡ндексно! шфраструктури, яка не погребуе прямо! вщповщносп "шдекс - запит".

7. Розробити арх!тектуру арх1вно! жформафйно-пошуково! системи, в ямй передбачено компонент» самооргашзацп даних.

Метою пнсерташйпо! роботн е тдсилення штелектуаль-ного потенщалу дослщншав, як1 працюготь ¡з значними маснвами арх1вно-б1бл10течиих шформашйних ресурав, що входять до Нацюналыюго архивного фонду Укранш, а також перехщ вщ звичиого пошуку необхщно! шформацц до стратепчного використання шформащйних ресурао.

Методи посл!дження: Теор1я систем, сб'ектпо-ор1ентована методолопя, дискретна оптим1зац!я, теор1я баз даних та теор!я штучного нггелекту.

1. Обгрунтовано ефектившсть застосування сучасних ппертекстових технолопй в арх!вшй 1 б!блютечшй справ! та виявлен! фактори !х обмеженосп.

2. Запропоновано концепщю малтигшертекстового подання шформаци в шформащйно-пошукових системах та вперше виконано дослщжеиня п властивостей.

3. Застосовано асощативну технолопю структуризаци даних для динам!чно! побудови ппертекстопих структур великих обсяпв шформацц6.

4. Побудовано модел1 динамичного синтезу пперпростору.

5. Розроблено оригшальш алгоритми адаптивно! оргашзацп шдекЫв, як! не потребують прямо! вщповщнос-п "¡ндекс - запит", для пщгримки процест динашчио! побудови гшертекст!в.

6. Розроблено архггектуру архивно! шформащИно-лошуково! системн на основ! малтигшертекстово! технолог!!, в якШ вперше передбачено компонента самооргашзацп даних.

^ Таким чином, досягаеться ефектишисть наявност! щло! множини гтертекспв у розпорядженш користувача, тобто е пщстави говорнти про малтигшертекст (миожишшй ппергскст).

Практична uinniCTü результат^, одержаиих у робоп, полягае в тому, що зазначеш ¡де! були використаш при розробц1 алгорнтм1чного та програмного забезпечення штелектуал^зованого штерфейсу користувача в рамках проекту "Розробка програмного забсзпечення шдтримки Иацюнально! apxiBiiof шформащйно! системн (HAIC) - юиентська частина", що впроваджено в дослщну експлуатацш в 1нститут1 укражсько! археографы та джерелознавства im. М.С. Грушевського HAH УкраГни. Передбачаеться використання здобутих наукових результат)в при впровадженш в промислову експлуатащю проекту "Нацюнальна apxisiia шформащйна система (НА1С)" в установах Головного apxipnoro управления при Кабшетт MinicTpiB УкраТни.

РеалЬаи!я результатов роботи виконувалась у рамках программ 8.4.2-92 "Архшна та рукописна украинка" Державного комитету Укранщ з питгань. науки та техиолопй за темою "Apxinna та рукописна украппка: ».Нацюнальна зведена система документально! шформацн" (напрям Нацюнально! apxieiiol шформащйно! системн), а також у рамках проекту створення комп'ютерного довщника "Археоб1бл1обаза" як складово! "ApxiBnoi та рукописно! украинки" та ш.

Аиробаи!я результат^ роботн: OcuoBui положения та результата дослщження були викладеш на Мшнародному ceMinapi "Проблеми повернення культурних цшностей в Украшу" (Чершпв, 1994); Всеукрашсьюй нарад! "Актуальш проблеми розвитку apxißnoi справи" (Кшв, 1995); М1жнародшй нарад1 "Гипертекстов! технолог!! i мджнародш комп'ютерш мереж! Internet" (Шблютека конгресу США, Вашингтон, США, 1995); ГМжнародному пауковому семшар! "Археоб!блюбаза (АББ): проблеми загально-

доступносп украшських арх1вних матср!ал1в" (Украшський науко-вий шститут Гарвардського ушверситету, Кембридж, США, 1995). Иа захнст внносяться так] положения:

1. На основ1 анал1зу класичних ппертекстових технолог^ пропонуеться концепщя малтиппертекстЬвого подання шформац».

2. ЗапропонованиП метод асощативно! оргашзаци сховища даних для малтигшертекстово! технологи.

3. Побудоваш модел1 оцшки реактивное™ Малтигшертекстово? шформащйно-пошуково! систеМк.

4. Запропоноваш алгоритми самооргашзацп ¡ндексно! пщтримки малтигшертекстовоГ технолог!!.

5. Розроблена архЬектура асощативно! технологи.

Структура 1 обсяг роботи; Дисертащйна робота складаеться з вступу, чотирьох роздйив, ВИСНОВК1В, перелжу використано! л1тератури 1 додатку.

Перший роздш: Сформульоваш сучасн1 вимоги до використання архтних ¡нформащйних ресурс1в; зроблено огляд проблем шформащйного пошуку в класичних арх1Вно-б1блютечних шформащйно-пошукових системах; обгруитовано ефектившсть застосування сучасних ппертекстових техиолопй в арх1вшй та б1блютечн№ справ1 та виявлеш фактори 1х обмеженос-п: Визначеш та обгрунтоваш завдання дослщження, показано ¡х м1сце у загалыюму кол! питань, що виршують проблсми усунёння обмежень на пошукову нав1гацпо в шформацШному простор г та внршення проблемн релевантное-!! шформащйного пошуку в 1ПС.

Другий розд1л: Зроблений опис основних властивостей класу "малтигшертекст" та показан! основа елементи малтигшертекстово! арх1тектурн; визначено технолопю формування ¡ерарх1чннх сегмеипв (агрега^в). мялтиппертексту; описано

архпектуру асоц1ативно1 бази даних як основн малтш шергекстово! технолог!!; сформульоваш модел! оцшкн ефективност! використання ресурсу пам'ят! ! модел! оцшки ефективност! швидкост! пошуку для асощативно! бази даних (АсБД).

Третей роз/ил: Охарактеризован! проблеми оптимального асоцповання для реал!заци дшшнчно! побудови малтиг!пертекст!в; розроблено модель оргаиьзаци асошатора АсБД; описано алгоритм!чну схему вибору плану побудови асоц!атора; зроблено опис амейств плашв побудови асоц!атора та доведено обгрунтування повноти модел! опису с!мейств; розроблено механ!зм вибору имейства плашв асощатора для розгалуження, ! виконан! оц!нки якосп с!мейств.

Четвертий розд1л: Запропоновано арх!тектуру асоц!атнвно! технологи для реал!зац!! пошуку в штелектуалыйй архшнй! !нформац!йно-пошуков!й систем! з малтиппертекстовим !нтерфейсом користувача; наведено ! описано сукупшсгь компонент асощативно! технолог!!, що дозволяють реал!зувати ефективний пошук та генеращю г!пертекстових структур у вадповадносп до творчо! повед!нки користувача.

ЗМ1СТ РОБОТ11 У першому розд!л! зазначено, що робота пов'язана з проблемами розробки ¡нформац!йно-пошукових систем на основ! ппертекстових технолог!й, в яких закладена певна множина напрям1в використання шформащйних ресурс1в шляхом моделювання процес!в творчого спрнйняття користувача. € очевидним, що гшертекст, який зор!ентований на дедку групу користувач!в шформацп та мае асощативш зв'язки з шшими фрагментами шформацп, позбавляе !х необхщност! користувапня

складшшп ) ив завжди яккними можлнвостямн класнчннх ¡п(})ормац1|11ю-по!1гуковнх систем, 1 не е головною метою створення ппертексту. Але класичш гшертекстов1 технологи - суб'ектнвш, один 1 той самий гипертекст за своею структурою не може однаково добре задовольняти р1зш категорп досл1дниюв-користувач»в шформаци. Щоб Зробитн ппертекстовий матер1ал корисним для доалдника, автор (розробннк) ппертексту •повинен ретельно продумати, як встановитн зв'язкн, що лоеднують рГзш частник даних шформашйного простору, I як корнстувач1 будуть переходнти вщ одше! частики Ыформацн до ¡ншоь Як им чипом розробники мс>жуть знайти правильно ршення? В1ДпОВ1Дь на це питания заложить В1Д ряду фактор!в: природ» лоданого матер!алу,

4

аудитор», для яко1 цей матер1эл подаеться, I мети його внкористаНня. Очевидно, що актуалыисть шформаци можпа збшьшнти, якщо дозволити надати користувачевьдосл'щннку певну свободу вибору, коли аш сам може контролювати спйаб подання Пому шформаци. 1ншнми словами, штерактнвгп зв'язкн форми пперме;иа мають устх тому, що користувач1, вольно викоиуючи • навпащю у ппершформащйному простор!, можуть самост1йно внрццувати, що вони бажають I в якому порядку.

У дрУгому роздЫ, як наслщок проведеного аналпу ¡сиуючих ппертекстових технолопй, було запропоновано концепщю мал шгшертексту (множшшого ппертексту), Що е технолопею в1зуального подання шформаци, яка може збер1гатись у формах, вщмнших В1Д класичних ппертеКст^в. Такий ппертскст мае назву "малтиНпертекст" у тому розумшш, що вш фактично е Ымейством рпних ппертекстш, заснованих на единому джерел1 шформаци. Малтнппертекстовий шдхщ як технолопя -заснований на обробш глибоко об'ектизованого шформащйного

t

простору, а не на обробщ лЫйних блок1в текстових баз даних з подальшнм синтезом з них гшермерело, що суттево р1знить його вщ ¡нших пщходш. Фактично мова йде про малтиппермережу або В1ртуальну ппермережу, яка регенеруеться кожний раз вщповщно до noeeAiiiKH мислення корнстувача у вщповщному k-му Micui об'екгизованого шформащйного простору предметно! галуз!, що складаеться з р1зномаштних шформащйпнх об'екпв.

Отже, малтигшертекст - це сукушисть об'ектизованого шформащйного простору i асощативного навпатора:

МНТ = {I, AsN}, де: I = {ioo,..., ink} - об'ектизований шформащйний npocTip; i„k -п-шформащйний об'ект k-ro класу (наприклад, об'екти, що визначають: Назвн арх!вних шстнтущй класу "Арх1восховище"\ Назви i/або Номери apxiaiinx фон;нв класу "Apxieui фонди"\ Пр13ваще або Назва установи класу "ФондоутаорювачГ\ Apxieinitt опис класу "Облшоео-пошукова документация"-, Пут1вники i/або довщннки класу "Б1блюграф1я" та in.).

AsN — асощативний навнатор, що е об'ектно-opien гованим мехашзмом, якнй дозволяе з об'ектизовано! структури шформащйного масиву синтезувати n-piBHeei ппертекстов1 структури, що побудоваш на вщношеннях входження i наслщування.

Основними типами iiasirauittuHx компоненте у малтигшертекст! слщ вважати:

1. Горизонталыи асоц1аци (асощацп з шшим (фактом на nofli6ni теми). Це так зваш спектральш зв'язки, як1 виз!шають pyx М1Ж компонентами одного р1вня iepapxii гшертекстово! мережь

2. АсоцтцИ' по iepapxii входження. Це асощаци до ннжчестоячого i вшцестоячого об'ектсв.

3. Лсощаци по спор1дненостI структур » спор1днёност! зшченъ. У даному випадку спорщнешсть вживаеться в контексп успадкування.

4. Немарковськ> асощацп. Це асошацн, котр» Ьггерпретукугься в контексп маршруту нав1гацц в гипертекстов^ мережь

5. Асощаци по тдструктурам гтертекстовсп мереж1. Це так зван! асощаци до 'пшшх рубрик поточного факту.

Виходячи з того, що для динамНного генерування малтигшертекстово! мереж! потр1бно иати деяку низку програмних засоб1В, дощльною е асощативна технолопя структурнзацп даних, яка б моделювала процеси предметного середовшца 1 забезпечувала синтез малтиппертекспв.

Асощатнвна база даних перв|'сно була задумана Як платформа для САБЕ-технолопй в частит збереження данях в процесс !х нормал1зацп. Проблема полягае в тому, що для конструювання нормал13ованих даних необхщно спочатку з1брати шформащю про загалып власти восп предметного середовшца. Це можливо зробити лише в процеа комп'ютерио? обробки даних. Таким чином, для • класичноГ технолог^ виникае парадокс, а саме — щоб спроектувати базу, треба мати базу. Класнчна теория нормал1зацн вщносин Е. Кодда декомпозуе опис об'екта на змютовному ргви! г дозволяв вид!лити нов1 в]'дношеиня м!ж даними, що дають можливкть уникнути аномал^, мнпмгзувати дублюйания шформацп » спростити процедури обробки та оновлення. Тобто необхщно у кожному випадку виршити питания про розмодення атрибут (рубрик) або фрагмента змюту у к1лькох вщпошеМнях (релящйних таблицях). Асощативиа база даних виршуе щ протир^ччя шляхом параметрнзаци структурних ршюнь. Гншими словами, шдивщуальш запити дослщника щодо бажано! структурн ппертекстового

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

У цьому випадКу структура шформащйного онису включае таю об'екти: значения; поняття; рубрики; факти; а асощаци.

Для створення асоцтщй вс1 об'ектн ефектнвно кодуються за принципом:

- помяття складаються з рубрик;

- рубрики складаються ¿3 значень;

- факти - це вшношення млькох зпачеиь рубрик.

У загальному випадку структура АсБД складаеться з довщннка рубрик, що внконуе функщю класифкатора рубрик; входження рубрик (ВР), що внконуе функцно воображения структуру складних рубрик; доввдннка значень (ДЗ), що внконуе функшю глобального словника снстемн; асощатора (Ас), що виконуе функщю збережения асощативних зв'язк!в семаитичних фрагмент з рнними нозищямн р1зннх факт)в; довщника мюць (ДМ), що е допом1Ж1юю структурою, нотр1бною для змеишення розм1р1в Ас, яка кожшй пар! "код зв'язку - код рубрики", що в5дображае певний шлях на дерев] рубрик, ставит ¡. у вадповщиють

"КОД М1СЦЯ".

Алгоритм пошуку у АсБД заснований па матпулюванш множинами асощащй. Результатом пошуку по елементу замовлення е множила код1в факт, як1 асоциоються з даним значениям. Иеретнувши згадаш множини для вох елеменпп запигу, отримуемо множину релевантних шформгщйних об'екттв.

Рис. 1. Залежшстъ роэм1ру баэи данпх в'/д потужност! ииожшш об'ект1в для асоцттнвно! БД (81) 1 для тскстово! БД з системою ¡ндекс1в (82) (у килобайтах).

Пом1тоим стае ряд побшних переваг тако( структури, а самё:

- швидка побудова меню вибору значень як при заповнешп опиав, так»при формуванн} запи-пв;

- виконання пошуку на фон} запиту з метою оперативно? перев1рки коректносп останнього;

- розпаралелювання процесу пошуку шляхом видшенпя серверов для р!зних компонента арх!тектури (ДР, Ас, ДЗ або навггь частшш цих елементтв);

- пристосування структури Ас до статнстичних параметр!В потоку заштв;

- ефективне упильнепня шформаци шляхом кодування сл|в та часто вживаних фраз;

- близьккть запропоновано! технологи пошуку до мехашзмж лопчних висновюв, вживаних у системах штучного штелекту, шо

робить можливим подальше нарощулання штелектуальност1 снсгемн.

Треба вщзначити, що оцшивши ефектившсть використання ресурсу пам'ят1 для АсБД у пор!внянш з текстовою базою даних (ТБД), що мае систему ¡ндекЫв, було пом1чено, що при обсяз1 шформац!йних об'ектпв 105 розм!р ТБД почннае стр1мко зростати по вщношеншо до АсБД, а при обсяз1 шформащйних об'ект1в 107 розм1р ТБД майже вчетверо бшьший за АсБД (див. рис. 1).

У третьому роздш! було вир1шеие завдання обгрунтування алгоритму пошуку семейства плашв асошатора з метою побудови оптимально! системи ¡ндекав (плану асощатора). Зокрема:

1. Доведено, що запропонована алгоритм! чна схема не повертаеться до розгляду вар1ант!в, що були проанал!зоваш на попередн!х ¡теращях.

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

3. Числов1 експерименти довели, що для отримапня досить ефективних плашв складшсть пошуку не перевшцуе складносп анал!зу 30 в!дсотк1в шформацп.

Нашгац1я у гшершформацШному простор! в малти-ппертекстов!й технологи супроводжуеться виконанням асощашй, де ефектившсть обслуговування запит!в залежить в!д того, иаскшьки план Ас в!дпов!дае структурам множини г!пертекст!в. МожЛиво визначита два таких крайшх випадки:

1. У план! Ас передбачен! тшьки одииочш асощаци (тальки по одн1й рубриц!). В цьому випадку вс1 множини асоц1аци обробляються як пере хин одиночных асощащй.

2. У плйш Ас шдтримуються bci множини асоц1ац1й для ecix актуал1зованих гщертекспв. У цьону випадку Ас буде мати максималы» розм1ри. При цьому розм1ри Ас диоть як гальмуючий фактор, а привштившсть пщготовки aconiaiiitl як прискорюючнй фактор. Тому завдання полягае в тому, щоб знайти точку оптимального асоцдовання. Опттмзащйна задача:

Мипм1защя середиьостатистичних витрат на асоц1ювання малтиппертекст1в, тобто миим1защя математичного очжування витрат на асоцновання, мае такий вигляд: ¡ч

де: x = lxl),jeJ - вектор piiueHb щодо вибору множишшх aconiauitt, як1 мають пщтримуватися у Ас;

1,(1) - функщя витрат на одне елементарне асощювання у-го типу (J - множина TimiB);

т(х) - функция posMipy Ас залежно вщ плану х;

log,(т(х)) - витрати на пошук у шдека типу бшарного дерева;

(0j - статистична оценка математичного очжування елементарннх

aconiai(ift j-го типу протягом одного циклу експлуатаци системи

(piK або квартал);

Функнно lt(x) можливо визначити за такою формулою:

1С/

де: 6 (0,1) - решения про використання /-го маснва для асошацШ j-го типу.

Треба вщзначити, що:

де: а:/ е (0,1) - характеристика i-ro масиву вщиосно j-го запиту.

Тобто 0 - коли val(i) a val(j), де val(J -множина рубрик, що входять до даного Ас.

Дане обмежения заперечуе використания Ас, якщо вш не е ЫдмшжИною асощащй.

гl|i.xl,VjeJ (*)

Асощац1я може бути використаною, якщо вона передбачена у нлаш Ас.

ы

В ведемо таке обмеження:

ГО

Иг

де: • 1 - якщо г- та рубрика включена в у-ий топ ¡к7; О-в протнлежному випадку.

де: 1 - якщо г-та рубрика включена в «-ту асощащю; О-в протнлежному випадку. Вишовщно можливо записати таке обмеження:

Останне обмеження потр1бно, щоб для кожного запиту був обраний саме повний наб1р асощащй. 3 шшого боку, через обмеження (*) це гарантуе порноту плану Ас х. Повнога полягае в тому, що для кожного запиту множинн ] можливий наб1р П0ВИ01 множили асощащй I.

Як 1 будь-яка непроцедурна система, малтнгшертексг потребуе автоматичного виршення завдання пщтримхи структури. Ця задача мае аналопю з задачею, яка розв'язуеться в SQL-сервер!

' Реально малтигшертекст складаеться ¡э топшв (тбм), як1 будуються динамично на вщмшу вщ класимного ппертексту. Топш - послщовннй линйннй ыдр130к тексгу, який збер1гастъся як одна одиннця або його адреса, що вщнссепа у шдекс: Пайбишш важливою оянакою тошку е те, що вж е лпнйною структурою. Для того, шоб побудувати принципово новий гипертекст з факголопчного материалу шформащйного простору, у пршому випадку ■ иеобхщио з пщмнОжнн рпшга топшв побудувати нов! тотки,

ctocorho оштпзаци плашв заштв. Тобто в системах под]бного типу noipi6en шгелектуалышй агент, яки» би розв'язував ui задач! i зшмав i'x з корнстувача.

Враховуючи надзвичайну комбшаторну складшсть задач], що пнзначена на множит пщмножин, застосування ушверсально! CTpaTerii висношав (метод резолющй) для даного штелектуалыюго агента е неприйнятливим. Тому в даному випадку застосовуеться спец1ал130вана, щлеспрямована стратет на ochobi методу "плок та границь" (branch and bound).

Семейство плашв описуеться як система обмежень на елементи, що можуть входити до складу Ас. Опис амейства плашв можливо подати в вигляд} тако! модели

< I, J, К >,

де: I - обмеження включения, яке несе в co6i елементи асощатора, що обов'язково присутш в плаш асощатора;

J - обмеження виключення, що описуе елементи асощатора,-як1 не будуть включатися в даному riMettCTBi планй;

К - обмеження осуст'льнення, що передбачае опис множин кнщевих асощащй, ям мають обслуговуватися сшльним набором асощацШ.

Якщо до 1ПС асощативного типу иадходить деякий запит на обслуговуЕання, то спочатку в плат Ас визначаються множинш aconiaijii а(1),..., а(п), що покривають далий запит.

Але при цьому виникае аномалия, що neeni елементарш асощаци вщповщно! множинно! асощацп, ям покривають сферу запиту, присутш в пшпй множиншй асощацц. Для усунення цього виникае потреба в осусшльненш виявленнх множинних асощащй i синтезу cni/ruioro набору асощащй b(l), ... b(n) з внключенням псэтору елг'. етарних асощащй (див. рнс. 2).

а(1)

а(2) а(3)

Н (-

Н I-

МЗ)

-II—II

-I

Рис. 2. У творения сильного набору асосцащй.

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

Визначення 1: Семейство називають закритим, якщо не ¡снуе способу його розподшу на ымейства, що мають'краиц сцшки.

Визначення 2: Семейство називають виродженим, якщо, в раз! врахування век обмежень, воно подае единий план асощатору.

Якщо амейство невироджене 1 незакрите, то його можлнво розбити на два пщамейства. Виб1р пщамейства для розпод1лу мае здШснюватися з урахуванням таких ознак:

1) верхньо! оцшки якосп амейства;

2) Нижньо! оцшки якостп амейслва;

3>) м.'фИ р1зноман1тност1, котра визначаеться юлъкктго . вар1ант)в, що мктяться в с!мейств1.

Оцшка верхньо! границ! амейства - це величина, яку не може перевищувати максимальна якють плану даного амейства. Оцшка нижньо! границ! сшейства - це величина, про яку вщомо, що найкращий план с!мейства буде не пршим. Тобто верхня границя -це шеальна (оптимютичпа) оценка, а нижня - песим>стична. В свою

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

Визиачения 3 (Правило ввдкидання амейств): Якщо верхня граииця Ымейства А менша иижиьоГ гранищ сшейства В, то ЫмеИство В треба виключити з розгляду.

Очевидно, оптимютичиу оцшку Ымейства можливо оцшити за таким алгоритмом;

I. Взята розм1р Ас найменшим при даних обмеженнях ciмeйcтв. И. Юлыисть елементарних пошуыв, що визначаються структурою Ас, також взяти найменшим.

Останне мае М1сце в тому випадку, коли пщтримуються множинш асощац11, що ыдповщають кшцевим запитам у вЫх випадках, що не суперечатъ обмеженням амейств.

Але при цьому залишаеться вщкритою задача визначення минмального розм1ру Ас. На думку автора, мш1мальний розм!р асощатора можливо оцшити так:

1. Виконати остаточну базисну декомпозищю.

2. Якщо вона мктить множит» асощаци, то кожну таку асощащю треба розбити на дв1 асощаци, якщо сумарний розм1р отриманих буде меншим за розмф первинно! асощацп.

Це завдання хоч ! мае квадратичну трудом1стк!сть, але враховуючи те, що вона застосовуеться до шдмножин конкретних кшцевих запил в, комбшаторно вона е щлком сприйнятливою.

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

У четвертому роздЫ розроблена асощативна технология формувания запиту в арх1вшй малтиппертскстовМ 1ПС, що наведена на рис. 3.

12

Рис. 3. Асощативна технология побудови арх1вно11ПС.

Направлен» зв'язки м1зк блоками означають:

1 - запит на шформащю узовшшшй мовшй форм);

2 - шдентифжуюч! реквизита запиту, нотр1бш для його воображения в реестри

3 - шформащя для статцстичног© ан&шзу потоку запита за встановлений пром1жок часу;

4 - шформащя для анал1зу вщповщносп поточно! структури БД та структури шдекыв потоку запита, що склався на даний момент;

5 - запит, насичений контекстною шформащею ¡3 позаоб'ектно! бази знань;

5' - запит, конвертований у внутриши коди понять (нщекси);

6 - запит, розкладений у вигляд! потоку елементарних (каношчних) запита для безпосереднього виконання пошукувачем;

7 - замовления на змшу структури збер1гання даних для п б1Льшо! вщповщносп характеристикам потоку запита, що склався на даний момент;

8 - замовлення на змшу структури шдекав для и бтьшо! вщповщносп характеристикам потоку заштв.гцо склався на даний момент;

9 - шформащя, подана у внутршньому кодовому формат! для пошуку;

10 - шформащя, подана у зовшшшх мовних формах для анал1зу запитувачем;

11 - шдексна шформащя для ефективного звуження зони пошуку;

12 - зв1т про пошук у вигляд1 гипертексту, поданий за формою 1 змютом, замовленими запитувачем.

OCHOBHI РЕЗУЛЬТАТ!! РОБОТИ

1. Доведено юнування щлого ряду шформащйних проблем, пов'язаних з класичними ппертекстовнми технолопями, як1 в повшй Mipi не забезпечують дослщник1в релевантною шформацшю через !х фжсовану спрямовашсть на певну трупу корнстува'пв, як! генерують опосередковану структуру запи пв.

2. Запропоновано щею малтиппертексту як технолопю В1зуального подання шформаци, що може збер1гатися у формах, вщмшних В1д класичних ппертекстш. Такнй гшертекст мае назву "малтиг1пертекст" у тому розумшш, що Bin фактично е с1мейством pi3HHX rinepTeKCTiB, заснованих на единому джерел1 шформаци, де користувач може змшювати структуру гипертексту згщно з сво1ми поточними проблемами.

3. Запропоновано метод внутршнього подання даних, що заснований на асощатившй технолог!! структуризащ! даних, для динамично! побудови ппертекстових структур.

4. Розроблеш математичш модели що дозволяють оцшнти ефектившсть динам1члого синтезу ппертекспв на платформ! SQL-серверу, що працюе з базою даних, побудованою за асощативним прннщшом.

5. Доведено можливкть ефективного керування процесом конструювання rinepTeKCTiB шляхом оргашзацп ¡ндексно! ¡нфрасгруктури.

6. Запропоновано алгоритми автоматизованого налагодження ¡ндексно! шфраструктури на структуру запит1в корисгувач1в, що можуть бути покладеш в основу штелектуальннх areHTie -упорядник!в "date warehouse".

OCHOBHI ПОЛОЖЕНИЯ ДИСЕРТАЦ11 ВИКЛАДЕШ В ТАКИХ ПУБЛ1КАЦ1ЯХ:

1. FinepTeKCTOBi снстеми та технолога (Перспектившсть використання !х в арх1вних шформащйних системах) // Нацюнальна apxißiia шформац)йна система "ApxißHa та рукописна украинка" i комп'ютеризащя apxiBno! справи в Украйп: 36. наук, праць. - К., 1996. Вип. 1: 1нформатизащя apxienoi справи в Украпп: Сучасний стан та перспективи. - С. 88-97.

2. Програмно-технолопчт аспекти розбудови Нацюналыю! apxienoi шформащйно! системн (Асощативний пщхщ) // Там само. (У сшвавторств! з Гришою С.М.). - С. 72-87.

3. Нацюнальна apxiena ¡нформащйна система: техшчне завдання // Там само. (У сп1вавторств1 з Гришою С.М., Галяпою A.A., Пийтером М.В., К1ржаевим С.М., Ново-хатським К.С., Захарченко Т.М.). - С. 196-224.

4. Ппертекспш технологи i глобальш мереж! Internet. Чн це' потр1бно сучасному apxiey? // Актуальш проблеми розвитку архивно! справи в УкраГш": Матер ¡ал и наради. Керезень 1995 р. - К., 1996.-С. 135-137.

5. Нацюнальна apxiena шформацШна система: структура даних (Матер1али для обговорення) // Упор. Сохань О.В. - К., 1994.- (У сшвавторств1 з Дубровшою Л. А.). - 46 с.

6. Нацюнальна apxißiia шформащйиа система та Ii Miene у реституцп культурно! спадщини Украши : Матер1алн М^жнародного сем!иару "Проблеми повернення культуриих цшностей в Украшу". Чершпв. Вересень 1994 р. - К., 1996. -С. 270-271.

Сохань О. В. Методы построения архивной малтигилертекстовой информационно-поисковой системы.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.25.05. - "Системы информации и оборудования архивов, библиотек и музеев". Национальная библиотека Украины им. В.И. Вернадского. Киев, 1996.

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

Sokhan O.V. Methods of forming archival multi-hypertext Information searching systems.

Dissertation submitted for the granting of the. academic degree Candidate in Technical Sciences in the specialization 0S.25.Q5. "Information Systems and Equipment of Archives, Libraries and Museums". V.I. Vernadsky National library of Ukraine, Kiev, 1996.

The thesis proposes a concept of rnuiti'hypertext presentation of information and presents research on its characteristics. Associative technology for the structuraliration of data is applied for the dynamic construction of hypertext structures. Studied are models of the dynamic construction of hypérïields. Algorithms for the control of Indexing support of dynamic construction of hypertexts are developed. Also developed is an information searching systems architecture, which is based on multi-hypeitext technology.

Kfltosoei слова: пп$ртекстов> системи i технологи, системи обробки ¡нформацП', ¡нформацшно-лошуков! системи, бази даних, арх!ви та йблютеки.