Přejít k navigační liště

Zdroják » Různé » Jak na přelkepy?

Jak na přelkepy?

Články Různé

S překlepy se potkáváme denně a jejich automatická oprava je už přirozenou součástí nových nástrojů („Did you mean?“ v Google, případně návrhy na opravu ve Wordu při psaní dokumentu). V článku si ukážeme, jak strojově rozpoznat překlepy a dva základní algoritmy použitelné pro jejich detekci.

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

První řetězec Druhý řetězec Levenstheinova vzdálenost Jaro-Winkler
eklep íklep 1 0,9238
Evgeni Viktorovich Plushenko Evgeni Viktorovich Plushchenko 2 0,9867
Hradec Králo Hradec Kráol 2 0,9857
Svobodová Trobodová 2 0,8519
Praha Brno 4 0,4833

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

Slovo s překlepem Metoda 1. návrh 2. návrh 3. návrh 4. návrh
vyzkumem Word výzkumem
algoritmus výzkumem Výzkumem výzkumném výzkumum
Camridge Word Cambridge Cambridgi Cambridgí
algoritmus Cambridge Cambridgi cartridge
majevo Word najevo májovou májová májové
algoritmus najevo malého nalevo manévr
neázleží Word nezáleží nezaleží
algoritmus nezáleží náleží Nezáleží neleží

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

Komentáře

Subscribe
Upozornit na
guest
11 Komentářů
Nejstarší
Nejnovější Most Voted
Inline Feedbacks
View all comments
Marek

Ďakujem za zaujímavý článok. Práve riešim niečo podobné v php – porovnanie dvoch reťazcov. Mám text v niekoľkých verziách a potrebujem zistiť čo pribudlo, čo ubudlo, čo sa zmenilo medzi dvoma verziami. Nepotrebujem ani tak mieru zhody, len vyznačiť zmeny. Viete mi poradiť nejaký dobrý tip, kde by som sa dozvedel k tejto téme viac?

aranel

na text je nejlepsi:
http://en.wikipedia.org/wiki/Diff

snad to pomuze.

gawan

ale diff vypisuje len rozdielne riadky nie? Sa mi zdá, že na klasický text to nie je vhodné. Lebo odstavce môžu byť dlhé aj niekoľko riadkov a ENTER je až na konci. Takže potom mi to označí celý odstavec, čo môže byť aj cez 10 riadkov, ale ak je rozdiel len jedno slovíčko, tak to je veľmi neprehľadné. Alebo sa dá diff nastaviť aj tak, že bude napríklad porovnávať nie konce riadkov, ale medzery?

pd

Diff je váš kamarád. Určitě existuje i implementace pro PHP.

AraxoN

Väčšina wiki enginov dokáže zobrazovať históriu zmien. Časť z nich je zároveň v PHP a open-source. Takže by som si vybral jeden zo zoznamu:
http://en.wikipedia.org/wiki/Comparison_of_wiki_software
a začal ho pitvať.

jampadampa

Jednoduché použití a výsledek značně uspokojující. http://www.raymondhill.net/blog/?p=441

digri

Zmíněnou slabinu Levenshteinova algoritmu řeší „rozšířený Levenshtein“, kde se za jednu opravu počítá transpozice dvou po sobě jdoucích znaků.

Lukas S

Tak jak to autor popisuje se to da pouzit jen, pokud jsou slova omezena na nejakou malou mnozinu z DB.

V praxi pro volny text se IMHO pouziva to, ze kdyz slovo neni ve slovniku, hleda se shoda se slovnikem pro jednoznakove zmeny daneho slova (pripadne viceznakove/pre­hozeni dvou po sobe jdoucich pismen atd.). Je to casove nejefektivnejsi.

Ale cela veda je za tim, jak z moznych oprav vybrat tu nejpravdepodobnejsi (idealne pouzit bigramy, ale to, kvuli jejich velikosti, lze jen na serverech, nikoliv napr. v mobilu).

Jan Pobořil

Z opravy překlepů v iOS mám pocit, že bere v úvahu i vzdálenost mezi písmeny na klávesnici. Nemáte někdo tento algoritmus trochu více prozkoumán?

Jerry

Pokud se chcete podívat na jednoduchou (méně než 30 řádků kódu) kompletní implementaci spellcheckeru v Pythonu, můžete zkusit http://norvig.com/spell-correct.html .

flv

Co se tyce googlu tak mam dojem ze oni nepouzivaji zadny zvlastni algoritmus (v prvnim priblizeni).

Dalaji to statisticky. Maji obrovskou zakladnu uzivatelu. Pokdu uzivatel udela preklep, nevybere si z vysledku (nikam dal neklikne) ale misto toho znovu zada slovo (tentokrat uz spravne).

Takze co se deje je ze k danym preklepum prirazuji to na co po dalsim vyhledavani uzivatel kliknul.

Aby to skutecne fungovalo musi to byt bezpochyby hodne promakane (tj. spoustu chytrych algoritmu), nicmene v zaklade delaji jenom tu statistiku.

Enum a statická analýza kódu

Mám jednu univerzální radu pro začínající programátorty. V učení sice neexistují rychlé zkratky, ovšem tuhle radu můžete snadno začít používat a zrychlit tak tempo učení. Tou tajemnou ingrediencí je statická analýza kódu. Ukážeme si to na příkladu enum.