Forrás alapú kereső rendszer az Interneten



Nagy Tamás <bigtom@avalon.aut.bme.hu>

BME, Automatizálási és Alk. Informatikai Tanszék



A kulcs a web robot

Ha áttekintjük a web keresési metódusait, akkor különböző keresési feladatokat, feladat osztályokat különböztethetünk meg, ám megvizsgálva őket, mindegyikről kiderül, hogy működésének kulcsa, valamilyen web robot. A legismertebb, leggyakrabban használt keresési metódus, az indexelt adatbázisokon alapuló keresés, ahol teljesen természetes, hogy az információ gyűjtést, az oldalak felindexelését a web robotok végzik. Ugyancsak web robotok végzik az egyes oldalak változásainak a figyelését, amely – mint azt korábban már megállapítottuk – minden egyéb keresési módszer esetén megtalálható mint részfeladat. Számtalan próbálkozás van a keresés hatékonyabbá tételére, ám – bár különböző kontextusokban –, ezekben az esetekben is mindig megtalálható a háttérben megbújó web robot, aki az információ lokalizációs és elemzési feladatokat végzi, végül természetesen nem maradhatnak ki a felsorolásból azok a feladatok, amelyek számára az információ valamilyen rendszer működési minősége, hibái, számosságai, a feladatuk pedig statisztikai, hiba keresési és karbantartó jellegűek, ám a web robotok mint felhasznált eszközök nélkül képtelenek lennének a feladatuk ellátására.













A sokféle feladatosztály létezésének oka egyrészt a sokféle feladat típus, másrészt és leginkább az a tény, hogy a jelenlegi keresési módszerek rossz hatékonyságúak, ezért szüntelenül új és új módszerek jelennek meg, amelyek valamilyen irányban megoldást próbálnak mutatni. Jellemző, hogy az újabb módszerek a legtöbb esetben nem futnak be jelentős karriert, sőt rendszerint hamar feledésbe merülnek, és jóformán az egyetlen olyan módszer, ami a mai napig fejlődik, és ami széles tömegek által vált ismertté az az indexelt adatbázisokon alapuló keresés. Bár ez a módszer talán a legvitatottabb, érdemes közelebbről is megvizsgálni, mert a módszer vizsgálata során néhány igen értékes, és az egyéb – talán hasznosabb – keresési módszerek számára is hasznos tapasztalatra lehet szert tenni.

Egy lehetséges indexelt adatbázis alapú kereső architektúrális elemzése

Egy általános indexelt adatbázis alapú rendszer logikailag három lényeges részre bontható. Az első egység feladata az Interneten található adatok gyűjtése, letöltése, elemzése. A második egység maga az adatbázis, ahol az adatok találhatók, valamint az adatbázis kiszolgálására alkalmas menedzser (Itt történik tehát az adatok kezelése). A harmadik egység a felület, amely a felhasználóval kommunikál, amely a keresési kéréseket gyűjti feldolgozza és szükség esetén az adatbázishoz továbbítja.

A jelen architektúrában a lényeges az első logikai egység, hiszen itt történik a keresés, itt dolgoznak a web robotok. Legalább két eltérő feladatú robotra van szükség Az első kizárólag a lehetséges címek gyűjtését végzi és saját adatbázissal rendelkezik a már megtalált oldalakról. A második robot az oldalak változásait ellenőrzi, szintén saját adatbázissal az oldalak eddigi állapotáról amelyet egy vagy több ellenőrző összeg ír le.

Ezen felül természetesen szükséges egy indexelő alkalmazás is, amely az első robot által talált, vagy a második robot által megváltozottnak talált oldalakon dolgozik, azokat elemzi és a lekérdezésekhez – a felhasználói kérések kiszolgálásához – használt adatbázist megfelelően frissíti. Jellemző, hogy ennek az adatbázisnak a struktúrája – és így a rendszer teljesítményével kapcsolatos paraméter együttes – erősen függ a választott indexelési módszertől.

