Hlavní navigace

PHP pro experty: Inteligentní vyhledávání

Martin Koníček

Potýkáte se s problémy s vyhledáváním na vašich webových stránkách? Čas potřebný pro vyhledávání je dlouhý a výsledky irelevantní? Přestaňte se spoléhat pouze na vyhledávání v databází MySQL a navrhněte si vlastní algoritmus, který zohlední všechny vaše požadavky!

Teorie relevance

Vyhledávač Google – jeden z nejoblíbenějších vyhledávácích strojů – hodnotí relevanci stránek zejména podle počtu klíčových slov, jejich umístění, jejich důležitosti (nadpisy atd.) a také podle počtu zpětných odkazů. To je ostatně jeden z mnoha důvodu, proč jeho popularita neustále roste.

I vy ovšem můžete mít část této revoluční technologie spoutanou na svém dynamickém webu. Nemusíte pro to ani psát složité algoritmy, stačí si přečíst tento článek a jednoduše implementovat námi vytvořenou knihovnu, jež zohledňuje mnohem více parametrů než klasické fulltextové vyhledávání v databázi MySQL.

O co se nyní tedy pokusíme? Hned zpočátku je potřeba převzít část technologie kvalitního a relevantního vyhledávače, abyste zajistili co nejpřesnější výsledky. Nebudeme se ovšem zabývat takovými maličkostmi jako počtem zpětných odkazů (který se zejména na redakčních webech stejně utváří zcela automaticky) či technologií na potlačení podvodů, protože předpokládáme, že budete indexovat pouze své webové stránky, jež máte plně pod kontrolou.

Pravděpodobně již nyní vás napadá, že je třeba zaměřit se především na hustotu klíčových slov a jejich pozici. Je takřka samozřejmé, že výskyt jakéhokoliv slova v nadpisu či perexu bude pravděpodobně důležitější než výskyt slova v obsahu článku. Jak lze ovšem tento předpoklad technicky realizovat?

Technologická realizace

Přestože se vám podle předešlého odstavce bude zdát realizace relevantního vyhledávání jako opravdový technický oříšek, nemusí tomu tak být. Zkusme si nyní představit, že máme jednoduchý redakční systém obsahující tabulku s články, která vypadá takto:

+----+--------+-------+-------+
| ID | Nadpis | Perex | Obsah |
+----+--------+-------+-------+
| 1  | PHP    | O PHP | Uvod d|
+----+--------+-------+-------+

Nyní se rozhodneme, že pro tuto tabulku vytvoříme databázi, která bude sloužit pouze pro hledání. Ano, vytvoříme si speciální tabulku, jež bude obsahovat každé slovo, k němuž bude přiřazeno ID článku a bodové ohodnocení závislé na jeho důležitosti (například slovo v nadpisu bude mít pět bodů, zatímco slovo v perexu bude mít váhu pouhé tři body).

+----+-----------+-------+-------+
| ID | Clanek_ID | Slovo | Score |
+----+-----------+-------+-------+
| 1  | 1         | PHP   | 5     |
| 2  | 1         | O     | 3     |
| 3  | 1         | PHP   | 3     |
+----+-----------+-------+-------+

Dobře, přeskočme nyní na chvilku praktickou realizaci tvorby této tabulky a přejděme do stavu, kdy již máme připravenu tabulku, jež obsahuje všechna hledaná slova v jednom sloupci a jejich bodové ohodnocení v druhém sloupci. Jistě vás napadne, jestli takové vyhledávání nebude pomalé. Mohu vás ujistit, že právě naopak, takovéto vyhledávání je mnohem rychlejší než běžné indexované vyhledávání v MySQL, jelikož dotaz se vyhodnocuje obdobně jako binární vyhledávání, jehož časová náročnost je řádově O(n) = log n, kde n je počet záznamů v tabulce. Z tohoto vzorce je zřejmé, že prohledání tabulky o velikosti 1.000.000 záznamů bude jen dvakrát pomalejší než prohledání tabulky obsahující 1.000 záznamů. Pro vaši představu, kdyby prohledávání tabulky o 1000 záznamech trvalo 0,3 ms (Athlon XP 1800+), tak prohledání tabulky o 1.000.000.000­.000 záznamů by trvalo 1,2 ms, což je v praxi neporovnatelně méně, než kolik by trvalo prohledání tabulky přes fulltextový index v MySQL.

Jak lze jedním SQL dotazem vybrat nejrelevantněj­ší data?

Ano slyšíte správně, použijeme pouze jeden rychlý SQL dotaz. Zkusme si představit, že do databáze zadáme následující dotaz:

SELECT
        Clanek_ID,
        SUM(Score) AS relevance
FROM search
WHERE Slovo = 'PHP'
GROUP BY Clanek_ID
ORDER BY relevance DESC;

Databáze MySQL začne pracovat nyní zhruba takto. Nejdříve vyhledá všechny výskyty slova PHP (což by mělo trvat méně než 1 ms), poté spočte počet bodů pro každý článek, a podle toho nám seřadí výsledky.

+-----------+-----------+
| Clanek_ID | relevance |
+-----------+-----------+
| 1         | 8         |
| 2         | 5         |
------------+------------

Cache vyhledávání

Výsledek dříve zmíněného vyhledávání nám je bohužel takřka stále k ničemu. Hlavním problémem je, že řeší pouze vyhledání jednoho slova a neřeší navázání na data o článku, která budeme potřebovat z databáze vybrat. Tento problém lze globálně možná řešit jediným SQL dotazem, ale z důvodu možného poklesu výkonu vyhledávání je pravděpodobně lepší výsledky vyhledání jednotlivých slov uložit do prozatímní tabulky, na kterou budeme dále navazovat výsledky dalších vyhledávání.

