Náměty na ročníkové projekty

kontakt: zeman@ufal.mff.cuni.cz

http://ufal.mff.cuni.cz/daniel-zeman/

VAROVÁNÍ: Seznam témat níže je poměrně starý a aktualizuji ho zřídka. Podívejte se také do SISu, zda nemám momentálně nějaká volná témata na bakalářské práce. Ve většině případů je možné začít práci na bakalářských tématech jako ročníkový projekt.

Výběr tématu

Silně preferuji zájemce o počítačové zpracování přirozeného jazyka, popř. vyhledávání informací v db a na webu (opět s přihlédnutím k lingvistice) apod.

Chcete-li dělat (např.) hry, počítačovou grafiku (snad s výjimkou jazykově znalého OCR), multimédia všeho druhu, low-level věci s operačními systémy a sítěmi, vyhněte se mi. Tento seznam nedoporučených témat samozřejmě není úplný, k jeho rozšíření mě mohou inspirovat i nápady ročníkářů, kteří se ke mně pohrnou .

Nicméně vždycky existují výjimky potvrzující pravidlo. Proto se nedivte, pokud v seznamu mnou navržených témat na konci tohoto dokumentu najdete i témata zjevně odporující právě uvedenému.

Platforma a jazyk

Preferuji Perl, Python, Gnu C/C++, popř. i Javu a různé webové aplikace. Nejsem zvláštní kamarád Pascalu ani Delphi.

Pokud budete chtít udělat něco, co nepůjde spustit jak pod Windows, tak pod Linuxem, měli byste k tomu mít zatraceně dobré důvody. Okenní aplikace jsou tím v nevýhodě, ale nejsou samozřejmě vyloučeny; pokud chcete nějakou interakci, zvažte, jestli už není výhodnější udělat to jako webovou aplikaci.

Návrhy témat

Můžete samozřejmě navrhovat svá vlastní témata (ale s přihlédnutím ke kapitole Výběr tématu výše, protože já se s vašimi návrhy nemusím ztotožnit). Inspirovat se můžete i níže uvedenými nápady. Samozřejmě budu chtít, aby žádní dva studenti, kteří jsou u mě zapsaní na ročníkový projekt v jednom roce, nedělali totéž.

Viz též témata bakalářských prací v SIS. Vzhledem k tomu, že ročníkové projekty často přerostou v bakalářskou práci, mnou nabízená bakalářská témata jsou také relevantní. (A pokud je vypíšu v SISu, nesnažím se je nezbytně zkopírovat i na tuto stránku.)

Zpracování pozvánek na konference. Maily s pozvánkami na konference jsou psané anglicky a jeden druhému se dost podobají, bez ohledu na to, kdo je poslal a o jakou konferenci jde. Obvykle v nich jsou informace jako kdy a kde se konference koná, do kdy a komu je potřeba poslat svůj příspěvek, kdy se autor dozví, zda byl příspěvek přijat, kdo je členem programového výboru atd. Úkolem by bylo přečíst takový mail, vytáhnout z něj co nejvíc informací a uložit je do databáze, kde už se s nimi bude pracovat snadno. Typické využití by bylo v programu, který filtruje maily a když na nějakou konferenci narazí, uloží výsledek tak, aby nějaký cgi skript mohl na webu zobrazovat přehled konferencí, blížících se deadlinů apod. Vzorové maily dodám.

Vyhledávání a přepis adres institucí a osob na čínských webových stránkách. Vzhledem k vlastnostem čínského písma (nejednoznačné zobrazení mezi znaky a výslovností, chybějící mezery mezi slovy) není snadné napsat program pro automatický přepis čínských znaků do latinky. Ještě těžší je přepsat romanizovaný text zpět do čínských znaků: neobejdeme se bez znalosti kontextu a čínské slovní zásoby a jakákoli automatická procedura prakticky nemá šanci zvládnout tuto úlohu bez chyb. Pokud tedy dostaneme do ruky adresu čínské instituce přepsanou do latinky (případně částečně přeloženou do angličtiny), bez znalosti čínštiny neumíme tuto adresu přepsat správně čínsky (na rozdíl od např. ruštiny, kde stačí znát ruskou abecedu, ale ne nutně ruský jazyk jako takový). Pokud však známe adresu webových stránek dané instituce, velmi pravděpodobně můžeme její plný název a adresu v čínštině nalézt na webu. Otázka je, jak ji bez znalosti čínštiny na čínsky psaném webu poznat. Naštěstí čínské adresy mají poměrně pevně danou strukturu: většinou jde o dlouhý řetězec, který začíná názvem země nebo města a končí číslem domu; někdy je na začátku dokonce výraz pro slovo „adresa“: 地址：北京海淀区中关村科学院南路6号　邮编：100190　电话：010-62601166 邮箱：xuanchuanban@ict.ac.cn. Kromě toho můžeme využít dalších indicií: adresa bývá buď na dolním okraji titulní stránky nebo na stránce, na kterou vede odkaz „kontakt“; někdy jsou stránky dvojjazyčné čínsko-anglické s paralelní strukturou; je možné vytvořit a využívat malý slovníček čínských klíčových slov jako „adresa“, „kontakt“, „ulice“, „PSČ“ atd. Cíl práce: na vstupu je anglický (popř. český) název čínské instituce a URL její vstupní webové stránky. Na výstupu chceme plný název instituce (a popř. oddělení), adresu rozepsanou na složky (provincie, město, městská část, ulice, číslo, PSČ…) jednak ve zjednodušených čínských znacích, jednak podle možnosti v přepisu pchin-jin s vyznačením tónů (určité tabulky pro přepis jsou k dispozici), případně též v anglické podobě. Alternativně lze také nabídnout webovou stránku s barevně zvýrazněnou adresou. Možným rozšířením této práce je vyhledávání čínsky zapsaných jmen osob, které jsou v dotyčné instituci zaměstnány.