Az architektúra elemzésének a tanulsága, hogy a keresés szűken vett feladata is – az információhoz jutás – legalább három különböző típusú alkalmazást – web robotot – igényel, egyet, aki oldalakat keres (lokalizál), egyet aki az oldalak változásait követi nyomon, és egyet aki a tartalmat elemzi. Természetesen különböző keresési elképzelések esetén a három feladat alkalmazáshoz rendelése nem mindig ilyen egyértelmű, de mindig megfigyelhetők az egyes alkalmazásokon belül a vázoltakhoz hasonló funkciójú elemek, mint ahogy az előző példában nem kifejezetten robot szerű részfeladat, az oldal elemzés, indexelés is sokszor szerepel más feladatú web robotokban egyéb feladatok megoldás implementációjának részeként.

A lokalizálás problémái

Az indexelt adatbázis alapú keresés egyik kulcs lépése annak az információnak az összegyűjtése, hogy mely web címeken létezik web oldal. A probléma a kereséssel kapcsolatos speciális megközelítés miatt elsődlegesen fontos, ugyanis az indexelt keresők célja minden létező web oldal feltérképezése, de látni fogjuk, hogy a felmerülő problémák, és a belőlük adódó következtetések más keresési struktúrákban is kiemelt fontosságot kapnak.

A lokalizációs célú web robotok az Internet oldalait szélességi kereséssel keresik. Ha egy oldalt kiinduló pontnak tekintünk, akkor a web robot minden az oldalon található link által mutatott irányban megpróbálja bejárni a webet. A bejárás akkor ér véget, ha az aktuális oldalon nincs egyetlen további kapcsolat, illetőleg, ha a további kapcsolatok és az általuk megjelölt címek már mind megtalálhatók az adatbázisban.

A lokalizálás eme módszeréből több dolog is következik. Az a weboldal, amelyekre a külvilágból egyetlen kapcsolat sem mutat, a lokalizációs web robotok számára láthatatlan marad. Ugyanakkor az is megállapítható, hogy azokra az oldalakra nem mutat semmilyen külső kapcsolat, amelyek egyedülálló oldalak, vagy kis elszigetelt oldalcsoport részei. Ezzel ellentétben azokat az oldalakat, melyek egy valamely jól ismert oldalcsoporthoz tartoznak, nem csak, hogy megtalálják, de meglepően rövid idő alatt megtalálják a kereső szerverek robotjai. Ez pedig azt jelenti, hogy a web egyre inkább két részre oszthatóvá válik, egyik oldalon vannak az ismert, illetőleg a hozzájuk kapcsolódó oldalak, melyek a keresők, és így a teljes Internetes társadalom számára láthatók, másik oldalon pedig az ismeretlen, az egyszerű felhasználók, vagy kis vállalkozások által létesített oldalak, melyek az Internet nagy része számára sötétben maradnak. A helyzet kiélezettségét tovább növeli a tény, hogy a keresők robotjai egyre kevésbé képesek felvenni a tempót az Internet növekedési ütemével, tehát egyre kevesebb energiát képesek a “kis” oldalak felkutatásába fektetni, miközben nagyon sok információ esetleg csak ezeken az oldalakon érhető el.

