Rozpoznávání a třídění jazyků

spolecne

Napište program, který dokáže rozpoznat jazyk dokumentu, věty a slova a roztřídit vstupní text podle jazyků. Součástí zadání bude konkrétní skupina jazyků, které má program umět poznat, váš program by však měl být jazykově nezávislý. Vše, co potřebuje o konkrétních jazycích vědět, by měl být schopen se naučit z dat. (Z toho plyne, že vy dané jazyky ovládat nemusíte, naopak je možná výhodou, když jsou vám zcela neznámé.)

Úloha má tyto části:

1. Program na natrénování statistiky, podle které dokážeme rozpoznat jazyk dokumentu.
2. Program, který na základě statistiky přiřadí jazyk dokumentu i jednotlivým jeho částem. Skupinu dokumentů v jedné složce dokáže roztřídit do složek podle jazyka.
3. Natrénování rozpoznávače pro zadanou skupinu jazyků a kódování. Trénovací data sežeňte sami, například na webu.

Odevzdávat budete oba programy a natrénované statistiky.

Program se jmenuje rjtrain.pl a nepotřebuje žádné argumenty. Pokud je přece dostane, považuje je za cesty k souborům, ze kterých má načíst svůj vstup. Jinak čte ze standardního vstupu (STDIN). Na standardní výstup (STDOUT) vypíše frekvenční charakteristiku textů, které měl na vstupu. Standardně by měl sbírat frekvence trojic, dvojic a samostatných znaků/bajtů. Volitelně můžete evidovat i nejčastější slova.

Volitelně může program dostat volbu -u, která říká, že vstup bude v UTF-8 a že v tomto kódování chceme dostat i frekvenční charakteristiku. Nebyl-li program zavolán s touto volbou, žádné kódování nepředjímejte. Čtěte i vypisujte prostou posloupnost bytů (“:raw”).

