[PHP] MySQL FULLTEXT relevantiealgoritme nabouwen

[Genoil]

Ik heb in m'n classlibrary 2 zoek-classes, 1 die gebruik maakt van MySQL fulltext en 1 gebasseerd op good-old LIKE. Aangezien fulltext automatisch een relevantie aan de resultaten toekent, wil ik dat in m'n 'LikeSearch' ook. Ik vond met Google de volgende 2 links:

http://groups.google.com/...e&rnum=1#39b6d97aada7db15
http://www.alegsa.com.ar/...%20scores%20by%20hand.php

Die laatste is een PHP script van iemand die het geprobeerd heeft na te bouwen op basis van hetgene wat in de eerste link wordt verteld. Maar ik geloof niet dattie het helemaal goed heeft gedaan. Dus ik heb het zelf ook in elkeaar gezet op deze manier:

PHP:

    function setupRelevancy(& $objects, & $params, $keyword) {
        $sumw1 = 0;
                
        for($n = 0; $n < count($objects); $n++) {           
            $plainText = "";
            foreach ($params["columns"] as $field) {
                $contents = str_replace("-", " ", strtolower(strip_tags($objects[$n]->$field)));                
                $contents = preg_replace("/[^a-z0-9\s]/", "", $contents);
                $plainText.= $contents." ";
            }
            $dcount = substr_count($plainText, $keyword);   
            $objects[$n]->w1    = log((float)$dcount) + 1;      
            $objects[$n]->uniq  = sizeof(array_flip(str_word_count($plainText, 1)));
            $sumw1 += $objects[$n]->w1;
        }
        $params["sumw1"]    = $sumw1;
        $params["found"]    = count($objects);
        $params["qcount"]   = 1;
        
        
        $tableName  = $params["table"]; 
        $r = mysql_query("SELECT count(*) AS rows FROM ".$tableName." LIMIT 1");
        $rowCountResult = mysql_fetch_object($r);
        
        $params["rows"] = $rowCountResult->rows;
        
    }
        
    function calculateRelevancy($object, $params) 
    {
        /*------------------------------------------------------------------------------------------------------------------------
            Explanation of integer variables:
    
            1) $w1 = intermediate weight
            2) $dcount = number of times word is present in document (or query row)
            3) $sumw1 = sum of all values of $w1 found
            4) $uniq = number of unique words in the document (or query row)
            5) $rows = total number of rows in the table
            6) $found = number of rows in the table that contain the word in question (@sizeof($result))
            7) $qcount = number of times this word is present in the query
        ------------------------------------------------------------------------------------------------------------------------*/
        
        $w1     = $object->w1;
        $uniq   = $object->uniq;
        $sumw1  = $params["sumw1"];
        $found  = $params["found"];
        $rows   = $params["rows"];
        $qcount = $params["qcount"];
        
        $score = (float)($w1 / $sumw1 * $uniq / (1 + 0.0115 * $uniq) * log((float)(($rows - $found) / $found)) * $qcount);
        return $score;
    }

$objects zijn alle zoekresultaten
$object is 1 zoekresultaat

Ik heb e.e.a. voorlopig ff versimpeld door maar op 1 woord te zoeken dus qcount is altijd 1. Die harrie die zelf ook een PHP implementatie had gemaakt, had van qcount hetzelfde gemaakt als sumw1, dus daar klopte sowieso geen hout van.

Werkt allemaal wel en de resultaten lijken ok. Maar wanneer ik dan m'n 'FullTextSearch' gebruik, krijg ik totaal verschillende waarden. Dat is me verder niet zo'n zorg, maar als je de resulaten nou zou gaan sorteren op m'n zelfberekende score, is de volgorde compleet anders dan met de echte fulltext search

Ik vraag me af of er hier nog mensen zijn die zelf ook met dit soort algoritmes aan het stoeien zijn geweest of zien waarom mijn algoritme andere resultaten oplevert...

[JeRa]

Zonder even te zoeken naar fouten in je code; je baseert je algoritme op een bericht uit 2001. Inmiddels is het 2005 en is de kans niet gering dat ze in die tijd het een en het ander hebben veranderd je zou de broncode van MySQL erop na kunnen slaan om te zoeken naar het algoritme dat ze gebruiken.

[Genoil]

JeRa schreef op donderdag 04 augustus 2005 @ 15:53:
Zonder even te zoeken naar fouten in je code; je baseert je algoritme op een bericht uit 2001. Inmiddels is het 2005 en is de kans niet gering dat ze in die tijd het een en het ander hebben veranderd je zou de broncode van MySQL erop na kunnen slaan om te zoeken naar het algoritme dat ze gebruiken.

