[ Skip to the content ]

Institute of Formal and Applied Linguistics Wiki


[ Back to the navigation ]

Table of Contents

Pavouk

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

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). Nepoužívejte vlastnosti jazyka, které jsou nové v Perlu 5.12 nebo ještě mladší, omezili byste tím přenositelnost.

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ň 500000 slov (před tokenizací, tedy od mezery do mezery).


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

Specifikace programu pro trénování jazyků


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

Specifikace volání a práce pavouka


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 -f frq -t 0.36 -n 500000 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 parametrem -f 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 500000 říká že program má procházení ukončit poté, co velikost získaného korpusu překročí půl miliónu 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.

Stažené texty posílejte na standardní výstup (STDOUT, viz níže). Kromě toho na standardní chybový výstup (STDERR) pište (přinejmenším): jaký dokument (URL) právě zpracováváte, N nejpravděpodobnějších jazyků, ve kterých by dokument mohl být, a váhy, které vyjadřují, jak moc se dokument podobá danému jazyku. To je důležité, protože bez možnosti vidět váhy uživatel těžko dokáže odhadnout vhodný práh do parametru -t. Ze stejného důvodu by neškodilo, aby se na STDERR objevilo i několik slov ze začátku dokumentu.

Specifikace výstupního formátu


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).

Stahování vašeho jazyka


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.

Další informace


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.

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 nebo v minulých letech byly v nabídce:

2009-2010

Japonština


日本語(にほんご、にっぽんご)は、主として、日本で使用されてきた言語である。日本国は法令上、公用語を明記していないが、事実上の公用語となっており、学校教育の「国語」で教えられる。使用人口について正確な統計はないが、日本国内の人口、および海外に住む日本人や日系人など約1億3千万人と考えられる。ほぼ全ての日本在住者は日本語を第一言語とする。日本語の文法体系や音韻体系を反映する手話として日本語対応手話がある。

2008-2009

Hindština

भारत गणराज्य, पौराणिक जम्बुद्वीप, दक्षिण एशिया में स्थित एक देश है। यह भारतीय उपमहाद्वीप का सबसे बड़ा देश है। भारत का भौगोलिक फैलाव ८० ४' से ३७० ६' उत्तरी अक्षांश तक तथा ६८० ७' से ९७० २५'पूर्वी देशान्तर तक है। भारत का क्षेत्रफल ३२,८७,२६३ वर्ग कि. मी. हैं| भारत का विस्तार उत्तर से दक्षिण तक ३,२१४ कि. मी. और पूर्व से पश्चिम तक २,९३३ कि. मी. हैं। भारत की समुद्र तट रेखा ७५१६.६ किलोमीटर लम्बी है। भारत, भौगोलिक दृष्टि से विश्व का सातवाँ सबसे बड़ा और जनसँख्या के दृष्टिकोण से दूसरा बड़ा देश है| भारत के पश्चिम में पाकिस्तान, उत्तर-पूर्व में चीन, नेपाल, और भूटान और पूर्व में बांग्लादेश और म्यांमार देश स्थित हैं। हिन्द महासागर में इसके दक्षिण पश्चिम में मालदीव, दक्षिण में श्रीलंका और दक्षिण-पूर्व में इंडोनेशिया है। भारत उत्तर-पश्चिम में अफ़गानिस्तान के साथ सीमा का दावा करता है। इसके उत्तर में हिमालय पर्वत है। दक्षिण में हिन्द महासागर है। पूर्व में बंगाल की खाड़ी है। पश्चिम में अरब सागर है। भारत में कई बड़ी नदियाँ है। गंगा नदी भारतीय सभ्यता में बहुत पवित्र मानी जाती है। अन्य बड़ी नदियाँ ब्रह्मपुत्र, यमुना, गोदावरी, कावेरी, कृष्णा, चम्बल, सतलज, बियास हैं।

2007-2008

Rumunština

Limba română (sau dacoromână) este o limbă indo-europeană, din grupul italic, făcând parte din subgrupul oriental al limbilor romanice. Printre limbile romanice, româna este a cincea ca mărime după numărul de vorbitori, în urma spaniolei, portughezei, francezei şi italienei.

Svahilština

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.

Telugština

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

Pokud je proti vašemu přesvědčení pracovat s textem, který si neumíte ani přečíst, zkuste ho prohnat programem telugu2latin.pl. Výstup vašeho pavouka ale samozřejmě musí být původní telužský text!

Urdština

اردو انڈوآریائی زبانوں کی انڈو ایرانی شاخ کی ایک زبان ہے جس کا تعلق انڈويورپی زبانوں سے ہے۔اردو تيرھويں صدی ميں بر صغير ميں پيدا ہوئی ـ اردو پاکستان کی سرکاری زبان ہے اور بھارت کی سرکاری زبانوں ميں سے ايک ہے۔ اردو بھارت ميں 5 کروڑ اور پاکستان ميں دو کروڑ لوگوں کی مادری زبان ہے مگر اسے بھارت اور پاکستان کے تقریباً 50 کروڑ لوگ بول اور سمجھ سکتے ھیں ۔ جن میں سے تقریباً 10.5 کروڑ لوگ اسے باقاعدہ بولتے ھیں۔

Vietnamština

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.


[ Back to the navigation ] [ Back to the content ]