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.

EBF17_braverman

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?