Transcription of natural language text from one script to another is needed for various tasks such as:
- transcription of foreign personal or geographical names to be used in other than original language
- pronunciation guide for foreigners
- input method on computers and other devices lacking keybord for the target script
Transcription, in contrast to transliteration, does not necessarily mean a 1-1 mapping between sets of characters. Transcription focuses on capturing the pronunciation using the spelling rules of another script AND language. I.e., transcription of the Russian name Чайковский into the Latin script may result in Chaikovsky, Tchaïkovski, Tschaikowski or Čajkovskij, among others, depending on the target language. The focus on pronunciation can be exploited if we decompose transliteration into modeling pronunciation of all the languages involved, using the International Phonetic Alphabet (IPA). We could model the mapping between sequences of characters in language L1 and sequences of IPA symbols. Then we could combine the models so that L1 -> IPA -> L2 would render the desired transliteration L1 -> L2.
The goal of the thesis is to test the approach on at least three languages, two of which use the Latin script and one using a different script. Create a rule-based model of pronunciation of each language (i.e. bi-directional mapping Lx IPA) and use the models to test and evaluate all 6 (or more in case of more languages) transcription directions.

Interpret JavaScriptu v Perlu. V jazyce Perl jsou k dispozici velmi příjemné knihovny pro psaní robotů, které procházejí web, analyzují stránky, případně dokonce vyplňují webové formuláře. Funkce z těchto knihoven si však většinou vylámou zuby na stránkách, které silně využívají JavaScript. Pokud se obsah stránky (např. webového formuláře) může podstatně změnit na základě akcí uživatele, je velmi obtížné zařídit, aby robot vyplnil a odeslal formulář ve stejném tvaru, v jakém to udělá uživatelův prohlížeč, který umí interpretovat JavaScript. Interpret by se měl snažit napodobit DOM (document object model), např. takový, jaký je v prohlížečích Mozilla (zdokumentovaný na webu). Potom by poskytl funkce, které nasimulují akce jako kliknutí na tlačítko či vyplnění textového pole a upraví odpovídajícím způsobem obsah DOM.

Archivní témata

Jak nadpis napovídá, tato témata již nenabízím, pouze zde archivuji jejich zadání.

Scrabble. Především jádro, až pak případně grafické rozhraní, hrátky se slovníkem aj. Jádro by mělo umět převzít popis stavu na hrací desce scrabble a seznam písmen v zásobníku hráče. Dále by mělo mít odkaz na slovník a seznam kamenů (písmeno, počet, bodová hodnota). Rovněž velikost desky, umístění startovacího pole a rozmístění 4 druhů prémiových polí lze jádru zadat, byť standardní scrabblová deska má samozřejmě jednotný vzhled. Musí zvládat libovolný jazyk (Unicode)! „Písmeno“ na kameni se může skládat i z více než jednoho znaku (např. „CH“). Jádro by mělo na základě uvedených vstupů vrátit nejlépe bodovaný tah. Volitelně lze též implementovat funkci pro „nejvýhodnější“ tah, tedy takový, který nebude pouze maximalizovat body, ale pokusí se zhodnotit i další faktory (snaha po zbavení se nevhodných písmen ze zásobníku, snaha nenahrát soupeři, snaha prodat žolíka dostatečně draho…)

Jádro bude funkce, případně obalená konzolovou aplikací. Měla by fungovat ve Windows i v Linuxu. K ní lze přibalovat další nadstavby – vedení skutečné hry v normálním či opisovaném scrabblu, grafické rozhraní, webové rozhraní, analýzu partií apod.

