.

XML-owe systemy informacyjne.

Spis treści

1. Tradycyjne metody wyszukiwania informacji.

2. Wyszukiwanie strukturalne.

3. Podstawowe koncepcje XML.

4. Problemy wyszukiwania XML.

5. Model przestrzeni dla wyszukiwania XML.

6. Ocena wyników wyszukiwania XML.

7. Porównanie wyszukiwania XML dla danych i tekstu.

1. Tradycyjne metody wyszukiwania informacji.

Systemy wyszukiwania danych często porównywane są z relacyjnymi bazami danych.

2. Wyszukiwanie strukturalne

Podczas wyszukiwania zadawane pytania mogą mieć dwie postacie: strukturalne i niestrukturalne. Dla ułatwienia zakładamy, że przetwarzane dokumenty są strukturalne.

Takimi dokumentami są:

• biblioteki cyfrowe

• bazy patentowe

• blogi

• Office Suites

Przykłady zapytań dla wyszukiwań niestrukturalnych:

• Podaj streszczenia artykułów, których autorem jest… .

• Podaj artykuł o … .

• Podaj poradniki o konserwacji drukarek i skanerów.

• Podaj sztuki teatralne, w których występują akty ze słowem „tragedia” w tytule.

Przykłady odpowiedz dla wyszukiwań niestrukturalnych:

• Brak rozróżnienia na autora i bohatera.

• Brak klasyfikacji dokumentów na rodzaje.

• Zwrócenie tekstów zawierających słowa „drukarka”, „skaner” i „konserwacja”.

• Brak możliwości sortowania wyniku po relewancji.

Z tym rozwiązaniem wiąże się jednak problem:

• Jak poznać strukturę dokumentu?

• Czy można wymagać od użytkownika stosowania zaawansowanych metod wyszukiwania?

Odpowiedzią jest zastosowanie XML-a.

W kontekście wyszukiwania informacji bierzemy pod uwagę XML jako język do odkodowania tekstu i dokumentów. Dla przykładu, możemy chcieć pobrać dane z systemu planowania zasobów pewnego przedsiębiorstwa, a następnie wczytać je do programu analitycznego tworzącego wykresy na podstawie tych danych. Ten typ aplikacji XML określany jest jako „data-centric” z powodu dominujących numerycznych i nietekstowych atrybutów.

Istnieje typ wyszukiwań znajdujący się pomiędzy wyszukiwaniem niestrukturalnym a wyszukiwaniem w relacyjnych bazach danych: wyszukiwanie parametryczne oraz strefowe. W modelu danych wyszukiwania parametrycznego oraz strefowego wyróżniamy pola parametryczne(data, wielkość pliku, itp.) oraz pola zwane strefami(autor, tytuł, itp.). Struktura takiego dokumentu jest płaska, bez zagnieżdżonych elementów, a ilość atrybutów jest niewielka.

3. Podstawowe koncepcje XML.

Dokument XML jest uporządkowanym i opisanym drzewem. Każdy węzeł jest elementem XML. Każdy element posiada znacznik otwarcia i zamknięcia. Element może posiadać atrybuty oraz zawartość. Zawartość może być tekstem lub zagnieżdżonym elementem. Atrybuty muszą być unikalne dla każdego elementu.

Elementy opisują strukturę i meta dane. Drzewo odzwierciedla strukturę dokumentu. Standardem dostępu przetwarzania dokumentów XML jest XML Document Object Model czyli DOM. DOM reprezentuje elementy, atrybuty oraz tekst w elementach będących węzłami w drzewie. Z DOM API przetwarza się dokument XML rozpoczynając od korzenia, kierując się w dół drzewa do przez kolejne węzły.

node	Zwraca wszystkie elementy o tej nazwie
komputer/część lub komputer// część	Zapis ścieżki
/	Ustawia w korzeniu

• Dokument może wskazywać na swój schemat

• Jest ważny ze względu na późniejsze przetwarzanie dokumentu

• Zadawanie zapytań strukturalnych praktycznie nie możliwe bez znajomości schematu

• Dwa standardy dla XML: DTD i XML Schema

• Wyszukujemy sekcję o lecie i wakacjach wewnątrz artykułu z lat 2001/2002

• „//” i „/” jak w XPath

• „.” odwołuje się do obecnego elementu

• „about” wykonuje funkcję sortowania relewancji

Zapytanie przedstawione na powyższym rysunku szuka sekcji o letnich wakacjach, które były częścią artykułów z lat 2001 lub 2002.

4. Problemy wyszukiwania XML

Zwykle pozbywa się ograniczeń atrybutów stosując przefiltrowanie lub postfiltrowanie. Polega to na wyłączeniu wszystkich elementów z wynikowego zbioru które nie spełniają założeń budowy relacyjnej atrybutów. Kiedy atrybuty relacyjne zostaną wyłączone, możemy zaprezentować dokument jako drzewo z tylko jednym rodzajem węzłów.

Spójrzmy na problemy na jakie się natykamy .

PROBLEM PIERWSZY:

• Zwrócenie części dokumentu XML (elementu XML)

