Archief - Algoritme (PHP): search engine voor forum

[JohnBeton]

Hello,


ik zou graag de search engine van mijn forum wat aanpassen.
Momenteel doorzoekt de searchfuntie bij elke search de posts in de database naar de given string, maar zoals je je kan inbeelden is dat verre van ideaal, vooral als het aantal posts toeneemt.

Ik had gedacht aan een soort "caching", maar heb het nog niet helemaal uitgedacht.

Wat is volgens jullie een goede manier om het searchen in een forum (op threadnaam, inhoud van posts & usernaam) vlot te laten verlopen?

Eventuele codevoorbeelden in PHP zijn welkom btw

[EdMeister]

phpBB doet dit door lijsten van woorden bij te houden in zijn database. Het voordeel is dat het heel snel werkt, nadeel is uiteraard dat je database veel groter wordt.
Ik zou zeggen: kijk eens in de broncode van phpBB, installeer en draai dat forum desnoods lokaal en implementeer het systeem in je eigen forum.

[JohnBeton]

phpBB doet dit door lijsten van woorden bij te houden in zijn database. Het voordeel is dat het heel snel werkt, nadeel is uiteraard dat je database veel groter wordt.
Ik zou zeggen: kijk eens in de broncode van phpBB, installeer en draai dat forum desnoods lokaal en implementeer het systeem in je eigen forum.

Worder die woorden gecached op de moment dat er iemand naar dat woord zoekt, of wordt er gewoon een soort index aangelegd van woorden die groter zijn dan x-aantal karakters?

(Mijn cache-idee was trouwens het opslagen van zoekresultaten, zodat deze later nog eventueel kunnen opgevraagd worden (indien niet teveel later))

En als er naar "xxx" gezocht wordt in threadnamen alleen, worden posts dan ook doorzocht (en dus gecached) of wordt begehouden wat de parameters waren voor die bepaalde search en wordt enkel de cache gebruikt indien deze parameters hetzelfde zijn bij een volgende search.

[servi]

een manier om dat te versnellen is door te hashen.

Een (héél) eenvoudig hash-algoritme is alles per lengte van letters sorteren.


edit : hier vind je enkele hash-functies : ( weliswaar in c++ geschreven )
http://www.cs.yorku.ca/~oz/hash.html


hierdoor heb je dus slechts 3 velden nodig in je zoektabel :
-id bigint unsigned auto_increment primary key
- hash bigint unsigned ( INDEXED !!! )
- postid bigint unsigned ( verwijzing naar de juiste post )

[JohnBeton]

een manier om dat te versnellen is door te hashen.

Een (héél) eenvoudig hash-algoritme is alles per lengte van letters sorteren.


edit : hier vind je enkele hash-functies : ( weliswaar in c++ geschreven )
http://www.cs.yorku.ca/~oz/hash.html


hierdoor heb je dus slechts 3 velden nodig in je zoektabel :
-id bigint unsigned auto_increment primary key
- hash bigint unsigned ( INDEXED !!! )
- postid bigint unsigned ( verwijzing naar de juiste post )

Maar dan moet je elke keer je hash-tabel updaten als er een iets gepost wordt, right? Nuja, dat updaten zal zolang wel niet duren zeker?
(en is een bigint niet overdreven om de lengte van het woord uit te drukken?)

Maar het lijkt me inderdaad geen slechte manier om de zoekresultaten al aanzienlijk te verminderen (en om daar dus verder in te zoeken).



Oja, even tussendoor: bestaat er een manier om het ordenen (vb: "order bij postid") te versnellen? (indexen versnellen enkel de where clause, toch?)
Wanneer ik een grote result set terugkrijg durft het ordenen wel eens lang duren
(Vb: opvragen zonder order: 0.06s/query; met order: 0.24s/query!)

[servi]

Maar dan moet je elke keer je hash-tabel updaten als er een iets gepost wordt, right? Nuja, dat updaten zal zolang wel niet duren zeker?

beter de insert 0.1 seconden langer laten duren, dan de search 10 seconden langer te laten duren.
en is een bigint niet overdreven om de lengte van het woord uit te drukken?

nee het getal moet voor die lettercombinatie gegarandeerd uniek zijn of anders heb je problemen.

[JohnBeton]

Mmmmh
Ik denk dat ik het dan verkeerd begrepen heb...

Wat wordt er dan precies opgeslagen? Een hashwaarde van elk woord? (zal wel niet, want dan kan je evengoed de woorden zelf opslagen)

[servi]

Wat wordt er dan precies opgeslagen? Een hashwaarde van elk woord? (zal wel niet, want dan kan je evengoed de woorden zelf opslagen)


jawel die waarde wordt opgeslagen.
Met woorden kan je onmogelijk snel zoeken,
met getallen kan je heel snel zoeken
Als je een getal moet vinden tussen 0 en 1000, kan je dat getal vinden in maximaal 10 beurten, met woorden gaat dit niet zomaar.

[JohnBeton]

Wat wordt er dan precies opgeslagen? Een hashwaarde van elk woord? (zal wel niet, want dan kan je evengoed de woorden zelf opslagen)


jawel die waarde wordt opgeslagen.
Met woorden kan je onmogelijk snel zoeken,
met getallen kan je heel snel zoeken
Als je een getal moet vinden tussen 0 en 1000, kan je dat getal vinden in maximaal 10 beurten, met woorden gaat dit niet zomaar.

