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

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í.