Søgealgoritme?

Tags:    php mysql

Hej udviklere,

jeg har i den seneste periode arbejdet på et par projekter hvor der skulle være en søgefunktion, og hver gang har søgealgoritmen virkeligt irriteret mig.

Måden jeg lave en søgning på er at dele søgeordet ved mellemrum og derefter søge efter dette ord i alle de felter jeg gerne vil finde noget fra i databasen. Som eksempel har jeg lavet noget der skal søge efter elever og lærere. Her søger den altså både på elevens navn, elevens klasse, lærerens navn og lærerens "shortcode" (en forkortelse på 3 karakter).

Eftersom det er noget live-search søger den hver gang man skriver et bogstav hvilket vil sige at hvis jeg f.eks. skriver "simon s" vil den første søge efter "simon" i elevnavn, elevklasse, lærenavn og lærekode. Dette er alt sammen meget fint, men når jeg så søger på "s" får jeg jo bare de samme resultater igen eftersom den forsøger at matche et elevnavn (mit navn: simon smith) med "simon" og "s" hvilket vil sige at den finder alle dem der hedder simon uden at de nødvendigvis har et efternavn der starter med "s".

Nogle vil måske spørger hvorfor jeg vælger at dele det op så og svaret er ganske enkelt at jeg ikke vil have at brugeren skal tage højde for eventuelle mellemnavn eller efternavne eleverne ikke bruger til hverdag.

Det er php og MySql jeg laver det med, så hvis nogen har et forslag til hvordan jeg bedst muligt kunne lave dette for at få en lidt bedre søgning må I endeligt sige til.

Et eksempel på en MySql forespørgsel i øjeblikket kunne være som følger:

Fold kodeboks ind/udSQL kode 


På forhånd mange tak :-)


EDIT
For at være lidt mere specifikt med mit problem er det at jeg vil skulle lave en masse søgninger på partielle ord, f.eks. et halvt fornavn, mellemnavn eller efternavn eller måske kun en årgang ved søgning på klasser hvor klasserne er af format "2.a" og jeg kun søger på "2"



Indlæg senest redigeret d. 08.08.2011 12:02 af Bruger #8773
7 svar postet i denne tråd vises herunder
2 indlæg har modtaget i alt 20 karma
Sorter efter stemmer Sorter efter dato
Den starter ikke en ny forespørgsel før den forrive er forrige forespørgsel er færdig. Har du et forslag til hvordan jeg kan skære ned på antallet af forespørgsler? Hvis der inden for 200ms ikke kommer et nyt bogstav eller der er skrevet 2-3 nye bogstaver skal den søge, eller sådan noget?


Typisk starter fyrer man en setInterval() af, der efter X antal milisekunder sender forespørgslen. Hver gang brugeren trykker på en tast, bruger man clearInterval() til at stoppe den forgående timer, og laver en ny med setInterval(). På den måde sender man kun en forespørgsel når brugeren har trykket på en tast og derefter ventet mere end X antal milisekunder med at trykke på den næste :)

Mvh.

Kasper (TSW)



Indlæg senest redigeret d. 08.08.2011 11:08 af Bruger #1
Dette er et eksempel på hvordan det muligvis kan se ud i en fiktiv jQuery opsætning:
Fold kodeboks ind/udKode 


Om fulltext er det nok bedre at henvise dig til http://en.wikipedia.org/wiki/Full_text_search og http://dev.mysql.com/doc/refman/5.0/en/fulltext-search.html



Indlæg senest redigeret d. 08.08.2011 11:11 af Bruger #10216
Jeg ved ikke om du er bekendt med Fulltext søgning/indexering. F.eks kan du lave en index tabel som indeholder de søgebare informationer og en reference til hvor de originale data findes.

