(úloha z počítačového zpracování přirozeného jazyka)

Upozornění: Specifikace je detailnější (a tudíž více svazující) než bývá u zápočtových úloh zvykem. Ideálně by díky tomu měla tři řešení téže úlohy od tří různých lidí být zaměnitelná; šetří vám to také práci s dokumentací, která už je součástí zadání. Samozřejmě nelze vyloučit, že najdete dobrý důvod, aby něco bylo jinak než ve specifikaci; takové případy se mnou prosím konzultujte. Bez posvěcení se raději od specifikace zbytečně neodchylujte. Kdo bude místo na STDOUT čmárat do souboru, jehož cesta je zadrátována ve zdrojáku jako “C:\Documents and Settings\PanVopička\Dokumenty\tisícdalšíchadresářů\mujchytrysoubor.dat” apod., nejenže nedostane zápočet, ale bude podroben veřejnému zostuzení.

Kontrola pravopisu (spell checking) obvykle zahrnuje dvě podúlohy:

• zjistit, zda je slovo ve slovníku
• navrhnout seznam podobných slov, která ve slovníku jsou

Pokud nemáte ručně vytvořený slovník, můžete si vypomoci tím, že se ho naučíte z dostatečně velkého korpusu. Musíte ale pamatovat na to, že korpusy někdy obsahují i překlepy, tedy slova, která ve slovníku mít nechcete. Slova, která navrhujete, by pak měla být seřazená podle pravděpodobnosti, že jsou opravou dané chyby. Díky tomu jednak uživatel dostane nabídku, která mu skutečně pomůže, jednak by mělo být možné kontrolu aplikovat neinteraktivně, tj. program sám nahradí chybná slova nejpravděpodobnějšími opravami ze slovníku.

Pravděpodobnost, že dané slovo w má být opraveno na slovo c (correction) lze vyjádřit jako P(c|w). Hledáme slovo c s nejvyšší takovou pravděpodobností, tj. hledáme výsledek výrazu argmax(c)(P(c|w)). Pod touto pravděpodobností se skrývají dvě (resp. tři) složky, které můžeme zviditelnit pomocí Bayesova vzorce:

P(c|w) = P(w|c) * P(c) / P(w)

• P(w|c) je pravděpodobnost, že správné slovo c může být zkomoleno na slovo w
• P(c) je pravděpodobnost výskytu slova c jako takového
• P(w) je pravděpodobnost výskytu slova w. Z hlediska argmax(c) je to konstanta: ať bude výsledkem kterékoli c, pravděpodobnost slova w bude vždy stejná. Proto ji můžeme z dalších úvah vypustit.

Pravděpodobnost P(c) je dána jazykovým modelem. Snadno ji odhadneme na základě korpusu, ve kterém spočítáme výskyty jednotlivých slov. Chytrý jazykový model bude navíc brát v úvahu i kontext okolních slov: některá slova nemusejí být sama o sobě nejpravděpodobnější, ale v určitém kontextu přesto převáží.

Pravděpodobnost P(w|c) je pravděpodobnost chyby. Tu je těžší odhadnout. Obvykle se pracuje s tzv. editační vzdáleností, což je počet editačních operací, kterými se dostaneme od c k w. Editační operace jsou několika druhů:

• Vynechání písmene (deletion)
• Přidání písmene (insertion)
• Záměna jednoho písmene za jiné (replacement)
• Prohození dvou sousedních písmen ve slově

Záměnu a prohození lze pochopitelně simulovat posloupností vynechání a přidání, ale z hlediska psychiky autora chybného textu jsou to určitě samostatné druhy chyb, které stojí za to brát v úvahu samostatně.

I v rámci jednoho druhu editační operace jsou různé chyby různě pravděpodobné. Zejména u přidání písmene nebo u nahrazení jednoho písmene jiným hraje roli, zda jde o podobná písmena a autor si nebyl jistý pravopisem daného jazyka (např. náhrada jedné samohlásky jinou, třeba a místo e, je pravděpodobnější než dejme tomu výměna a za t, obdobně jsou si podobná třeba c a č), a pak také zda dotyčná písmena leží na klávesnici vedle sebe (a autor se prostě uklepl). Také vynechání písmene je pravděpodobnější tam, kde správný pravopis požaduje dvě stejná písmena za sebou.

Na odhadnutí pravděpodobností jednotlivých druhů chyb bychom potřebovali korpus opravených překlepů. Pokud ho nemáme k dispozici, můžeme se pokusit uvedené příklady formalizovat pomocí ad-hoc bodových penalizací. Podstatnou roli bude každopádně hrát editační vzdálenost - zkomoleniny, které vzniknou jednou editační operací jsou mnohem běžnější než ty, kde potřebujeme operace dvě.

Zvláštním případem je, když autor vynechá (nebo přidá) mezeru. V tom případě vám vznikne dlouhé slovo, které typicky bude mít od všech existujících slov velkou editační vzdálenost, pokud nebudete vynechání mezery brát v úvahu. Tyto chyby lze sice reálně očekávat, ale vy je můžete zanedbat, celou úlohu komplikují.

Vaším úkolem je napsat v Perlu tyto nástroje:

1. Trénovací skript train.pl, který přečte ze standardního vstupu (popř. ze souboru, jehož jméno dostane jako argument, pokud nějaké argumenty dostane) korpus (text v UTF-8, nemusí být tokenizovaný) a na standardní výstup vypíše natrénovaný jazykový model, tedy v nejjednodušším případě frekvenční slovník. Skript by měl být schopen částečně odfiltrovat slova podezřelá z toho, že jsou to překlepy (vyskytují se zřídka a současně se velmi často vyskytuje podobné slovo, které z nich vznikne jednoduchou editační operací). Pozor, např. v českých koncovkách nemusí jít o překlep, ale prostě o to, že stejné slovo se v jednom pádě vyskytuje často (chlapce) a v jiném zřídka (chlapče).
2. Skript guess.pl -s model načte statistiku ze souboru, jehož jméno dostane jako argument volby -s, ze standardního vstupu pak načte seznam slov (každé na samostatném řádku) a na standardní výstup vypíše tentýž seznam, ale za každým slovem bude tabulátor a pak nejvýše deset návrhů na opravu slova, seřazených podle pravděpodobnosti. Návrhy jsou oddělené čárkami, pravděpodobnost je za každým návrhem uvedená v závorce.
3. Skript correct.pl -s model se volá podobně jako guess, ale na vstupu má souvislý text (nemusí být tokenizovaný). V něm najde chyby, nahradí je nejpravděpodobnější opravou a opravený text pošle na standardní výstup.

Pro testování skriptů dostanete k dispozici data v konkrétním jazyce, skripty však pište tak, aby na jazyce nezávisely.

Tento úkol (včetně zadání konkrétního jazyka) si můžete zarezervovat vyplněním formuláře na http://ufal.mff.cuni.cz/cgi-bin/zeman/zapoctaky/rezervace_ukolu.pl (pokud ještě není rozebrán).

Pokud se individuálně nedohodneme jinak, termín odevzdání je konec listopadu. Při některé prosincové přednášce program předvedete ostatním.