7. Indexový soubor

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í
sipka
sipka2 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

algor1

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.

algor2

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.

algor3

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.

algor4

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.

index1

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ů

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
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
AutorNázevCenaRok
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

index2

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

index3

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