Překlepy ve vyhledávání

Školení, která pořádám

Pokud se uživatel překlepne při vyhledávání, obvykle se mu nenajde žádný nebo jen velmi málo výsledků. Může být zmaten a svoji vlastní chybu si neuvědomit. Někdy ani správný tvar slova nazná. Proto mu můžeme k vyhledávání nabídnout seznam podobných slov, která mohl mít na mysli.

V PHP lze pro nalezení podobných slov použít funkce similar_text nebo levenshtein, pro angličtinu také funkci soundex, která je k dispozici i v MySQL.

Opravy bychom měli nabízet jen v případě, že nenalezneme žádný nebo jen velmi málo dokumentů a zároveň existuje dostatečně podobné slovo, které vrátí výsledků více:

<?php
$result = mysql_query("SELECT url, nadpis FROM clanky WHERE MATCH(nadpis, clanek) AGAINST ('" . mysql_real_escape_string($_GET["search"]) . "')");
$nalezeno = mysql_num_rows($result);
while ($row = mysql_fetch_assoc($result)) {
    echo "<a href='$row[url]'>" . htmlspecialchars($row["nadpis"]) . "</a><br />\n";
}
mysql_free_result($result);
if (!$nalezeno) {
    $podobne = array();
    $result = mysql_query("SELECT slovo FROM nejhledanejsi WHERE slovo != '" . mysql_real_escape_string($_GET["search"]) . "'");
    while ($row = mysql_fetch_assoc($result)) {
        if (levenshtein($row["slovo"], $_GET["search"]) <= 2) {
            $podobne[] = "<a href='?search=" . urlencode($row["slovo"]) . "'>" . htmlspecialchars($row["slovo"]) . "</a>";
        }
    }
    mysql_free_result($result);
    if ($podobne) {
        echo "Neměli jste na mysli " . implode(" nebo ", $podobne) . "?\n";
    }
}
?>

Funkce levenshtein vrací počet změn potřebných k převedení jednoho řetězce na druhý (pozor na to, že pracuje v jednobajtovém kódování), uvedený kód tedy dovoluje dva překlepy. Tabulku nejhledanejsi můžeme buď předem naplnit slovy, o kterých naše stránky pojednávají, nebo ji můžeme aktualizovat podle skutečně hledaných slov (v tom případě by ale bylo vhodné zohlednit i počet výsledků, který dané slovo nalezne, aby se uživateli nenabídl jiný překlep).

Uvedený kód předpokládá, že uživatel vyhledává samotné slovo. Pokud vyhledává více slov, bylo by obvykle žádoucí mu pro každé slovo nabídnout překlepy zvlášť.

Jakub Vrána, Řešení problému, 7.2.2007, diskuse: 25 (nové: 0)

Diskuse

Michal Hantl:

Zdá se mi to, nebo procházíš v tom dotazu opravdu všechna slova slovníku nejhledanějších? V tomto případě by bylo ideální mít u každého z nejhledanější uložený nějaký soundex a neprocházet každé slovo.

7.2.2007 10:35:14

Jakub Vrána :

Myslíš zkombinovat soundex a levenshtein? Se soundexem je ten problém, že když uděláš překlep v prvním písmenu (nebo ho vynecháš nebo přidáš), tak je soundex úplně jiný. Dalo by se to samozřejmě taky ošetřit, ale už by s tím bylo dost práce a výrazné zrychlení by to nepřineslo. Soundex je navíc použitelný jen v angličtině.

Nejvyhledávanějších slov by nemělo být moc (desítky), takže bych se výkonostních problémů nebál.

7.2.2007 10:51:52

Michal Hantl:

Pakliže budou desítky bude pravděpodobnost že se najde hledané slovo je dost malá. Jinak dík za poučení s tím soundexem, chtělo by to vymyslet něco aby se "podobné" slova daly najít jedním dotazem podle nějakého chytrého indexu.

Souhlas s Michalem.

8.2.2007 12:44:25

Jakub Vrána :

Příklad, kdy to může fungovat podle mě docela dobře: Web o plastických operacích, spousta odborných termínů a cizích slov (z nichž nejjednodušší je liposukce), ve kterých lidé často dělají překlepy, i když jich je dohromady třeba jenom 40.