O praktické realizaci tohoto vyhledávání pomocí knihovny se dozvíte v dalším dílu. Ovšem zatím pouze pro přiblížení teorie vyhledávání prozradím, že princip ukládání výsledku do cache je založen na známé dvojici SQL příkazů INSERT..SELECT, která vybere data z databáze a následně je ihned vloží do nějaké tabulky bez použití PHP – to opět zajišťuje vyšší výkon, a o ten nám jde při vyhledávání především.

Vytváření indexu

Snad nejhorším bodem tohoto systému vyhledávání je vytváření indexu. Nejen, že je programově na realizaci nejvíce komplikovaný, ale je náročný i na výpočetní výkon. V mnoha případech to naštěstí nevadí, protože přidávání záznamů není tak časté a navíc indexování jediného záznamu trvá několikrát méně než jeho samotné vyhledání.

Indexování záznamu probíhá velmi zajímavým způsobem. Nejdříve je celý řetězec standardizován, poté jsou odstraněny speciální znaky, jako například pomlčka, hvězdička apod., a je ořezána veškerá diakritika. Slovo Motýlek je upraveno na slovo motylek. Poté je celý řetězec rozřezán na slova (pomocí funkce explode) a s příslušným bodovým ohodnocením vložen do databáze. I když se z principu jedná o relativně náročnou operaci, u řetězců v rozmezí několika kilobajtů (články, komentáře) probíhá indexace v nepozorovatelném čase. Ovšem je třeba upozornit na to, že tento princip není vhodné používat na indexování velkých objemů dat (knih, celých webů), kde je mnohem výhodnější doprogramovat indexování v Perlu či Pythonu, který je při indexování minimálně 10× rychlejší než samotné PHP.

Popis vlastností

Klady

  • Vysoká rychlost vyhledávání
  • Cachování výsledků
  • Nezávislost na zvoleném kódování češtiny
  • Relevantní výsledky

Zápory

  • Nutnost programové indexace (pomalejší vkládání záznamů)
  • Větší index

Pokračování

Bohužel už mi kvůli redakčnímu limitu nezbývá v tomto článku místo na popis praktické implementace, takže se vše dozvíte v dalším dílu. Praktická implementace bude obsahovat předpřipravené SQL tabulky i samotný kód knihovny určené k vyhledávání.

Poznámka

Zde uvedené příklady jsou pouze informativní z důvodu vysvětlení principu a nemají návaznost na samotnou implementaci vyhledávání. Nesnažte se proto raději na základě aktuálního článku vytvářet knihovny a počkejte si až na další díl, kde bude funkční a praktické řešení.

Našli jste v článku chybu?

13. 1. 2005 21:07

SoCo (neregistrovaný)

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 tres…

13. 1. 2005 1:10

Mustafa (neregistrovaný)

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

googleformore..





Vitalia.cz: Paštiky plné masa ho zatím neuživí

Paštiky plné masa ho zatím neuživí

Měšec.cz: Sleva na dítě a manželku pro OSVČ je zpět. Ale..

Sleva na dítě a manželku pro OSVČ je zpět. Ale..

Podnikatel.cz: K EET. Štamgast už peníze na stole nenechá

K EET. Štamgast už peníze na stole nenechá

Vitalia.cz: Mondelez stahuje rizikovou čokoládu Milka

Mondelez stahuje rizikovou čokoládu Milka

Podnikatel.cz: Přehledná titulka, průvodci, responzivita

Přehledná titulka, průvodci, responzivita

Měšec.cz: U levneELEKTRO.cz už reklamaci nevyřídíte

U levneELEKTRO.cz už reklamaci nevyřídíte

Podnikatel.cz: Podnikatelům dorazí varování od BSA

Podnikatelům dorazí varování od BSA

Podnikatel.cz: Udávání a účtenková loterie, hloupá komedie

Udávání a účtenková loterie, hloupá komedie

Lupa.cz: Insolvenční řízení kvůli cookies? Vítejte v ČR

Insolvenční řízení kvůli cookies? Vítejte v ČR

DigiZone.cz: Sat novinky: slovenská TV8 HD i ruský NTV Mir

Sat novinky: slovenská TV8 HD i ruský NTV Mir

Vitalia.cz: Láska na vozíku: Přitažliví jsme pro tzv. pečovatelky

Láska na vozíku: Přitažliví jsme pro tzv. pečovatelky

Vitalia.cz: Nejlepší obranou při nachlazení je útok

Nejlepší obranou při nachlazení je útok

Měšec.cz: Zdravotní a sociální pojištění 2017: Připlatíte

Zdravotní a sociální pojištění 2017: Připlatíte

Podnikatel.cz: Chtějte údaje k dani z nemovitostí do mailu

Chtějte údaje k dani z nemovitostí do mailu

120na80.cz: Na ucho teplý, nebo studený obklad?

Na ucho teplý, nebo studený obklad?

Vitalia.cz: Jsou čajové sáčky toxické?

Jsou čajové sáčky toxické?

Vitalia.cz: Potvrzeno: Pobyt v lese je skvělý na imunitu

Potvrzeno: Pobyt v lese je skvělý na imunitu

Vitalia.cz: Když přijdete o oko, přijdete na rok o řidičák

Když přijdete o oko, přijdete na rok o řidičák

Podnikatel.cz: Chaos u EET pokračuje. Jsou tu další návrhy

Chaos u EET pokračuje. Jsou tu další návrhy

Vitalia.cz: Pamlsková vyhláška bude platit jen na základkách

Pamlsková vyhláška bude platit jen na základkách