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

Napište programy, které najdou v textu hranice slov a vět. K testování dostanete data v konkrétním jazyku, váš program by však měl být v maximální možné míře jazykově nezávislý. Vše, co potřebuje o konkrétním jazyku vědět, by měl být schopen se naučit z dat. (Z toho plyne, že vy daný jazyk ovládat nemusíte.)

Úloha má tyto části:

1. Tokenizátor. Čte text ze standardního vstupu, hledá a vyznačuje v něm hranice tokenů (slov), výsledek píše na standardní výstup.
2. Oddělovač vět. Čte ze standardního vstupu tokenizovaný text s vyznačenými hranicemi odstavců. Hledá a vyznačuje v něm hranice vět, výsledek píše na standardní výstup.
3. Program, který se z trénovacích dat, ve kterých jsou vyznačené věty, naučí statistiku, potřebnou pro zlepšení rozhodování o hranicích vět.

Programy pište v Perlu a snažte se vyvarovat obratů, které by omezily přenositelnost mezi platformami (např. nevolejte externí programy, které se vyskytují pouze v Unixu, resp. pouze ve Windows).

Token je společný termín, který se někdy používá pro slova a další prvky věty (čísla, interpunkci). Pokud nebude řečeno na konkrétním místě něco jiného, my budeme používat výrazy token a slovo jako zaměnitelné. Tokenizátor je program, který má rozdělit vstupní text na tokeny.

Váš program se má jmenovat token.pl, nevyžaduje žádné argumenty, čte standardní vstup a píše na standardní výstup. Pokud by se argumenty přece vyskytly, interpretují se jako cesty k souborům, které se mají číst místo standardního vstupu.

Vstupní i výstupní text je v UTF-8 v libovolném jazyku. Na vstupu mohou být vyznačené hranice odstavců pomocí zalomení řádku (znak LF nebo dvojice CR LF). Tokenizátor nesmí ztratit informaci o tom, zda mezi dvěma slovy byl konec odstavce (řádku), má však mazat nadbytečné prázdné odstavce, ve kterých není žádné slovo. Na začátku a na konci řádku nemají zůstat žádné mezery, mezi dvěma tokeny má být právě jedna mezera (bez ohledu na to, kolik jich bylo na vstupu). Nejdůležitějším úkolem programu je přidat mezeru mezi tokeny, které na vstupu nebyly oddělené. Pravidla, podle čeho poznat hranici tokenu, následují.

Upozornění: Níže uvedená pravidla pochopitelně nejsou jediným správným způsobem, jak dělat tokenizaci. Jejich účelem je sjednotit výstupy tokenizátorů, které vyrobíme. Součástí vašeho řešení mohou být návrhy, jak tato pravidla zpřesnit nebo změnit a proč.

