Главная / Рефераты / Информатика, программирование

Реферат: Структура пошукових систем, показники ефективності пошуку

Міністерство освіти і науки, молоді та спорту України

Державний вищий навчальний заклад

Київський національний економічний університет імені Вадима Гетьмана

Кафедра інформаційного менеджменту

Реферат

на тему: Структура пошукових систем, показники ефективності пошуку

Київ 2011

Вступ

Завдання будь-якої пошукової системи – доставляти людям ту інформацію, яку вони шукають. Навчити людей робити “правильні” запити, тобто запити, відповідні принципам роботи пошукових систем неможливо. Тому розробники створюють такі алгоритми і принципи роботи пошукових систем, які б дозволяли знаходити користувачам саме ту інформацію, яку вони шукають. Це означає, пошукова система повинна “думати” так, як думає користувач при пошуку інформації.

Автоматичні системи інформаційного пошуку використовують для зменшення так званого "інформаційного перевантаження". Найвідомішим прикладом систем ІП можна назвати пошукові системи в Інтернеті.

Об’єктом інформаційного пошуку є текстова інформація, зображення, аудіо, відео інформація.

З інформаційним пошуком змикаються проблеми: розсилки інформації (information routing); сортування інформації (information filtering); упорядкування (класифікація) інформації (information categorization); відбір інформації (information extraction).

1. Поняття «пошукова система»

Пошукова система це — онлайн-служба, яка надає можливість пошуку інформації на сайтах в інтернеті, а також (можливо) у групах обговорення та ftp-серверах.

