Інформаційно-пошукові системи Internet

1. Архітектура сучасних ІПС для WWW
2. Інформаційні ресурси та їх подання в ІПС
3. індекс пошуку
4. Інформаційно-пошукова мова системи
5. інтерфейс системи
6. Висновок
7. література

Користувачам Internet добре відомі назви таких сервісів і інформаційних служб, як Lycos, AltaVista, Yahoo, OpenText, InfoSeek і ін. - без послуг цих систем сьогодні практично не можна знайти що-небудь корисне в море інформаційних ресурсів Мережі. Що собою являють ці сервіси зсередини, як вони влаштовані, чому результат пошуку в терабайтних масивах інформації здійснюється досить швидко і як влаштовано ранжування документів при видачі - все це зазвичай залишається за кадром. Проте без правильного планування стратегії пошуку, знайомства з основними положеннями теорії ІПС (Інформаційно-Пошукових Систем), що нараховує вже двадцятирічну історію, важко ефективно використовувати навіть такі скорострільні сервіси, як AltaVista або Lycos.

Інформаційно-пошукові системи з'явилися на світ досить давно. Теорії і практиці побудови таких систем присвячено безліч статей, основна маса яких припадає на кінець 70-х - початок 80-х років. Серед вітчизняних джерел слід виділити науково-технічний збірник "Науково-технічна інформація. Серія 2", який виходить до сих пір. Російською мовою видана так само і "біблія" по розробці ІПС - "Динамічні бібліотечно-інформаційні системи" Ж. Солтона [ 1 ], В якій розглянуті основні принципи побудови інформаційно-пошукових систем і моделювання процесів їх функціонування. Таким чином, не можна сказати, що з появою Internet і бурхливим входженням його в практику інформаційного забезпечення з'явилося щось принципово нове, чого не було раніше. Якщо бути точним, то ІПС в Internet - це визнання того, що ні ієрархічна модель Gopher, ні гіпертекстова модель World Wide Web ще не вирішують проблему пошуку інформації у великих обсягах різнорідних документів. І на сьогоднішній день немає іншого способу швидкого пошуку даних, крім пошуку за ключовими словами.

При використанні ієрархічної моделі Gopher доводиться досить довго блукати по дереву каталогів, поки не зустрінеш потрібну інформацію. Ці каталоги повинні кимось підтримуватися, і при цьому їх тематичне розбиття має збігатися з інформаційними потребами користувача. З огляду на анархічність Internet і величезна кількість всіляких інтересів у користувачів Мережі, зрозуміло, що комусь може і не пощастити і в мережі не буде каталогу, що відображає конкретну предметну область. Саме з цієї причини для безлічі серверів Gopher, званого GopherSpace була розроблена інформаційно-пошукова програма Veronica (Very Easy Rodent-Oriented Net-wide Index of Computerized Archives).

Аналогічне розвиток подій спостерігається і в World Wide Web. Власне ще в 1988 році в спеціальному випуску журналу "Communication of the ACM" [ 2 ] Серед інших проблем розробки гіпертекстових систем і їх використання Франк халазою назвав в якості першочергового завдання для наступного покоління систем цього типу назвав проблему організації пошуку інформації у великих гіпертекстових мережах. До сих пір багато ідей, висловлені в тій статті, не знайшли ще своєї реалізації. Природно, що система, запропонована Бернерсом-Лі [ 3 ] І отримала таке широке поширення в Internet, повинна була зіткнутися з тими ж проблемами, що і її локальні попередники. Реальне підтвердження цьому було продемонстровано на другий конференції по World Wide Web восени 1994 року, на якій були представлені доповіді про розробку інформаційно-пошукових систем для Web, а система World Wide Web Worm, розроблена Олівером МакБрайном з Університету Колорадо, отримала приз як кращий навігаційне засіб . Слід також зазначити, що все-таки довге життя призначена аж ніяк не чудесним програмами талановитих одинаків, а засобів, що є результатом планового і послідовного руху наукових і виробничих колективів до поставленої мети. Рано чи пізно етап досліджень закінчується, і настає етап експлуатації систем, а це вже зовсім інший рід діяльності. Саме така доля чекала два інших проекти, представлених на тій же конференції: Lycos, підтримуваний компанією Microsoft, і WebCrawler, що став власністю America On-line.