Anotační nástroj pro rozbor věty. Jako inspirace může posloužit program Tred, který je sice skvělý, ale už mnoho let se nevyvíjí ani neudržuje. Místo komplikovaných datových formátů založených na XML by nový nástroj pracoval s relativně jednoduchým formátem CoNLL-U. Ke splnění projektu zdaleka není nutné (a v podstatě ani možné) re-implementovat všechny funkce Tredu. Stačilo by základní zobrazení stromu (reprezentace vztahů ve větě), schopnost měnit zapojení uzlů přetažením myší, možnost editovat atributy uzlu a atributy věty, vyhledávání uzlu (napříč celým souborem) na základě kritérií pro atributy uzlu. Nutná je ale podpora Unicodu, tj. libovolného jazyka. Další podrobnosti ústně.

Strojový překlad v procmailu. Strojový překlad z češtiny a cestiny do angličtiny napojený na procmail a překládající maily. Bylo by možné využít např. v e-mailových konferencích, kde většina účastníků píše a čte česky, ale někteří rozumí pouze anglicky. Zahrnovalo by natrénování frázového open-source systému (např. Moses nebo Joshua), snahu o snížení výpočetních nároků a rychlý start (nebo trvale běžící „překladový server“), adaptaci na neobvyklou doménu mailů (chybějící diakritika, znaky „>“ uvozující odpověď…)

Rozpoznávač spamu. Pochopitelně by měl umět víc než to, co umí každý mailový klient, tj. pravidla typu „zahoď zprávu když Subject obsahuje text Enlarge your…“. Rozpoznávač by měl být schopen se učit, protože témata spamů se vyvíjejí; měl by být schopen se aspoň částečně vyrovnat s tím, že spammeři cpou do spamů navíc mezery, interpunkci či pozměněná písmenka, aby obešli antispamová pravidla. Program nemusí spoléhat pouze na lingvisticky motivovaná pravidla, může sledovat i další věci jako HTML odkazy v mailu, měl by také být schopen využít seznam povolených a zakázaných adres odesilatelů atd. Pokud máte ve své vlastní schránce málo studijního materiálu, můžu dodat. Březen 2005: Zadání si vzal Martin Žember.

Novelizátor zákonů. Projde sbírku zákonů, najde novelizace daného předpisu a vyrobí úplné znění se zvýrazněnými změnami. Novely zákonů jsou pro normálního člověka nečitelné a neposkytují přehled o platném znění zákona. Úplné znění zákona se při tom vydává vždy až po několika novelách. Novely často obsahují konstrukce typu "čárka a všechno za ní se vypouští", "za druhou větu odstavce se vkládá věta..." atd. Cílem projektu by bylo analyzovat text, kterým jsou provedené změny popsány, změny provést a vytvořit tak úplné znění zákona. Pozor, bude to chtít sehnat nějakou knihovnu pro práci s PDF soubory, protože sbírka je na webu k dispozici v PDF. Březen 2005: Zadání si vzal David Mareček.

Analýza záznamu z GPS. Navigační přístroje GPS obvykle umožňují zaznamenat tzv. „stopu“, tedy trasu, kterou uživatel prošel nebo projel. Stopa je posloupnost bodů, u každého bodu je uvedena poloha v prostoru (zeměpisné souřadnice, nadmořská výška) a čas. Stopy jsou ukládány v různých formátech, nejrozšířenější je tzv. GPX (založený na XML). Ze zaznamenané stopy lze triviálně vypočítat např. celkový čas jízdy, průměrnou rychlost, nejvyšší nadmořskou výšku atd. Neméně zajímavé, avšak mnohem méně triviální, by bylo rozdělit stopu na úseky se stejným stylem pohybu, takže bychom např. poznali, že část trasy šel uživatel pěšky, potom nasednul do auta a jel městem, posléze po dálnici, aby nakonec vystoupil u pumpy a vešel do obchodu, kde kvůli slabému signálu GPS začala poloha zmateně poskakovat po okolí.

Cílem práce je vybrat a otestovat charakteristiky, na jejichž základě bude možné rozpoznat jednotlivé druhy pohybu, a natrénovat na pokusných datech model, který umožní rozebrat nová data a označkovat jednotlivé úseky stopy. Toto téma vede na metody strojového učení a značkování sekvenčních dat, má tedy společné rysy s metodami počítačového zpracování přirozeného jazyka, i když data, se kterými budeme pracovat, jsou zcela nelingvistická. Březen 2016: Zadání si vzal Petr Sokola.

Swiss Perfect. Nová implementace funkcí programu, který už existuje (www.swissperfect.com), ale bohužel se dále nevyvíjí a není open-source. Úkolem programu je asistovat při organizaci turnaje (např. šachového): nalézt pro každé kolo optimální párování hráčů podle zadaných kritérií, evidovat výsledky partií, vypočítat průběžné a závěrečné pořadí hráčů, žebříčky apod. Okenní aplikace, která musí být spustitelná pod Windows i pod Linuxem (lze využít např. Perl s knihovnou Tk), případně lze uvažovat i o webové aplikaci.