Struktury informačních zdrojů: studijní opora
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í  |
||||
 |
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