Розробка нових інформаційних систем для Web не завершена. Причому як на стадії написання комерційних систем, так і на стадії досліджень. За минулі два роки знятий тільки верхній шар можливих рішень. Однак багато проблем, які ставить перед розробниками ІПС Internet, не вирішено досі. Саме цією обставиною і викликана поява проектів типу AltaVista компанії Digital [ 4 ], Головною метою якого є розробка програмних засобів інформаційного пошуку для Web і підбір архітектури для інформаційного сервера Web.

Архітектура сучасних ІПС для WWW

Перш ніж описати проблеми побудови інформаційно-пошукових систем Web та шляхи їх вирішення розглянемо типову схему такої системи. У різних публікаціях, присвячених конкретним системам, наприклад [ 5,6 ], Наводяться схеми, які відрізняються один від одного тільки способом застосування конкретних програмних рішень, а не принципом організації різних компонентів системи. Тому розглянемо цю схему на прикладі, взятому з роботи [ 6 ] (Мал.).

Мал. Типова схема інформаційно-пошукової системи.

Client (клієнт) на цій схемі - це програма перегляду конкретного інформаційного ресурсу. Найбільш популярні сьогодні мультипротокольні програми типу Netscape Navigator. Така програма забезпечує перегляд документів WWW, Gopher, Wais, FTP-архівів, поштових списків розсилки і груп новин Usenet. У свою чергу всі ці інформаційні ресурси є об'єктом пошуку інформаційно-пошукової системи.

User interface (призначений для користувача інтерфейс) - це не просто програма перегляду, в разі інформаційно-пошукової системи під цим словосполученням розуміють також спосіб спілкування користувача з пошуковим апаратом: системою формування запитів і переглядів результатів пошуку.

Search engine (пошукова машина) - служить для трансляції запиту на інформаційно-пошуковому мовою (ІПМ), в формальний запит системи, пошуку посилань на інформаційні ресурси Мережі та видачі результатів цього пошуку користувачеві.

Index database (індекс бази даних) - індекс, який є основним масивом даних ІПС і служить для пошуку адреси інформаційного ресурсу. Архітектура індексу влаштована таким чином, щоб пошук відбувався максимально швидко і при цьому можна було б оцінити цінність кожного із знайдених інформаційних ресурсів мережі.

Queries (запити користувача) - зберігаються в його (користувача) особистій базі даних. На налагодження кожного запиту йде досить багато часу, і тому надзвичайно важливо запам'ятовувати запити, на які система дає хороші відповіді.

Index robot (робот-індексіровщік) - служить для сканування Internet і підтримки бази даних індексу в актуальному стані. Ця програма є основним джерелом інформації про стан інформаційних ресурсів мережі.

WWW sites - це весь Internet або точніше - інформаційні ресурси, перегляд яких забезпечується програмами перегляду.

Розглянемо тепер призначення і принципу побудови кожного з цих компонентів більш докладно і визначимо, в чому відмінність даної системи від традиційної ІПС локального типу.

Інформаційні ресурси та їх подання в ІПС

Як видно з малюнка, документальним масивом ІПС Internet є все безліч документів шести основних типів: WWW-сторінки, Gopher-файли, документи Wais, записи архівів FTP, новини Usenet і статті поштових списків розсилки. Все це досить різнорідна інформація, яка представлена ​​у вигляді різних, ніяк неузгоджених один з одним форматів даних: тексти, графічна і аудіоінформація і взагалі все, що є в зазначених сховищах. Природно виникає питання - як інформаційно-пошукова система повинна з усім цим працювати?