hmm scherp . ik heb de broncode van MySQL er al op nageslagen en ik denk dat ik de file waarin het algoritme staat wel gevonden heb, maar daar kan ik echt geen kaas van maken. ik denk dat het genoemde algoritme een soort versimpeling is van hoe het in het echt gaat. Of dat het in de broncode geoptimaiseerd is, waardoor het niet echt meer terug te vinden is...

[edit]
ik zat in .c files te zoeken, maar de waarde 0.0115 vond ik dus wel mooi terug in een .h...nu ff verder doorspitten

[edit2]
hmm voor zover ik het enigszins begrijp lijkt het er anno 2005 allemaal nog steeds verdacht veel op.

dit heb ik er uit op kunnen maken, en volgens mij is dat precies mijn formule:

code:

word->weight = (count?(log( (double) count)+1):0)
docstat->sum+=word->weight;
..
..
p->weight = (p->weight/docstat.sum*docstat.uniq)/(1+0.0115*docstat.uniq) * log(((double)(aio->info->state->records-doc_cnt))/doc_cnt)

ik realiseerde me echter wel ineens dat ik beter speciale fulltext kolommen in m'n database op kan nemen, omdat ik nu ook html in m'n database heb staan. Aangezien in de MySQL fulltext search geen wildcards aan de voorkant van woorden ondersteunt, zullen woorden tussen html tags nooit gevonden gaan worden en kan ik dus nooit een goede vergelijking maken

[edit3]
Google is echt gaaf :):
http://www.miislita.com/term-vector/term-vector-5-mysql.html
http://dev.mysql.com/doc/internals/en/full-text-search.html

[ Voor 50% gewijzigd door Genoil op 04-08-2005 17:29 ]

[Genoil]

