Klasifikace a systémová analýza - AISPV1001

Technologie přístupu k informačním zdrojům

Podmínky efektivního přístupu

• zdroje musí být sémanticky popsané (musí být znám jejich význam, tj. musí k nim existovat metadata)
• zdroje musí být organizované (uspořádané, tj. musí být určeny vztahy mezi nimi)

Techniky organizace - umístění a označení

	umístění	označení
Otázka	Kde je to?	Co je to?
Typ techniky	konkrétní	abstraktní
Typ vlastnosti	vnitřní, statická	vnější, dynamická
Teoretický základ	fyzika	sémiotika
Typ objektů	materiální objekty nemovité objekty	neomezené
Omezení	místo - objekt: 1:1 jednoznačné	označení - objekt: N : M nejednoznačné

Typy technologií přístupu k informacím

		jednotka uložení	jednotka zpracování	struktura	přístup	jazyk
vyhledávání	strukturované	záznam	atribut (element, pole, sloupec)	relační	množinový	SQL
	plnotextové	text	slovo (lexém)	lineární (text), stromová (index)	množinový (prostřednictvím indexu)
prohlížení / navigace		zdroj (dokument/datový objekt)	uzel, odkaz (hrana, reference, spoj, link)	síťová	navigace	SPARQL

Vyhledávání

• stanovení, zda konkrétní údaj je prvkem určité množiny, a určení jeho umístění (tj. identifikace)
• princip: porovnávání hodnoty vyhledávacího klíče s hodnotami prvků dané množiny (souboru)

kritérium efektivnosti:

počet prvků prohledávaného souboru (slov, záznamů, dokumentů...), které musíme tímto způsobem otestovat (tj. doba potřebná k vyhledávání)

Vyhledávací algoritmy

rychlost vyhledávání / stupeň zpracování
			bez indexu	s indexem
	sekvenční	úplné
		zkrácené
	množinové

1. Úplné vyhledávání

Sekvenční vyhledávání v nesetříděném souboru (lineární vyhledávání řetězců v textu) - vždy je nutné zpracovat všechna data

Příklad: hledáme heslo "alma mater" v nesetříděném souboru

2. Zkrácené vyhledávání v setříděném souboru

Poté, co najdeme hledanou hodnotu, lze zpracování ukončit

Typy třídění / řazení:

a) podle označení: abecedně, chronologicky, číselně

b) podle obsahových nebo funkčních charakteristik, např. podle pravděpodobnosti požadavku

2.1 Sekvenční vyhledávání v setříděném souboru

Příklad: hledáme heslo "alma mater" sekvenčním vyhledáváním v abecedně setříděném souboru.

2.2 Intervalové vyhledávání v setříděném souboru

Součástí prohledávaného souboru je tzv. blokový (řídký) index (např. v encyklopedii - první a poslední heslo na straně).

• nejprve (sekvenčně) prohledáváme setříděný seznam intervalů
• po nalezení potřebného intervalu sekvenčně prohledáme setříděné záznamy, jež jsou v něm obsaženy

Příklady:

Hledáme časopis Knihovna v Portálu e-časopisů UK: 1. zvolíme písmeno K, 2. zvolíme interval Kli-Kni, 3. najdeme časopis Knihovna.

Hledáme heslo "alma mater" s použitím blokového indexu v encyklopedii.

2.3 Binární vyhledávání (binary search) v setříděném souboru

Půlení intervalu (rozdělení souboru vždy na polovinu) v setříděném souboru.

Vyhledávanou hodnotu porovnáme s prostředním záznamem intervalu; jestliže >, postupujeme zpět, jestliže <, postupujeme vpřed.

Příklad: hledáme číslo 63 - hledanou hodnotu porovnáme s číslem 50, poté s číslem 75, poté s číslem 62 (zaokrouhlená hodnota 62,5), poté s číslem 69, poté s číslem 66, poté s číslem 64, skončíme na čísle 63.

3. Vyhledávání s použitím indexu

Dvoufázové vyhledávání: nejprve prohledáme index, pak primární soubor.