Maar die hash waar jij het over hebt is dan niet hetzelfde als md5()? (is zowat de enige waar ik een beetje familiar mee ben).
Want daar zitten toch ook letters in?

(van C++ ken ik niets btw, dus als het antwoord in die C++ code zit, vergeef mij )

[servi]

Maar die hash waar jij het over hebt is dan niet hetzelfde als md5()? (is zowat de enige waar ik een beetje familiar mee ben).
Want daar zitten toch ook letters in?


t'is daarmee dat ik die hash ga opslagen in een bigint ....

[JohnBeton]

Maar die hash waar jij het over hebt is dan niet hetzelfde als md5()? (is zowat de enige waar ik een beetje familiar mee ben).
Want daar zitten toch ook letters in?t'is daarmee dat ik die hash ga opslagen in een bigint ....

(dat had ik ook wel door, wat ik eigenlijk bedoelde: hoe zorg ik ervoor dat ik dit aan de praat krijg in PHP? )

(mhash?)

In ieder geval al bedankt!

[JohnBeton]

"Fatal error: Call to undefined function: mhash() in ..."

mhash is toch een "standaardfunctie"?

MOD: blijkbaar niet :/



Wat denken jullie van dit:
bin2hex(md5($string));

Zorgt dit voor een uniek getal?
Je kan trouwens toch ook met 2 verschillende strings 1zelfdemd5 hash bekomen, toch (kan is klein dat het gebeurd, maar toch...)?

[JohnBeton]

"Fatal error: Call to undefined function: mhash() in ..."

mhash is toch een "standaardfunctie"?

MOD: blijkbaar niet :/



Wat denken jullie van dit:
bin2hex(md5($string));

Zorgt dit voor een uniek getal?
Je kan trouwens toch ook met 2 verschillende strings 1zelfdemd5 hash bekomen, toch (kan is klein dat het gebeurd, maar toch...)?

Dit zou werken, moest het resultaat in een bigint passen

is zoeken in een int tabel sneller als in een chartabel, ook al bevat die char tabel enkel cijfers?

[JohnBeton]

En nog een nadeel: met deze methode kan je geen wildcards gebruiken

[JohnBeton]

Ik zit nu wel met een probleempje voor het opzoeken...

Stel dat het hele forum geindexeerd is, dat alle woorden > 2 karakters in de hashtabel zijn opgenomen.

Tabel bestaat uit hetvolgende:
hash | threadID



Als ik nu het volgende ingeef om te zoeken:
"(abcd OR efgh) AND ijkl"

Dan zou hij moeten zoeken naar alle threads waar ofwel "abcd" of "efgh" instaat, en waar altijd "ijkl" in staat...

Gaat dit anders dan met subqueries? (ik gebruik Mysql)
Of moet ik dit met code oplossen?

[Cakeman]

Miischien biedt dit een oplossing?
http://dev.mysql.com/doc/mysql/en/Fulltext_Search.html

[JohnBeton]

Miischien biedt dit een oplossing?
http://dev.mysql.com/doc/mysql/en/Fulltext_Search.html

Lijkt me sowieso niet al te snel naarmate het aantal posts stijgt.

[Cakeman]

Lijkt me sowieso niet al te snel naarmate het aantal posts stijgt.

Eventjes tussen de comments gesnuffeld en je hebt blijkbaar gelijk:

Greetings!

FYI benchmark freaks:

Currently, I'm using mysql's full text search support. I have a database of 3-5 million rows. Each row is unique, let's say a product. Each row has several columns, but the two I search on are title and description. I used the syntax above to create a full text index on title and description. Title has approximately 100 characters, and description has 255 characters.

At the moment, mysql is taking 50 seconds plus to return results on simple one word searches. My dedicated server is a P4, 2.0 Gighz, 1.5 Gig RAM RedHat Linux 7.3 platform, with nothing else running on it, i.e. another server is handling HTTP requests. It is a dedicated mysql box.

Obviously, the above performance is unacceptable for real world web applications.

[JohnBeton]

Inderdaad niet al te interessant

Heb trouwens nog een klein vraagje, misschien wel een eigen thread waard maar goed:
Ik zou willen kunnen werken met haken ('(' en ')') om de volgorde van zoeken te bepalen.
Stel dus dat er gezocht wordt naar "A AND (b OR c)", dan zou er eerst gezocht moetne worden naar "b OR c". Deze string is nog makkelijk te ontleden, maar stel nu dat hetvolgende gevraagd wordt:

"((A OR B) AND (C OR D))"
=> Eerst "A of B" vinden en "C of D", en daaruit dan de "AND" voorwaarde checken.

Nu is het probleem: hoe kan ik het best de "middelste" haakgroepjes hieruit filteren?

Alvast bedankt

[Ansur]

Inderdaad niet al te interessant
Stel dus dat er gezocht wordt naar "A AND (b OR c)", dan zou er eerst gezocht moetne worden naar "b OR c". Deze string is nog makkelijk te ontleden, maar stel nu dat hetvolgende gevraagd wordt:

...dan zou er eerst naar A gezocht moeten worden

Je kan mss de ingevoerde string parsen naar een SQL query en deze laten uitvoeren ofzo.