12.2.2007 14:42:06

Michal Illich:

Ale fuj, tohle by bylo nebetycne pomale (samotny levenshtein je pomaly a provadet ho na kazdem slovu ze slovniku je nesmysl), a navic by to stejne plne nefungovalo - lide spise delaji preklepy ve slovech mene znamych a obtiznych a ty zase nebudou ve slovniku nejhledanejsich.

Proc radsi nepouzijete skutecny vyhledavac? Delat jej v PHP/SQL je hodne nestastne rozhodnuti.

7.2.2007 11:04:10

Jakub Vrána :

Děkuji za názor odborníka. Toto řešení je samozřejmě dimenzované na interní vyhledávání na středně velkém webu a ne na opravy překlepů při prohledávání Internetu.

Mohl bys nám poradit, jaký opensource vyhledávač nabízí možné překlepy slov?

7.2.2007 11:15:31

Baha:

Nenech se vytočit Jakube,
já se levenshteina vždycky bál použít pro jeho pro mne složitost a tohle je první příklad, který chápu i jako názorný pro ostatní použití. Dík

7.2.2007 11:49:48

Jakub Vrána :

Tohle mě opravdu nijak nevytočilo. Michal Illich je v této oblasti expert na slovo vzatý (autor Jyxa) a pokud nám k tomu řekne cokoliv relevantního, budu jen rád. Navíc s ním i samozřejmě souhlasím v tom, že pro obrovské weby (nebo dokonce celý Internet) je toto řešení nepoužitelné.

7.2.2007 12:09:47

Michal Illich:

První věc, kterou můžete pro zlepšení udělat, je zcela otočit způsob uvažování:

Ve způsobu popsaném v článku se musí udělat N levenshteinů, kde N je počet slov v slovníku vybraných "správných" slov. A tady je buď N přílis malé, takže to některé překlepy vůbec nenajde, nebo bude N příliš velké a program nedoběhne v rozumném čase. Prostě ať zvolíte jakékoliv N, tak to bude blbě.

Když způsob uvažování otočíte: tak, si nejdřív vygenerujete překlepy zadaného slova a pak je porovnáte se zaindexovanými slovy. Teď tedy bude N jiné - nebude závislé na vašem rozhodnutí, jak velký slovník udělat, ale na tom, kolik písmen slovo má. A pak také neděláte už N levenshteinů, ale N prostých porovnání. A bude to fungovat nezávisle na velikosti webu.

I tak to bude docela dost - kdybyste to chtěli ještě vylepšit, tak si předpřipravíte indexy slov tak, že budou obsahovat i varianty jako "?rána", "v?ána", "vr?na", "vrá?a", "vrán?", čímž se řadově sníží to N. Tady záleží na tom, zda máte víc dokumentů nebo dotazů - při určitých poměrech se tahle optimalizace vyplatí, při jiných ne.

---------------

Jiný způsob jak toto dělat, je reprezentovat si původní slova v trii a pak procházet ten strom nejen tak, že následujete jen správné odbočky, ale budete následovat i nejvýše třeba 2 špatné. Tohle je velmi efektivní, protože nehledáte věci, které neexistují.

----------

Každopádně rady z posledních dvou odstavců v PHP/SQL nepůjde efektivně realizovat, proto si i nadále myslím, že tyhle jazyky se pro vyhledávač nehodí.

10.2.2007 16:00:21

D1ce:

Teorie pěkná, ale nebyl by prosím alespoň odkaz na zdrojové kódy "něčeho", co takhle anebo podobně funguje?

13.2.2007 15:37:14

mark:

Další lepič kódu :-(

13.2.2007 23:50:15

dgx:

similar_text() je drasticky pomalejší než levenshtein
(složitost max(N,M)^3 vs. N*M), navíc je v PHP špatně implementován (hrubá chyba v algoritmu). Tedy, jednoznačně používejte pouze levenshtein().

soundex() je něco trošku jiného, a na toleranci překlepů se absolutně nehodí - hledá totiž toleranci podobně znějících slov v angličtině.

Každopádně, jak zmínil Michal Illich, tento druh hledání se hodí pouze pro speciální případy, ale nikdy ne pro fulltext. A to, ať už jde o mini web, střední web nebo megagigaweb. Tady vždy bude lepší Jyxo nebo Google s parametrem site:....

7.2.2007 12:52:15

gaspoda:

BTW: Levenstein se da napsat se slozitosti min(m,n) * E
kde E je pocet chyb. To je vyrazne mene nez m * n.

7.2.2007 15:08:36

mach:

To je fakt zajimave.

Nicmene byste se tu nemeli ohanet asymptotickou casovou slozitosti, kdyz je prostor vsech uloh omezeny maximalni rozumou delkou slova (rekneme 15 znaku). Lepsi by bylo rict, co je opravdu pro slova pod 15 znaku rychlejsi, cili porovnat algoritmy vcetne multiplikativni konstanty. Nevim jak v tomhle pripade, ale casto plati, ze cim lepsi je asymptoticka slozitost, tim vetsi multiplikativni konstantu to ma...

8.2.2007 18:50:59

MiSHAK:

Asi by bylo jednodužší mít v db rovnou všechny možné překlepy naindexovane na správná slova.

7.2.2007 15:18:38

Jakub Vrána :

Problém je v tom, že fantazie uživatelů při vytváření překlepů je nezměrná...

7.2.2007 15:21:14

Magelan:

Před rokem jsem si, už ani nevím proč, zřejmě jenom ze zvědavosti co se tam vlastně vyhledává a jestli to bude fungovat, do jednoho vyhledávacího algorytmu dodělal logování skutečně zadaných slov, včetně přičítání jejich počtu v případě opakovaného vyhledávání téhož výrazu. A tak mám pocit, že to konečně bude k něčemu i užitečnému - poskytne mi to tu databázi nejhledanějších slov... díky.

8.2.2007 21:58:24

RiZe:

Ale možná není úplně od věci logovat zadaná slova. Chce to napsat skript, který bude procházet texty (v DB) a u jednotlivých slov bude vytvářet index těchto překlepů a zároveň bude vytvářet překlepy slov z logu interního vyhledávače, aby byly přichystané na příště :). Vše samozřejmě na CRONu

10.2.2007 23:48:23

Michal:

Před asi dvěma týdny jsem byl na přednášce kterou měl Chris DiBona z Google a ten nám ukazoval jak Google využívá toho že má k dispozici obrovské množství (kon)textu. Kupříkladu když zadáte hledání slova "Kofee" tak google nebude vědět co přesně máte na mysli. Ale když zadáte "Kofee Anan" tak Google zjistí že takhle podobně znějící slova se spolu vyskytují celkem často ale častěji ve tvaru "Kofi Annan", takže vám tuhle variantu nabídne. Naproti tomu když hledáte "Kofee Schop" tak o Annanovi nepadne ani slovo a Google vám nabídne "Coffee shop". Není Kofee jako Kofee. Takže, Jakube, navrhuju abys rozšířil svoje vyhledávátko o kontextové hledání a podle toho opravoval překlepy ;-)

13.2.2007 00:34:05

shmoula:

Tak mě napadlo, protože slova delší nebo kratší o více jak 2 písmena budou mít Levenshtein vždy větší než 2, nemusí se pro ně Levenshtein vůbec počítat. Kdyby se tato slova odřízla už pomocí dotazu, nevedlo by to ke zrychlení?

<?php
$search_len = strlen($_GET['search']);
$result = mysql_query("SELECT slovo FROM nejhledanejsi WHERE ABS(LENGTH(slovo) - $search_len) <= 2 AND slovo != '$_GET[search]'");
?>

Nebo je to blbost?

16.2.2007 00:59:06

dgx:

To není blbost, to je naopak velmi chytré!

Možná by na to byla ještě lepší syntax:
SELECT slovo FROM nejhledanejsi WHERE LENGTH(slovo) BETWEEN $search_len-2, $search_len+2 AND slovo != '$_GET[search]'

16.2.2007 01:34:35