Index

Pomocný soubor strukturovaný a tříděný podle jiného hlediska než základní (primární) soubor. Obsahuje záznamy o struktuře "klíč, adresa", kde klíč je hodnota (slovo, fráze, atribut) a adresa je ukazatel na místo uložení této hodnoty v základním souboru. Prostřednictvím odkazu propojuje index označení zdroje s jeho umístěním. Účelem indexového souboru je urychlit přístup ke zdrojům a tím zkrátit dobu vyhledávání.

Poznámka: Slovo index se používá v mnoha různých významech - viz rozcestník na Wikipedii.

klad:

• urychluje přístup k datům (zkracuje dobu vyhledávání)
• umožňuje vyhledávat podle více hledisek

zápor:

• zabírá místo
• údržba indexu zpomaluje práci při aktualizaci primárního souboru

indexovaný soubor:

primární soubor není setříděn (sekvenční vyhledávání)

index-sekvenční vyhledávání (ISAM - index-sequential access method):

primární soubor je sekvenčně setříděn (zkrácené vyhledávání)

Typy indexů

Termínové indexy

a) strukturovaný - fulltextový

1. Plnotextový (fulltextový) index

index s rozdělením víceslovných výrazů na jednotlivá slova

vyhledávaná jednotka: text (dokument), příp. jeho část

složení:

1. slovo
2. pořadové číslo dokumentu v kolekci
3. pořadí slova v rámci dokumentu (příp. v rámci elementu)

Příklad: Plnotextový index vytvořený pro záznamy knih

Číslo záznamu/dokumentu	Text
116	Čapek, Karel. Loupežník. 31. 1958
117	Apollinaire, Guillaume. Pražský chodec. 60. 1984
118	Hartwigová, Julia. Apollinaire. 48. 1967
119	Čapek, Karel. R.U.R. 32. 1962
120	Čapek, Karel. Krakatit. 48. 1958
121	Dostojevskij, Fjodor Michajlovič. Idiot. 120. 1984
122	Čapek, Karel. Věc Makropulos. 48. 1967
123	Hrabal, Bohumil. Pábitelé. 1967
124	Čapek, Karel. Život a dílo skladatele Foltýna. 32. 1978
125	Hrabal, Bohumil. Ostře sledované vlaky. 32. 1978
126	Hrabal, Bohumil. Inzerát na dům, ve kterém už nechci bydlet. 1967
127	Apollinaire, Guillaume. Kaligramy. 32. 1962
128	Orwell, George. 1984. 32. 1991
129	Olbracht, Ivan. Nikola Šuhaj loupežník. 25. 1962

Slovo	Číslo záznamu/dokumentu	Pořadí v dokumentu
120	121	5
1958	116	5
	120	5
1962	119	5
	127	5
	129	7
1967	118	5
	123	4
	126	11
1978	124	1
1984	117	1
	121	1
	128	1
1991	128	1
25	129	1
31	116	1
32	119	1
	124	1
	125	1
	127	1
	128	1
48	118	1
	120	1
	122	1
60	117	1
a	124	2
Apollinaire	117	1
	118	1
	127	1
Bohumil	123	2
	125	2
	126	2
bydlet	126	8
Čapek	116	1
	119	1
	120	1
	122	1
	124	1
dílo	124	3
Dostojevskij	121	1
dům	126	3
Fjodor	121	2
Foltýna	124	5
George	128	2
Guillaume	117	2
	127	2
Hartwigová	118	1
Hrabal	123	1
	125	1
	126	1
chodec	117	2
Idiot	121	1
Inzerát	126	1
Ivan	129	2
Julia	118	2
Kaligramy	127	1
Karel	116	2
	119	2
	120	2
	122	2
	124	2
Krakatit	120	1
kterém	126	5
loupežník	129	3
Loupežník	116	1
Makropulos	122	2
Michajlovič	121	3
na	126	2
nechci	126	7
Nikola	129	1
Olbracht	129	1
Orwell	128	1
Ostře	125	1
Pábitelé	123	1
Pražský	117	1
R.U.R.	119	1
skladatele	124	4
sledované	125	2
Šuhaj	129	2
už	126	6
ve	126	4
Věc	122	1
vlaky	125	3
Život	124	1

