A keresési index egy olyan adatstruktúra , amely dokumentumokkal kapcsolatos információkat tartalmaz, és a keresőmotorokban használatos . A keresőmotor által végzett indexelés az adatok gyűjtésének, rendezésének és tárolásának folyamata a gyors és pontos információ-visszakeresés érdekében . Az index létrehozása a nyelvészet , a kognitív pszichológia , a matematika , a számítástechnika és a fizika interdiszciplináris fogalmait foglalja magában . A webindexelés a weboldalak keresésére tervezett keresőmotorok indexelési folyamatára utal .az interneten.
A népszerű keresőmotorok a természetes nyelveken írt dokumentumok teljes szöveges indexelésére összpontosítanak [1] . A keresésben olyan multimédiás dokumentumok is részt vehetnek, mint a videó és hang [2] , valamint a grafikák [3] [4] .
A metakeresők más keresőmotorok indexeit használják, és nem tárolnak helyi indexet, míg a gyorsítótárazott oldalakon alapuló keresőmotorok hosszú ideig tárolják az indexet és a szöveges korpuszokat is . A teljes szövegű indexekkel ellentétben a részleges szöveges szolgáltatások korlátozzák az indexelési mélységet, hogy csökkentsék az index méretét. A nagyobb szolgáltatások általában egy adott időkereten belül indexelnek a feldolgozási idő és a költségek miatt, míg az ügynökalapú keresőmotorok valós időben építik fel az indexet .
Az index használatának célja, hogy felgyorsítsa a keresési lekérdezéshez releváns dokumentumok megtalálását . Index nélkül a keresőmotornak minden dokumentumot fel kellene térképeznie a korpuszban, ami sok időt és feldolgozási energiát igényelne. Például míg egy 10 000 dokumentumból álló index ezredmásodperceken belül lekérdezhető, 10 000 nagy dokumentum minden egyes szavának szekvenciális beolvasása órákig tarthat. Az index tárolására lefoglalt további memóriát és az index frissítéséhez szükséges időnövekedést ellensúlyozza az információkereséshez szükséges idő csökkenése.
A keresőmotor tervezésekor a következő tényezőket kell figyelembe venni:
Összefolyási tényezők Hogyan szerepelnek az adatok az indexben? Hogyan kerülnek a szavak és az alfüggvények az indexbe a szövegkorpusz bejárása során? És több bejáró is működhet aszinkron módon? A bejárónak először ellenőriznie kell, hogy frissít-e régi tartalmat, vagy új tartalmat ad-e hozzá. A keresőmotor- index egyesítése hasonló az SQL Merge -hez és más egyesítő algoritmusokhoz [5] . Tárolási módszerek Hogyan tároljunk indexelt adatokat ? Vagyis meghatározzák a tárolt információ típusát: tömörített vagy szűrt. Index mérete Mennyi számítógépmemória szükséges egy index fenntartásához. Keresés sebessége Milyen gyorsan található egy szó egy fordított indexben . A számítástechnika számára fontos, hogy összehasonlítsa az adatstruktúrában lévő rekord megtalálásának sebességét az index frissítésének/törlésének sebességével. Tárolás Az index hosszú távú tárolása [6] . hibatűrés Fontos, hogy a keresőszolgáltatás megbízható legyen. A hibatűrési problémák közé tartozik az index sérülésének kérdése, annak meghatározása, hogy a rossz hardverhez kapcsolódó hibás adatok, a particionálás és a hash függvényeken alapuló sémák és az összetett particionálás [7] , valamint a replikáció külön kezelhető-e .A keresőmotor architektúrája különbözik az indexelési módszerekben és az indextárolási módokban, kielégítve a tényezőket . Az indexek a következő típusúak:
utótag fa Képletesen faként strukturált , támogatja a lineáris keresési időt. A szóutótagok tárolására épült. A fák támogatják a fejlett kivonatolást, ami fontos a keresőmotorok indexeléséhez [8] . A DNS-szekvenciák mintaillesztésére és klaszterezésre használják . A fő hátrány az, hogy egy szó fában való tárolása több helyet igényelhet, mint amennyi magának a szónak a tárolásához szükséges [9] . Egy alternatív ábrázolás egy utótag tömb . Úgy gondolják, hogy kevesebb virtuális memóriát igényel, és támogatja a blokk szerinti adattömörítést. Fordított index Tárolja az egyes keresési kifejezések előfordulási listáját [10] , általában hash-táblázatok vagy bináris fa formájában [11] [12] . Hivatkozási index Hivatkozások vagy dokumentumok közötti hiperhivatkozások tárháza a hivatkozáselemzés támogatására, a bibliometria tárgya . N-gramm Adathosszúságú sorozatok tárolása más típusú keresés vagy szövegelemzés támogatására [13] . Dokumentum kifejezés mátrix A látens szemantikai elemzésben (LSA) használatos, kétdimenziós ritka mátrixban tárolja a szavak előfordulását a dokumentumokban .A keresőmotorok tervezésének egyik fő feladata a szekvenciális számítási folyamatok menedzselése. Vannak helyzetek, amikor versenyfeltételeket és összefüggő kudarcokat lehet teremteni. Például egy új dokumentumot adnak hozzá egy korpuszhoz, és frissíteni kell az indexet, ugyanakkor az indexnek továbbra is válaszolnia kell a keresésekre. Ez két egymással versengő feladat ütközése. Úgy gondolják, hogy a szerzők az információk előállítói, és a bejáró ennek az információnak a fogyasztója, rögzíti a szöveget és tárolja a gyorsítótárban (vagy korpuszban). A direkt index a korpusz által előállított információ fogyasztója, a fordított index pedig a közvetlen index által előállított információ fogyasztója. Ezt általában termelő-fogyasztó modellnek nevezik . Az indexelő a kereshető információ előállítója, az azt kereső felhasználók pedig a fogyasztók. A problémát súlyosbítja az elosztott tárolás és az elosztott feldolgozás. Nagy mennyiségű indexelt információ skálázásához a keresőmotor elosztott számítási architektúrán alapulhat , ahol a keresőmotor több, egymással összehangoltan működő gépből áll. Ez növeli a logikátlanság valószínűségét, és megnehezíti a teljesen szinkronizált, elosztott, párhuzamos architektúra fenntartását [14] .
A továbbítási index az egyes dokumentumokhoz tartozó szavak listáját tárolja. A következő a közvetlen index egyszerűsített formája:
közvetlen index| Dokumentum | A szavak |
|---|---|
| 1. dokumentum | a mi, Tanya, hangosan, sírva |
| 2. dokumentum | leesett, be, folyó, labda |
| 3. dokumentum | hallgass, Tanechka, ne sírj! |
| 4. dokumentum | nem, megfullad, be, folyó, labda |
A közvetlen index kialakításának oka, hogy a szavakat célszerű azonnal a dokumentumok mögé tárolni, mivel azokat később elemezve keresési indexet készítenek. A továbbított indexgenerálás aszinkron rendszerfeldolgozást foglal magában, amely részben megkerüli a fordított indexfrissítési szűk keresztmetszetet [15] . A közvetlen index úgy van rendezve , hogy fordítsa át az indexet. A közvetlen index lényegében dokumentumok és szavak párjainak listája, dokumentumok szerint rendezve. A közvetlen index invertálttá alakítása csak a szópárok rendezésének kérdése. Ebből a szempontból az invertált index szó szerint rendezett közvetlen index.
Sok keresőmotor fordított indexet használ a keresési lekérdezés kiértékelésekor, hogy gyorsan megtalálja a lekérdezésben szereplő szavakat tartalmazó dokumentumokat, majd ezeket a dokumentumokat relevancia szerint rangsorolja . Mivel a fordított index az egyes szavakat tartalmazó dokumentumok listáját tárolja, a keresőmotor közvetlen hozzáféréssel megkeresheti a lekérdezésben szereplő egyes szavakhoz társított dokumentumokat, és gyorsan visszakeresheti azokat. Az alábbiakban a fordított index egyszerűsített ábrázolása látható:
Fordított index| Szó | A dokumentumok |
|---|---|
| ban ben | 2. dokumentum, 4. dokumentum |
| hangosan | 1. dokumentum |
| labda | 2. dokumentum, 4. dokumentum |
| a miénk | 1. dokumentum |
| nem | 3. dokumentum, 4. dokumentum |
| kiáltás | 1. dokumentum, 3. dokumentum |
| folyó | 2. dokumentum, 4. dokumentum |
| Tanya | 1. dokumentum, 3. dokumentum |
| csendes | 3. dokumentum |
| csepp | 2. dokumentum |
| megfullad | 4. dokumentum |
Az invertált index csak azt tudja meghatározni, hogy egy szó létezik-e egy adott dokumentumon belül, mivel nem tárol semmilyen információt a szó gyakoriságáról és helyzetéről, ezért logikai indexnek minősül. Az invertált index meghatározza, hogy mely dokumentumok felelnek meg a lekérdezésnek, de nem értékeli ki a megfelelő dokumentumokat. Bizonyos esetekben az index további információkat is tartalmaz, például az egyes szavak gyakoriságát az egyes dokumentumokban, vagy a szó pozícióját a dokumentumban [16] . A szópozíció információ lehetővé teszi a keresési algoritmus számára, hogy azonosítsa a szó közelségét a kifejezéskeresés támogatása érdekében. A gyakoriság segítségével a dokumentumok rangsorolhatók egy lekérdezéshez. Ilyen témák állnak az információkeresési kutatások középpontjában.
Az invertált indexet ritka mátrix képviseli, mivel nem minden szó szerepel minden dokumentumban. Az index hasonló az LSA-ban használt dokumentumkifejezés-mátrixhoz. Az invertált index felfogható egy hash-tábla formájának. Egyes esetekben az index bináris fa formájában van, amely további memóriát igényel, de csökkentheti a keresési időt. Nagy indexeknél az architektúrát általában egy elosztott hash tábla reprezentálja [17] .
Az invertált indexet egyesítés vagy visszaállítás tölti fel. Az architektúra úgy tervezhető, hogy támogassa a növekményes indexelést [18] [19] , ahol az összevonás meghatározza a hozzáadandó vagy frissítendő dokumentumot vagy dokumentumokat, majd minden dokumentumot szavakba elemez. A technikai pontosság érdekében az egyesítés egyesíti az újonnan indexelt dokumentumokat, amelyek általában a virtuális memóriában találhatók , egy index-gyorsítótárral, amely a számítógép egy vagy több merevlemezén található .
Az elemzés után az indexelő hozzáadja a megadott dokumentumot a dokumentumok listájához a megfelelő szavakhoz. Egy nagyobb keresőben a fordított indexhez tartozó szavak keresése túlságosan időigényes lehet, ezért általában két részre oszlik:
Az invertált indexet azért nevezték így, mert ez a közvetlen index inverze .
Egy nagyszabású keresési index felépítése és karbantartása jelentős memória- és feldolgozási feladatokat igényel. Sok keresőmotor valamilyen tömörítést használ a lemezen lévő indexek méretének csökkentésére [6] . Fontolja meg a következő forgatókönyvet egy teljes szövegű internetes keresőmotor esetében:
Ebben a forgatókönyvben egy 2 milliárd weboldal tömörítetlen indexének 500 milliárd szóbejegyzést kellene tárolnia. Karakterenként 1 bájt vagy szónként 5 bájt csak 2500 gigabájt memóriaterületet igényelne. Ez több, mint 2 személyi számítógép átlagos szabad lemezterülete. A hibatűrő elosztott architektúra még több memóriát igényel. A választott tömörítési módszertől függően az index ennek a méretnek a töredékére csökkenhet. A tömörítés és a kitömörítés végrehajtásához szükséges idő és feldolgozási teljesítmény kompromisszuma.
Nevezetesen, a nagyszabású keresőmotor-projektek tartalmazzák a tárolási költségeket, valamint a tárolás energiaköltségeit.
A dokumentum elemzése (vagy elemzése ) magában foglalja a dokumentum komponensekre (szavakra) történő elemzését a közvetlen és fordított indexekbe való beillesztéshez. A talált szavakat tokennek hívják , a keresőmotor indexelése és a természetes nyelvi feldolgozás kontextusában pedig az elemzést gyakran tokenizációnak (vagyis tokenekre bontásnak) nevezik. Az elemzést néha beszédrész- jelölésnek , morfológiai elemzésnek, tartalomelemzésnek , szövegelemzésnek, szövegelemzésnek, megállapodásgenerálásnak , beszédszegmentálásnak , lexikális elemzésnek is nevezik . Az „indexelés”, „elemzés” és „tokenizálás” kifejezéseket a vállalati szleng felcserélhetően használják.
A természetes nyelvi feldolgozást folyamatosan kutatják és fejlesztik. A tokenizációnak problémái vannak a szükséges információk kinyerésével a dokumentumokból az indexeléshez a minőségi keresések támogatása érdekében. Az indexelés tokenizálása számos technológiát foglal magában, amelyek megvalósítása üzleti titok lehet .
A legtöbb emberrel ellentétben a számítógépek nem értik a természetes nyelvű dokumentumok szerkezetét, és nem képesek automatikusan felismerni a szavakat és mondatokat. A számítógép számára a dokumentum csak bájtok sorozata. A számítógép nem "tudja", hogy a szóköz karakter a szóelválasztó a dokumentumban. A személynek be kell programoznia a számítógépet, hogy meghatározza, mi az a szó, amelyet tokennek neveznek. Az ilyen programot általában tokenizálónak vagy elemzőnek (parser), valamint lexikális elemzőnek nevezik [21] . Egyes keresőmotorok és más természetes nyelvi feldolgozó szoftverek támogatják az olyan speciális elemző programokat, mint a YACC vagy a Lex [22] .
A tokenizálás során az elemző meghatároz egy olyan karaktersorozatot, amely szavakat és más elemeket, például írásjeleket , numerikus kódokkal képvisel, amelyek közül néhány nem nyomtatható vezérlőkarakter . Az elemző képes felismerni bizonyos objektumokat, például e-mail címeket , telefonszámokat és URL -eket . Az egyes tokenek felismerésekor néhány jellemző tárolható, például a nyelv vagy a kódolás, a beszédrész, a pozíció, a mondat száma, a mondatban elfoglalt hely, a hossza és a sorszám [21] .
Ha a kereső több nyelvet is támogat, akkor a tokenizálás során az első lépés az egyes dokumentumok nyelvének meghatározása lesz, mivel sok további lépés ettől függ (például a szótövis és a beszédrész meghatározása). A nyelvfelismerés az a folyamat, amelynek során egy számítógépes program megpróbálja automatikusan felismerni vagy besorolni egy dokumentum nyelvét. Az automatikus nyelvfelismerés a természetes nyelvi feldolgozás kutatásának tárgya [23] .
Ha a kereső több dokumentumformátumot is támogat, akkor a dokumentumokat fel kell készíteni a tokenizálásra. A probléma az, hogy egyes dokumentumformátumok a szöveges tartalom mellett formázási információkat is tartalmaznak. Például a HTML dokumentumok HTML címkéket tartalmaznak [24] . Ha a keresőmotor figyelmen kívül hagyja a tartalom és a szövegjelölés közötti különbséget, akkor az indexbe idegen információk kerülnének, ami rossz keresési eredményeket eredményezne. Formátumelemzés – A dokumentumba ágyazott jelölőnyelv azonosítása és feldolgozása. A formátumelemzést szerkezeti elemzésnek, címkefelosztásnak , szövegnormalizálásnak is nevezik .
A formátum elemzésének feladatát bonyolítja a különféle fájlformátumok bonyolultsága. Egyes fájlformátumokat szellemi tulajdonjogok védik , kevés információ áll rendelkezésre róluk, míg mások éppen ellenkezőleg, jól dokumentáltak. A keresőmotorok által támogatott általános, jól dokumentált fájlformátumok [25] [26] :
Egyes keresőmotorok támogatják a tömörített vagy titkosított formátumban tárolt fájlokat [27] [28] [29] . Ha tömörített formátummal dolgozik, az indexelő először kicsomagolja a dokumentumot. Ez a lépés egy vagy több fájlt eredményezhet, amelyek mindegyikét külön kell indexelni. A következő tömörített fájlformátumok támogatottak:
A formátumelemzés minőségjavító technikákat is tartalmazhat, hogy elkerülje a szükségtelen információk indexbe való felvételét. A tartalom kezelheti a formázási információkat, hogy további információkat is tartalmazzon. Példák a dokumentum formázásával való visszaélésre internetes spam esetén :
Egyes keresőmotorok tartalmaznak szakaszfelismerést, amely azonosítja a dokumentum főbb részeit a tokenizálás előtt. A korpuszban nem minden dokumentum olvasható úgy, mint egy jól megírt, fejezetekre és oldalakra osztott könyv. Az interneten található egyes dokumentumok, például a hírlevelek és a vállalati jelentések hibás tartalmat és oldalsávokat tartalmaznak, amelyekből hiányzik a fő tartalom. Ez a cikk például más weboldalakra mutató hivatkozásokat jelenít meg a bal oldali menüben . Egyes fájlformátumok, például a HTML vagy a PDF, lehetővé teszik a tartalom oszlopokban való megjelenítését. Bár a dokumentum tartalma különböző területeken jelenik meg a képernyőn, a forrásszöveg szekvenciálisan tárolja ezeket az információkat. A forrásszövegben szekvenciálisan megjelenő szavak szekvenciálisan indexelve vannak, még akkor is, ha a mondatok és bekezdések a monitor különböző részein jelennek meg. Ha a keresőmotorok minden tartalmat úgy indexelnek, mintha az a dokumentum fő tartalma lenne, akkor az index és a keresés minősége romolhat. Két fő probléma merül fel:
Egy szakasz elemzése megkövetelheti, hogy a keresőmotor megvalósítsa az egyes dokumentumok megjelenítési logikáját , azaz magának a dokumentumnak absztrakt ábrázolását, majd a dokumentum helyett az ábrázolást indexelje. Például néha JavaScriptet használnak a tartalom megjelenítésére egy weboldalon . Ha a keresőmotor "nem látja" a JavaScriptet, akkor az oldalak hibásan vannak indexelve, mivel a tartalom egy része nincs indexelve. Tekintettel arra, hogy egyes keresőmotorok nem törődnek a megjelenítési problémákkal, a webfejlesztők igyekeznek nem JavaScript-en keresztül megjeleníteni a tartalmat, vagy a NoScript címkét használják annak biztosítására, hogy a weboldal megfelelően legyen indexelve [30] . Ugyanakkor ez a tény felhasználható arra, hogy a keresőindexelő „láthassa” a különféle rejtett tartalmakat.
Bizonyos dokumentumok gyakran tartalmaznak beágyazott metaadatokat, például szerzőt, kulcsszavakat , leírást és nyelvet. A HTML-oldalakon a metacímkék olyan kulcsszavakat tartalmaznak, amelyek szintén szerepelnek az indexben. A korábbi internetes keresési technológiák indexelték a kulcsszavakat a közvetlen index metacímkéiben, és nem elemezték a dokumentum teljes szövegét. Ekkor még nem volt teljes szöveges indexelés, és a számítógépes hardver nem volt képes támogatni ezt a technológiát. A HTML jelölőnyelv eredetileg tartalmazta a meta tagek támogatását a helyes és egyszerű indexelés érdekében, tokenizálás nélkül [31] .
Az internet 1990- es évekbeli fejlődése során számos vállalat hozott létre vállalati webhelyeket. A weboldalak leírására használt kulcsszavak marketingorientáltabbá váltak, és úgy tervezték, hogy növeljék az eladásokat azáltal, hogy bizonyos keresési kifejezések esetén egy weboldalt helyeznek el a keresési eredményoldal tetején. Az a tény, hogy ezeket a kulcsszavakat szubjektív módon határozták meg, spamekhez vezetett, ami arra kényszerítette a keresőmotorokat, hogy elfogadják a teljes szöveges indexelést. Előfordulhat, hogy a keresőmotor-fejlesztők sok "marketing kulcsszót" tettek bele egy weboldal tartalmába, mielőtt érdekes és hasznos információkkal töltötték volna meg. A weboldalak tervezésének célja azonban az ügyfelek vonzása volt, ezért a fejlesztők érdekeltek voltak abban, hogy a látogatók megtartása érdekében több hasznos tartalom kerüljön az oldalra . Ebben az értelemben a teljes szövegű indexelés objektívebb volt, és javította a keresőmotorok eredményeinek minőségét, ami hozzájárult a teljes szövegű indexelési technológiák kutatásához.
A helyi keresésben a megoldások tartalmazhatnak metacímkéket, amelyek lehetővé teszik a szerzők általi keresést, mivel a keresőmotor különféle fájlok tartalmát indexeli, amelyek tartalma nem nyilvánvaló. A helyi keresés inkább a felhasználó ellenőrzése alatt áll, míg az internetes keresőmotoroknak inkább a teljes szöveges indexre kell összpontosítaniuk.
| Információk keresése az interneten | |
|---|---|
| Eszközök | |
| Indexelés | |
| Kérés | |
| keresési eredményeket | |
| Egyéb | |