1. Nepřerušený řetězec písmen a/nebo číslic je jedno slovo nebo jeho část. Pozor, tato část by měla být jazykově nezávislá a v některých jazycích jsou písmena, se kterými se v češtině nesetkáte. Obdobně číslice jsou i jiné, třeba arabské. Tip: Nemusíte kvůli jazykové nezávislosti procházet celý Unicode a vypisovat do zdrojáku, co je písmeno a co ne. To už někdo udělal za vás. Podívejte se do dokumentace Perlu na části perlre (regulární výrazy) a perlunicode. Např. \p{Lu} odpovídá velkému písmenu, ať už je anglické, s diakritikou nebo třeba v cyrilici.
2. Mezerové znaky (řídící znaky včetně TAB, CR a LF, mezera 32, asi i NBSP 160, případné mezery ve vyšších patrech Unicodu) netvoří slovo ani jeho část. Považují se za oddělovače (ale viz výjimky níže). Na výstupu tokenizátoru může být buď jedna prostá mezera, nebo konec řádku.
3. Zvláštní znaky (cokoliv, co není písmeno, číslice ani mezera) zpravidla netvoří jedno slovo s písmeny a číslicemi, ani když od nich nejsou oddělené mezerou. Týká se i pomlček ve složených výrazech typu “česko-německý” nebo apostrofů ve výrazech, jako je anglické “don't” nebo francouzské “d'Artagnan”. (Zvláště u anglického “don't” tento přístup narušuje představu o tom, co je ve skutečnosti slovo, ale neexistuje jazykově nezávislé pravidlo, které by takové případy podchytilo. Je snadnější je nejdříve rozdělit a potom ve vybraných případech na základě jazykově závislého pravidla opět spojit.) Výjimky jsou popsány v samostatných pravidlech.
4. Zvláštní znaky obklopené z obou stran číslicemi jsou spolu s číslicemi na obou stranách součástí jednoho slova. To se týká zejména desetinné čárky nebo tečky, ale i oddělovače řádů (tečka, čárka, apostrof). Oddělovačem řádů může být i mezera. Proto mezera mezi dvěma čistě číselnými řetězci by se měla (spolu s oběma číselnými řetězci) považovat za součást jediného slova. (Takové mezery nejsou oddělovači, a proto by se normálně neměly z textu odstraňovat. Protože ale některé nástroje pro práci s přirozeným jazykem mohou mít problémy s tím, že mezera může být součástí slova, je vhodné něco s tím udělat. Nejjednodušší řešení je nahradit mezery ve slovech podtržítky, i když nepůjde zpětně rozlišit, kde bylo už v původním textu podtržítko.) Slova neodděluje ani pomlčka mezi dvěma číselnými řetězci (vyskytuje se např. v telefonních číslech). Naopak zvláštní znaky přiléhající k číslu pouze z jedné strany (z druhé strany mají něco jiného než číslo; např. závorky, +/-, tečka či čárka za číslem, %, $) se nepovažují za součást číselného slova. Totéž platí o zvláštních znacích oddělených od sousedního čísla mezerou.
5. Výjimkou z předcházejícího pravidla (tedy vlastně výjimkou z výjimky) jsou data. Pokud se pozná, že jde o datum, mělo by být rozděleno tak, aby den, měsíc a rok byly samostatnými slovy a případná interpunkce také. (Důvod: bude-li jinde uvedeno stejné datum, ale s měsícem vyjádřeným slovně (“1. července 2005”), bude každá ze tří složek data samostatným slovem. Je logické požadovat, aby to u dat vyjádřených číselně bylo stejně.) Za datum se považuje posloupnost číslic a vhodných interpunkčních znamének (teček, pomlček, lomítek, apostrofů), ve které lze rozpoznat dvě až tři číselné části den, měsíc a rok, kde rok je volitelný a v rozsahu 00 až 9999 (alespoň dvojciferný, i když by začínal nulou), měsíc je v rozsahu 1-12 (popř. 01-12, ale max. dvojciferný) a den je v rozsahu 1-31 (popř. 01-31, ale max dvojciferný). Pořadí těchto tří složek v rámci data může být různé, ale rok nemůže ležet mezi dnem a měsícem.
6. Sousedící, mezerou neoddělené zvláštní znaky se zpravidla považují za samostatná slova (např. uvozovky vedle závorek, čárka/tečka/vykřičník/otazník vedle uvozovek). Výjimky jsou následující (pokud přijdete na dalšího vhodného kandidáta, dejte mi prosím vědět): … (trojtečka zapsaná jako tři tečky), `` a '' (anglické uvozovky zapsané jako dva apostrofy), – (dlouhá pomlčka zapsaná jako dva spojovníky).
7. Znak dolaru může přiléhat zprava k posloupnosti písmen, v tom případě s nimi tvoří jedno slovo (např. US$, A$, C$, HK$).
8. E-mailové adresy a URL jsou výjimky a tvoří vždy jedno slovo. (Pozor, pokud se vyskytnou na vhodném místě věty, může k nim být zprava přilepená interpunkce, která není jejich součástí. URL může končit lomítkem, ale ne třeba tečkou.)

Pomocný program sentrain.pl je zodpovědný za jazykovou nezávislost vašeho programu na hledání hranic vět. Měl by se naučit z dat to, co byste jinak psali jako soubor pravidel (ať už do externího souboru, nebo dokonce do zdrojáku). Může sbírat prakticky libovolné informace, ale nejzajímavější pro vás asi bude seznam krátkých slov, která se často vyskytují před tečkou a přitom obvykle tato tečka neukončuje větu.

Vstupem programu je tokenizovaný text v UTF-8, ve kterém jsou hranice vět vyznačené tak, že každá věta leží na samostatném řádku. Pokud je program zavolán bez argumentů, vstup se čte ze standardního vstupu. Pokud je zavolán s argumenty, ty se považují za cesty k souborům, které se mají načíst.

Program by měl vždy psát na standardní výstup, formát výstupu si však stanovte sami podle toho, jaké informace chcete sbírat.

Program sent.pl přečte tokenizovaný text v UTF-8 s vyznačenými odstavci a vypíše tentýž text s vyznačenými větami. Jak odstavce na vstupu, tak věty na výstupu jsou vyznačené zalomením řádku: každý odstavec, resp. věta leží na samostatném řádku.

Veškerá pravidla závislá na slovníku konkrétního jazyka (např. seznam zkratek) by měl být program schopen načíst z externího souboru vyrobeného programem sentrain.pl. Pravidla závislá na abecedě jazyka (např. které znaky Unicodu mohou být koncovou interpunkcí) mohou být ve zdrojáku (ovšem takovým způsobem, aby se zdroják zbytečně nestával jazykově závislým, viz též rady k tokenizaci výše). Chcete-li, můžete i tato pravidla zahrnout do učení. Základním pravidlem každopádně je, že věta je podmnožinou odstavce. Jinými slovy, zalomení řádku máte na vhodná místa přidat, ale nemáte je odstraňovat. Na vstupu samozřejmě můžou být odstavce neukončené tečkou (nadpisy).

Program může být zavolán s volbou (option) -s cesta_k_souboru, která říká, že v daném souboru najde statistiku vyrobenou programem sentrain.pl. Tato volba je nepovinná. Pokud není k dispozici statistika, program bude mít nižší úspěšnost, ale může alespoň aplikovat pravidla, která máte přímo ve zdrojáku (např. že mezi tečkou a velkým písmenem velmi pravděpodobně končí věta).

Hlavní vstup (text k rozebrání) se čte ze standardního vstupu, pokud nebyl program zavolán s argumenty; potom tyto argumenty slouží jako cesty k souborům se vstupním textem. Text s vyznačenými hranicemi vět se píše (opět v UTF-8) na standardní výstup.

Kromě zkratek mějte na paměti i další věci (seznam samozřejmě není úplný):

1. Některé jazyky neznají pojem velkého a malého písmena. Ta se rozlišují v latince, cyrilici, řecké a arménské abecedě.
2. Kromě velkého písmena může věta začínat i číslem nebo interpunkcí (levá závorka, uvozovky).
3. Věta nemusí končit jen tečkou, vykřičníkem a otazníkem. Opět můžou na konci ležet i různé druhy pravých závorek a uvozovek. Není ale předem jisté, zda bude tečka před závorkou nebo za ní: .) ). ).“ .”) atd.
4. Tečka mezi dvěma číselnými tokeny může být součást data.

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.

Další informace k úkolu najdete v http://ufal.mff.cuni.cz/~zeman/vyuka/podklady/pzpj03-prvni_ukoly.pdf.

V zimním semestru 2007-2008 jsou v nabídce němčina, švédština a ruština. Odkaz na trénovací data se zde objeví do konce října 2007.