Udover det, så kunne du jo se på at dit javascript kun sender requests efter 100-200ms. Det giver mulighed for at brugeren kan nå at indtaste et helt navn, før søgning bliver foretaget. Det uhensigtsmæssigt at sende requests på alle keyup/-down events da f.eks et navn på tyve tegn giver tyve requests i rap, hvis man er lidt hurtig til at skrive.



Jeg ved ikke om du er bekendt med Fulltext søgning/indexering. F.eks kan du lave en index tabel som indeholder de søgebare informationer og en reference til hvor de originale data findes.

Udover det, så kunne du jo se på at dit javascript kun sender requests efter 100-200ms. Det giver mulighed for at brugeren kan nå at indtaste et helt navn, før søgning bliver foretaget. Det uhensigtsmæssigt at sende requests på alle keyup/-down events da f.eks et navn på tyve tegn giver tyve requests i rap, hvis man er lidt hurtig til at skrive.


Den starter ikke en ny forespørgsel før den forrive er forrige forespørgsel er færdig. Har du et forslag til hvordan jeg kan skære ned på antallet af forespørgsler? Hvis der inden for 200ms ikke kommer et nyt bogstav eller der er skrevet 2-3 nye bogstaver skal den søge, eller sådan noget?

Er ikke bekendt med fulltext søgning/indexering - kan du uddybe det lidt?



Tak for tippet til mit javascript begge to - det vil jeg få implementeret ;-)

Jeg har prøvet at lege lidt med FULLTEXT search nu, men synes ikke på nogen måde at være specielt effektivt.

Jeg har følgende query:

Fold kodeboks ind/udSQL kode 


I min database findes der ca. 20 elever med fornavnet "simon" hvor jeg gerne vil finde mig selv "simon rose smith". Ved ovenstående får jeg mig selv som det 5. resultat og kun én anden før mig har et mellemnavn der starter med s, ellers er der ikke andre s'er end det s i "simon".

Når jeg prøver uden "IN BOOLEAN MODE" findes jeg som det 11. resultat.

Ved ikke om jeg er helt galt på den?



Hvorfor laver du i det hele taget en forespørgelse ved hvert bogstav?

Såvidt jeg lige kan vurderer behøver du kun en forespørgelse ved det første bogstav eller når et bogstav slettes (Selv det kan spares, hvis du husker det originale søgning.). Da alle senere bogstaver vil give et resultat der er et subset af det foregående kan du bruge javascript til at fjerne i det eksitsterende resultat:

navne:
Alex
Adam
Allan

Ved A:
Alex
Adam
Allan

Ved Al
Alex
Allan

Ved Ale
Alex


Du kunne også forfine din søgning ved med javascript at fjerne de enkelete ord der bliver matchet før du matcher med næste ord:

Så ved Simon S
fjernes Simon og den søger med S i resultatet

Simon Rose Smith -> fjern simon -> Rose Smith -> S.





Hvorfor laver du i det hele taget en forespørgelse ved hvert bogstav?

Såvidt jeg lige kan vurderer behøver du kun en forespørgelse ved det første bogstav eller når et bogstav slettes (Selv det kan spares, hvis du husker det originale søgning.). Da alle senere bogstaver vil give et resultat der er et subset af det foregående kan du bruge javascript til at fjerne i det eksitsterende resultat:

navne:
Alex
Adam
Allan

Ved A:
Alex
Adam
Allan

Ved Al
Alex
Allan

Ved Ale
Alex


Du kunne også forfine din søgning ved med javascript at fjerne de enkelete ord der bliver matchet før du matcher med næste ord:

Så ved Simon S
fjernes Simon og den søger med S i resultatet

Simon Rose Smith -> fjern simon -> Rose Smith -> S.



Jeg gik tilbage til den oprindelige løsning da den egentligt fungerede fint, har bare skåret ned på antallet af forespørgsler ved at bruge Kasper og Michael's idéer med et timeout der bliver reset ved hver tryk på en knap ;-) 200 miliseconds delay fra man stopper med at skrive til den søger :-)



t