Názory k článku PHP pro experty: Inteligentní vyhledávání

"poté jsou odstraněny speciální znaky, jako například pomlčka, hvězdička apod."

tohle totalne suckz :-) pak ma clovek najit neco o C++ nebo A* ... IMHO dobry vyhledavac ulozi formu se spec. znaky i bez znaku a pri vyhledavani to nejdriv zkusi i se spec. znakama a teprve kdyz nic nenajde tak je odstrani

Takze ked "M*o*t*ý*l*e*k" => "Motýlek"
potom "open-source" => "opensource" a nie "open source"

Toto ste chceli, slovaci? ;-)

Co takhle

Schwarz-Cauchy-Buňakovského nerovnost => schwarzcauchybunakovskeho nerovnost

balíček fonts-xorg-ISO8859-2-100dpi => balicek fontsxorgiso88592100dpi

Třeba to patří do ,Zde uvedené příklady ... nemají návaznost na samotnou implementaci vyhledávání.` A ořezávání diakritiky snad taktéž.

Jasně, to chce pořádnej parser. Problematika fulltextu je daleko komplikovanější.

Asi by to adhoc řešení chtělo "zabalit" do nějaké matematiky. Např. vektory podobnosti, které se používají v IR, vykazují dobré výsledky a nejsou náročné na implementaci...

No, asi by to tam chtelo vlozit oboji kdyz prochazim text, cili by tam sly slova:
schwarzcauchybunakovskeho nerovnost schwarz cauchy bunakovskeho

No a je to ... :o)

... ja mel za to, ze FULLTEXT index v mysql pracuje prave takto. Muzete nekdo objasnit, jak to teda v ramci MySQL funguje?

fulltext v mysql funguje vypoctom vektorov podobnosti... treba si to predstavit tak, ze je v databaze 1000 unikatnych slov a tak je vytvorenych 1000 "dimenzii" a kazdemu slovu priradena jedna. Kazdy zaznam ma nejaky vektor vypocitany z klucovych slov. Pri hladani sa z hladanych slov vypocita vektor a porovna sa rozdiel uhlu od vektoru klucoveho slova a vsetkych vektorov v indexe. Vypocita sa cosinus a to da cislo od 0 po 1, kde 0 je ziadny match a 1 je uplny match. Ked sa k tomu doda nejaky treshold napr. 0.7 a vysledok sa zoradi, tak to ma vystup ako mysql fulltext.

Problem mysql je, ze nevie ohybat slova - funguje dobre pri anglictine (este lepsie ak sa slova dostanu do neurcitych stavov, resp. korenov). Pri jazykoch ako slovencina, kde neexistuje moznost jednoduchou funkciou zistit koren slova - je problem, resp. ovela mensia ucinnost ("prirucky o linuxe" vs. "prirucka linux" == 0% match). Ak sa chce korektne vyhladavat, je treba zohnat si lematizator :)

Ja si myslim, ze kazdy clovek si upravy zaradovaci algoritmus sam. Takze mozte pomlcku zachovat, pripadne ju nahradit medzerou, alebo pri vyskyte slova napr. "open-source", ulozit aj jeho ekvivalenty "open source" a opensource (trosicka nam narastie velkost databazy ;-). Clanok len ukazuje "ako na to", vlastne zaradovanie do databazy a uprava kazdeho slova je zalezitost web-designera.

P.S.: Slovo un*x moze vo vyhladavaci znamenat: "Hladaj vsetky slova obashujuce un ..... x, ale pri indexovani
je dobre hviezdicky odstranit, mnoho ludi "okrasluje" svoje texty niecim podobnym ako napr.: O*p*e*n*S*o*u*r*c*e).

Dost dobře nechápu, co je jako rychlější než "indexované vyhledávání v MySQL". Snad měl autor na mysli, že to bude díky indexu rychlé, pokud bude mít indexy na ID článku a slovu... S logaritmickou složitostí (o základu dva - většinou, zleží na typu indexu).

Řetězec standardizován? Co je to za pojem? Snad parsován ne? Rozhodně bych začal u kvalitního parseru. Ten je velmi důležitý a data může znehodnotit velice. Například internetové odkazy, emaily, zkratky. To všechno představuje problém. Pokračoval bych synonymy, stemmingem a stop slovy - některá slova nemá cenu indexovat, protože neposkytují informační hodnotu a jen zvětšují index (spokjy, částice, citoslovce atd).

Ty bonusy by neměly být tak velké, kvalitní fulltextové knihovny nedávají velké bonusy za kontext, ale spíše se zaměří na absolutní a relativní výskyty termu, délku dokumentu, entropii a podobně. Dokáží na základě statistických metod vyfiltrovat slova, které nejsou relevantní.

Tohle je opravdu _velmi_ jednoduchý fulltext s dvoustavovým výskytem, který jen se štěstím bude vykazovat dobré výsledky. Pokud něndo napříkad nadpisem vytvoří nějaký off-topic text v diskuzním příspěvku, velmi tak ovlivní chování algoritmu.

O indexech nad ID, tedy primarnim klicem slysim poprve v zivote. Pokud vim, nad ID se v MySQL nikdy index nedava.

to ze se neco jmenuje ID jeste neznamena, ze je to PRIMARY klic. Toto nebylo explicitne v clanku uvedeno, i kdyz z kontextu to vyplyva. Predpokladam, ze to bude i auto_increment.

samozrejmne, protoze je automaticky na kazdym pk unikatni index...

No takže asi tak. :-)

Kdyby to ještě někdo nechápal, tak zde uvedu, že primární klíč automaticky na většině SQL strojích vytvoří i index, navíc je jedinečný.

Bez indexu by jaksi primární klíče neměly praktický smysl...

Ještě k té rychlosti: pokud bychom měli tabulku se strukturou navrženou v článku, tak slovo s častým výskytem (třeba ty neošetřená stop slova) by při použití v dotazu stejně způsobilo procházení (rozuměj operace s diskem) značné části tabulky index neindex. Ten bilión záznamů za milisekundy je opravdu velká nadsázka.

Místo score by možná bylo lepší ukládat prostě pořadí slova od začátku textu (text = nadpis + perex + tělo) a definovat nějakou funkci, která score spočítá. Umožní se tím i použití proximity operátorů (hledání frází) a algoritmus je nezávislý na uložení nebo strukturování článků.

BTW: sice je to PHP pro experty a ne SQL pro experty, ale opravdu by hledání více slov jedním dotazem vedlo k poklesu výkonu? Domnívám se, že v mnoha případech by to bylo naopak - minimálně pro spojení slov operátorem OR.

Ano, spojení slov OR by zvýšilo výkon prohledávání, nicméně uživatelé chtějí většinou AND. Google byl jeden z prvních vyhledávačů co přišel se standardním AND, v té době kdy altavista ještě používala OR.

Ohledně přiřazování scóre to záleží na parseru. Můžete si naprogramovat vlastní, který zohlední datum, pozici v textu, prostě cokoli. Mým cílem je představit základní implementaci, který si každý doupraví. Ostatně cílem článku je vyprovokovat programátory k vytvoření lepšího hledání a zaslání názorů a připomínek. Přeci jenom buďme upřímní, vyhledávání na mnoha webech je přinejmenším nedostačující.

S tím PHP pro experty máte pravdu, na SQL jsou ty jiní odborníci. Rád se přiučím pokud někdo zkomentuje výkony SQL v různých operací. Nejsem expert přes SQL, jediné co jsem potřeboval řešit byla opravdu velmi chabá možnost v SQL rozumně vyhledávat.

Některé výsledky hledání řazené podle data také podle toho vypadají. Zkuste si jen na Root.cz vyhledat slovo Slackware, o relevantnosti výsledku lze stěží mluvit, a takto je 80% webů. Root.cz je typickým příkladem, kdy komentář má stejnou váhu jako titulek článku a to se já snažím řešit.

Co takhle:

SELECT Clanek_ID, COUNT(DISTINCT Slovo) AS wordcount, SUM(Score) AS relevance
FROM search
WHERE Slovo IN ('instalace', 'PHP')
GROUP BY Clanek_ID
HAVING wordcount = 2
ORDER BY relevance DESC;

Obecně je třeba brát v úvahu režii na parsování SQL dotazu a případně režii na vytváření temporary tabulky, ale tyhle věci záleží na použité databázi.

A teď mi řekněte, proč vymýšlet další super originální řešení web vyhledávače... Není jich snad dost?

Proč se radši nepřipojíte k nějakému z existujících projektů a nevylepšujete ho? Snad je nám všem jasné, že vyhledávačů jsou mraky a většina jich je velmi špatných i přesto, že na tom jejich vývojáři nechali spoustu a spoustu času.

Tak to si rad poslechnu jmena tech projektu, zadne takove jsem nenasel. Ano, jsou tu nejake v PHPcku, ale vetsinou se nejedna o knihovny, ale cele stroje, a to mi je jako asi vetsine PHP programatoru k nicemu.

BTW otazka jestli je jich dost je podle me irelevantni. To je jako rici je 1000 redakcnich systemu a stejne se vyvijeji dalsi a dalsi. Ono totiz kdyz clovek zacne ty RS prochazet, zjisti ze tenhle ma tuhle nevyhodu, tenhle onu, a tamten zas jinou.

Muj cil je nabidnout snadne, ciste reseni, ktere si kazdy doupravi.

Přes vesměs oprávněnou kritiku v komentářích myslím, že článek je zajímavý a přínosný. Těším se na pokračování, které doufám osvětlí další věci. Hlavně by mě zajímala například implementace onoho fultextového MySQL indexu, případně zda se musí řešit nějaké prořezávání indexovaných výrazů (má to vůbec význam?), nebo jak řešit podobnost porovnávaných slov - vesměs kritika ohledně odstraňování diakritiky a dalších znaků vede na zavedení fuknce, které spočte podobnost mezi dvěma výrazy.

Psát si vlastní vyhledávač pro nějaký PHP projekt v dnešní době? To mi přijde jako naprostý nesmysl.

V praxi jsem se setkal asi s takovýmto rozložením potřeb:
- 80 % projektů bohatě vystačí s trapným SELECT .. LIKE '%slovo%' AND/OR .. LIKE .... anebo s MySQL fulltextem
- 10 % projektů vystačí s ještě trapnějším mnogosearch
- 10 % projektů potřebuje nějaký hodně pokročilý vyhledávač, který ovšem sami napsat nezvládneme, ať už z nedostatku znalostí anebo času

Možná byste se někteří divili, jak je to SELECT LIKE krásně rychlé a funkční :) Řazení dle relevance netřeba, maximálně podle data.

proč ten můj příspěvek skončil úplně nahoře? nebo se mi to jen zdá? nebo jsem haxoooor? vidí ho ještě nahoře?

Taky ho vidím nahoře, asi nějaká chybka.

1. Z čeho autor vychází, když tvrdí, že tento způsob je rychlejší než "běžné indexované vyhledávání v MySQL", když hledání nad FULLTEXT indexem funguje principiálně podobně?

2. Když už je celý odstavec věnován popisu toho, jak je to úžasně rychlé, jak může zůstat nezmíněno, že nad sloupcem Slovo musí být vytvořen index, bez kterého to naopak bude velmi pomalé?

3. Proč není nad sloupci (Slovo, Clanek_ID) zřízen unikátní index a hodnoty v těchto sloupcích se mohou opakovat? Data se tak zbytečně nafukují a všechno se zpomaluje.

No nic, článek dobře zapadá do seriálu "PHP pro experty".

1. Hledani nad fulltextem funguje podobne, ale ne stejne. Predevsim vychazim z toho, ze standardni indexy nemaj cache a navic zaznamu v indexu neni tolik.

2. Ano, indexy by tam byt meli

3. Neznam zpusob jak zajistit, aby se data nenafukovala a nezpomalit vkladani dat do databaze. Nicmene muzete udelat SUM na celou tabulku a nekde v CRONu to jednou za mesic komprimovat, coz je asi nejefektivnejsi cesta.

No, s fulltextem mysql jsem mel v minulosti obcas problemy.
Jednak slovo, ktere se vyskytuje vice nez v 50% stranek to ignoruje (coz je blby hlavne ze zacatku kdyz je v systemu malo dokumentu, nebo kdyz nekdo zada hledani ve stylu "Bezneslovo AND Vzacneslovo" - pokud se "bezneslovo" vyskytuje ve vice nez 50% dokumentu, nenajde se nic)
Taky to neindexuje veci kratsi nez asi 4 pismena (jde to sice zmenit, ale chce to prava roota, neboli vrtat se v konfiguraci mysql, coz na hostingu neni.)
Cili kdyz hledam treba slovo "vlk" tak mam smulu ...

A ma to celkem dost problemu s diakritikou.

Na mensi mnozstvi dokumentu a pri male navstevnosti stranek lze pouzit "select ... where like '%slovo%'", jenze to prochazi pri kazdem hledani vsechny dokumenty v databazi, coz je celkem hloupe .... vetsi navstevnost ci mnoho dokumentu tohle uz neutahne.

Takze pak je potreba mit nejaky vlastni system .... to co tam je v mysql je spis takovy nanastavitelny quick fix nez poradne vyhledavani

Ignorování moc častých slov lze vypnout buď ve zdrojáku (je to sice popsáno v dokumentaci, ale moc použitelné řešení to opravdu není) nebo použít BOOLEAN MODE, který je k dispozici od MySQL 4.0.

1. Já tedy nevím, jak přesně bude cache implementována, ale podle toho nástinu, který je uveden v článku, k žádnému výraznému zrychlení nepřispěje. Rozhodně ne takovému, které by se nedalo zařídit i elegantněji.

3. Jde o to, že proces ukládání do databáze je už tak dost pomalý (což je zmíněno i v článku) a navíc se dělá na úrovni PHP. Z toho plyne, že je možné ho navrhnout tak, aby data ukládal efektivně a nevedl k výraznému zpomalení tohoto procesu, který navíc není tak důležitý, jako rychlost vyhledávání.

1. Cache je implementována na úrovni slov, v určitých případech ke zrychlení dojde. Pokud třeba máte server o PDA, a každý hledá text PDA xxxxx, tak potom se bude PDA tahat z cache a vyhledávat se bude jen druhé slovo. Nicméně samotný proces vyhledávání je již tak rychlý, že cache je tam spíše jako temporary tabulka, která mimo jiné cachuje, ale hlavně se z ní tahaj přímo výsledky a nikoli jednotlivá slova.

3. Ano je možné navrhnout jej, aby se data ukládala efektivněji. Nicméně se zvýší zátěž databázového serveru a ne PHP serveru. Zatímco já ukládám slovo jedním SQL dotazem, ostatní řešení potřebují minimálně 2 SQL dotazy. Navíc jak říkám, výkonově je mé řešení lepší, protože nevzniká fragmentace a data jsou do databáze ukládány sekvenčně. Z mých zkušeností je lepší řešení než tady něco sečíst a pozměnit raději to všechno naházet na hromadu a pak jednou za čas přepočítat tabulku.

Clanek jsem si otevrel jako PHPkar a i kdyz je tenhle dil spis o algoritmu, myslim, ze je to inspirujici pro me, jako pro cloveka, ktery neni expertem na vyhledavani. Dobry napad, sem s dalsim dilem!

"jehož časová náročnost je řádově O(n) = log n,"

Takto sa to nepouziva. Viac sa hodi casova narocnost je O(logn). Tiez plati, ze vyrazy s velkym O sa daju vzdy na pravu stranu rovnosti (napr. f(n)=g(n)+O(h(n)) )

Zdravim

Poznámka: Vhodné by bolo v článku jednotlivé tabuľky pomenovať, aby bolo jasné o ktorej človek akurát hovorí (aj v článku aj tu v komentároch).

K tomu vykonu zatiaľ iba toľko, že nerozumiem, prečo sú v tabuľke indexu uložené celé slová. Keď budem mať 100 článkov o PHP a v každom sa toto slovo vyskytne v priemere 5 krát, tak to bude 500 krát v tabuľke. To teda tej výkonnosti nepridá.

Podľa mňa by bolo vhodné vytvoriť tabuľku iba na slová, s dovma stĺpcami. Prvý by bol číselný, predstavujúci ID slova a bol by to primárny kľúč. Druhý stĺpec textový a nad nim by bol unikátny index.

V tabuľke indexu by sa potom stĺpec "Slovo" zmenil na niečo ako "id_slovo" a hlavne by bol číselný.

Ďalšia vec je, že ak sa slovo v článku vyskytuje viackrát, do tabuľky indexu ho stačí zapísať iba raz, pričom "Score" by bola suma tej relevancie. Pre daný ukážkový príklad, by pre slovo "PHP a článok 1 bol záznam:
ID = ?,
Clanok_ID = 1,
Slovo_ID = 3,
Score = 8.

Stĺpec "ID" je úplne zbytočný, čiže by tam nemal byť a primárny kĺúč na tabuľke by bol kombinácia Clanok_ID, Slovo_ID. A ešte by sa zišiel index nad stĺpcom Slovo_ID.

Tým pádom už je jednoduché aj vyhľadávanie viacerých slov a ani nepotrebujem kešovanie. Napr. budem chcieť vyhľadať články, pričom zadám reťazec "PHP SQL funkcie". reťazec najprv podľa potreby rozparsujem na jednotlivé slová a z tabuľky slov vyberiem ich IDčka.
Tie si v cykle uložím do reťazca pre SQL operátor "IN" (pre tie tri slová by som napr. dostal reťazec z IDčiek "1,5,28"). A nakoniec vyhľadám jednotlivé články:

SELECT Clanok_ID, SUM(Score) AS relevance
FROM search
WHERE Slovo_ID IN (1,5,28)
GROUP BY Clanok_ID
ORDER BY relevance DESC;

PS: No Takže k tej mojej poznámke na začiatku. Tá druhá tabuľka sa teda volá "search". Ale aj tak by mali byť ich názvy explicitne uvedené v článku.

Tak zatiaľ.... Uvidíme, čo bude v pokračovaní. :)

Jasně, příště bude implementace. Je možné, že když někdo napíše lepší implementaci s lepším algoritmem, rád ji nahostuji na svém webu a dáme ji tady na root.cz do novinek, v tom by neměl být problém.

Ono upřímně jedna věc je vmýšlet hezkou teorii (takových jsem měl) a druhá věc je najít čas a doťukat jí do použitelnosti. A bohužel se mi na každou věc i v open source produktech snáší kritika, ale opravy nikdo neposílá :(

Mno. Tak ja som tam toho napisal dost. Tak to mozes brat ako opravu. :)

Tady je neco podobneho pro Perl:
http://www.perl.com/pub/a/2003/09/25/searching.html?page=1

http://www.risearch.org/
http://www.phpdig.net/
http://www.me.lv/jse/index.html

googleformore..