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

Tato úloha má blízký vztah k úloze Chart parser. Parser je program, který s pomocí gramatiky umí rozebírat text a rozpoznávat v něm jednotlivé složky. Text může být slovo, které chceme rozložit na morfémy (morfologická analýza), nebo věta, kterou chceme rozložit na fráze podle větné stavby (syntaktická analýza). Zatímco cílem zmiňované úlohy Chart parser je napsat parser, cílem této úlohy je napsat gramatiku a další obslužné programy, které umožní chart parser opravdu využít. Aby bylo možné řešení obou úloh propojit, je nezbytné na obou stranách dodržet specifikaci. Formát souboru s gramatikou a formát výstupu z parseru (derivační strom ve zhuštěné podobě) je popsán u úlohy Chart parser.

Úloha má tyto části (podrobnosti níže):

1. Soubor s bezkontextovou gramatikou. Požadovaný formát je popsán zde.
2. Slovník a skript v Perlu, který ze slovníku vygeneruje slovníková pravidla a spojí je s gramatikou.
3. Uživatelsky přítulná metoda, jak přidat do slovníku nové slovo a přiřadit ho ke vzoru.
4. Skript v Perlu, který přečte výstup parseru (formát je popsán zde) a udělá z něj srozumitelný výstup morfologické analýzy.

Gramatika má sloužit pro morfologickou analýzu, terminály tedy budou jednotlivá písmena. Gramatiku navrhněte tak, aby z derivačního stromu bylo možné vyčíst nějakým předem stanoveným způsobem 1. lemma analyzovaného slova; 2. zakódované údaje o slovním druhu a o relevantních morfologických kategoriích (např. rod, číslo, pád; takto zakódovaným informacím budeme zkráceně říkat značka neboli tag).

Příklad: gramatika může rozebrat slovo matce jako složené ze dvou částí, mat+ce, přičemž první části přiřadí dejme tomu neterminál “NF_matka” a druhé části přiřadí neterminál “S3”. Derivační strom by pak vypadal takto (zde reprezentovaný pomocí závorek, tedy nikoli ve formátu, v jakém má být výstup úkolu Chart parser):

SLOVO ( NF_matka ( mat ) S3 ( ce ) )

V tomto případě tedy onen “předem stanovený způsob”, jak zjistit lemma a značku, zní: Vezmi neterminály z poslední úrovně těsně nad terminály (tzv. preterminály). Jeden z nich musí obsahovat podtržítko; část za podtržítkem je lemma analyzovaného slova. Část před podtržítkem sřetěz s ostatními neterminály a dostaneš značku. Dvojice lemma-značka v našem příkladu je matka NFS3. Interpretace značky je N = noun = podstatné jméno, F = feminine = ženský rod, S = singular = jednotné číslo, 3 = 3. pád.

Gramatika se z pohledu uživatele skládá ze dvou částí (z pohledu parseru mezi nimi není rozdíl): z obecné a slovníkové. Obecná část obsahuje pravidla, která nejsou přímo vázána na jedno konkrétní slovo, ale spíše na skupinu slov patřících ke stejnému vzoru (i když se výjimečně může stát, že některá nepravidelná slova budou ve své skupině sama). Slovníková část napojuje gramatiku na slovní zásobu daného jazyka. Typicky obsahuje mnohem více pravidel než obecná část (pro každé slovo alespoň jedno pravidlo). Tuto část bývá vhodné reprezentovat v nějaké kompaktnější podobě, např. jako seznam slov s čísly jejich vzorů, ze kterého se příslušná pravidla gramatiky vygenerují nějakým skriptem.

Slovníkovou část reprezentujte ve zhuštěné podobě. Přesný formát navrhněte sami s ohledem na potřeby vaší gramatiky, jednou možností je např. na každém řádku lemma, za ním mezera a název nebo číslo vzoru. Připojte perlový skript gramdict.pl, který dostane jako 1. argument cestu k souboru s obecnou částí gramatiky, jako 2. argument cestu k souboru se slovníkem ve zhuštěném tvaru a na standardní výstup vypíše výslednou gramatiku s dogenerovanými slovníkovými pravidly, tedy ve tvaru, v jakém už se dá předat chart parseru.

Dá se očekávat, že pro takto pojatou morfologickou analýzu budete potřebovat skloňovací vzory, které se učí ve škole, rozštěpit na desítky nebo stovky podvzorů. To je ale nevýhodné pro toho, kdo chce do slovníku přidat nové slovo. Pokud umí česky, dokáže ještě poznat, že slovo mrak patří pod vzor hrad, ale jak má poznat, jestli patří pod vámi definovaný podvzor 227, nebo třeba 380? Proto musíte navrhnout nějakou uživatelsky přítulnou metodu, která přidávání nových slov usnadní. Jako vždy by implementace měla být v Perlu, konkrétní podoba však záleží na koncepci vaší gramatiky.

