spolecne

T9 je zkratka pro text na 9 klávesách a jde o technologii určenou pro vkládání textu na mobilních telefonech. Každá klávesa může odpovídat několika různým písmenům, pro různé jazyky různým, následující příklad je pro češtinu:

• 1 = .,-?!'@:;/()1
• 2 = AÁBCČ2
• 3 = DĎEÉĚF3
• 4 = GHIÍ4
• 5 = JKL5
• 6 = MNŇOÓ6
• 7 = PQRŘSŠ7
• 8 = TŤUÚŮV8
• 9 = WXYÝZŽ9

Obsazení klávesy 1 se může na různých telefonech lišit, pro jednoduchost předpokládejme, že všechny nealfanumerické znaky patří sem.

Vaším úkolem je napsat program, který převede posloupnost číslic (a mezer) na text. V jistém smyslu jde o variaci na úlohu Háčkování, na rozdíl od ní je zde ale mnohem těžší se trefit do správné volby. Proto budete vypisovat každé slovo na samostatný řádek, přičemž v případě, že pro nějaké slovo existuje více hypotéz, vypíšete na daný řádek všechny, oddělené mezerami a seřazené sestupně podle pravděpodobnosti.

V prvním přiblížení budete nejspíš pravděpodobnost slova odhadovat jeho relativní četností, porovnanou s četnostmi ostatních kandidátů pro danou posloupnost číslic. Tento přístup ale pochopitelně nebude stačit. Znamenal by, že se vždy vybere (resp. umístí na první pozici v seznamu hypotéz) nejčastější slovo, takže je předem vyloučené, že by šlo srozumitelný text vygenerovat i bez interakce s uživatelem. Zjistěte proto, nakolik lze výsledky vylepšit s pomocí kontextu. Nesledujte pouze relativní četnosti jednotlivých slov, sledujte také n-tice sousedních slov. Například “626” může znamenat mám, nám, naň, man, mao, nán, ale “5 626” už je velmi pravděpodobně k nám, zatímco “626 2886” bude spíš znamenat mám auto (i když věta by mohla být delší a třeba “8572354 626 2886” bude ukradli nám auto, nikoli ukradli mám auto. Můžete se pokusit sledovat i kontext částí slova. Např. pravděpodobnost, že v trénovacích datech potkáte právě frázi “ukradli nám”, není příliš velká, ale poslední dvě písmena (“-li”) statistickému modelu celkem spolehlivě napoví, že jde o sloveso v minulém čase, což by v tomto případě mělo jako kontext stačit.

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ý. Procedura pro převedení trénovacích dat do posloupnosti číslic musí obsahovat abecedu daného jazyka a měla by tedy být dobře oddělená od zbytku kódu, aby ji bylo možné snadno vyměnit. Vše ostatní, co potřebuje o konkrétním jazyku vědět, by měl program být schopen se naučit z dat. (Z toho plyne, že vy daný jazyk ovládat nemusíte.)

Úloha má tyto části:

1. Trénovací program. Projde trénovací data (tokenizovaný text v UTF-8) a naučí se slovník, tj. pro každý řetězec číslic všechna možná slova (nebo čísla), ze kterých mohl vzniknout.
2. Vlastní “T9”. Čte ze standardního vstupu posloupnost číslic, mezer a zalomení řádku, na standardní výstup vypisuje odpovídající slova (v UTF-8), co slovo, to řádek, případné alternativní hypotézy pro dané slovo jsou všechny na jednom řádku, oddělené mezerami a seřazené od nejpravděpodobnější k nejméně pravděpodobné.
3. Za pomoci trénovacího programu nebo jeho upravené verze:
   1. Najděte v daných datech slova, pro která je predikce nejvíce nejednoznačná (tj. existuje největší množina odpovídajících hypotéz).
   2. Zjistěte, jaké procento číselných kódů má jedinou hypotézu (když nepočítáme, že může jít také o číslo).
   3. Zjistěte, jaká je průměrná míra nejednoznačnosti (tj. průměrný počet možných odpovědí) na jeden slovní výskyt (pozici v testovacích datech).

Program t9train.pl čte ze standardního vstupu tokenizovaný text v UTF-8. Nepotřebuje argumenty, ale pokud je dostane, čte místo standardního vstupu soubory, k nimž jsou cesty uvedené v argumentech. Program každé vstupní slovo převede na posloupnost číslic a pro všechny posloupnosti číslic si zapamatuje všechna jim odpovídající slova, která viděl v trénovacích datech. Pamatuje si také četnosti výskytů jednotlivých variant, aby T9 mohlo posoudit, která varianta je nejpravděpodobnější. Naučený slovník vypíše na standardní výstup. Formát výstupu navrhněte sami.

Program t9.pl čte ze standardního vstupu posloupnost číslic, mezer a zalomení řádku. Program se volá bez argumentů (pokud s argumenty, pak jsou to cesty k souborům, které se mají číst místo standardního vstupu), ale s povinnou volbou (option) -s soubor, která udává cestu k souboru se statistikou (slovníkem) vyrobenou programem t9train.pl.

Program píše na standardní výstup. Každý řádek výstupu odpovídá jednomu slovu textu. Pokud řádek obsahuje více než jedno slovo, jsou to různé hypotézy interpretace téhož číselného kódu, oddělené mezerami a seřazené sestupně podle pravděpodobnosti. Výstup je v UTF-8.

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

V zimním semestru 2009-2010 je v nabídce čeština. Pro přístup k trénovacím datům je potřeba souhlasit s licenční smlouvou a odeslat registraci na http://ufal.mff.cuni.cz/corp-lic/pdt20-reg.html; do kolonky Optional information vyplňte “NPFL007”. O registraci bych se měl dozvědět a poslat vám odkaz na data.

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.