Index vyhledávání je datová struktura , která obsahuje informace o dokumentech a používá se ve vyhledávačích . Indexování prováděné vyhledávačem je proces shromažďování, třídění a ukládání dat za účelem rychlého a přesného vyhledávání informací . Tvorba indexu zahrnuje mezioborové koncepty z lingvistiky , kognitivní psychologie , matematiky , informatiky a fyziky . Indexování webu označuje proces indexování v kontextu vyhledávačů určených k vyhledávání webových stránek.na internetu.
Populární vyhledávače se zaměřují na fulltextové indexování dokumentů napsaných v přirozených jazycích [1] . Do vyhledávání se mohou zapojit i multimediální dokumenty , jako je video a zvuk [2] a grafika [3] [4] .
Metavyhledávače používají indexy z jiných vyhledávačů a neukládají lokální index, zatímco vyhledávače založené na stránkách uložených v mezipaměti ukládají index i textové korpusy po dlouhou dobu . Na rozdíl od fulltextových indexů omezují služby částečného textu hloubku indexování, aby se zmenšila velikost indexu. Větší služby mají tendenci indexovat v daném časovém rámci kvůli době zpracování a souvisejícím nákladům, zatímco vyhledávače založené na agentech vytvářejí index v reálném čase .
Účelem použití indexu je zvýšit rychlost hledání relevantních dokumentů pro vyhledávací dotaz . Bez indexu by vyhledávač musel procházet každý dokument v korpusu, což by vyžadovalo spoustu času a výpočetního výkonu. Zatímco například index 10 000 dokumentů lze vyhledat během milisekund, sekvenční skenování každého slova v 10 000 velkých dokumentech může trvat hodiny. Dodatečná paměť přidělená k uložení indexu a prodloužení doby potřebné k aktualizaci indexu je kompenzováno zkrácením doby potřebné k vyhledání informací.
Při navrhování vyhledávače je třeba vzít v úvahu následující faktory:
Faktory konfluence Jak jsou data zahrnuta do indexu? Jak se slova a podfunkce přidávají do indexu během procházení textového korpusu? A může více prohledávačů pracovat asynchronně? Prohledávač musí nejprve zkontrolovat, zda aktualizuje starý obsah nebo přidává nový obsah. Sloučení indexů vyhledávače je podobné jako SQL Merge a další slučovací algoritmy [5] . Způsoby skladování Jak ukládat indexovaná data ? To znamená, že určují typ uložených informací: komprimované nebo filtrované. Velikost indexu Kolik paměti počítače je potřeba k udržení indexu. Rychlost vyhledávání Jak rychle lze najít slovo v obráceném indexu . Pro informatiku je důležité porovnat rychlost nalezení záznamu v datové struktuře a rychlost aktualizace/smazání indexu. Úložný prostor Jak je index uložen po dlouhou dobu [6] . odolnost proti chybám Je důležité, aby vyhledávací služba byla spolehlivá. Problémy s tolerancí chyb zahrnují problém poškození indexu, určování, zda lze nesprávně tvarovaná data spojená se špatným hardwarem, rozdělení a schémata na základě hašovacích funkcí a složeného rozdělení na oddíly [7] a replikace řešit samostatně .Architektura vyhledávače se liší v metodách indexování a metodách ukládání indexů, což vyhovuje faktorům . Indexy jsou následujících typů:
příponový strom Obrazově strukturovaný jako strom podporuje lineární dobu vyhledávání. Postaveno na ukládání slovních přípon. Stromy podporují pokročilé hashování, které je důležité pro indexování vyhledávačů [8] . Používá se pro porovnávání vzorů v sekvencích DNA a shlukování . Hlavní nevýhodou je, že uložení slova do stromu může vyžadovat prostor nad rámec toho, co je potřeba k uložení samotného slova [9] . Alternativní reprezentací je pole přípon . Předpokládá se, že vyžaduje méně virtuální paměti a podporuje kompresi dat s tříděním bloků . Invertovaný index Uložte si seznam výskytů každého hledaného výrazu [10] , obvykle ve formě hashovacích tabulek nebo binárního stromu [11] [12] . Citační rejstřík Úložiště citací nebo hypertextových odkazů mezi dokumenty pro podporu analýzy citací, předmět bibliometrie . N-gram Ukládání sekvencí délek dat pro podporu jiných typů vyhledávání nebo analýzy textu [13] . Matice termínů dokumentu Používá se v latentní sémantické analýze (LSA) a ukládá výskyty slov v dokumentech do dvourozměrné řídké matice .Jedním z hlavních úkolů při návrhu vyhledávačů je řízení sekvenčních výpočetních procesů. Existují situace, ve kterých je možné vytvořit závodní podmínky a koherentní selhání. Například je do korpusu přidán nový dokument a index musí být aktualizován, ale zároveň musí index nadále reagovat na vyhledávání. Jedná se o kolizi dvou konkurenčních úkolů. Předpokládá se, že autoři jsou producenty informací a prohledávač je konzumentem těchto informací, zachycuje text a ukládá jej do mezipaměti (nebo korpusu). Přímý index je spotřebitelem informací produkovaných korpusem a převrácený index je spotřebitelem informací produkovaných přímým indexem. To je běžně označováno jako model výrobce-spotřebitel . Indexer je výrobcem prohledávatelných informací a uživatelé, kteří je hledají, jsou spotřebitelé. Problém je umocněn distribuovaným úložištěm a distribuovaným zpracováním. Pro škálování velkého množství indexovaných informací může být vyhledávač založen na distribuované výpočetní architektuře , přičemž vyhledávač sestává z více strojů pracujících ve shodě. To zvyšuje pravděpodobnost nelogičnosti a ztěžuje udržování plně synchronizované, distribuované, paralelní architektury [14] .
Dopředný index ukládá seznam slov pro každý dokument. Níže je uvedena zjednodušená forma přímého indexu:
| Dokument | Slova |
|---|---|
| Dokument 1 | naše, Tanyo, hlasitě pláče |
| dokument 2 | klesl, v, řeka, míč |
| Dokument 3 | Ticho, Tanechko, neplač, |
| Dokument 4 | ne, utopit, v, řeka, míč |
Důvodem pro vývoj přímého indexu je, že je lepší ukládat slova za dokumenty hned, protože jsou později analyzována za účelem vytvoření vyhledávacího indexu. Dopředné generování indexu zahrnuje asynchronní systémové zpracování, které částečně obchází zúžené místo aktualizace obráceného indexu [15] . Přímý index je setříděn , aby byl převeden na invertovaný. Přímý index je v podstatě seznam dvojic dokumentů a slov seřazených podle dokumentu. Převod přímého indexu na invertovaný je jen otázkou řazení slovních dvojic. V tomto ohledu je invertovaný index slovně seřazený přímý index.
Mnoho vyhledávačů používá při vyhodnocování vyhledávacího dotazu obrácený index k rychlému vyhledání dokumentů obsahujících slova v dotazu a následnému seřazení těchto dokumentů podle relevance. Protože obrácený index ukládá seznam dokumentů obsahujících každé slovo, může vyhledávač použít přímý přístup k vyhledání dokumentů spojených s každým slovem v dotazu a jejich rychlému načtení. Níže je zjednodušená reprezentace převráceného indexu:
| Slovo | Dokumenty |
|---|---|
| v | Dokument 2, Dokument 4 |
| hlasitě | Dokument 1 |
| míč | Dokument 2, Dokument 4 |
| náš | Dokument 1 |
| ne | Dokument 3, Dokument 4 |
| plakat | Dokument 1, Dokument 3 |
| řeka | Dokument 2, Dokument 4 |
| Tanya | Dokument 1, Dokument 3 |
| klid | Dokument 3 |
| pokles | dokument 2 |
| utopit | Dokument 4 |
Invertovaný index může pouze určit, zda slovo existuje v konkrétním dokumentu, protože neukládá žádné informace týkající se frekvence a pozice slova, a proto je považován za logický index. Invertovaný index určuje, které dokumenty odpovídají dotazu, ale nevyhodnocuje odpovídající dokumenty. V některých případech index obsahuje další informace, jako je frekvence každého slova v každém dokumentu nebo pozice slova v dokumentu [16] . Informace o poloze slova umožňuje vyhledávacímu algoritmu identifikovat blízkost slova pro podporu vyhledávání frází. Frekvenci lze použít k seřazení dokumentů pro dotaz. Na taková témata se zaměřuje výzkum vyhledávání informací.
Převrácený index je reprezentován řídkou maticí, protože ne všechna slova jsou přítomna v každém dokumentu. Index je podobný matici termínů dokumentu používané v LSA. Invertovaný index si lze představit jako formu hashovací tabulky. V některých případech je index ve formě binárního stromu, který vyžaduje další paměť, ale může zkrátit dobu vyhledávání. Ve velkých indexech je architektura obvykle reprezentována distribuovanou hashovací tabulkou [17] .
Invertovaný index se naplní sloučením nebo obnovením. Architektura může být navržena tak, aby podporovala inkrementální indexování [18] [19] , kde sloučení definuje dokument nebo dokumenty, které mají být přidány nebo aktualizovány, a poté analyzuje každý dokument do slov. Kvůli technické přesnosti spojuje sloučení nově indexované dokumenty, obvykle umístěné ve virtuální paměti , s mezipamětí indexu, která je umístěna na jednom nebo více pevných discích počítače .
Po analýze indexátor přidá zadaný dokument do seznamu dokumentů pro shodu slov. Ve větším vyhledávači může být proces hledání každého slova pro invertovaný index příliš časově náročný, takže se obvykle dělí na dvě části:
Invertovaný index je tak pojmenován, protože je inverzní k přímému indexu.
Vytváření a údržba rozsáhlého vyhledávacího indexu vyžaduje značné množství paměti a zpracování. Mnoho vyhledávačů používá nějakou formu komprese ke zmenšení velikosti svých indexů na disku [6] . Zvažte následující scénář pro fulltextový internetový vyhledávač:
Vzhledem k tomuto scénáři by nekomprimovaný index pro 2 miliardy webových stránek musel uložit 500 miliard slovních záznamů. 1 bajt na znak nebo 5 bajtů na slovo by vyžadovalo jen 2500 gigabajtů paměti. To je více než průměrné volné místo na disku 2 osobních počítačů. Distribuovaná architektura odolná proti chybám vyžaduje ještě více paměti. V závislosti na zvolené kompresní metodě může být index zmenšen na zlomek této velikosti. Kompromis času a výpočetního výkonu potřebného k provedení komprese a dekomprese.
Je pozoruhodné, že rozsáhlé projekty vyhledávačů zahrnují náklady na skladování a také náklady na energii pro skladování.
Analýza (nebo analýza ) dokumentu zahrnuje analýzu dokumentu na komponenty (slova) pro vložení do přímých a invertovaných indexů. Nalezená slova se nazývají tokeny a v kontextu indexování vyhledávačů a zpracování přirozeného jazyka se parsování často nazývá tokenizace (tedy rozdělení na tokeny). Analýza se někdy nazývá značkování slovních druhů , morfologická analýza, obsahová analýza , textová analýza, textová analýza, generování shody , segmentace řeči, lexikální analýza . Pojmy „indexování“, „analýza“ a „tokenizace“ se v podnikovém slangu používají zaměnitelně.
Zpracování přirozeného jazyka je neustále zkoumáno a zdokonalováno. Tokenizace má problémy s extrahováním potřebných informací z dokumentů pro indexování pro podporu kvalitního vyhledávání. Tokenizace pro indexování zahrnuje několik technologií, jejichž implementace může být obchodním tajemstvím .
Na rozdíl od většiny lidí počítače nerozumí struktuře dokumentu v přirozeném jazyce a nedokážou automaticky rozpoznat slova a věty. Pro počítač je dokument jen posloupnost bajtů. Počítač "neví", že znak mezery je oddělovač slov v dokumentu. Osoba musí naprogramovat počítač, aby určil, co je jediné slovo zvané token. Takový program se obvykle nazývá tokenizer nebo parser (parser) a také lexikální analyzátor [21] . Některé vyhledávače a další software pro zpracování přirozeného jazyka podporují specializované programy pro analýzu, jako je YACC nebo Lex [22] .
Během tokenizace analyzátor určí sekvenci znaků, které představují slova a další prvky, jako je interpunkce , reprezentovaná číselnými kódy, z nichž některé jsou netisknutelné řídicí znaky . Analyzátor dokáže rozpoznat některé objekty, jako jsou e-mailové adresy , telefonní čísla a adresy URL . Při rozpoznávání každého tokenu lze uložit některé vlastnosti, například jazyk nebo kódování, slovní druh, pozici, číslo věty, pozici ve větě, délku a číslo řádku [21] .
Pokud vyhledávač podporuje více jazyků, pak prvním krokem při tokenizaci bude určení jazyka každého dokumentu, protože na tom závisí mnoho následných kroků (například odvození a určení slovního druhu). Rozpoznávání jazyka je proces, kterým se počítačový program pokouší automaticky detekovat nebo klasifikovat jazyk dokumentu. Automatické rozpoznávání jazyka je předmětem výzkumu zpracování přirozeného jazyka [23] .
Pokud vyhledávač podporuje více formátů dokumentů, musí být dokumenty připraveny na tokenizaci. Problém je v tom, že některé formáty dokumentů obsahují kromě textového obsahu i informace o formátování. Například HTML dokumenty obsahují HTML tagy [24] . Pokud by vyhledávač ignoroval rozdíl mezi označením obsahu a textu, byly by do indexu zahrnuty nadbytečné informace, což by vedlo ke špatným výsledkům vyhledávání. Formátová analýza – Identifikace a zpracování značkovacího jazyka vloženého do dokumentu. Formátová analýza je také označována jako strukturální analýza, dělení tagů , normalizace textu.
Úkol analýzy formátu je komplikován složitostí různých formátů souborů. Některé formáty souborů jsou chráněny právy duševního vlastnictví , je o nich málo informací, jiné jsou naopak dobře zdokumentovány. Běžné, dobře zdokumentované formáty souborů podporované vyhledávači [25] [26] :
Některé vyhledávače podporují soubory, které jsou uloženy v komprimovaném nebo šifrovaném formátu [27] [28] [29] . Při práci s komprimovaným formátem indexátor nejprve dokument dekomprimuje. Výsledkem tohoto kroku může být jeden nebo více souborů, z nichž každý musí být indexován samostatně. Jsou podporovány následující formáty komprimovaných souborů:
Formátová analýza může zahrnovat techniky zlepšení kvality, aby se zabránilo zahrnutí zbytečných informací do indexu. Obsah může spravovat informace o formátování tak, aby zahrnoval další informace. Příklady zneužití formátování dokumentu v případě webového spamu :
Některé vyhledávače zahrnují rozpoznávání sekcí, které identifikuje hlavní části dokumentu před tokenizací. Ne všechny dokumenty v korpusu se čtou jako dobře napsaná kniha rozdělená do kapitol a stránek. Některé dokumenty na internetu, jako jsou informační bulletiny a podnikové zprávy, obsahují chybný obsah a postranní panely, které postrádají hlavní obsah. Tento článek například zobrazuje odkazy na jiné webové stránky v nabídce vlevo . Některé formáty souborů, jako HTML nebo PDF, umožňují zobrazení obsahu ve sloupcích. Přestože je obsah dokumentu zobrazen na obrazovce v různých oblastech, zdrojový text ukládá tyto informace postupně. Slova, která se ve zdrojovém textu objevují postupně, jsou indexována postupně, i když se věty a odstavce objevují v různých částech monitoru. Pokud vyhledávače indexují veškerý obsah, jako by to byl hlavní obsah dokumentu, může dojít ke snížení kvality indexu a vyhledávání. Jsou zaznamenány dva hlavní problémy:
Analýza sekce může vyžadovat, aby vyhledávač implementoval logiku vykreslování každého dokumentu, tj. abstraktní reprezentaci dokumentu samotného, a potom indexoval reprezentaci namísto dokumentu. Někdy se například JavaScript používá k zobrazení obsahu na webové stránce . Pokud vyhledávač „nevidí“ JavaScript, pak jsou stránky indexovány nesprávně, protože část obsahu není indexována. Vzhledem k tomu, že některé vyhledávače si problémy s vykreslováním nedělají, weboví vývojáři se snaží nevykreslovat obsah pomocí JavaScriptu nebo používat značku NoScript , aby se ujistili, že je webová stránka správně indexována [30] . Tento fakt lze zároveň využít k tomu, aby indexer vyhledávače „viděl“ různý skrytý obsah.
Některé dokumenty často obsahují vložená metadata, jako je autor, klíčová slova , popis a jazyk. Na stránkách HTML obsahují meta tagy klíčová slova, která jsou také zahrnuta v indexu. Dřívější technologie internetového vyhledávání indexovaly klíčová slova v metaznačkách přímého indexu a neanalyzovaly úplný text dokumentu. V té době ještě neexistovala fulltextová indexace a počítačový hardware nebyl schopen takovou technologii podporovat. Značkovací jazyk HTML původně obsahoval podporu pro meta tagy, aby bylo možné správně a snadno indexovat, bez použití tokenizace [31] .
Během rozvoje internetu v 90. letech vytvořilo mnoho korporací firemní webové stránky. Klíčová slova používaná k popisu webových stránek se stala více marketingově orientovaná a navržena tak, aby zvyšovala prodej umístěním webové stránky do horní části stránky s výsledky vyhledávání pro určité hledané výrazy. Skutečnost, že tato klíčová slova byla subjektivně určena, vedla ke spamu, který donutil vyhledávače akceptovat fulltextové indexování. Vývojáři vyhledávačů možná vložili mnoho „marketingových klíčových slov“ do obsahu webové stránky, než ji naplnili zajímavými a užitečnými informacemi. Účelem návrhu webových stránek však bylo přilákat zákazníky, takže vývojáři měli zájem zahrnout na stránky užitečnější obsah, aby si udrželi návštěvníky . V tomto smyslu byla fulltextová indexace objektivnější a zvýšila kvalitu výsledků vyhledávačů, což přispělo k výzkumu technologií fulltextové indexace.
V místním vyhledávání mohou řešení zahrnovat meta tagy, které umožňují vyhledávání podle autorů, protože vyhledávač indexuje obsah z různých souborů, jejichž obsah není zřejmý. Lokální vyhledávání je více pod kontrolou uživatele, zatímco internetové vyhledávače by se měly více zaměřit na fulltextový index.
| Vyhledávání informací na internetu | |
|---|---|
| Nástroje | |
| Indexování | |
| Žádost | |
| výsledky vyhledávání | |
| jiný | |