Uživatelskou přítulností se rozhodně nemá na mysli okenní aplikace s nabídkami, barevnými animacemi a bůhvíčím ještě! Komfort uživatele v tomto případě tkví hlavně v tom, aby údaje, které chcete mít ve slovníku, dokázal program zjistit na základě údajů, které uživatel zná. Např. pokud uživatele požádáte, aby vám spolu s nominativem (1. pád, např. mrak) sdělil i tvar genitivu (2. pád, mraku), dozvíte se z koncového -u, že nejde o mužský rod životný, ale neživotný, a to podle vzoru hrad. Z koncového -k zřejmě poznáte, aniž byste uživateli kladli další otázky, že jde o podskupinu, která má v 6. pádě množného čísla koncovku -cích nebo -kách, nikoli -ech jako u základního hradu. Pokud nelze skupinu určit jednoznačně, můžete uživateli položit doplňující otázky, podobně jako v klíči k určování rostlin („pokud to má listí, jděte na otázku 2; má-li to jehličí, jděte na 47“ … až se nakonec dozvíte přesný rod a druh).

Program pro přidání slova může fungovat interaktivně, v některých případech se však uživateli může hodit i skript pracující dávkově: přečte ze vstupu 1000 slov, ke kterým třeba budou připsány koncovky 2. pádu, vygeneruje slovník ze slov, u kterých mu tyto informace stačí, problematická slova pak vypíše spolu s popisem informace, která mu u nich ještě chybí. (Pak samozřejmě musí být schopen při dalším spuštění tento druh informace načíst a použít.)

Poslední skript interpret_tree.pl by měl z poměrně obecného výstupu parseru přečíst informace, které nás při morfologické analýze zajímají především, tedy lemma a značku, a vypsat je ve srozumitelné podobě. Skript čte výstup parseru na svém standardním vstupu, interpretaci (morfologickou analýzu) píše na standardní výstup.

První částí problému je vygenerování, resp. postupné procházení derivačních stromů, které se ve výstupu parseru skrývají. Parser vypíše jednotlivé složky, které v analyzovaném řetězci našel, jejich rozsah (od pozice 5 do pozice 7) a všechny možné rozklady na menší podsložky. V takovém zápisu se ale může skrývat potenciálně obrovské množství různých odvození analyzovaného slova podle gramatiky. Kvůli lepšímu přehledu by bylo dobré, abyste každý derivační strom vypsali v závorkové notaci jako v příkladu výše na této stránce.

Hlavní část ale spočívá v interpretaci derivačního stromu způsobem, jaký jste si sami definovali pro svoji gramatiku. Tedy např. že přečtete preterminály, část za podtržítkem prohlásíte za lemma a zbytek za značku. Viz též příklad výše. Zatímco první část problému by mohl řešit kdokoliv i bez znalosti vaší gramatiky, tato část přímo souvisí s vaším řešením ostatních částí úlohy.

Na rozdíl od většiny jiných úloh tato vyžaduje vaši znalost zpracovávaného jazyka. Budete proto pracovat s češtinou. Úlohu lze řešit pro několik skupin českých slov.

I pokud si ze základní školy pamatujete všechny základní vzory, budete možná překvapeni, kolik drobných odchylek existuje. Proto vám doporučuji nahlédnout do některé mluvnice (např. Petr Karlík et al.: Příruční mluvnice češtiny. Nakladatelství Lidové noviny, Praha, 1996. ISBN 80-7106-134-4)

Tam, kde mluvnice připouští více tvarů (páni vs. pánové), by měla gramatika popsat všechny. Naopak gramatika nesmí připustit tvary, které jsou chybné (např. *mužemi). Pro homonymní tvary musí gramatika popsat všechna čtení (např. růže může být 1., 2. nebo 5. pád jednotného čísla a 1., 4. nebo 5. pád množného čísla).

Gramatiku sestavte pro podstatná jména v češtině. Obecná část by měla pokud možno pokrývat všechny varianty skloňování. Slovník nemusí obsahovat všechna česká podstatná jména, ale měl by obsahovat alespoň 100 podstatných jmen, mezi nimiž budou zastoupeny všechny 4 rody (mužský životný, mužský neživotný, ženský a střední) a co nejvíce různých vzorů a podvzorů skloňování (včetně změn kmenových hlásek).

Některá doporučená podstatná jména: pán, hoch, občan, muž, otec, obyvatel, host, kněz, rukojmí, předseda, paňáca, husita, sluha, soudce, patriarcha, hrad, ostrov, zámek, domeček, stroj, den, žena, matka, banka, bába, díra, skica, ruka, růže, píseň, ulice, dveře, město, jablko, středisko, pončo, moře, bojiště, kuře, stavení, génius, virus, kuli, idea, Nikaragua…