У традиційних системах використовується поняття пошукового образу документа - ПІД. Зазвичай, цим терміном позначають щось, що заміняє собою документ і використовується при пошуку замість реального документа. Пошуковий образ є результатом застосування деякої моделі інформаційного масиву документів до реального масиву. Найбільш популярною моделлю є векторна модель [ 7 ], В якій кожному документу приписується список термінів, найбільш адекватно відображають його зміст. Якщо бути більш точним, то документом приписується вектор розмірності, рівний числу термінів, якими можна скористатися при пошуку. При булевої векторної моделі елемент вектора дорівнює 1 або 0, в залежності від наявності або відсутності терміну в ПОД. У більш складних моделях терміни зважуються - елемент вектора рівний не 1 або 0, а деякого числа (вазі), що відбиває відповідність даного терміну документу. Саме остання модель стала найбільш популярною в ІПС Internet [ 4,6,7 ].

Взагалі кажучи, існують і інші моделі опису документів: імовірнісна модель інформаційних потоків та пошуку і модель пошуку в нечітких множинах [ 7 ]. Не вдаючись в подробиці, має сенс звернути увагу на те, що поки тільки лінійна модель застосовується в системах Lycos, WebCrawler, AltaVista, OpenText і AliWeb. Однак ведуться дослідження по застосуванню та інших моделей, результати яких відображені в роботах [ 4,6 ]. Таким чином, перше завдання, яке повинна вирішити ІПС, - це приписування списку ключових слів документу або інформаційного ресурсу. Саме ця процедура і називається індексуванням. Часто, однак, індексуванням називають складання файлу інвертованого списку, в якому кожному терміну індексування ставиться у відповідність список документів в яких він зустрічається. Така процедура є тільки окремим випадком, а точніше, технічним аспектом створення пошукового апарату ІПС. Проблема, пов'язана з індексуванням, полягає в тому, що приписування пошукового образу документа або інформаційного ресурсу спирається на уявлення про словнику, з якого ці терміни вибираються, як про фіксовану сукупності термінів. У традиційних системах існувало розбиття на системи з контрольованим словником і системи з вільним словником. Контрольований словник припускав ведення деякої лексичної бази даних, додавання термінів в яку проводилося адміністратором системи, і все нові документи могли бути заіндексувати тільки тими термінами, які були в цій базі даних. Вільний словник поповнювався автоматично по мірі появи нових документів. Однак на момент актуалізації словник також фіксувався. Актуалізація передбачала повне перезавантаження бази даних. У момент цього поновлення перевантажували самі документи, і оновлювався словник, а після його поновлення проводилася переіндексація документів. Процедура актуалізації займала досить багато часу і доступ до системи в момент її актуалізації закривався.

Тепер уявімо собі можливість такої процедури в анархічною Internet, де ресурси з'являються і зникають щодня. При створенні програми Veronica для GopherSpace передбачалося, що всі сервери повинні бути зареєстровані, і таким чином вівся облік наявності або відсутності ресурсу. Veronica раз на місяць перевіряла наявність документів Gopher і оновлювала свою базу даних ПІД для документів Gopher. У WWW нічого подібного немає. Для вирішення цього завдання використовуються програми сканування мережі або роботи-індексіровщікі [ 8 ]. Розробка роботів - це досить нетривіальне завдання; існує небезпека зациклення робота або його потрапляння на віртуальні сторінки. Робот переглядає мережу, знаходить нові ресурси, приписує їм терміни і поміщає в базу даних індексу. Головне питання полягає в тому, що за терміни приписувати документам, звідки їх брати, адже ряд ресурсів взагалі не є текстом. Сьогодні роботи зазвичай використовують для індексування наступні джерела для поповнення своїх віртуальних словників: гіпертекстові посилання, заголовки, заголовки (H1, H2), анотації, списки ключових слів, повні тексти документів, а також повідомлення адміністраторів про свої Web-сторінках [ 9 ]. Для індексування telnet, gopher, ftp, нетекстової інформації використовуються головним чином URL, для новин Usenet і поштових списків поля Subject і Keywords. Найбільший простір для побудови ПІД дають HTML документи. Однак не слід думати, що всі терміни з перерахованих елементів документів потрапляють в їх пошукові образи. Дуже активно застосовуються списки заборонених слів (stop-words), які не можуть бути вжиті для індексування, загальних слів (прийменники, сполучники і т.п.). Таким чином навіть те, що в OpenText, наприклад, називається повнотекстових індексуванням реально є вибором слів з тексту документа і порівнянням з набором різних словників, після якого термін потрапляє в ПОД, а потім і в індекс системи. Для того щоб не роздувати словників та індексів (індекс системи Lycos вже сьогодні дорівнює 4 Тбайт), застосовується таке поняття, як вага терміна [ 10 ]. Документ зазвичай індексується через 40 - 100 найбільш "важких" термінів.