A probléma megoldása meglehetősen összetett feladat, de lehetséges olyan módszert kidolgozni, ami a létező web oldalak túlnyomó többsége esetén garantálná azok megtalálhatóságát. A megoldás alapja a Domain Name Service, amely egy bárki által hozzáférhető adatbázis, amelyben a létező – regisztrált – szerver nevek találhatók meg. Ennek felhasználásával már meg lehetne találni a web szerverek nagy többségét. Nem mindet, hiszen lehet DNS-be nem regisztrált gépen is web szerver, és bejegyzett gépen is lehet nem 80-as portra tenni web szervert, így az továbbra is elrejthető, de az alapvetően a nyilvánosságnak szánt kiszolgálók elérhetőek lennének. Természetesen ez még korántsem minden, hiszen önmagában a web kiszolgálók megtalálása nem garantálja a rajta található oldalak megtalálását is, hiszen azok tetszőleges könyvtárakban és neveken szerepelhetnek. De kifejleszthető lenne egy olyan web szerver architektúra, amelynél a web szerver egy speciális kérésre vissza adja az általa eddig kiszolgált minden egyes oldal elérhetőségét. Ehhez a módszerhez természetesen a web kiszolgálók felépítésén kellene változtatni – nyilvánvalóan meghagyva a lehetőségét annak, hogy amennyiben egy felhasználó egy oldaláról nem szeretné, hogy az a keresők számára elérhető legyen, akkor annak az oldalnak az ilyen kiadása meggátolható legyen –, de a változtatás egyértelműen hasznos lenne, hiszen megszüntetné a web megosztottságát és enyhítene az adatbázis alapú keresők leterheltségén.

Oldalak dinamizmus szerinti osztályozása

Az Internet oldalai változékonyság szempontjából kategóriákra oszthatók. Vannak oldalak, melyek statikusak, sohasem változnak. Nyilvánvalóan fölösleges ezen oldalak változásainak figyelésébe komoly energiát fektetni. Vannak oldalak, amelyek ritkán változnak bár, de a tartalmuk mégsem tekinthető állandónak, ezeknél az oldalaknál tehát már fontos a változások figyelemmel kisérése, ugyanakkor fontos azt is észre venni, hogy – a ritka változások miatt – elegendő ritkán ránézni a lapokra. Hogy mégis milyen ritkán az persze szoros kapcsolatban van a változások gyakoriságával, ezért érdemes az oldalakat dinamizmus szerint osztályozni. Ha valamely oldal az aktuális dinamizmus osztályánál jóval régebben változott, akkor egy osztállyal feljebb kell sorolni, ha azonban rövidebb idő alatt változott, mint ahogy az dinamizmus osztálya szerint változnia kellett volna, akkor egyel lejjebb kell sorolni. Az osztályozás legalján a leggyakrabban változó oldalak találhatóak. Ezeket kell a leggyakrabban – akár percenként – újra ellenőrizni, hiszen tartalmuk folyamatosan változik. A gyakori ellenőrzések gyakori adatbázis változtatás szükségességét is jelentik, ami nagy terhelést jelenthet, ám ettől megfelelően kialakított rendszerek esetén nem kell tartani, mert viszonylag kevés olyan oldal (portál) létezik aki nagyon gyakran változik, hiszen a gyakori változtatás nagy energiákat emészt fel a szolgáltatás oldaláról is. Mindez azt jelenti, hogy a dinamizmus szerinti osztályozással megoldható a keresők változó oldalakkal kapcsolatos problémái.

Az indexeléssel kapcsolatos problémák egy lehetséges megoldása

Az indexelt adatbázison alapuló keresés rossz hatékonysága tény. Ezen lehet javítani különböző szűrők alkalmazásával, amik akár előre, még az indexeléskor, de főleg utólag keresésre adott válasz listázásakor leellenőrzik, és szűrik az oldalakat. A szűrés sok mindenre irányulhat. Nyilvánvalóan ki kell hagyni azokat az oldalakat, amelyek már nem léteznek, vagy amelyekről eldönthető, hogy igazából érdektelenek (bár a kereset szó megtalálható rajta). Külön kezelést érdemel azon oldalak köre, amelyekről az ellenőrzéskor kiderül, hogy tartalma nem egyezik az indexeléskori tartalmával. Ilyenkor az oldalt újra indexelni kell, és csak akkor adható meg egy találati listában, ha a változás ellenére szerepel rajta a keresett információ. Ez a fajta szűrés a dinamizmus osztályozással együttműködésben is jól alkalmazható.

