Domů › Programování › Vlastní vyhledávání – česky a relevantně

Vlastní vyhledávání – česky a relevantně

Každá stránka, nebo alespoň každá větší stránka, potřebuje nějaký druh vyhledávání. Setkáváme se s ním všude, takže opisovat nač je potřebné je plýtvání místem. Kromě jiného se taky často stává, že když si něco vyhledáte v googlu, tak se vám ve výsledcích zobrazí odkaz na výsledky vnitřního vyhledávání určité stránky, co v některých případech může znamenat zisk a udržení si zákazníka, jelikož se po vstupu na takovýto server bude pravděpodobně už pohybovat spíš v našich výsledcích a na google se vráti jen pokud nenajde to, co je pro něj relevantní.

Z tohoto důvodu je taky potřeba, aby vyhledávání na naší stránce bylo kvalitní. Je potřeba vyhledávaný řetězec najít všude kde je (a někdy i tam kde není – k tomu se dostaneme), podle jeho umístění mu dát váhu zvýraznit jej ve výpisu výsledků aby bylo uživatelům hned jasné že se v textu relevantní slovo skutečně vyskytuje a že si je naše stránka nevycucala z prstu, a nakonec samozřejmě výsledky zobrazit.

Samotné vyhledávání by jsme si tedy mohli rozdělit do několika kroků:

Úprava uživatelského vstupu.
Nalezení záznamů kde se vyhledávaný řetězec nacházi, a jejich vytažení z databáze.
Zjištění relevantnosti záznamu (na základě váhy a množství výskytů řetězce).
Zvýraznění nalezených řetězců v záznamu
Zobrazení

Půjdeme tedy postupně.

Pro ty líné – Existující řešení/postupy

Ano, PHP i MySQL (resp. SQL obecně) už obsahují funkce na porovnávání textu, které se dají použít při vyhledávání. Při MySQL se jedná jmenovitě o porovnávání s pomocí LIKE, MATCH … AGAINST, nebo REGEXP, přičemž první dvě varianty můžeme pro naše účely rovnou zahodit.

MySQL – LIKE

LIKE je klíčové slovo použitelné místo znaku rovnosti:

SELECT * FROM tabulka WHERE sloupec LIKE 'řetězec'

Hlavními výhodami LIKE je, že je jednoduché a poměrně rychlé. Konec.
Mezi nevýhody LIKE patří, že vám sice možná vyhledá relevantní záznamy, ale nic víc. Jen záznamy, které obsahují hledaný řetězec písmeno po písmenu stejně jako byl zadán.

Ano, v syntaxi řetězce se dají použít speciální znaky (např. _ pro libovolné jedno písmeno, nebo % pro libovolné množství libovolných znaků), ale s LIKE prostě nic víc nedokážete.

SELECT * FROM tabulka WHERE Text LIKE '%MySQL%'

vám tedy najde záznamy v tabulce kde v sloupci Text je kdekoliv slovo MySQL (například i v řetězci „kecykecyMySQLkecy“, tzn. Pokud slovo není odděleno mezerami). LIKE je case-insensitive, takže vám nalezne i mYsql, nebo jakékoliv další varianty. Pokud je však jedno z porovnávaných polí binární, stává se like case-sensitive.

Jak sami vidíte, LIKE je sice jednoduché, ale pro kvalitní vyhledávání skutečně nepoužitelné.

MySQL – MATCH … AGAINST

MATCH … AGAINST je dá se říci trošku rozšířený LIKE. Syntaxe je:

SELECT * FROM tabulka WHERE MATCH(sloupec1, sloupec2) AGAINST('řetězec')

V závorce za MATCH se nachází výčet sloupců kde se bude hledat text, a v závorce za AGAINST je zase hledaný text. Počet sloupců kde se hledá je libovolný. Text v against nemůže použít žádné speciální znaky jako v případě LIKE, ale na druhou stranu samotné AGAINST může mít druhý parametr, který určuje chování porovnávání. Nutno dodat, že MATCH AGAINST je aplikovatelný jen na polích v databázi které mají fulltext index.

Prvním parametrem je IN BOOLEAN MODE (zapisuje se

AGAINST('řetězec' IN BOOLEAN MODE)

) – tento parametr způsobí, že celý MATCH … AGAINST vrací váhu konkrétního záznamu. Dá se tedy použít v části SELECT, a po zadání aliasu pomocí AS získáte parametr na základě kterého se teoreticky data z databáze dají seřadit od nejrelevantnějších po ty nejméně relevantní.

SELECT který vrací takováto data může vypadat například:

SELECT *, MATCH(sloupec1, sloupec2) AGAINST('MySQL' IN BOOLEAN MODE) AS score
FROM tabulka WHERE MATCH(sloupec1, sloupec2) AGAINST('MySQL');

Tento příkaz vám vrátí tabulku kompletních řádků z tabulky “tabulka”, kde se buď v sloupci1 nebo sloupci2 nachází výraz MySQL, a na konec každého záznamu jěště připojí sloupec “score” kde bude číslo vyjádřující relevantnost daného záznamu. Toto číslo bývá obvykle v rozmezí 0 – 1, ale někdy se vyskytne i hodnota kolem 4.

Je třeba poznamenat, že MATCH AGAINST chápe řetězec jako množinu slov, takže při zadání víceslovného řetězce hledá v první iteraci jeho přesnou, celou formu, a v druhé iteraci rozdělí slova (podle mezer) a hledá je jednotlivě, což je oproti LIKE (které vždy hledá řetězec přesný) mírné zlepšení.

V BOOLEAN MODE máme taky možnost použít několik speciálních znaků, ale ne na upravení vyhledávaného řetězce, ale na určení důležitosti jednotlivých slov, resp. jejich příspěvku k hodnotě relevantnosti výsledku:

+ – dává se před slovo ve vyhledávaném řetězci a značí přesně to, co známe z vyhledávání na googlu: toto slovo se musí nacházet v každém nalezeném záznamu.
- – Mínus má taky stejné použití a funkci jako na www.google.com: slovo za ním se v žádném z vyhledaných záznamů nacházet nesmí.
( ) – výraz v nich je “podřetězec” (substring) a podle dostupných informací dává výskyt podřetězce záznamu větší váhu oproti případu, kdy se v něm jen vyskytují obě/všechny slova. Např.: máme podřetězec “(a tak)”. Ve výsledcích se objeví záznamy obsahující “a tak” stejně jako “tak a” , ale záznamy s “a tak” budou mít větší váhu/lepší score.
< > – operátory, mění (zvyšují/znižují) příspěvek slova kt. se za nimi nacházi, k celkové váze/relevantnosti záznamu. Např. Pokud hledáme >slovo, jeho výskyt relevanci záznamu ovlivní víc než bez modifikátoru, a naopak <slovo relevanci záznamu ovlivní méně.
~ – Tilda před slovem znamená, že výskyt slova v textu ovlivní celkovou relevanci záznamu negativně, tzn. Zníží ji.
” ” – dvojité uvozovky určují, že se bude vyhledávat jen přesná fráze v nich obsáhnutá, stejně jako na googlu.

Tyto modifikátory se dají libovolně kombinovat a ve výsledku se dá pomocí nich vytvořit poměrně silný vyhledávací nástroj.

Proč jsem teda na začátku řekl, že je to jen mírně vylepšený LIKE?

Protože oba tyto příkazy stojí a padají na uživatelském vstupu. Jednak je těžké si představit uživatele, který bude do vyhledávání zapisovat komplikovaný vzorec pomocí těchto modifikátorů, aby se dostal k tomu co hledá, a taky by se tyto modifikátory do vyhledávacího řetězce těžko doplňovaly automaticky (kdo napíše skript rozeznávající důležitá a nedůležitá slova má u mě pivo – možné to sice je, ale vyžaduje to zaznamenávání a analýzu statistik předešlých vyhledávání a je to komplikované).

A druhý bod je nejkritičtější, ale měl by být taky nejjasnější. Pochybnost uživatelského vstupu.

Jak nehledat blbosti – pochybnost uživatelského vstupu

V předchozí části jsme si ukázali příkazy v MySQL které by nám mohli při vyhledávání v databázi pomoct, a uzavřeli jsme ji tím, že nám příliš nepomůžou kvůli pochybnosti uživatelského vstupu.

V následující části si jěště ukážeme funkce které na pokročilejší porovnávání řetězců poskytuje PHP, a jejich výčet a popis uzavřeme přibližně podobnou větou.

Co tím ale vlastně myslím?

Všechny knížky o programování, anebo alespoň ty co za něco stojí, obsahují kapitolku která se věnuje uživatelskému vstupu a jeho ošetření, a poselství které by se dalo shrnout do jedné věty: Nikdy nevěřte uživatelům, protože buď nevědí co dělají, nebo to vědí až příliš dobře.