індекс пошуку

Після того як ресурси заіндексувати і система склала масив ПІД, починається побудова пошукового апарату. Цілком очевидно, що лобовий перегляд файлу або файлів ПІД займе багато часу, що абсолютно неприйнятно для інтерактивної системи WWW. Для прискорення пошуку будується індекс, яким в більшості систем є набір пов'язаних між собою файлів, орієнтованих на швидкий пошук даних за запитом. Структура і склад індексів різних систем можуть відрізнятися один від одного і залежать від багатьох факторів: розмір масиву пошукових образів, інформаційно-пошукова мова, розміщення різних компонентів системи і т.п. Розглянемо структуру індексу на прикладі системи [ 6 ], Для якої можна реалізовувати не тільки примітивний булевий, але і контекстний і зважений пошук, а також ряд інших можливостей, які відсутні у багатьох пошукових системах Internet, наприклад Yahoo. Індекс даної системи складається з таблиці ідентифікаторів сторінок (page-ID), таблиці ключових слів (Keyword-ID), таблиці модифікації сторінок, таблиці заголовків, таблиці гіпертекстових зв'язків, інвертованого (IL) і прямого списку (FL).

Page-ID відображає ідентифікатори сторінок в їх URL, Keyword-ID - кожне ключове слів в унікальний ідентифікатор цього слова, таблиця заголовків - ідентифікатор сторінки в заголовок сторінки, таблиця гіпертекстових посилань - ідентифікатор сторінок в гіпертекстове посилання на цю сторінку. Інвертований список ставить у відповідність кожному ключовому слову документа список пар - ідентифікатор сторінки, позиція слова в сторінці. Прямий список - це масив пошукових образів сторінок. Всі ці файли так чи інакше використовуються при пошуку, але головним серед них є файл інвертованого списку. Результат пошуку в даному файлі - це об'єднання і / або перетин списків ідентифікаторів сторінок. Результуючий список, який перетворюється в список заголовків, забезпечених гіпертекстовими посиланнями повертається користувачеві в його програму перегляду Web. Для того щоб швидко шукати записи інвертованого списку, над ним надбудовується ще декілька файлів, наприклад, файл буквених пар із зазначенням записів інвертованого списку, що починаються з цих пар. Крім цього, застосовується механізм прямого доступу до даних - хешування. Для оновлення індексу використовується комбінація двох підходів. Перший можна назвати корекцією індексу "на ходу" за допомогою таблиці модифікації сторінок. Суть такого рішення досить проста: старий запис індексу посилається на нову, яка і використовується при пошуку. Коли число таких посилань стає достатнім для того, щоб відчути це при пошуку, то відбувається повне оновлення індексу - його перезавантаження. Ефективність пошуку в кожній конкретній ІПС визначається виключно архітектурою індексу. Як правило, спосіб організації цих масивів є "секретом фірми" і її гордістю. Для того щоб переконатися в цьому, досить ознайомитися з матеріалами OpenText [ 11 ].

Інформаційно-пошукова мова системи