2. Strukturovaný index

klasický index relační databáze (s celými hodnotami atributů/položek)

vyhledávaná jednotka: záznam

složení:

1. hodnota atributu/pole
2. pořadové číslo záznamu v souboru
3. pořadové číslo pole nebo název pole v záznamu

Příklad: Strukturovaný index vytvořený pro záznamy knih

Základní soubor						Index
Číslo záznamu	Autor	Název	Cena	Rok vydání		Hodnota pole	Číslo záznamu	Název pole
116	Čapek, Karel	Loupežník	31	1958		120	121	Cena
117	Apollinaire, Guillaume	Pražský chodec	60	1984		1958	116	Rok vydání
118	Hartwigová, Julia	Apollinaire	48	1967			120	Rok vydání
119	Čapek, Karel	R.U.R	32	1962		1962	119	Rok vydání
120	Čapek, Karel	Krakatit	48	1958			127	Rok vydání
121	Dostojevskij, Fjodor Michajlovič	Idiot	120	1984			129	Rok vydání
122	Čapek, Karel	Věc Makropulos	48			1967	118	Rok vydání
123	Hrabal, Bohumil	Pábitelé		1967			123	Rok vydání
124	Čapek, Karel	Život a dílo skladatele Foltýna	32	1978			126	Rok vydání
125	Hrabal, Bohumil	Ostře sledované vlaky	32			1978	124	Rok vydání
126	Hrabal, Bohumil	Inzerát na dům, ve kterém už nechci bydlet		1967		1984	117	Rok vydání
127	Apollinaire, Guillaume	Kaligramy	32	1962			121	Rok vydání
128	Orwell, George	1984	32	1991			128	Název
129	Olbracht, Ivan	Nikola Šuhaj loupežník	25	1962		1991	128	Rok vydání
						25	129	Cena
						31	116	Cena
						32	119	Cena
							124	Cena
							125	Cena
							127	Cena
							128	Cena
						48	118	Cena
							120	Cena
							122	Cena
						60	117	Cena
						Apollinaire	118	Název
						Apollinaire, Guillaume	117	Autor
							127	Autor
						Čapek, Karel	116	Autor
							119	Autor
							120	Autor
							122	Autor
							124	Autor
						Dostojevskij, Fjodor Michajlovič	121	Autor
						Hartwigová, Julia	118	Autor
						Hrabal, Bohumil	123	Autor
							125	Autor
							126	Autor
						Idiot	121	Název
						Inzerát na dům, ve kterém už nechci bydlet	126	Název
						Kaligramy	127	Název
						Krakatit	120	Název
						Loupežník	116	Název
						Nikola Šuhaj loupežník	129	Název
						Olbracht, Ivan	129	Autor
						Orwell, George	128	Autor
						Ostře sledované vlaky	125	Název
						Pábitelé	123	Název
						Pražský chodec	117	Název
						R.U.R	119	Název
						Věc Makropulos	122	Název
						Život a dílo skladatele Foltýna	124	Název

b) index z 1 pole (elementu) - index z více polí (elementů)

1. Index vytvořený z hodnot 1 pole (elementu)

Příklad: Index vytvořený z hodnot pole NÁZEV

2. Index vytvořený z hodnot více polí (elementů)

• složený index (původní položky zůstanou zachovány, třídí se kaskádovitě)
• hodnoty různých polí (elementů) jsou umístěny do stejného pole indexového souboru

Příklad: Složený index vytvořený z hodnot polí AUTOR a NÁZEV

Využití indexového souboru pro kontextové operátory

a) operátor proximity

podmínka vzdálenosti se vyhodnocuje přes absolutní hodnocení rozdílu pořadí slov

b) operátor pořadí

podmínka pořadí je vyhodnocována na základě větší velikosti čísla udávajícího pořadí slov