Každé pole kam necháme uživatele zadat vstup podle jejich libovůle je nebezpečné. Ne potenciálně, ale reálně. Buď může odhalit chybu v naší aplikaci/stránce, nebo může odhalit krátkozrakost/línost programátora v podobě nesmyslných výsledků při zadání nesmyslného vstupu. A můžete si být jisti, že tyto chyby skutečně i odhalí – jediná otázka je kdy se to stane. Vlastně teď mluvím najednou o SQL/PHP Injection a překlepech. A jelikož tento článek není o bezpečnosti ale o vyhledávání, tu injection vyškrtneme.

Pokud použijete na vyhledávání některou z funkcí uvedených výše, a použivatel zadá slovo s překlepem, nedostane nic. Nebo dokonce pokud uživatel zadá slovo správně, ale ten kdo obsah vytvořil v něm udělal překlep, taky bude počet výsledků nula.

A hledající bude zmateně nebo znechuceně zírat na obrazovku.

Problém je totiž v tom, že uživatel si většinou v obou těchto případech nebude vědom své chyby. V jednom z nich sice oprávněne – pokud je překlep v samotném textu stránky, skutečně to nebude jeho chyba, a to jednoznačně říká, že nemáme právo uživateli neposkytnout odpověď na jeho otázku. V druhém případě si za to sice může uživatel sám, ale to nás stále neopravňuje řvát na něj že je blbec (nebo spíš potichu se chechtajíc sedět v koutě). Takový uživatel (a tedy zákazník) spíš půjde někam jinam, kde mu stránka/aplikace najde to co hledá i s překlepy.

Zkrátka a jasně: zapamatujte si, že za chybu může programátor i když je na straně uživatele, a tedy by si ji měl i napravit.

Takže pokud uživatel udělá překlep, je třeba jej opravit, a tím se dostáváme k první části prvního bodu (zní to vtipně, že?) našeho vyhledávání: Úprava uživatelského vstupu: Oprava překlepů a chyb.

Mezi nejčastější a nejsnáze opravitelné “chyby” při psaní patří záměny písmen, ať už v důsledku hrubek (i/y), nekonzistentního používání diakritiky (ě/e, á/a, atď…) a některých “vysoce stylových” úmyslných záměn kterých se uživatelé dopouštějí (v/w, t/th…).

Stránek kde má uživatelská základna ve zvyku dělat chyby posledního typu je sice (doufejme) míň, ale proč s těmito druhy chyb nepočítat?

Dále jsou tady chyby které se opravují trochu komplikovanějším způsobem, jako například vynechaná písmena a podobně. Těm se budeme věnovat později, teď se zaměříme hlavně na záměny písmen.

Záměny písmen pomocí regulárních výrazů – Ať uživatelé najdou to co hledají i když to nehledají

V pořádku, takže dostaneme uživatelský vstup, a je potřeba zajistit, aby se nevyhledával přímo tento vstup, ale spíš všechny jeho alternativní varianty (tedy ty co počítají s tím, že je chybný, ale i ty které počítají s tím, že chybný je výskyt na stránce).

Takže vygenerujeme všechny možné variace vyhledávaného řetězce kde všechna písmena která můžou být chybná nahradíme jejich korektními i chybnými variantami a pak je dosadíme do query a pustíme?

Asi spíš ne: například ve slovu “například” je takovýchto písmen teoreticky 7 (tzn. písmena která mají verzi s diakritikou i bez ni, případně je to i/y), a pokud bychom chtěli vygenerovat všechny “varianty” tohoto slova, bylo by jich 2*2*2*4*3*2*2 = 384 (schválně jestli zjistíte jak jsme na to přišli…). Takže by jsme buď museli udělat query s 384 OR pro jedno slovo, nebo 384 samostatných query pro každou variantu.

Mimochodem, na počet variant jsme přišli tak, že písmena které ve slovu “například” mají vícero “variant” jsou nařílad, přičemž při n jsou to dvě varianty (n, ň), při a dvě (a, á), a tak dále…

Ptáte se proč 4 varianty při í? Odpověď je jednoduchá – hrubky. Takže pod variantami písmena í chápeme í, i, ý, y.

Ale nezoufejte – v této chvíli nám na pomoc přijdou regulární výrazy (regular expressions, nebo taky regexp, nebo regex), a jejich podpora v MySQL, kterou zabezpečuje klíčové slovo REGEXP.

Pokud nevíte co regex-y jsou a jak se používají, doporučuju vám podívat se na stránku www.regular-expressions.info, protože je to téma rozsahově daleko mimo možností tohoto tutorialu. Dialektů regexp-ů je vícero, ale jejich nuance nás zatím zajímat nemusejí, protože se budeme snažit používat jen jejich základní možnosti.