• Pytanie - który element?

• Element relewantny jest najczęściej zagnieżdżony

STRUCTURED DOCUMENT RETRIEVAL PRINCIPLE

A SYSTEM SHOULD ALWAYS RETRIEVE THE MOST SPECIFIC PART OF A DOCUMENT ANSWERING THE QUERY.

Według tej strategii powinniśmy otrzymywać najmniejszą możliwą część odpowiadającą na pytanie. Trudność implementacji polega na postawieniu pytania. Pytając o element tytuł o wartości „Makbet” możemy z większym prawdopodobieństwem otrzymać odpowiedź dotyczącą dzieła niż jednego z aktów.

PROBLEM DRUGI:

• Co indeksować?

• Wyszukiwanie niestrukturalne indeksuje całe pliki np. pliki na pulpicie, maile

• Wyszukiwanie strukturalne ma różne podejścia do podziału elementów

Rozwiązanie pierwsze:

Podział na rozłączne niepokrywające się sekcje.

Rozwiązanie drugie:

Indeksowanie po korzeniu. Rozwiązanie to ma wadę: stopień relewancji dokumentu jest dużo niższy niż pojedynczego elementu (tracimy najlepsze rozwiązania)

Rozwiązanie trzecie:

• Zamiast przeszukiwania góra-dół stosujemy dół-góra

• Przeszukujemy wybrane niższe poziomy

• Wybieramy najlepsze elementy

• W fazie postprocessingu decydujemy jak wysoko przejść do korzenia

• Wada: : stopień relewancji dokumentu jest dużo niższy niż pojedynczego elementu (tracimy najlepsze rozwiązania)

Spróbujmy zatem zaindeksować wszystkie elementy

• Nadal możemy otrzymać odpowiedz redundantną

• Odpowiedź możemy przetwarzać w postprocessingu

• Można „zwijać” odpowiedzi i podkreślać graficznie elementy redundantne

• Zmniejszamy przez to zbiór odpowiedzi

• Zyskujemy kontekst i większą czytelność dzięki zaznaczeniu elementów zapytania

• Heterogeniczność kolekcji

Często zdarza się, że kilka różnych schematów XML występuje w kolekcjach pochodzących z różnych źródeł. Na poniższej ilustracji można zaobserwować, że te same elementy mogą mieć różne nazwy: creator w d₂ i author w d₃.

5. Model przestrzeni wyszukiwania XML

Na potrzeby wyszukiwania strukturalnego (kontekstowego) musimy określić przestrzeń wielosektorową. Aby to osiągnąć można zakodować termy wraz z ich pozycją w drzewie dokumentu. W tym celu rozbijamy drzewo reprezentujące strukturę.

Możemy przedstawić dokumenty i pytania jako wektory przestrzeni poddrzew i porównać ze sobą. Ilość wymiarów określa dokładność odpowiedzi. Ograniczenie się do warstwy termu powoduje zgubienie kontekstu. Pamiętać należy, że indeksuje się tylko ścieżki kończące się termem.

• Indeksujemy pary kontekst-term

• Nazywamy je termem kontekstowym <c, t>

• Zakładamy stosowanie „//” zamiast „/”

• Nadal preferujemy odpowiedzi o strukturze najbliższej pytaniu

Do sortowania termów stosujemy funkcję:

• |c| - długość ścieżki

• c_q i c_d pasują jeśli można je przekształcić w siebie dodając międzywęzły

Końcowy wynik dla dokumentu obliczamy:

• t - term

• q - pytanie

• d - dokument

• c - kontekst

• B - zbiór wszystkich kontekstów XML

• V - zbiór wszystkich termów

ALGORYTMY

SimNoMerge - algorytmy obliczania podobieństwa rozważający poszczególne konteksty XML osobno

SimMerge - alternatywna funkcja z nieco luźniejszym podejściem do warunków zapytań i dokumentów

6. Ocena wyników wyszukiwania XML

System INEX (Initiative for Evaluation of XML Retrieval)

• Powiązane kolekcje danych, zbiory zapytań, miary relewancji

• Coroczne dyskusje nad rezultatami wyszukiwań

• Relewancja działania systemu oceniania jest wg wyspecyfikowanego standardu

• Zajmuje się problemami content - only (CO) oraz content - and - structure (CAS)

Statystyki INEX 2002

Schemat dokumentu INEX

Obie miary w zestawieniu tworzą klasyfikator:

• Teoretycznie występuje 16 kombinacji

• Nie wszystkie mają sens

• Pozbywamy się problemu z binarna relewancją

• Zyskujemy możliwość sortowania wyników po relewancji

• Wada: nie mierzy redundancji wyników

Funkcja oceniająca:

Porównanie skuteczności algorytmów klasyfikujących:

Usprawnienie wyszukiwania bezkontekstowego:

7. Porównanie wyszukiwania XML dla danych i tekstu

• Systemy text - centric nie radzą sobie z join'ami oraz ograniczeniami porządkującymi

8. Bibliografia

 Manning C. D., Raghavan P., Schutze H. „Introduction to Information Retrieval” Cambridge 2009

1

---