indexace

prvni, co budeme potrebovat je nejakym zpusobem rozebrat text na nejake zakladni jednotky - kterym se bud to rika "slova", "termy", "tokeny", "lexemy". v php trivialita - ereg_replace("[^a-zA-Z0-9]+", " ", $text), pak uz jenom explode()... v rade fulltextu se jednotlive slova jeste nejak upravuji... treba se jim odstrani diakritka, prevedou se na zakladni tvar nebo neco podobneho.

ted bude stacit jenom do pripravene databaze nasypat dokument a pocty jednotlivych termu v nem.

create table ft_terms (
id serial primary key,
term varchar(128));
create unique index ft_terms_term_idx on ft_terms (term);

create table ft_weights (
document_id int,
term_id int references ft_terms (id),
count int default 0,
weight double precision default 0,
preview text,
primary key (document_id, term_id));

do ted to byla vcelku nuda, kterou zvladne kazdy. ale ted prijde ta "prava veda". bude nutne predstavit si mnozinu dokumentu jako mnozinu vektoru v n-dimenzionalnim prostoru, kde kazdy term predstavuje jednu dimenzi a kazda slozka vektoru predstavuje pocet termu v dokumentu. diky tomu muzeme urcit podobnost mezi jednotlivymi dokumenty - podle toho jak jsou od sebe vzdaleny. vyhledavani pak nebude nic jineho nez hledat dokumenty, ktere se budou podobat polozenemu dotazu. (zni to hrozne, ale je to pohoda)

nejdriv ohodnotime jednotlive termy podle dulezitosti. napriklad casta slova jako treba "jako" nebo "treba" nebo "nebo" by meli byt min dulezita, nez fundamentalni slova, ktera se vyskytnou jenom v par ultimatnich textech - protoze podle nich jdou prave dokumenty nejlip poznat. ktery exot by taky takove slova pouzival?

pro ohodnoceni dulezitesti termu se pouziva funkce tzv. inverse document frekvency, coz je:
idf(term) = log(dc / tc(term)) + 1, kde dc je celkovy pocet dokumentu a tc(term) je pocet dokumentu, ktery obsahuje dany term. z pohledu databaze to pak resi jeden hezky pohled:

create view ft_idfs as
        select
        term_id, 
        log((select count(distinct document_id) from ft_weights)::double precision 
            / count(distinct document_id)) + 1 as idf
    from ft_weights group by term_id;

dal si spocitame jak moc dulezite jsou jednotlive slova v jednotlivych dokumentech.
pouzijeme dalsi dobre znamy vzorecek: w(term,dokument) = tf(term, dokument) * idf(term). coz neni nic jineho nez kolikrat se v danem dokumentu slovo vyskytuje a jak je dulezite. zase pro to mame hezky pohled:

create view ft_calculated_weights as
    select
        ft_weights.document_id, 
        ft_weights.term_id, 
        (count::double precision / cnt) * idf as weight from ft_weights, ft_idfs, 
        (select document_id, sum(count) as cnt 
            from ft_weights 
            group by document_id) doc_cnt 
    where 
        (ft_weights.document_id = doc_cnt.document_id)
        and (ft_idfs.term_id = ft_weights.term_id);

a jelikoz se jednotlive vahy budou vybirat casto, tak si je ulozime do tabulky.

update ft_weights 
    set weight = ft_calculated_weights.weight from ft_calculated_weights 
            where (ft_calculated_weights.document_id = ft_weights.document_id)
            and (ft_calculated_weights.term_id = ft_weights.term_id)

a aby se nam k tomu pristupovalo jeste lip zavadeneme si dalsi pomocny pohled:

create view ft_term_weights as
        select 
        document_id,
        term,
        weight 
    from
        ft_weights,
        ft_terms
    where
	(ft_weights.term_id = ft_terms.id)

vyhledavani

data uz mame nasypane do databaze vcetne spousty pomocnych informaci, kterym muzeme i nemusime verit. ted v nich muzeme zacit vyhledavat. jak uz jsem psal dokumenty tvori body v n-dimenzionalnim prostoru, ale to same muzeme prohlasit taky o dotazu, de facto je to taky dokument.... i kdyz jej nezridka tvori jedno dve slova. nicmene, vyhledavani neni nic jineho nez hledani dokumentu, ktere jsou podobne dotazu.

celou dobu tu operuju s terminem podobnost, ale jeste jsem jej nezavadl. muzeme zavest treba podobnost jako vzdalenost mezi dokumenty (neco na zpusob pythagorovy vety) nebo treba jako uhlovou vzdalenost mezi dokumenty. druha varianta ma tu vyhodu, ze si vystacime se skalarnim soucinem, se kterym se da velice krasne pracovat v databazi. diky specialnim vlastnostem dotazu (je to jednotkovy vektor a kazda slozka ma stejnou relevanci) nam staci spocitat vahy jednotlivych hledanych slov v dokumentech.

select
    document_id,
    count(term) as success, 
    sum(weight) as score 
from
    ft_term_weights
where 
    (term in ('term1', 'term2')) -- termy dle libosti
group by 
    document_id
order by 
    success desc,
    score desc

tento zpusob vyhledavani ma radu vyhod i nevyhod. treba prepocitavani vah. mezi velkou vyhodu, ale patri ze najde i vysledky, ktere nemusi odpovidat presne zadani, ale snazi se najit nejblizsi nejlepsi reseni. tzn. pokud hledate dokument se tremi slovy, ale zadny takovy tam neni, tak se snazi najit treba i ten kde jsou obsazeny jenom dve.

nicmene toto je jenom zaklad, tato metoda lze dal rozsirovat, at uz je to sofistikovanjsi pocitani vah nebo rozsireni dotazovani s operatory +slovo, -slovo, ktere jsou spojenim vice dotazu pomoci operaci INTERSECT, apod.

Vytvořil(a) deda.jabko v 24. 03. 2007, 18:35