Od roku 2003 e-mailový svět obletěl následující text (uvádím v češtině):

V suoivsoltsi s vzýukemm na Cmabridge Uinervtisy vlšyo njaveo, že nzeáelží na pořdaí psíemn ve solvě. Jedniná dleůitžá věc je, aby blyy pnvrí a psoelndí pímesna na srpváénm mstíě.
Zybetk mžůe být totánlí směs a ty to přoád bez porlbméů peřčetš. Je to potro, že ldiksý mezok netče kdažé pensímo, ale svolo jkao cleek. Zjíamvaé, že?

(„Překlad“: V souvislosti s výzkumem na Cambridge University vyšlo najevo, že nezáleží na pořadí písmen ve slově. Jediná důležitá věc je, aby byly první a poslední písmena na správném místě.
Zbytek může být totální směs a ty to pořád bez problému přečteš. Je to proto, že lidský mozek nečte každé písmeno, ale slovo jako celek. Zajímavé, že?)

Více o textu, jeho záhadném původu, ale i o schopnosti lidského mozku rozeznávat překlepy přímo od pracovníka Cambridge University v [1].

Co ale zvládne lidský mozek, může být problémem pro software při vyhledávání v naší databázi, kontrole shodnosti slov a podobně.

V případě, že víme, že se jedná o prohozená písmena je lehké tento problém vyřešit jednoduchou funkcí. Ale co v případě, že se jedná o jiný typ překlepu, například použití špatného písmena nebo přidání nebo odebrání jednoho znaku? Nebo co v případě, že se uživatel nespletl, ale překlep není v naší databázi, případně jenom použil množné číslo nebo jiný pád než nominativ?
Zaměřme se jenom na překlepy v krátkých textových řetězcích.

Existuje několik funkcí, které nám vrátí míru podobnosti mezi 2 textovými řetězci. V tabulce vidíme 5 různých dvojic a výsledky dvou funkcí pro ně. Rozdíly ve dvojicích jsou tučně.

Levenstheinova vzdálenost

Levenstheinova vzdálenost (v angličtině Levensthein distance nebo často edit distance) vrací počet překlepů mezi dvěma textovými řetězci. Hodnota, kterou vrací, je srozumitelná a jasná i bez znalosti algoritmu.

Na co si dát pozor:

Tato funkce nebere do úvahy délku řetězců, takže vrátí stejným výsledek pro příklady z tabulky Svobodová a Evgeni Viktorovich Plushenko. Poměrně častou chybu, prohození 2 sousedních písmen, považuje za 2 překlepy, i když to lidé obvykle považují jenom za 1 překlep – příklad Hradec Králové. V některých implementacích (například v Oracle – package utl_match) vrací pro prázdný řetězec hodnotu –1.

Víc o algoritmu najdete například na wikipedii [2].

Jaro-Winkler

Další funkcí je Jaro-Winkler, který vrací hodnotu mezi 0 a 1 (0 znamená absolutní neshodu, 1 znamená absolutní shodu) a bere do úvahy i délku řetězců.

Výsledky Jaro-Winkler nejsou tak zřejmé jako Levenstheinovy vzdálenosti a je nutné na datech otestovat pro stanovení vhodné hranice, co je možné považovat za podobnost. Je nutné si uvědomit, že dlouhý společný podřetězec znamená automaticky vysokou hodnotu – viz příklad Svobodová. Ženská přechýlená příjmení mají v češtině společný řetězec „ová“, a proto porovnání „stejných“ mužských příjmení vrací nižší hodnotu pro Jaro-Winkler než porovnání „stejných“ ženských přechýlených příjmení.

Víc o algoritmu najdete například na Wikipedii [3].

Tyto funkce slouží na porovnání dvou výrazů, tj. jeden výraz, kde je překlep, porovnáváme s výrazy ze slovníku. Když se zákazník internetového knihkupectví překlepne při hledání knihy, jako slovník použijeme seznam knih a jednotlivé položky porovnáme pomoci těchto funkcí s hledaným výrazem. Výhodou Levenstheinovy vzdálenosti a Jaro-Winklera je jejich dobrá srozumitelnost, velké množství článku a jejich implementace v různých programovacích jazycích. Nevýhodou je jejich obrovská složitost pro velký objem dat.

Použití v textu a porovnání s MS Office 2010

Pro porovnání překlepů jsem si vybral první větu e-mailu s několika překlepy: „V souvislosti s vyzkumem na Camridge University vyšlo majevo, že neázleží na pořadí písmen ve slově.“ Podtržená slova vyhodnotil MS Word jako chybné a nabídl několik návrhu oprav. Podtržená slova jsem porovnal se srovnávacím frekvenčním seznamem [4] po standardizaci (lowercase + odstranění diakritiky) pomocí Levenstheinovy vzdálenosti (uvažoval jsem hodnoty 0,1,2). Výsledky jsem seřadil vzestupně dle Levenstheinovy vzdálenosti a sestupně dle absolutní frekvence. V tabulce uvádím první 4 výsledky z tohoto postupu a první 4 výsledky, které nabídl MS Word. Správný návrh na opravu je tučně.

V uvedených příkladech je vždy první návrh, jak u Wordu, tak u algoritmu, správný. Nejde ale o pravidlo, spíše byly příklady příliš jednoduché a jednoznačné.

Závěr

Tyto dvě funkce a několik příkladů jsou jenom úvodem do problému překlepů a vyhledávání s neúplnou shodou.

Pro hlubší analýzu fuzzy match algoritmů doporučuji článek Davida Pejčocha [5].

Pro širší pojetí problému můžeme dále uvažovat například o možnosti prohození slov v textovém řetězci, použití algoritmu pro vyhledání nejdelšího společného podřetězce nebo použití historie hledání našich klientů.

Před implementaci řešení bychom se měli na data podívat a ujasnit si mnohé další věci: například jak se postavíme k diakritice, nealfanumerickým znakům, case sensitivite, příponám a předponám atd.

Zdroje:

[1] Aoccdrnig to a rscheearch at Cmabrigde Uinervtisy http://www.mrc-cbu.cam.ac.uk/pe­ople/matt.davis/cma­bridge/

[2] Levenshtein distance http://en.wiki­pedia.org/wiki/Le­venshtein_dis­tance

[3] Jaro–Winkler distance http://en.wiki­pedia.org/wiki/Ja­ro%E2%80%93Win­kler_distance

[4] Český národní korpus: Srovnávací frekvenční seznamy. Ústav Českého národního korpusu FF UK, Praha 2010 http://uc­nk.ff.cuni.cz/srov­nani10.php

[5] Využití Fuzzy Match algoritmu pro čištění dat http://www.pej­coch.com/clan­ky/cl_fuzzy_mat­ch_porovnavani_re­tezcu.pdf