Hlavní navigace

Jehla v kupce sena: fulltextový stroj na 72 řádcích

Karel Pánek

V dnešním pokračování odbouráme poslední mýty o tom, jak jsou fulltexty komplikované. Uvedeme kompletní zdrojové texty stroje, který napíšeme přímo ve skriptovacím jazyce a to vše na 72 řádcích. Tento fulltext můžeme rychlostí i kvalitou odpovědí řadit někam mezi Kompas (dlouhá léta využívaný na Seznam.cz) a Webfast (Centrum.cz).

Pro jednoduchost jsme se rozhodli nekomplikovat fulltext lemmatizací, ačkoliv by její přidání neprodloužilo zdrojový text ani o jeden řádek.

Naším dnešním cílem je poodkrýt ono podivné tajemno, které obestírá střeva stroje. Proto jsme jej neopatřovali dokonalým crawlerem (díky čemuž jsme pak výsledné zdrojové texty mohli zkrátit o dalších sedm řádků kódu). Stejně jsme naložili s WWW rozhraním. Fulltext disponuje pouze příkazovým řádkem, od něhož není daleko k CGI.

Indexujeme…

Náš indexátor bude indexovat určené HTML stránky. Ty jsou v našem případě umístěny na lokálním datovém svazku, ale nic nebrání tomu, aby do procesu vstupovala i konkrétní URL. Výsledný seznam bude posléze uložen v podadresáři index, kam umístíme invertované výčty pro termy. Stejně tak informační data o jednotlivých dokumentech – v naší implementaci pouze název souboru, případně URL.

Zdrojový kód
#!/bin/sh




# ID-cko indexovane stranky
IDPG=1000




mkdir index