Індекс - це только частина пошуково апарату, прихована від користувача. Другою частиною цього апарату є інформаційно-пошукова мова (ІПМ), що дозволяє сформулювати запит до системи в простій і наочній формі. Вже давно залишилася позаду романтика створення ІПМ, як природної мови, - саме цей підхід використовувався в системі Wais на перших стадіях її реалізації. Якщо навіть користувачеві пропонується вводити запити на природній мові, то це ще не означає, що система буде здійснювати семантичний розбір запиту користувача. Проза життя полягає в тому, що зазвичай фраза розбивається на слова, з яких видаляються заборонені і загальні слова, іноді проводиться нормалізація лексики, а потім все слова зв'язуються або логічним AND, або OR. Таким чином, запит типу:

> Software that is used on Unix Platform

буде перетворений в:

> Unix AND Platform AND Software

що буде означати приблизно наступне: "Знайди всі документи, в яких слова Unix, Platform і Software зустрічаються одночасно".

Можливі й варіанти. Так, в більшості систем фраза "Unix Platform" буде визначена як ключова фраза і не буде поділятися на окремі слова. Інший підхід полягає в обчисленні ступеня близькості між запитом і документом. Саме цей підхід використовується в Lycos. У цьому випадку відповідно до векторної моделлю подання документів і запитів обчислюється їх міра близькості. Сьогодні відомо близько дюжини різних заходів близькості. Найбільш часто застосовується косинус кута між пошуковим чином документа і запитом користувача. Зазвичай ці відсотки відповідності документа запиту і видаються в якості довідкової інформації при списку знайдених документів.

Найбільш розвиненою мовою запитів з сучасних ІПС Internet має Alta Vista. Крім звичайного набору AND, OR, NOT ця система дозволяє використовувати ще і NEAR, що дозволяє організувати контекстний пошук. Все документ в системі розбиті на поля, тому в запиті можна вказати, в якій частині документа користувач сподівається побачити ключове слово: посилання, заголовок, анотація і т.п. Можна також задавати поле ранжирування видачі і критерій близькості документів запиту.

інтерфейс системи

Важливим фактором є вид подання інформації в програмі-інтерфейсі. Розрізняють два типи інтерфейсних сторінок: сторінки запитів і сторінки результатів пошуку.

При складанні запиту до системи використовують або меню - орієнтований підхід, або командний рядок. Перший дозволяє ввести список термінів, зазвичай розділяються пропуском, і вибрати тип логічного зв'язку між ними. Логічний зв'язок поширюється на всі терміни. На схемі з малюнка вказані збережені запити користувача - в більшості систем це просто фраза на ІПМ, яку можна розширити за рахунок додавання нових термінів і логічних операторів. Але це тільки один спосіб використання збережених запитів, званий розширенням або уточненням запиту. Для виконання цієї операції традиційна ІПС зберігає не запит як такий, а результат пошуку - список ідентифікаторів документів, який об'єднується / перетинається зі списком, отриманим при пошуку документів по нових термінів. На жаль, збереження списку ідентифікаторів знайдених документів в WWW не практикується, що було викликано особливістю протоколів взаємодії програми-клієнта і сервера, що не підтримують сеансовий режим роботи.

Отже, результат пошуку в базі даних ІПС - це список покажчиків на задовольняють запиту документи. Різні системи представляють цей список по-різному. У деяких видається тільки список посилань, а в таких, як Lycos, Alta Vista і Yahoo, дається ще й короткий опис, яке запозичується або з заголовків, або з тіла самого документа. Крім цього, система повідомляє, на скільки знайдений документ відповідає запиту. В Yahoo, наприклад, ця кількість термінів запиту, що містяться в ПОД, відповідно до якого ранжируется результат пошуку. Система Lycos видає міру відповідності документа запиту, по якій здійснюється ранжування.