Szintén alkalmas a találatok minőségének a javítására a találatok megjelenítésének rendezése és megfelelő formázása. Ez akkor eredményez javulást, ha egy adott oldal csoport több eleme is megjelenítendő a listán, és akkor a rendezés és a megfelelő megjelenítés eredményeképpen (lásd: google – www.google.com) a megjelenített lista nem lesz tele fölöslegesen egy oldal csoport sok elemével.

Javíthat a hatékonyságon az indexelési módszerek változtatása, fejlesztése is, a fő probléma azonban továbbra is az, hogy az ilyen rendszerű keresőkben a web robot az adatgyűjtés során nem rendelkezik információval a valódi keresések tárgyáról. Ez nyilvánvalóan óriási hátrány, hiszen ez azt jelenti, hogy valójában nem lehetséges olyan index adatbázis összeállítása, amely a web egészét képes jó minőségben leírni. Ez azt is jelenti, hogy az ilyen módszerek minden előnye ellenére mindenképpen helyük van olyan új keresési stratégiáknak és modelleknek, amelyek egy más megközelítésben lehetőséget adnak arra, hogy a web robot pontosan azt keresse, amit a felhasználó keresni akar. Természetesen ez lerontja a keresés real-time jellegét, ez az ár amit a jobb minőségért fizetni kell, de ez sok esetben megfizethető.

Információ forrás központú kereső rendszer

A kereső rendszer központi eleme az információ forrás – források –, és a címét tároló adatbázis. Az információ forrás egy web oldal. Egy olyan web oldal, amelyen keresztül egy adott típusú információt gyorsabban, hamarabb talál meg egy web robot, mint egy más web oldal közvetítésével. Az indexelt adatbázis alapú keresők például tekinthetők információ forrásnak, mégpedig általános információ forrásnak, hiszen a legtöbb információ esetén valószínűleg közelebb visznek az információ megtalálásához, mint általában egy másik oldal. Ugyanakkor vannak speciális tudások, amelyekhez bizonyos oldalakon keresztül hamarabb eljutni, mint a keresőkön keresztül – mert esetleg a keresők is ezeket az oldalakat adják meg az adott téma keresése esetén. A cél egy olyan adatbázis fölállítása és folyamatos tovább építése, ahol nem az indexelt adatok találhatók, hanem azoknak az oldalaknak a címei, amelyek információ forrásként felhasználhatók. Az adatbázis találatai nem pontos eredmények, csak bemenetek egy web robot számára, amely így nem tetszőleges oldalakon, hanem célzottan indul el, és próbálja a kérdéses információt megtalálni. Természetesen a forrás adatbázis is folyamatosan változik, hiszen a megtalált vagy érintett oldalak is potenciális források.

Néhány nagyon jelentős különbség van az indexelt adatbázis alapú keresőknél alkalmazott robotok, és az itt használt robot között. Ebben az esetben nincs szükség az oldalak címeinek gyűjtésére, hiszen a robot folyamatosan halad, lépésről lépésre, csak azért kell bizonyos címeket eltárolni, hogy tudható legyen mely oldalakon járt már a robot. Bár az információs forrás adatbázist folyamatosan frissen kell tartani, az oldalak hagyományos értelemben vett dinamizmusa itt nem jelent problémát, hiszen a robot mindig a legfrissebb oldalakat elemzi. Végül az oldal elemzés is jóval egyszerűbb így, hiszen a megválaszolandó kérdés nem az, hogy mi van az oldalon, hanem, hogy mennyire felelnek meg az oldalon találtak a keresési kritériumoknak. Ez nyilván egy jóval egyszerűbb feladat, mi több a kapott eredmények is jól rangsorolhatók, aminek végső soron jobb minőségű lista lehet a következménye.

Források:

Mark Watson

Mark S. Ackerman, Brian Starr, Michael Pazzani

Martijn Koster http://info.webcrawler.com/mak/projects/robots/eval.html

Martijn Koster http://info.webcrawler.com/mak/projects/robots/guidelines.html

Mitsuyuki Inaba

http://info.webcrawler.com/mak/projects/robots/norobots.html