nouja uiteindelijk zelf opgelost (wel kick-waardig . ik had de som van de weights niet goed berekend. (zie laatste link in vorige post) Scores kloppen nu nog steeds niet, maar dat komt waarschijnlijk doordat er een verschil zit tussen het tellen van woorden omdat ik html in de database heb staan. dus er moet even een aparte fulltext kolom zonder html bij...

[Bosmonster]

Genoil schreef op donderdag 04 augustus 2005 @ 16:17:
[...]

ik realiseerde me echter wel ineens dat ik beter speciale fulltext kolommen in m'n database op kan nemen, omdat ik nu ook html in m'n database heb staan. Aangezien in de MySQL fulltext search geen wildcards aan de voorkant van woorden ondersteunt, zullen woorden tussen html tags nooit gevonden gaan worden en kan ik dus nooit een goede vergelijking maken

Tipje: Doe een strip_tags en sla de html content los op (dus zonder tags) in een tabel met FULLTEXT.

[Genoil]

Bosmonster schreef op donderdag 04 augustus 2005 @ 17:51:
[...]


Tipje: Doe een strip_tags en sla de html content los op (dus zonder tags) in een tabel met FULLTEXT.

Ja dat is nou exact wat ik vandaag van plan ben te doen. Ik had nog iets meer dan strip_tags:

PHP:

$contents = str_replace("-", " ", strtolower(strip_tags($objects[$n]->$field)));                
$contents = preg_replace("/[^a-z0-9\s]/", "", $contents);

Voor het zoeken is strip_tags wel voldoende, maar voor die handmatige relevancy is het noodzakelijk puur lowercase woorden over te houden, anders werkt substr_count niet goed, en woorden met koppeltekens tel ik ook graag los, omdat delen daarvan een grote kans hebben een zoekwoord te zijn.

Maar hoe zit dat nou met zo'n FULLTEXT index? Helpt die ook bij een "LIKE search" of is die alleen relevant voor MATCH AGAINST? En beetje een datavase n00b vraag, maar hoe werkt dat eigenlijk met zo'n index als ik de inhoud van een cel wijzig. Moet dan de indexering overnieuw gedaan worden of gaat dat automagisch? Of gaat het wel automagisch maar is het effcienter als ik de indexering af en toe weg gooi en opnieuw genereer?

[Genoil]

Nou, hij doet het aardig...nog steeds niet dezelfde relevantiewaarden als uit MySQL, maar de volgorde van resultaten is redelijk overeenkomend. Geen idee waar het verschil em zit maar ik vinnet best zo. Ik post het maar even voor als er ooit nog mensen mee bezig willen. Voor een uitleg kun je het beste die twee links uit m'n twee na laatste post zoeken. Wat wel belangrijk is om het snappen is dat de waarden die getObjectFtVars teruggeeft opgeslagen worden bij het object in de database, zodat je dat niet elke zoekopdracht overnieuw hoeft te doen.

Ook wel handig is om te weten dat de basisklasse kan zoeken in meerdere tabellen, en de resultaten in een array $results teruggeeft die gegroepeerd zijn per tabel. Maar daar gaat het hier verder niet echt om...

PHP:

<?
import("nl.shapers.php4.search.LikeSearch");

function order_objects_by_relevance_desc($a, $b) {
   if ($a->relevance == $b->relevance) {
       return 0;
   }
   return ($a->relevance > $b->relevance) ? -1 : 1;
}

class FtLikeSearch extends LikeSearch {
                        
    function getResults($objects = null) {
        $results = BaseSearch::getResults($objects);
        
        foreach($results as $class => $objects) {
            if(count($objects) > 0) {
                $G = $this->setupWeights($objects, $this->words, $this->properties[$class]["table"]);
                foreach($objects as $n => $object) {
                    $objects[$n]->relevance = $this->calculateRelevance($object, $G);
                }
                usort($objects, "order_objects_by_relevance_desc");
                $results[$class] = $objects;
            }
        }
        
        return $results;
    }
    
    function getObjectFtVars($object, $ft_fields) {
    
        $fulltext = "";
        foreach ($ft_fields as $field) {
            $words = str_replace(array("-", "\r\n", "\n", "\r"), " ", strtolower(strip_tags($object->$field)));
            $words = str_replace("\t", "", $words);         
            $words = preg_replace("/[^a-z0-9\s]/", "", $words);
            $fulltext.= $words." ";
        }
        
        $unique_words = FtLikeSearch::getUniqueWords($fulltext);

        $sum_dtf      = FtLikeSearch::getSumDtf($fulltext, $unique_words);
        $U            = sizeof($unique_words);
        $norm_pivot   = $U/(1 + 0.0115 * $U);
    
        return array("fulltext" => $fulltext, "sum_dtf" => $sum_dtf, "norm_pivot" => $norm_pivot );
    }
        
    function getUniqueWords($fulltext) {
        return array_keys(array_flip(str_word_count($fulltext, 1)));
    }
    
    function getSumDtf($fulltext, $unique_words) {
        
        $sum_dtf = 0;
        for($n = 0; $n < count($unique_words); $n++) {
            $dtf  = substr_count($fulltext, $unique_words[$n]);
            $sum_dtf += log((float)$dtf) + 1;
        }
        
        return $sum_dtf;
    } 
        
    function setupWeights(& $objects, $words, $table) {
        $lcquery    = implode(" ", $words);
                    
        for($n = 0; $n < count($objects); $n++) {
            
            $objects[$n]->LNqf = array();
        
            $ft         = $objects[$n]->ft;
            $sum_dtf    = $objects[$n]->sum_dtf;
            $norm_pivot = $objects[$n]->norm_pivot;
            
            foreach($words as $word) {                  
                $dtf    = substr_count($ft, $word);
                $qf     = substr_count($lcquery, $word);
                $L      = (log((float)$dtf) + 1) / $sum_dtf;
                
                $N      = $norm_pivot;
                
                $objects[$n]->LNqf[] = $L * $N * $qf;
            }
        }           
        
        $r = mysql_query("SELECT count(*) AS rows FROM ".$table." LIMIT 1");
        $rowCountResult = mysql_fetch_object($r);
        
        $N  =  $rowCountResult->rows;
        $nf =  count($objects);
        
        
        $G  = log((float)(($N - $nf) / $nf)); // IDFP;  
        //  $G  = log((float)($N / $nf));   // IDF;
    
        
        return $G;      
    }
        
    function calculateRelevance($object, $G) 
    {   
        $relevance  = 0;
                
        foreach($object->LNqf as $LNqf) {
            $R = $LNqf * $G;
            if(sizeof($object->LNqf) == 1 && $R < 0) $R = -$R;
            if(is_finite($R))
                $relevance += $R;
        }
            
        return $relevance;
    }
}

?>

[edit]
Mocht iemand hier ooit nog iets mee willen doen maar twijfelen over de performance, twijfel dan niet!
Ik heb net de hele bijbel in een database gegooid in 3 verschillende (ongelinkte) tabellen, "book", "chapter" en "verse". Er zijn 65 boeken van plm 66K, een dikke 1000 chapters van plm 4K en 30.000+ versen van een zin lang. Wanneer een zoekterm in veel verzen voorkomt is de MySQL fulltext een stuk sneller omdat alle resultaten in m'n eigen versie nog gewogen moeten worden. De queries zelf draaien ongeveer even snel.

[edit2]Voor de search maar even editten, want wat hier eerst stond is kolder

[ Voor 35% gewijzigd door Genoil op 09-08-2005 10:37 ]