При огляді інтерфейсів і засобів пошуку можна пройти повз процедури корекції запитів за релевантністю [ 7 ]. Релевантність - це міра відповідності знайденого системою документа потреби користувача. Розрізняють формальну релевантність і реальну. Першу обчислює система, і на підставі чого ранжируется вибірка знайдених документів. Друга - це оцінка самим користувачем знайдених документів. Деякі системи мають для цього спеціальне поле [ 6 ], Де користувач може відзначити документ як релевантний. При наступній пошуковій ітерації запит розширюється термінами цього документа, а результат знову ранжируется. Так відбувається до тих пір, поки не настане стабілізація, що означає, що нічого кращого, ніж отримана вибірка, від даної системи не доб'єшся.

Крім посилань на документи в списку, отриманому користувачем, можуть виявитися посилання на частини документів або на їх поля. Це відбувається при наявності посилань типу http: // host / path # mark або посилань за схемою WAIS. Можливі посилання і на скрипти, але зазвичай такі посилання роботи пропускають, і система їх не індексує. Якщо з http-посиланнями все більш-менш зрозуміло, то посилання WAIS - це набагато більш складні об'єкти. Справа в тому, що WAIS реалізує архітектуру розподіленої інформаційно-пошукової системи, при якій одна ІПС, наприклад Lycos, будує пошуковий апарат над пошуковим апаратом іншої системи - WAIS. При цьому сервери WAIS мають свої власні локальні бази даних. При завантаженні документів в WAIS адміністратор може описати структуру документів, розбивши їх на поля, і зберігати документи у вигляді одного файлу. Індекс WAIS буде посилатися на окремі документи і їх поля як на самостійні одиниці зберігання, програма перегляду ресурсів Internet в цьому випадку повинна вміти працювати з протоколом WAIS, щоб отримати доступ до цих документів.

Висновок

В оглядовій статті були розглянуті основні елементи інформаційно-пошукових систем та принципи їх побудови. Сьогодні ІПС є найбільш потужним механізмом пошуку мережевих інформаційних ресурсів Internet. На жаль, в російському секторі Internet поки не спостерігається активного вивчення цієї проблеми за винятком, може бути, проекту LIBWEB, що фінансується РФФД і системи "Павук", яка працює недостатньо надійно. Найбільшим досвідом розробки такого ґатунку систем безумовно володіє ВІНІТІ, але тут робота зосереджена поки на розміщенні своїх власних ресурсів в Мережі, що принципово відрізняється від інформаційно-пошукових систем Internet типу Lycos, OpenText, Alta Vista, Yahoo, InfoSeek і т.п. Здавалося б, що така робота могла бути зосереджена в рамках таких проектів, як Росія On-line компанії SovamTeleport, але тут ми поки спостерігаються посилання на чужі пошукові машини. Розвиток ІПС для Internet в США почалося два роки тому, з огляду на вітчизняні реалії та темпи розвитку технологій Мережі в Росії, можна сподіватися, що у нас ще все попереду.

література

1. Дж. Солтон. Динамічні бібліотечно-інформаційні системи. Світ, Москва, 1979.
2. Frank G. Halasz. Reflection notecards: seven issues for the next generation of hypermedia systems. Communication of the acm, V31, N7, 1988, p.836-852.
3. Tim Berners-Lee. World Wide Web: Proposal for HyperText Project. 1990.
4. Alta Vista . Digital Equipment Corporation, 1996..
5. Brain Pinkerton. Finding What People Want: Experiences with the WebCrawler .
6. Bodi Yuwono, Savio L.Lam, Jerry H.Ying, Dik L.Lee. A World Wide Web Resource Discovery System .
7. Martin Bartschi. An Overview of Information Retrieval Subjects. IEEE Computer, N5, 1985, p.67-84.
8. Michel L. Mauldin, John RR Leavitt. Web Agent Related Research at the Center for Machine Translation .
9. Ian R.Winship. World Wide Web searching tools -an evaluation . VINE (99).
10. G.Salton, C.Buckley. Term-Weighting Approachs in Automatic Text Retrieval. Information Processing & Management, 24 (5), pp. 513-523, 1988.
11. Open Text Corporation Releases Industry "s Highest Performance Text Retrieval System.

Павло Храмцов ( [email protected] ) - незалежний експерт, (Москва).