Індексація в пошукових системах сайтів здійснюється пошуковим роботом. Робот – це невелика програма, що ходить по посиланнях на сайті й індексує (збирає і запам'ятовує) зустрінуту на шляху інформацію. Також інформація з веб-сайтів збирається за допомогою «спайдерів» та «кроуберів».

Основними критеріями якості роботи пошукової системи є релевантність, повнота бази, врахування морфології мови.

Сьогодні Інтернет поєднує безліч різних мереж, мільйони комп'ютерів, близько 800 мільйонів користувачів усіх континентів і, за різними оцінками, число таких користувачів збільшується на 15-80% щорічно. Можна виділити два основних напрямки у використанні Інтернет у бізнесі. Це оперативний доступ до воістину неозорих джерел інформації з будь-якої тематики (на сотнях тисяч інформаційних серверів), пошук і інтерактивне спілкування з партнерами, практично в будь-якій спеціалізації і географічному розташуванні. Як зорієнтуватися в настільки масштабному інформаційному просторі? Для цього існують спеціалізовані пошукові сервера. Їх можна розділити на тематичні каталоги, роботи індексів (пошукові машини). Також, для пошуку необхідної інформації в Інтернет дуже корисні системи пошуку в конференціях Usenet і служби пошуку людей.

2. Методи організації пошуку

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

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

До другої групи засобів відноситься повнотекстовий пошук і вибірка видань. Дійсно, будь-яка книга, зокрема – в електронному вигляді, є слабо структурований набір символів, організованих в слова, пропозиції, розділи, параграфи і розділи. Для організації повнотекстового пошуку необхідно спочатку провести індексацію видань, скласти для них так званий повнотекстовий індекс. У простому випадку він є списком всіх значущих слів в текстовій базі даних з вказівкою, в яких виданнях зустрічаються ці слова. Зустрічаються багаторівневі індекси, в яких на верхньому рівні розташований словник або пошуковий індекс слова. В ньому кожному значущому слову відповідає покажчик розташований на наступному рівні, список місцезнаходжень або індекс посилань, в якому містяться адреса видання і, іноді, позиція слова усередині документа.

Багато хто з читачів, ймовірно, використовував повнотекстовий пошук, працюючи в мережі Інтернеті пошуковими серверами. В цьому випадку в спеціальне поле пошуку вводиться конструкція з деякої кількості слів або фраз, іноді зв'язаних один з одним знаками логічних операцій. Відповідний механізм на сервері автоматично перевіряє вміст посилань на документи, що містяться в його базі даних і видає результат пошуку у вигляді списку відповідних або релевантних документів.

Можна сформулювати чотири основні відмінності повнотекстової вибірки від атрибутивної:

· повнотекстова вибірка відповідає на запити з меншою точністю;

· вибірка імовірнісна, а не детермінована;

· критерієм правильності вибірки є не точний збіг, а лише придатність видання, що витягує з бази;

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

Неважко зрозуміти, що першій моделі найкраще відповідає атрибутивний пошук, а другий – повнотекстовий. Принципова відмінність між цими двома методами пошуку полягає в тому, що результат застосування атрибутивного пошуку детермінований, тоді як повнотекстовий пошук слід характеризувати як імовірнісний, тобто його результат містить набір документів, що характеризуються певним рівнем релевантності, придатності.

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

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

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

Варіантом цієї моделі є зв'язане читання, яке використовує концепцію гіпертексту і переходи по гіперпосиланнях усередині одного видання або навіть між виданнями, включаючи малюнки, звукові- і відеофрагменти.

Найчастіше застосовується Булеві моделі пошуку, логічні конструкції, що використовують як основу, тобто слова або фрази (останні полягають зазвичай в круглі дужки), об'єднані знаками логічних операцій І (AND &), АБО (OR) і НЕ (NO). Вхідні в конструкцію смислові елементи, тобто слова і фрази, якщо останні розглядаються як єдине ціле, зазвичай називають термами. Якщо в результаті запиту пошукова система видала надмірно великий список документів, запит можна спробувати ускладнити, включивши в нього більшу кількість термів і операторів І, що припускають одночасну наявність в документі базових слів і фраз. Навпаки, якщо знайдена невелика кількість придатних (релевантних) документів, запит можна спростити, виключивши з нього окремі конструкції з оператором І (або додавши конструкції з оператором АБО).

Спеціальне програмне забезпечення може забезпечити автоматичну оцінку ступеня корисності кожного з видань, що витягують. Ця оцінка робиться на основі частоти, з якою зустрічаються у виданні терми, використовувані в запиті. Результати зазвичай сортуються по ступеню релевантності. Така модель пошуку використовується, зокрема, на пошуковому сервері Rambler.

Векторна модель пошуку заснована на представленні кожного окремого видання деяким вектором в N-вимірному просторі. Запит також представляється у вигляді вектора. Ступінь корисності документа, визначається як його близькість у вказаному N-вимірному просторі до вектора запиту. Кількісна оцінка близькості виражається косинусом кута між цими векторами і змінюється в межах від 0 до 1.

Векторна модель пошуку обов'язково має на увазі послідовні ітерації. На початку пошуку користувач зі всієї безлічі вибраних видань визначає деякі як потрібні, корисні. На підставі цього вибору виробляється уточнене положення вектора запиту.

Ефективність – головний критерій при визначенні вживаного методу повнотекстової вибірки. Ефективність пошуку видання можна описати двома характеристиками: точність і обхват. Точність «P» визначається відношенням числа релевантних документів R до загальної кількості документів у вибірці

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

N (P=R/N)

Обхват «а» характеризується відношенням числа релевантних документів у вибірці R до загального числа релевантних документів в базі даних

Т (a=R/T)

У разі ідеального пошуку всі вибрані документи повністю придатні і вичерпують список придатних документів в базі даних, тобто а=1 і P=1. Проте численні дослідження, виконані різними фахівцями, показали що точність і обхват зв'язані один з одним зворотною залежністю, а максимальне значення суми P+а близько до 1,4.

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

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

У останньому випадку, збільшення кількості вибраних видань неминуче збільшить час обробки результатів пошуку. Реально, якщо кількість вибраних видань складає сотні значень, то час оцінки їх придатності стає надмірно великим, в результаті користувач стомлюється, увага його розсівається, що неминуче приводить до неточностей і помилок.

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

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

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

3. Організація пошуку інформації за допомогою тематичних каталогів та пошукових машин

Найбільш популярним в усьому світі визнаний тематичний каталог, згідно зі статистикою Alexa Internet и Netcraft, - Yahoo! (http://www.yahoo.com ). Глобальна мережа веб-сайтів Yahoo! опрацьовує 3,4 млрд. запитів веб-сторінок в день. Він являє собою величезну базу даних URL-адрес сайтів усілякої тематики. Yahoo! пропонує вам скористатися ієрархічним деревом при пошуку інформації. Тобто, ви обираєте спочатку загальну тематику, що задовольняє вашому запиту інформації, і далі конкретизуєте, випливаючи підказкам каталогу. Звичайно в результаті ви одержуєте список сайтів, що містять інформацію, що відповідає вашому запиту. Yahoo! (NASDAQ: YHOO) — американська компанія, яка володіє другою за популярністю (12.46 %) в світі пошуковою системою та представляє ряд сервісів, які з’єднані інтернет-порталом Yahoo! Directory; портал вміщує популярний сервіс електронної пошти Yahoo! Mail, один із найстаріших та найпопулярніших в Інтернеті. Не так давно була запущена нова версія поштового інтерфейсу, яка заснована на AJAX.

Компанія Yahoo! була заснована аспірантами Стенфордського університету Девідом Філо (англ. David Filo) та Джеррі Янгом (англ. Jerry Yang) в січні 1994 року; стала корпорацією 2 березня 1995 року. Головний офіс компанії знаходиться в місті Саннівейл (англ. Sunnyvale), штат Каліфорнія, США.

Якщо ж ви шукайте інформацію свідомо україномовну, то має сенс використовувати українські каталоги, наприклад, "Сузір'я Інтернет", що містить тільки обрані (найцікавіші) ресурси. Принцип роботи з ними ідентичний тому, який ми розглянули на прикладі з Yahoo!. Для пошуку російськомовної інформації слід відзначити перший російський каталог Russіa on the Net (http://www.ru), один з найбільших російськомовних каталогів Lіst.RU (http://www.lіst.ru), російський варіант Yahoo! (http://www.yahoo.ru).

Пошукові машини улаштовані трохи інакше. По суті це сервер з величезною базою даних URL-адрес, що автоматично звертається до сторінок WWW по всіх цих адресах, вивчає вміст цих сторінок, формує і прописує ключові слова зі сторінок у свою базу даних (індексує сторінки). Більш того, цей сервер звертається по всім, що зустрічаються на сторінках посиланнями і переходячи до нових сторінок, проробляє з ними теж саме. Тому що майже будь-яка сторінка WWW має безліч посилань на інші сторінки, то при подібній роботі пошукова машина в кінцевому результаті теоретично може обійти всі сайти в Інтернет. Одна з популярних пошукових машин AltaVіsta (http://www.altavіsta.com) містить 11 мільярдів слів, витягнутих з 30 мільйонів WWW-сторінок. Як користатися цим сервісом? Необхідно продумати рядок запиту інформації (не більш ніж 5 слів), як у випадку з Yahoo! і також набрати її в поле введення. Над кнопкою Search (Пошук) знаходиться спадаюче меню з вибором мови. Перед натисканням Enter чи кнопки Search необхідно вибрати мову представлення інформації. Крім того, у запит інформації можна включати спеціальний символ *, що розширює діапазон пошуку. Скажемо, що б Altavіsta могла знайти не тільки усі входження слова "легка", але слова "легку", "легкої" і т.д., у запиті треба писати "легк**", тобто букви закінчення заміняємо на символ *. Для пошуку в російськомовному Інтернет Altavіsta не дуже підходить. Якщо на запит "Lіght іndustry" Altavіsta формує список з 2917 URL-адрес, то по запиті "Легка промисловість" з'являється список посилань на всього 9 сайтів.

Проблема більше полягає в тому, що пошукова машина в результаті вашого запиту генерує гігантський список адрес URL з короткими описами. Варто також відзначити інші російськомовні пошукові машини Апорт (http://www. aport.ru) і АУ (http://www.au.ru).

Читаючи про всі перераховані пошукові служби, по неволі задумаєшся: "а якщо для пошуку необхідної мені інформації не досить однієї пошукової служби, та невже мені доведеться входити на всі тут перераховані сервера і щораз повторювати той самий запит?!". Найбільш якісний результат саме буде саме при такому підході. Але можна, виходячи з економії часу і грошей, скористатися системами позначка пошуку. Найбільш популярна у світі система такого класу Search.com (http://www.search.com), але якщо ми працюємо переважно з російськомовними документами, то можна використовувати Savvy Search. Це досить могутня система відсилає ваш запит на 13 найбільших пошукових машин (у тому числі і російських) і повертаючи вам їхні звіти.

4. Приклади пошукових систем

Пошукова система YANDEX

У 1996 році, на виставці InternetCom, офіційно об’явлено про створений компанією CompTek, зі 100% американською участю, пошукової системи YANDEX. Ця система незамінна, коли потрібно задати складні зв’язки між ключовими словами в якості критерія пошуку. Яндекс підтримує запит по рисунках, а запит оброблений при посиланні на family.yandex.ru буде мати фільтри ненормованої лексики. З вікном пошукової системи Яндекс можна ознайомитись на сайті www.yandex.ru

Знайомство з Rambler

Варто згадати про ще одну популярну російську пошукову машину Rambler (http://www.rambler.ru ). Цей сервер має ще більш повну базу даних URL-адрес, чим у Yandex. Відмітною рисою Rambler є те, що цей сервер веде статистику частоти відвідування посилань із власної бази даних. Ви завжди можете зайти в розділ "Рейтинг" на головній сторінці Rambler і побачити вміст тематичного каталогу, який відсортований по убуванню числа відвідувань сайтів (їхньої популярності). Тим самим відтинаються явні аутсайдери і ви не витрачаєте на них свій час. Rambler також як і Yandex, дозволяє, крім простого запиту, запит із мовою запитів. Підтримуються ті ж логічні оператори І, ЧИ, НЕ, метасимвол «*» (аналогічний символу «*», який розширює діапазон запиту у AltaVіsta), коефіцієнтні символи «+» і «-», для збільшення або зменшення значимості слів, що вводяться в запит.

Перша частина пошукової системи Rambler є роботом, який може отримувати адреси документів через проксі-сервер або безпосередньо з вказаного вузла, індексує зміст документа і поміщає результати цього індексування в базу даних. Другою частиною Rambler є власне сама пошукова система по серверах Росії і країн СНД, що містить мільйони документів з більш ніж 15,000 сайтів (імен DNS)

Знайомство з Google

Google (www.google.ru) – це найбільша пошукова система в світі з відвідуваністю приблизно 500,000 чоловік в день (рис.1). У відповідь на більшість запитів ця система видає набагато більш короткий список посилань, ніж, наприклад, Яndex (Yandex), але головне — серед перших позицій цього списку майже завжди є точна відповідь на заданий запит. Відбувається це завдяки використанню для оцінки релевантності (ступені відповідності запиту) веб-сторінок (Web Page) технології PageRank.

PageRank — це числова величина, яка характеризує «важність» сторінки в Google. Чим більше посилань на сторінку, тим вона стає «поважнішою». Крім того, «вага» сторінки А визначається вагою посилання, надісланого сторінкою B. Таким чином, PageRank — це метод розрахунку ваги сторінки шляхом підрахунку важності посилань на неї. PageRank є одним з допоміжних факторів при ранжируванні сайтів в результатах пошуку. PageRank не єдиний, але дуже важний спосіб визначення положення сайту в результатах пошуку Google.

Рисунок 1 – Українська пошукова машина Google

Пошукова система Google може знаходити інформацію 101 мовою. Google наприкінці серпня 2004 року складалась з 132 тис. машин, розташованих в різних точках планети. Інтерфейс Google містить досить складну мову запитів, що дозволяє обмежити область пошуку окремими доменами, мовами, типами файлів тощо.

Висновок

Сьогодення існує безліч пошукових систем. Серед них Google, Rambler та багато інших. Всі вони різняться своєю структурою та ефективністю пошуку, але кожен має право обирати саме ту, яка подобається йому найбільше і яка є назручнішою для нього.

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

Список використаних джерел

1. http://uk.wikipedia.org/wiki/Пошукова_система#

2. http://itb.ucoz.ru/publ/struktura_poshukovikh_sistem/5-1-0-300

3. http://buklib.net/component/option,com_jbook/task,view/