Informacijos paieška

Pradėjęs 1991-aisiais kaip CERN bendro naudojimo dokumentų apie branduolinę fiziką sistema, WWW virto begaliniu informacijos vandenynu su asmeninėmis svetainėmis, elektroninėmis bibliotekomis, menamos tikrovės (virtualiais) muziejais, gaminių, prekių ir paslaugų katalogais, vyriausybinių organizacijų žiniomis, mokslinių tyrimų ataskaitomis, straipsniais ir apžvalgomis, failų (FTP), naujienų (“Usenet”) ir el. pašto stotimis. Kai kurios apžvalgos teigia, kad šiuo metu yra apie 150 mln. WWW puslapių ir jų skaičius padvigubėja kas 4 mėnesiai (tik aš nežinau, ar teikiant tuos skaičius atsižvelgiama į “mirusius” puslapius, nes paieškos sistemų atsakymuose sutinku nepaprastai daug nuorodų į neegzistuojančius puslapius.

Ypatingą svarbą turi veiksminga informacijos paieška ir pateikimas. Naudojant galingus kompiuterius ir lygiagrečiųjų skaičiavimų technologiją, greitis jau nėra problema – dabartinės paieškos sistemos per kelių gigabaitų apimties indeksus “perbėga” per sekundės dalis. Tačiau paieškos efektyvumo įvertinimui reikia taikyti kitus kriterijus, nes dažnai pateikiama per daug dokumentų, iš kurių tinka tik keli – ir net neužtikrinama, kad tie keli būtų “iškilę” į sąrašo pradžią (ankstesniuose straipsniuose buvo aptariamos ne tik pačios paieškos sistemos, bet ir būdai, kaip efektyviai “pataikyti į dešimtuką” – tų straipsnių sąvadą rasite “Vartiklyje”.

Mažai žinoma apie komercinių paieškos sistemų architektūrą, informacijos apdorojimo metodus ir užklausų vykdymo strategijas. Toks “nuosavybės” detalių slėpimas padėjo atsirasti požiūriui, kad paieškos sistemos turi daugiau mistikos, nei racionalaus prado.

Kaip klajoti šiame informacijos Voratinklyje? Vienas iš būdų – į ten pasiųsti “robotą” (valkatą, bastūną, kirminą, vorą ar “informatorių”). Šis programinės įrangos gaminys gauna užklausą ir sistemingai peržiūri Voratinklį, ieškodamas užklausą tenkinančių dokumentų, jiems priskirdamas tinkamumo įverčius, ir pateikia surūšiuotą nuorodų sąrašą. Tačiau dėl Voratinklio apimties ir jo plėtimosi tempų, šis metodas nėra praktiškas kiekvienai užklausai.

Kitas būdas – naudoti iš anksto robotų surinktų dokumentų sukompiliuotą indeksų duomenų bazę (DB) – žodžių sąrašą su nuorodomis į WWW puslapius. Šį metodą naudoja dauguma dabartinių paieškos sistemų, kurių robotai nuolat naršo Voratinklį tikrindami visas jame esančias WWW svetaines. Kadangi Voratinklio struktūra yra panaši į vienos krypties kelius turintį grafą, jį galima apeiti naudojant šios (grafų) matematikos srities algoritmus. O kadangi WWW serveriai veikia kliento-serverio architektūros principu, užtenka vieno kompiuterio, kad būtų apkeliautas visas pasaulis. Šiuo metu yra naudojami trys apėjimo metodai:

1. Robotui duodama “sėkla”, t.y. pradinis kurio nors WWW puslapio adresas. Robotas indeksuoja jį, jame suranda visas nuorodas į kitus dokumentus, kuriuos vėliau rekursyviai peržiūri, naudodamas “pirma į gylį” arba “pirma į plotį” strategijas.
2. Pradedama grupe WWW puslapių, kurie atrenkami atsižvelgiant į jų populiarumą. Natūralu tikėtis, kad populiariausios svetainės turi informaciją bei nuorodas, kurios yra patraukliausios daugumai Voratinklio naršytojų.
3. Voratinklis suskaidomas į dalis paal “Internet” tinklų vardus (domenus), šalis ir kitus panašius kriterijus. Kiekvieną dalį apžiūri atskiras (kartais net keli) robotas. Šis metodas taikomas dažniausiai.

Voratinklio peržiūros intensyvumas yra svarbus veiksnys nusakantis sukuriamos DB pilnumą. Informacijos pateikimo sistemos naudoja du duomenų tipus: išorinius (dokumento adresas, autorius, apimtis ir data) bei vidinius (dokumento turinys). Indeksavimas yra procesas, kai dokumento vidiniams objektams priskiriama išoriniai atributai. Jo efektyvumas priklauso nuo dviejų pagrindinių parametrų:

1. indeksavimo nuodugnumo. Galima indeksuoti viską ir atsižvelgi į visus dokumento turinio aspektus – ir dirbti su milžiniškos apimties DB, o galima indeksuoti tik pagrindinius (raktinius) dokumento elementus;
2. terminų išskirtinumo, kai, atsakant į užklausą, pateikiama arba daugybė dokumentų (kuriuos visus sunku peržiūrėti) arba tik keletas, bet labiausiai tinkančių (su pavojumi, kad kuris nors reikalingas bus “pražiopsotas”).  

Idealu būtų, jei būtų įmanoma pateikti didelį dokumentų sąrašą tiksliai surūšiuotą jų tinkamumo tvarka. Tačiau praktikoje reikia ieškoti kompromisų.

Dokumentus indeksuoja arba “gyvas” žmogus arba robotas. Tačiau Voratinklio apimtis tokia, kad gyvi žmonės nėra pajėgūs jį suklasifikuoti (nors jie tai atlieka kokybiškiau). Automatinis indeksavimas nenaudoja griežtai prižiūrimų raktinių žodžių žodynėlių ir gali įsiminti daugiau informacijos apie dokumentą (tačiau išsipučia DB apimtys).

Automatinio indeksavimo metodai

A. Atskiro (vieno) objekto indeksavimas

Dokumento objektų aibė sudaroma iš žodžių, kuriems priskiriamas pasikartojimo dažnis, aibės. Žodžiai, turintys vien gramatines funkcijas (pvz., jungtukai) surašomi į skirtukų sąrašą ir yra pašalinami. Aibė gali būti “apšvarinta” sudarant sąrašus tik pagal žodžių kamienus (atmetant kintančias galūnes).

Atskiriems objektams priskiriant svorius naudojami statistiniai, informacijų teorijos ir tikimybiniai metodai.

1. Statistinis metodas ne tik “išsemia” visą dokumentų aibę, bet ir leidžia spėti, kad dokumentai, kuriuose yra daugiau paieškos užklausoje nurodytų objektų, yra svarbesni. Tegu aibėje A yra N elementų, F i j reiškia O j objekto dažnį D i dokumente, o T j yra bendras O j objekto dažnis aibėje A. Tada O j objekto svoris dokumente D i aprašomas formule

w i j = F i j log ( N / T j)
(čia logaritmas yra atvirkštinis dokumento dažnis, kuris yra svarbus dokumento atmetimui).

Kitas būdas kiekvieną dokumentą ima kaip tašką visoje dokumentų erdvėje. Jei dviejų objektų aibės yra artimos, tai tie taškai toje erdvėje yra arčiau vienas kito (dokumentų erdvės tankis yra didesnis). Tada galima išmatuoti atstumus tarp dokumentų. Objektas yra svarbus dokumento atmetimui, jei jo įtraukimas į dokumento aibę padidina atstumus tarp dokumentų (t.y., mažina erdvės tankį). Tegu E j yra objekto atmetimo reikšmė, kuri paskaičiuojama kaip skirtumas tarp dokumentų erdvės tankių – prieš ir po objekto įtraukimo. Tada objekto svoris paskaičiuojamas taip:

w i j = F i j E j
Pagal šį modelį dažni objektai turi neigiamas atmetimo reikšmes, vidutinio dažnio – teigiamą ir reti – artimi nuliui (atseit, nesvarbūs).

2. Informacijos teorijos modelyje mažiausiai tikėtini objektai turi didžiausią informacinę vertę. Naudojamas signalo triukšmo intensyvumo matas, pagal kurį irgi svarbesni tie dokumentai, į kuriuos objektas įeina po kelis kartus.

3. Tikimybinis modelis reikalauja “mokomosios” dokumentų aibės, kurią nagrinėdamas prašo, kad vartotojas nurodytų objektų svarbumą. Pagal šią aibę analizuojant nustatytus svorius atrenkami objektai, kurie yra svarbūs dokumentui, o kurie ne. Naudojant Bajeso (Bayes) teoremą paskaičiuojamas objekto svoris.

B. Kelių objektų (frazių) indeksavimas

Vieno atskiro objekto indeksavimas nėra tobulas, nesjo reikšmė (svarba) labai priklauso nuo konteksto. Frazių išskyrimas ir indeksavimas padidina paieškos tikslumą. Sinonimų grupių išskyrimas padidina užklausą tenkinančių dokumentų kiekį. Naudojami statistiniai, tikimybiniai ir lingvistiniai metodai.

1. Statistiniame modelyje frazė sudaroma iš “stuburo” (arba galvos), t.y. objekto, kurio dažnis viršija tam tikrą reikšmę, pvz., T > 2. Kiti frazės elementai turi mažesnį dažnį ir yra tam tikru būdu susiję su “stuburu”, pvz., yra tame pačiame sakinyje. Tai leidžia nustatyti, kurios objektų grupės naudojamos skirtinguose dokumentuose.
2. Tikimybiniame modelyje reikia įvertinti didelius objektų kombinacijų kiekius. Tad praktiškai metodas taikomas tik tam tikroms tarpusavyje susijusioms objektų poroms. Be to, tiek statistiniame, tiek tikimybiniame metoduose sudarant frazes neatsižvelgiama į semantiką – tad jie neužtikrina aukštos indeksavimo kokybės.
3. Lingvistiniame modelyje naudojamos žinios apie žodžius (ar tai daiktavardis, veiksmažodis, skaitvardis ar būdvardis). Sudarant frazes atsižvelgiama į reikalavimus sakinio sintaksei (sudaromos frazes: daiktavardis – daiktavardis, būdvardis – daiktavardis ir t.t.)

Informacijos pateikimo modeliai gali būti 4-ių tipų:

1. loginių reikšmių aibių modelyje kiekvienam objektui priskiriamas loginis kintamasis, galintis įgyti tik dvi reikšmes: “Taip”, jei objektas įeina į dokumentą ir “Ne” Visi objektai yra lygiaverčiai, t.y. vienodo svorio. Užklausos yra loginės išraiškos sudaromos naudojant “Arba”, “Ir” bei “Ne” veiksmus. Atsakymas į užklausą gali būti tik 1 (dokumentas tenkina užklausą) arba 0. Tokį modelį nesunku realizuoti ir jį naudoja dauguma komercinių sistemų. Bet jis nėra lankstus, pvz., dokumentas bus atmestas, jei tenkins 4 iš 5 užklausoje esančių sąlygų.

Negriežtos (fuzzy) logikos modelis leidžia dalinę narystę aibėje. Bet neseniai buvo įrodyta, kad negriežtos logikos metodai nedaug veiksmngesni nei griežtos logikos algoritmai. Abu jie taikytini, kai DB saugojimui neišskirta didelio atminties kiekio ir nereikia sudėtingo dokumentų panašumo atpažinimo.

2. Algebrinis arba vektorinės erdvės modelis naudoja prielaidą, kad dokumentai yra tapatūs tam tikros erdvės vektorių aibėms. Jei vektorinė erdvė yra normalizuota pagal N vektorių, tai kiekvienas dokumentas bus vaizduojamas tam tikru N-mačiu vektoriumi. Pirma šio vektoriaus koordinatės reikšmė yra objekto svoris (svarba) tame dokumente ir t.t. Užklausa pateikiama irgi kaip N-matis vektorius ir atsakymas į ją yra dokumento ir užklausos vektorių skaliarinė sandauga. Kuo didesnė ši reikšmė, tuo labiau dokumentas tenkina šią užklausą. Šio modelio jėga yra jo paprastume, tačiau prarandma galimybė formuoti sudėtingas užklausas.

3. Tikimybinis modelis (skirtingai nuo vektorinės erdvės, kuriame laikoma, kad erdvę normalizuojantys vektoriai yra ortogonalūs ir objektų sąryšiai neturi įtakos) atsižvelgia į tuos sąryšius. Jo pagrindas yra du parametrai Tk(sv) ir Tk(nesv) – dokumentų svarbumo ir nesvarbumo tikimybės. Papildomai naudojami du vertės parametrai a 1 ir a 2, nusakantys patiriamus nuostolius dėl nesvarbaus dokumento pateikimo ir dėl svarbaus dokumento “užmiršimo”. Šis metodas yra svarbus ankstesnių empirinių metodų teoriniam pagrindimui.

Paieškos sistemos nuo vartotojo paslepia visą informaciją apie indeksų DB struktūrą ir turinį.

“Altavista” naudoja “Scooter” vorą, ropinėjantį po Voratinklį ir “Usenet” grupes ir indeksuojantį visą dokumento tekstą. META direktyvos puslapio antraštėje yra panaudojamos kaip puslapio aprašas. Indeksų DB atnaujinama bent kartą per dieną. “Scooter” lanko puslapius priklausomai nuo to, kaip dažnai jie keičiasi (puslapis, nesikeitęs kelis mėnesius, bus prisimenamas rečiau, nei puslapis, kuris kiekvieno “Scooter” vizito metu buvo pasikeitęs. Galima indeksavimui pateikti savo WWW svetainės adresą. “Altavista” numato loginę ir frazių paiešką, atsižvelgdama į didžiąsias ir mažąsias raides. Rezultatus pateikia surūšiuotus pagal priskirtas svarbumo reikšmes, kurios paskaičiuojamos atsižvelgiant ar užklausoje nurodyti žodžiai yra dokumento pradžioje (pvz., pavadinime), ar dokumente jie yra netoli vienas kito ir kiek kartų įeina į dokumentą. Pateikiama dokumento antraštė, trumpas aprašymas, dydis ir paskutinio kitimo data.

“HotBot” turi “Slurp” vorą ir lygiagrečiųjų darbo stočių tinklą. Voras iš dokumento ištraukia visus adresus ir juos surašo į tvarkaraštį priskirdamas skirtingus procesorius priklausomai nuo to, kada paskutinį kartą buvo kreiptasi į adrese nurodytą serverį. Vartotojas gali nurodyti ir savo WWW svetainės adresą. Indeksuojami tik HTML ir tekstiniai dokumentai, kurių žod-iams priskiriami svoriai, kurie paskaičiuojami atsižvelgiant į tai, ar jie buvo naudojami META direktyvose. Indeksų DB tinklu išsiuntinėjamos keliems kompiuteriams, kad užklausą būtų galima vykdyti lygiagrečiai. Vartotojai užklausoje gali nurodyti žodžius (taip pat ir tikrinius), frazes arba “Internet” adresus (domenus). Atsižvelgiama į didžiąsias ir mažąsias raides, galima nurodyti ieškomo objekto formatą (pvz., GIF piešinį). “HotBot” pateikia dokumento paskutinio keitimo datą ir keletą pirmųjų jo eilučių (santrumpą).

“Lycos” robotas “protingai” klajoja po Voratinklį, įsimindamas dokumente esančių nuorodų sąrašą, iš kurio išsirenka vieną kurią tolimesnei paieškai. Viena iš jo naudojamų “gudrybių” yra nueiti į serverio pagrindinį puslapį. Jam galima pateikti ir savosios WWW svetainės adresą. Indeksuojama HTML, FTP ir “Gopher” dokumentų antraštės ir pavadinimai. Įsimenama tik 100 objektų, turinčių didžiausią svorį (ir 20 pirmųjų teksto eilučių), dokumento dydis ir žodžių kiekis. Svoris paskaičiuojamas kaip visų užklausoje pateiktų svorių suma. Skaičiuojant svorį turi įtakos, ar objektas buvo antraštėje ir jo atstumas iki dokumento pradžios. Yra režimas pasirinkimui tarp atitikimo kuriam nors vienam žodžiui, visiems žodžiams ir kažkuriam žodžių kiekiui. Galima nurodyti paiešką pagal žodžio fragmentą ir be galo mažą, silpną, artimą, gerą ir puikų dokumento sutapimo su užklausa laipsnį. Užklausoje galima naudoti loginio neigimo operatorių.

Yra dar daug kitų paieškos sistemų, bet jei aptartume kiekvienos jų galimybes, tektų pernelyg dažnai kartotis. Daugiau informacijos apie jas rasite jau minėto “Vartiklio” puslapio nuorodose. Čia tik išvardinsime populiaresniąsias iš jų:
“Yahoo!”
“Planet Search”
“Magelan”
Infoseek Guide
Excite
“WWW Virtual Library”
“Galaxy”
“IBM InfoMarket”
“OpenText”
“WebCrawler”
“World Wide Web Worm”
“MetaCrawler”
“Starting Point”
“Dogpile”
ir kitos.

Išvados

Dabartinės paieškos sistemos dar neužtikrina ypatingai geros kokybės, nes didesnį dėmesį skiria paieškos greičiui ir indeksų DB dydžiui. Iš dalies tai paaiškinama tuo, kad HTML kalba teikė nedaug galimybių turinio aprašymui (jos sukūrimo tikslas buvo užtikrinti dokumento pateikimą kuo didesniam įrenginių tipų kiekiui). Tik HTML 3 versija pasipildė META direktyvomis, leidžiančiomis aprašyti svarbią informaciją, pvz., naudojamą kodavimo lentelę, raktinius žodžius ir trumpą dokumento aprašą. Paskutiniu metu sustiprėjo dėmesys teksto priskyrimui vienai kuriai (ar kelioms) kategorijoms ar temoms (pvz., “Laisvalaikis” ir “Sportas”).