Frekvenční charakteristika obsahuje na každém řádku dva údaje oddělené tabulátorem: n-tice znaků a její relativní četnost v dokumentu (tedy číslo mezi 0 a 1). Volitelně můžete připsat i třetí údaj, absolutní četnost, ale až na třetím místě (za dalším tabulátorem). Tento údaj typicky slouží jen pro informaci člověku, který se na to bude koukat, nikoli vlastnímu rozpoznávači. Řádky frekvenčního souboru seřaďte na prvním místě podle délky sledované ntice (nejdříve trojice, pak dvojice, pak samostatné bajty, nakonec případná celá slova (bez ohledu na délku, pokud jste jejich frekvence sbírali). Druhé třídící kritérium je četnost (nejdříve nejčastější ntice, ty vzácné až nakonec). Příklad:

ní]     0.00712694877505568
[po     0.00623608017817372
[pr     0.00556792873051225
ch]     0.00489977728285078
[ne     0.00334075723830735
pro     0.00334075723830735
...
[p      0.0137118578601777
ov      0.0117806102742372
ra      0.00984936268829664
a]      0.00965623792970259
[s      0.00946311317110854
...
[       0.117286055233549
]       0.117286055233549
o       0.0555744971019434
e       0.0497783839072622
a       0.0422775315376747

Program se jmenuje rjaz.pl a volá se takto (příklad):

rjaz.pl -f ~/frq -i . -o ../roztrideno [-xdN|-xpN|-xwN]
rjaz.pl -f ~/frq < vstup > vystup [-xdN|-xpN|-xwN]

První volání znamená: 1. Ve složce ~/frq najdi všechny soubory, jejichž název končí příponou .frq, a načti z nich frekvenční charakteristiky známých jazyků. Za název jazyka se považuje název souboru po odtržení cesty a přípony .frq. Např. soubor cs.iso-8859-2.frq obsahuje charakteristiku jazyka “cs.iso-8859-2”. 2. Postupně načítej soubory ze složky . (aktuální složka), pro každý z nich urči jazyk. Pokud je podobnost dokumentu všem známým jazykům příliš malá, prohlaš jazyk za neznámý (unknown). 3. Kopii načteného a rozpoznaného dokumentu ulož do ../roztrideno do podsložky, která se jmenuje stejně jako jazyk dokumentu. (Pokud taková podsložka ještě neexistuje, vytvoř ji.)

Není-li zadána volba -i (jako ve druhém příkladu), čte se jediný dokument ze standardního vstupu. Na standardní chybový výstup (STDERR) se vypíše vyhodnocení jazyka celého dokumentu, tj. seznam známých jazyků, spolu s číselným vyjádřením podobnosti dokumentu každému jazyku, seřazený sestupně podle podobnosti. Pokud dokument není žádnému známému jazyku podobný dostatečně, před seznam se ještě napíše upozornění, že jde pravděpodobně o neznámý jazyk. Na standardní výstup (STDOUT) se vypíše dokument ze vstupu; to má smysl jen při volbách -xd, -xp nebo -xw.

Kterákoli z těchto voleb způsobí, že:

1. O vstupním dokumentu se předpokládá, že je tokenizovaný, tj. slova i jiné tokeny (interpunkce) jsou už oddělené mezerami a zalomení řádku odděluje odstavce.
2. Na výstupu není dokument pouze opsán, ale je obalen XML značkami podle následujících pravidel:
   • Celý dokument je obalen značkami <doc>…</doc>.
   • Každý odstavec (řádek) je obalen značkami <p>…</p>.
   • Každé slovo (token) je obaleno značkami <w>…</w>. Mezi těmito značkami se nevyskytují mezerové znaky (mezery, zalomení řádku aj.) Naopak vně těchto značek nemají mezerové znaky žádný zvláštní význam, takže může být např. každý token (včetně svých <w>…</w> značek) na samostatném řádku.
   • Odstavce a slova mají ve svých počátečních značkách atribut id, který je v rámci dokumentu jednoznačně identifikuje. Např. <p id=“1”><w id=“1.1”>.
   • Počáteční značka dokumentu, odstavce i slova může obsahovat atributy lang a lw, které udávají jazyk dokumentu / odstavce / slova a váhu (míru podobnosti) jazyka. Volba -xd znamená, že tyto údaje mají být uvedeny u dokumentu. Volba -xp zapne rozpoznávání jazyka odstavců a implikuje taky volbu -xd. Volba -xw znamená, že jazyk má být rozpoznáván na všech třech úrovních (dokument, odstavec i slovo).
   • Nezapomeňte, že na výstupu v XML musíte zakódovat znaky “&”, “<” a “>” jako entity (“&amp;”, “&lt;”, “&gt;”).
   • K volbám -xd, -xp a -xw může být ještě přilepen parametr N (buď číselný, nebo písmeno “a”), s jehož pomocí lze vynutit podrobné informace o rozpoznávání jazyka pro dokument nebo jeho prvek. V tom případě se navíc vypíše struktura <langs> (viz příklad níže), která obsahuje sestupně uspořádaný seznam jazyků s váhami, jaký se jinak také vypisuje na STDERR.
     • Struktura langs, patřící celému dokumentu, se píše hned za počáteční značku dokumentu.
     • Struktura langs, patřící celému odstavci, se píše hned za počáteční značku odstavce.
     • Struktura langs, patřící slovu, se píše hned za koncovou značku slova (tedy ne dovnitř slova, ale za něj).
     • Číselný parametr N říká, kolik nejpravděpodobnějších jazyků má být ve strukturách langs vypsáno. Je-li N=“a” (all), mají se vypsat všechny známé jazyky. Výchozí hodnotou N je 1, v tom případě se vůbec nevypisuje struktura langs a stačí atributy lang a lw uvnitř počáteční značky prvku. Pokud je N vyšší než 1 nebo “a”, vypisují se jak atributy lang a lw uvnitř počáteční značky prvku, tak struktura langs. Pokud je N 0, nevypisuje se struktura langs ani atribut lw v počáteční značce prvku, vypisuje se pouze atribut lang. Pokud je jazyk neznámý a N > 1, potom atribut lang ve značce prvku obsahuje informaci, že jazyk je neznámý, ale struktura langs zobrazuje váhy známých jazyků pro posuzovaný prvek.
   • V příkladu si všimněte, že na začátku dokumentu XML se uvádí značka <?xml…?>, ve které se mimo jiné musí říct, jaké kódování dokument používá. Spolu s jazykem tedy musíte rozpoznat i kódování.

<?xml version="1.0" encoding="utf-8"?>
<doc lang="cs" lw="0.363445894">
  <langs>
    <li lang="cs" lw="0.363445894"/>
    <li lang="sk" lw="0.289303854"/>
    <li lang="en" lw="0.154494783"/>
  </langs>
  <p id="1">
    <w id="1.1">To</w>
    <w id="1.2">je</w>
    <w id="1.3">čeština</w>
  </p>
</doc>

V zimním semestru 2007-2008 jsou součástí zadání následující jazyky. Samozřejmě můžete svůj program naučit i libovolné další jazyky. Nemáte-li pro dané jazyky trénovací data, sežeňte si je na webu. Trénovací data pro různá kódování získejte překódováním trénovacích dat z 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).

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.