(ú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 program, který dokáže stáhnout z internetu dostatečné množství textů, ze kterých lze vyrobit korpus určitého jazyka. Stáhněte texty v tomto jazyku a vyrobte korpus o alespoň 500000 slov. Součástí zadání bude konkrétní jazyk, váš program by však měl být 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, naopak je možná výhodou, když je vám tento jazyk zcela neznámý.)

Úloha má tyto části:

1. Vlastní pavouk. Program, který leze po webu, stahuje dokumenty, čistí je a vypisuje je (nebo vybrané části) na standardní výstup.
2. Program na natrénování statistiky, podle které dokážeme rozpoznat jazyk dokumentu.
3. Rozšíření pavouka o modul, který načte natrénované statistiky jazyků a o stahovaných dokumentech pak dokáže říct, zda jsou v požadovaném jazyku, nebo ne.
4. Vytipování počátečního URL pro jazyk, který vám byl zadán. Spusťte pavouka a stáhněte korpus, který po vyčištění bude obsahovat alespoň 1 milión slov (před tokenizací, tedy od mezery do mezery).

Odevzdávat budete oba programy a stažený korpus.

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 bude jmenovat pavouk.pl a bude se volat s jedním nebo více argumenty, které se interpretují jako URL (internetové adresy). Kromě toho se mohou mezi argumenty nacházet i volby (options), které určují, kolik textu a z jakého jazyka se má stáhnout.

pavouk.pl -l frq/cs.frq -t 0.36 -n 1000000 http://seznam.cz/ http://centrum.cz/

-l frq/cs.frq říká, že v souboru frq/cs.frq program najde frekvenční charakteristiku jazyka, ve kterém mají dokumenty být. Parametrem -t můžete předat prahovou hodnotu míry podobnosti dokumentu danému jazyku, pod kterou už se mají dokumenty zahodit (alternativně můžete zadat cestu ke složce s charakteristikami dalších jazyků a text, který se více podobá jinému jazyku, taky zahodit; bez prahu se ale neobejdete, protože jinak hrozí, že narazíte na jazyk, který se dostatečně nepodobá ničemu, co máte natrénováno, ale bohužel vašemu jazyku se podobá o něco víc než těm ostatním).

Parametr -n 1000000 říká že program má procházení ukončit poté, co velikost získaného korpusu překročí milión slov. Volba -n 0 by znamenala, že má běžet tak dlouho, dokud ho někdo neukončí násilím.

Úkolem programu je stahovat dokumenty na uvedených adresách, hledat v nich odkazy na další dokumenty, ty také stahovat a takto pokračovat až do nalezení dostatečného množství textu. Dokumenty, které nejsou v požadovaném jazyku, zahodí. Program se nesmí zacyklit, tj. opakovaně zpracovávat stránky, na kterých už byl. (K identifikaci takových stránek někdy nestačí URL, potřebujete sledovat i obsah. Některé dynamicky generované stránky obsahují odkaz na sebe sama pokaždé s jiným URL.)

Snažte se identifikovat a likvidovat opakované výskyty téhož odstavce (zejména pokud jde o jednoslovné odstavce, jako jsou různé položky nabídek na internetových portálech). Volitelně můžete také zkusit identifikovat jazyk každého odstavce a vyhodit intervenující např. anglické odstavce v dokumentu, který je jinak převážně ve vámi hledaném jazyku. Počítejte ale s tím, že určit statisticky jazyk krátkého řetězce je těžší než u delšího dokumentu.

Dokumenty, které projdou uvedeným filtrem, vyčistěte od veškerého kódu HTML a vypište na standardní výstup (STDOUT). Zachovejte pouze informaci o tom, kde začíná nový odstavec (HTML prvky div, h1, h2, h3, h4, h5, h6, p, table, tr, th, td, ul, ol, li, dl, dt, dd, select, option a možná některé další). Nezapomeňte odstranit kód JavaScriptu, definice stylů a text, který není součástí těla dokumentu (třeba prvek head). Entity převeďte na normální znaky.