Takže jak nám regexpy pomohou v našem vyhledávání?

Velice – vezmeme uživatelský vstup, uděláme z něj regulární výraz který umožňuje všechny alternativy hledaného řetězce, a ten pak budeme v dotazu na databázi porovnávat s poli ve kterých hledáme.

Abychom tedy ošetřili všechny varianty slov, je třeba nahradit písmena která mají i další “varianty” za regulární výraz který je pokryje. Na základě tohoto řetězce pak budeme vyhledávat v databázi.

Napíšeme tedy funkci, která přijme vyhledávaný řetězec, projde jej po znacích, a když narazí na nahraditelný znak, tak jej pochopitelně nahradí za kousek regexpu.

Kódování naše každodenní

Aby to nebylo tak jednoduché, musíme si říct jěště něco o kódování – snad každý už dnes používá utf8, což je pochopitelně dobře, protože se tím vyhneme mnoha problémům s diakritikou, ale z hlediska programování v PHP, a hlavně programování manipulace s textovými řetězci to přináší jisté komplikace.

Utf8 je totiž kódování multibajtové, tzn. jeden znak se zakóduje buď jedním (pokud se jedná o znaky které pokrývá standardní ASCII kódování), nebo několika bajty (znaky charakteristické pro jednotlivé jazyky, jako např ř, č, ť…).

Takže pokud na textový řetězec kódovaný jako utf-8 použijeme standardní funkce PHP jako např. substr nebo strlen, výsledek takovéto funkce bude zákonitě nesprávný, protože tyto funkce nejsou pro multibajtové kódování uzpůsobeny. Je tedy potřeba použít verze těchto funkcí, které dokáží pracovat i s multibajtovými řetězci. Tedy mb_substr a mb_strlen.

Pro kompletní výčet funkcí na práci s textovými řetězci které existují i v multibyte variantě doporučuju na stránce www.php.net zadat do vyhledávání „mb_“, my se však obejdeme jen s těmito dvěma.

Teď, po tomto obsáhlém úvodu, se konečně můžeme pustit do skutečného programování.

Vyhledávání

Úprava uživatelského vstupu

Napíšeme si tedy v PHP funkci, která bude mít jako vstupní parametr vyhledávaný řetězec, a jako návratovou hodnotu poskytne tento řetězec upraven ve formě regulárního výrazu.

function search_string_prepare($search)
{
	//pole s informacemi o náhradách znaků za kousky regulárních výrazů
	$reps["a"] = $reps["á"] = "(a|á)";
	$reps["c"] = $reps["č"] = $reps["ć"] = "(c|č|ć)";
	$reps["d"] = $reps["ď"] = "(d|ď)";
	$reps["e"] = $reps["é"] = $reps["ě"] = "(e|é|ě)";
	$reps["i"] = $reps["í"] = $reps["y"] = $reps["ý"] = "(i|í|y|ý)";
	$reps["l"] = $reps["ľ"] = $reps["ĺ"] = "(l|ľ|ĺ)";
	$reps["n"] = $reps["ň"] = $reps["ń"] = "(n|ň|ń)";
	$reps["o"] = $reps["ó"] = $reps["ô"] = "(o|ó|ô)";
	$reps["r"] = $reps["ř"] = $reps["ŕ"] = "(r|ř|ŕ)";
	$reps["s"] = $reps["š"] = $reps["ś"] = "(s|š|ś)";
	$reps["t"] = $reps["ť"] = "(t|ť)";
	$reps["u"] = $reps["ú"] = $reps["ů"] = "(u|ú|ů)";
	$reps["z"] = $reps["ž"] = $reps["ź"] = "(z|ž|ź)";

	//pokud je řetězec víceslovný, rozdělíme jej do pole po slovech, abychom mohli
	//kontrolovat výskyty jednotlivých slov
	$words = explode(" ", $search);

	//projdeme postupně všechny slova a uděláme v nich potřebné úpravy
	foreach($words as $key=>$word)
	{
		//projdeme postupně po znacích celé slovo
		for($c1 = 0; $c1 <= mb_strlen($words[$key], "UTF-8"); $c1++)
		{
			//jestli v poli náhrad pro aktuální znak existuje náhrada
			if($reps[mb_substr($words[$key], $c1, 1, "UTF-8")])
			{
				//zjistíme potřebný posun needle ($c1) po dosazení, abychom přeskočili
				//celý dosazený text a nenahrazovali části z něj (pokud chcete vidět co
				//se stane když needle neposuneme, následující řádek vykomentujte a na
				//konci každého cyklu si dejde vypsat $words[$key])
				$shift = mb_strlen($reps[mb_substr($words[$key], $c1, 1, "UTF-8")], "UTF-8");
				//teď uděláme náhradu
				$words[$key] =
				mb_substr($words[$key], 0, $c1, "UTF-8") .
				$reps[mb_substr($words[$key], $c1, 1, "UTF-8")] .
				mb_substr($words[$key], $c1 + 1, 90000, "UTF-8");
				//a posuneme needle
				$c1 = $c1 + $shift - 1;
			}
		}
	}

	//vrátíme pole s upravenými slovy
	return $words;
}