Pro každé podstatné jméno, které je ve slovníku, musí gramatika popisovat tvary všech 7 pádů obou čísel. Navíc by gramatika měla umožňovat odvození přivlastňovacího přídavného jména od podstatných jmen mužského a ženského rodu (obvykle se tvoří jen od životných, ale toto omezení ignorujte). Přídavná jména stačí odvodit v základním tvaru (mužský rod, jednotné číslo, 1. pád). Ostatní tvary umět nemusíte.

Pro každé přídavné jméno, které je ve slovníku, musí gramatika popisovat tvary všech 4 rodů (mužský životný, mužský neživotný, ženský a střední), 3 čísel (jednotné, dvojné a množné), 7 pádů, 3 stupňů (s výjimkou přídavných jmen, která se nestupňují), kladné i záporné tvary. Navíc by gramatika měla umožňovat odvození příslovce od přídavného jména (např. zelený → zeleně, opět ve všech 3 stupních a v kladném i záporném tvaru (tedy např. také nejnezeleněji).

Obecná část by měla pokud možno pokrývat všechny varianty skloňování. Slovník nemusí obsahovat všechna česká přídavná jména, ale měl by obsahovat alespoň 100 přídavných jmen, mezi nimiž bude zastoupeno co nejvíce různých vzorů a podvzorů skloňování (včetně změn kmenových hlásek).

Některá doporučená přídavná jména: mladý, dobrý, špatný, český, německý, tichý, drahý, levný, jarní, ryzí, krycí, otcův, matčin…

Varování: slovesa mají velké množství značně odlišných tvarů, proto je tato skupina pracnější (ale taky je to větší výzva ) než ty ostatní. Přehled tvarů, na které gramatika může narazit: infinitiv (alternativní tvary na -t, -ti, resp. -ct, -ci), přítomný a budoucí čas (jedu, pojedu, jedeš, pojedeš, jede, pojede, jedem, jedeme, pojedem, pojedeme, jedete, pojedete, jedou, pojedou), rozkazovací způsob (jeď, jeďme, jeďte), příčestí minulé (jel, jela, jelo, jeli, jely, jela), příčestí trpné včetně odvozeného přídavného jména (přibit, přibitý, přibita, přibitá, přibito, přibité, přibiti, přibití, přibity, přibité, přibita, přibitá), přechodník přítomný a minulý včetně odvozeného přídavného jména (nesa, nesouc, nesouce, nesoucí, vytisknuv, vytisknuvši, vytisknuvše, vytisknuvší). Různé skupiny tvarů téhož slovesa se tvoří až od tří různých kmenů: přítomného, minulého a infinitivního. Např. pro sloveso brát je infinitivní kmen brá- (tvoří se z něj infinitiv a příčestí trpné), minulý kmen bra- (tvoří se z něj příčestí minulé) a přítomný kmen ber- (tvoří se z něj přítomný čas, rozkazovací způsob a přechodník přítomný). Podle různého chování jednotlivých kmenů se slovesa dělí na 5 tříd a řadu vzorů (nese, bere, maže, peče, umře, tiskne, mine, začne, kryje, kupuje, prosí, trpí, sází, dělá), plus nepravidelná slovesa (být, jít a další).

Můžete vynechat přechodníky (ale samozřejmě dobrovolnosti se meze nekladou) a odvozování přídavných jmen. O budoucím čase předpokládejte, že se vždy tvoří opisem pomocí slovesa budu (nemusíte tedy řešit tvary jako pojedu, které se týkají jen několika sloves, zejména pohybových). Zbývají běžné slovesné tvary infinitiv, přítomný čas, příčestí minulé a trpné. Pokryjte alespoň výše uvedených 14 vzorů + 2 nepravidelná slovesa. Všímejte si případů, kde bude přidání dalších sloves vyžadovat nové podvzory, např. kvůli změnám kmenových hlásek (drtí - drť, hledí - hleď, kouří - kuř…)

Tento úkol (včetně zadání konkrétní skupiny slov) 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.

V ideálním případě bude vaše gramatika na závěr otestována ve spojení s existujícím chart parserem, který vytvořili vaši předchůdci v minulých letech. Záleží na tom, jak přesně jste vy i oni splnili zadání, a zda tedy vaše řešení budou vzájemně kompatibilní.

V případě zájmu můžete dostat k dispozici pro pokusy chart parser a anotovaná data z českého korpusu, ze kterých lze vytáhnout přehled podstatných jmen a některých jejich tvarů.