for i in /usr/share/doc/xfig/html/*.html
do
    COUNT=0
    PREVWORD="tohle slovo urcite NeDoStAnEmE"




echo "Indexujeme $i"




lynx -dump $i |
    tr '[:upper:]' '[:lower:]' |
    tr -cs '[:alnum:]' '[n*]' |
    sort | while read WORD
    do
    if [ "$WORD" == "$PREVWORD" ]
    then
        COUNT=`expr $COUNT + 1`
    else
        if [ "$COUNT" != "0" ]
        then
        echo $IDPG $COUNT >>index/$PREVWORD
        fi
        COUNT=1
        PREVWORD="$WORD"
    fi
    done
    echo $i >>index/.$IDPG
    IDPG=`expr $IDPG + 1`
done

Indexátor postupně převádí HTML dokumenty na obyčejné texty bez značek. Následně se zbavuje problému s velkými písmeny, protože je mění na písmena malá.

Tím jsme text převedli na tok slov, která jsou osamostatněna oddělovači řádků, neboli máme jedno slovo na jednom řádku. Pozn.: V tuto chvíli si můžeme dovolit nasadit ispell či jiný prostředek pro redukci termů na základní tvary, příp. provést eliminaci stopslov.

Zbývající kód je naprosto rutinní spočtení množství výskytů jednotlivých termů. Do invertovaného seznamu daného slova zaneseme jeho frekvenci a identifikátor dokumentu.

Nakonec uložíme informační data o konkrétním textu do souboru index/.(identi­fikátor_dokumen­tu).

Pozor! Pokud se budete snažit o inkrementální indexování, je potřeba zajistit, aby vám neustále rostly identifikátory (čísla) dokumentů. Blíže viz. v předchozí kapitole, kde jsme se zmiňovali o invertovaných seznamech a jejich formátu.

Vyhledáváme…

Nejprve si ukážeme nejsnadnější příklad, kdy dotaz tvoří jen jedno slovo (term).

Zdrojový kód
#!/bin/sh




WORD=$1




ILIST=index/$WORD




if [ ! -f $ILIST ]
then
    echo "No match"
    exit 1
fi




sort -k 2 -t ' ' -n -r $ILIST | while read ID FQ
do
    echo -n "($FQ) "
    cat index/.$ID
done

Vyhledávání jednoho slova je snadné. Nejdříve zjistíme, kde má uloženo svůj invertovaný seznam. Potom si tento seznam necháme sestupně seřadit podle druhé hodnoty – kam jsme zapisovali frekvenci slova – a vypíšeme výsledek. Místo nic neříkajících identifikátorů dáváme na výstup popisku, kterou v našem případě tvoří jen lokace dokumentu.

Ukázka
[CTO@yahoo fulltext]$ ./search1.sh angle
(28) /usr/share/doc/xfig/html/attributes.html
(14) /usr/share/doc/xfig/html/drawing.html
(12) /usr/share/doc/xfig/html/editing.html
(6) /usr/share/doc/xfig/html/contents.html
(4) /usr/share/doc/xfig/html/fig-format.html
(3) /usr/share/doc/xfig/html/printing.html
(1) /usr/share/doc/xfig/html/bugs_fixed.html

Při vyhledávání většího počtu slov je situace o trochu komplikovanější. Pro srozumitelnost zdrojového textu se omezíme pouze na dotazy typu A AND B. V opačném případě bychom využili pravděpodobně techniku samogenerování kódu a mohlo by se stát, že bychom tak mnohým čtenářům utekli do informační mlhy… Pozn.: Úpravu pro dotazy typu A OR B si můžete zkusit sami, je velice snadná.

Zdrojový kód
#!/bin/sh




WORD1=$1
WORD2=$2




ILIST1=index/$WORD1
ILIST2=index/$WORD2




if [ ! -f $ILIST1 -o ! -f $ILIST2 ]
then
    echo "No match"
    exit 1
fi




join -t ' ' $ILIST1 $ILIST2 | while read ID FQ1 FQ2
do
    echo $ID `expr $FQ1 + $FQ2`
done | sort -k 2 -t ' ' -n -r | while read ID FQ
do
    echo -n "($FQ) "
    cat index/.$ID
done

Pro vyhodnocování dotazu A AND B si vezmeme příslušné invertované seznamy a spojíme je přes identifikátory dokumentů. Tím vlastně vznikne index, který obsahuje identifikátory všech dokumentů, ve kterých jsou oba termy zastoupeny. Jako doplňkový parametr ponecháme součet frekvencí slov.

Takové sčítaní není pochopitelně kvalitní, ale pro náš fulltext bude zajisté postačovat. Kdybychom si chtěli o něco málo pomoci, mohli bychom použít výpočet ve stylu Q-hodnoty (Webfast.cz). Pro lepší výsledky je pochopitelně nutné sáhnout po některé z formulí, jež jsme prezentovali dříve. V tuto chvíli vystačíme se součtem, abychom zbytečně stroj nekomplikovali.

Ukázka
[CTO@yahoo fulltext]$ ./search2.sh draw xfig
(245) /usr/share/doc/xfig/html/drawing.html
(161) /usr/share/doc/xfig/html/editing.html
(153) /usr/share/doc/xfig/html/options.html
(142) /usr/share/doc/xfig/html/attributes.html
(95) /usr/share/doc/xfig/html/introduction.html
(88) /usr/share/doc/xfig/html/printing.html
(79) /usr/share/doc/xfig/html/installation.html
(62) /usr/share/doc/xfig/html/global_settings.html

Závěr

V dnešním díle jsme se podívali na fundamenty fulltextů a ukázali, jak je možné realizovat provozuschopný stroj. Přestože se to zdá nemožné, dokáže po rychlostní stránce (v malých bázích) bez problémů vzdorovat volně šířeným fulltextům s SQL základnou.

Doba napsání výše uvedených zdrojových textů se měří na minuty. Čím se tedy primitivní stroj liší od profesionálního fulltextu, který mnohdy vzniká několik měsíců? Stručně řečeno, dokáže nalézt onu pověstnou jehlu v kupce sena. To si ovšem ukážeme až na příkladech v dalším díle.

Našli jste v článku chybu?

26. 5. 2002 11:42

Srakyi (neregistrovaný)
Chtel bych autorovi podekovat za tento genialni serial clanku o fulltextovych vyhledavacich. O danou problematiku se docela zajimam a tak mne podobny clanek opravdu potesil!
Jeste jednou, DIKY!

26. 4. 2002 22:57

k.p. (neregistrovaný)
Bohuzel vetsina kvalitnich anglickych odkazu je placenych. Zatim se mi nepodarilo na internetu najit misto, kde by bylo mozne ziskat podobne udaje. Vetsina mych informaci pochazi z tistenych medii a vlastnich zapisku, ale pokud se mi podari nekde objevit volne dostupnou knihovnu podobnych clanku, rad uverejnim odkaz.
Měšec.cz: Zdravotní a sociální pojištění 2017: Připlatíte

Zdravotní a sociální pojištění 2017: Připlatíte

Podnikatel.cz: Změny v cestovních náhradách 2017

Změny v cestovních náhradách 2017

Vitalia.cz: Test na HIV je zdarma i za pět set

Test na HIV je zdarma i za pět set

120na80.cz: 5 nejčastějších mýtů o kondomech

5 nejčastějších mýtů o kondomech

Podnikatel.cz: Chtějte údaje k dani z nemovitostí do mailu

Chtějte údaje k dani z nemovitostí do mailu

120na80.cz: Rovnátka, která nejsou vidět

Rovnátka, která nejsou vidět

Podnikatel.cz: K EET. Štamgast už peníze na stole nenechá

K EET. Štamgast už peníze na stole nenechá

Podnikatel.cz: Chaos u EET pokračuje. Jsou tu další návrhy

Chaos u EET pokračuje. Jsou tu další návrhy

Měšec.cz: U levneELEKTRO.cz už reklamaci nevyřídíte

U levneELEKTRO.cz už reklamaci nevyřídíte

Vitalia.cz: Pamlsková vyhláška bude platit jen na základkách

Pamlsková vyhláška bude platit jen na základkách

Měšec.cz: Jak levně odeslat balík přímo z domu?

Jak levně odeslat balík přímo z domu?

DigiZone.cz: Recenze Westworld: zavraždit a...

Recenze Westworld: zavraždit a...

Vitalia.cz: To nejhorší při horečce u dětí: Febrilní křeče

To nejhorší při horečce u dětí: Febrilní křeče

120na80.cz: Stoná vaše dítě často? Upravte mu jídelníček

Stoná vaše dítě často? Upravte mu jídelníček

Root.cz: Mirai má nový cíl 5 milionů routerů

Mirai má nový cíl 5 milionů routerů

Vitalia.cz: Jmenuje se Janina a žije bez cukru

Jmenuje se Janina a žije bez cukru

120na80.cz: Co všechno ovlivňuje ženskou plodnost?

Co všechno ovlivňuje ženskou plodnost?

Podnikatel.cz: Vládu obejde, kvůli EET rovnou do sněmovny

Vládu obejde, kvůli EET rovnou do sněmovny

120na80.cz: Popraskané rty? Některé balzámy stav zhoršují

Popraskané rty? Některé balzámy stav zhoršují

Vitalia.cz: Mondelez stahuje rizikovou čokoládu Milka

Mondelez stahuje rizikovou čokoládu Milka