Výstup je vždy v kódování UTF-8. Pokud umíte na webu rozpoznat texty v jiném kódování téhož jazyka, překódujte je.

Každý řádek na výstupu odpovídá právě jednomu odstavci staženého dokumentu. Prázdné odstavce vynechte. Odstraňte všechny mezery na začátku a na konci každého řádku (odstavce). Pokud mezi slovy uvnitř odstavce leží více než jedna mezera, zařiďte, aby tam zůstala právě jedna mezera. Mezerové znaky jako tabulátor (kód 9), neoddělitelná mezera (kód 160), popř. řídící znaky nahraďte normální mezerou (kód 32). Text ale netokenizujte (tj. nesnažte se třeba odtrhnout čárku od předcházejícího slova, pokud mezi nimi v původním dokumentu mezera nebyla).

Sežeňte si dostatečně velkou webovou stránku v daném jazyce jako výchozí bod. Jazyky, které jsou součástí zadání, mohou být exotické, ale žádný není natolik vzácný, aby se na webu nedal objevit alespoň ve Wikipedii (http://wikipedia.org/). Ta je navíc celá v UTF-8, takže se ani nemusíte starat o různá další kódování.

Úvodní stránku si uložte jako text (bez HTML entit!) a získejte z ní frekvenční charakteristiku daného jazyka. Potom pokusně pusťte pavouka z této stránky na web a sledujte, jakých hodnot dosahuje vámi navržená míra podobnosti frekvenčních vektorů. Podle toho odhadněte vhodnou prahovou hodnotu a pusťte pavouka naostro.

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.

Krátké ukázky z jazyků, které jsou v nabídce v zimním semestru 2007-8:

Kiswahili ni lugha ya kibantu yenye misamiati mingi ya kiarabu inayozungumzwa katika eneo kubwa la Afrika ya Mashariki. Lugha hii ina utajiri mkubwa wa misamiati na misemo na mithali na mashairi na mafumbo na vitendawili na nyimbo. Nayo inatumika katika mashule kufundishia elimu mbali mbali za dini na dunia, na kuna vitabu vingi vilivyotungwa kwa kutumia lugha hii, vikiwa vya hadithi au hekaya au riwaya.

తెలుగు, భారత దేశములోని దక్షిణ ప్రాంతములోని ఆంధ్రప్రదేశ్ రాష్ట్రపు అధికార భాష, మరియు దాని పక్క రాష్ట్రములయిన తమిళనాడు, కర్ణాటక, ఒరిస్సా, చత్తీస్‌గఢ్ ప్రజలు మాట్లాడే భాష. ప్రపంచంలో అత్యధికముగా మాట్లాడే వాటిలో పదిహేనవ స్థానములోనూ, భారత దేశములో రెండవ స్థానములోను నిలుస్తుంది. 2001 జనాభా లెక్కల ప్రకారం సుమారుగా ఏడుకోట్ల ముప్పై లక్షల మంది ఈ భాషను మాట్లాడతారు.

Tiếng Việt hay Việt ngữ[2] là ngôn ngữ của người Việt (người Kinh) và là ngôn ngữ chính thức tại Việt Nam. Đây là tiếng mẹ đẻ của khoảng 85% dân cư Việt Nam, cùng với gần ba triệu Việt kiều ở hải ngoại, mà phần lớn là người Mỹ gốc Việt. Tiếng Việt còn là ngôn ngữ thứ hai của các dân tộc thiểu số tại Việt Nam. Mặc dù tiếng Việt có nguồn từ vựng vay mượn từ tiếng Hán và trước đây dùng chữ Hán (chữ Nho) để viết, sau đó được cải biên thành chữ Nôm, tiếng Việt được coi là một trong số các ngôn ngữ thuộc hệ ngôn ngữ Nam Á có số người nói nhiều nhất (nhiều hơn một số lần so với các ngôn ngữ khác cùng hệ cộng lại). Ngày nay tiếng Việt dùng bảng chữ cái Latinh, gọi là chữ Quốc Ngữ, cùng các dấu thanh để viết.