Nalezení záznamů obsahujících vyhledávaný řetězec

Když teď máme funkci na vygenerování správného regexpu pro náš vyhledávací řetězec, dalším krokem je vybrat z databáze ty záznamy, které tento řetězec obsahují.

Předpokládejme tedy v MySQL tabulku s položkami ID (INT), Owner (VARCHAR(40), Title (VARCHAR(255)) a Text (TEXT nebo LONGTEXT) a že vyhledávací řetězec skriptu dodáme přes get parametr search.

V PHP tedy vygenerujeme dotaz který z databáze vybere záznamy kde našemu vyhledávacímu regexpu odpovídá alespoň jedno, nebo vícero z těchto polí.

//vytvoříme z uživatelského vstupu regex
$search = search_string_prepare($_GET["search"]);

//spojíme pole do jednoho řetězce (s pomocí .*, tzn. mezi jednotlivými slovy
//může být libovolný počet jiných znaků). taky řetězec upravíme na kapitálky
//a budeme porovnávat s obsahem databáze taky převedeným na velká písmena, aby
//se nám nestalo že nedostaneme výsledky jen kvůli rozdílnosti velikosti písmen)
//původní $search se nám v dalším bodu jěště bude hodit

$sqlSearch = mb_strtoupper(implode(".*", $search), "UTF-8");
$query = "SELECT * FROM tabulka WHERE (Owner REGEXP '$sqlSearch') OR (Title REGEXP '$sqlSearch')
OR (Text REGEXP '$sqlSearch');";

$qr = mysql_query($query) or die(mysql_error());

Teď už máme údaje z databáze načteny a další krok je vypočítat relevantnost jednotlivých záznamů a zároveň zvýraznit výskyt vyhledávaných slov v textu.

Uděláme to tak, že budeme jednotlivé záznamy přidávat do pole výsledků a indexovat je pod hodnotou jejich relevantnosti (váhy).

while($fqr = mysql_fetch_assoc($qr))
{
	$weight = 0;

	//spočteme výskyt hledaného slova
	foreach($search as $val)
	{
		$val = mb_strtolower($val, "UTF-8");

		//spočteme výskyt slova a vynásobíme jej důležitostí podle toho kde se
		//nachází. Pokud se například slovo nachází ve jméně autora, je pro nás v
		//tomto případě 50x relevantnější než když se nachází v textu
		//pravidla váhy je samozřejmě potřeba upravit pro vaše účely
		$weight += preg_match_all("/(?i)$val/", strtolower($fqr["Owner"]), $trash)*50 +
		preg_match_all("/(?i)$val/", strtolower($fqr["Title"]), $trash)*2 +
		preg_match_all("/(?i)$val/", strtolower($fqr["Text"]), $trash);

		//zvýrazníme nalezená slova
		$fqr = preg_replace("/(?i)($val)/", '<strong>$1</strong>', $fqr);
	}

	//přidáme záznam do pole výsledků pod index shodný s váhou výsledku
	$resultArray[$weight][] = $fqr;
}

//seřadíme pole od nejvyšších indexů (relevantností) po nejnižší
krsort($resultArray);

V $resultArray se nám teď nachází několik položek s číselnými indexy. Tyto indexy označují váhu a pod nimi nalezneme jeden nebo vícero kompletních záznamů z DB, které mají všechny tuto váhu/relevantnost. To jak si seřadíme samotné tyto položky je už na nás.

Zobrazení

Velice jednoduše, například

<ul>
<?php
foreach($resultArray as $weight)
{
	foreach($weight as $item)
	{
		?>
		<li>
		<h3><?php echo($item["Title"] . ", " . $item["Owner"]);?></h3>
		<div><?php echo($item["Text"]);?>
		</li>
		<?php
	}
}
?>
</ul>

Konkrétnější implementace samozřejmě závisí od struktury stránky v konkrétním případě, nebo například od toho, jestli používáte např. Smarty…

Výhody takovéhoto vyhledávání: