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.

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://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.