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.

ikona Jakub Vrána OpenID:

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.

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.

ikona Jakub Vrána OpenID:

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.

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.

ikona Jakub Vrána OpenID:

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?

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

ikona Jakub Vrána OpenID:

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

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

ikona D1ce:

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

mark:

Další lepič kódu :-(

ikona 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:....

gaspoda:

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

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

ikona MiSHAK:

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

ikona Jakub Vrána OpenID:

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

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.

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

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 ;-)

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?

ikona 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]'

ikona Jakub Vrána OpenID:

BETWEEN má syntaxi BETWEEN min AND max. LENGTH() je délka v bytech, my potřebujeme CHAR_LENGTH().

hh:

No a co takhle na to jít úplně od lesa, a rovnou uživatelům nabízet správné tvary podle již zadané části slova / sousloví?

Petr :

Možná by taky nemuselo být odvěci naučit přímo databázi levenshteina. Inspiraci hledejte http://codejanitor.com/wp/2007/02/10/levenshtein-…-stored-function/

j.r.fish:

sice poněkud staré téma, ale stejně...

tady je levenshtein jako funkce do mysql

http://codejanitor.com/wp/2007/02/10/levenshtein-…-stored-function/

Vložit komentář

Používejte diakritiku. Vstup se chápe jako čistý text, ale URL budou převedeny na odkazy a PHP kód uzavřený do <?php ?> bude zvýrazněn. Pokud máte dotaz, který nesouvisí s článkem, zkuste raději diskusi o PHP, zde se odpovědi pravděpodobně nedočkáte.

Jméno: URL:

avatar © 2005-2018 Jakub Vrána. Publikované texty můžete přetiskovat pouze se svolením autora. Ukázky kódu smíte používat s uvedením autora a URL tohoto webu bez dalších omezení Creative Commons. Můžeme si tykat. Skripty předpokládají nastavení: magic_quotes_gpc=Off, magic_quotes_runtime=Off, error_reporting=E_ALL & ~E_NOTICE a očekávají předchozí zavolání mysql_set_charset. Skripty by měly být funkční v PHP >= 4.3 a PHP >= 5.0.