Kdy se narodil. . . ´ Vypracovali: Mrk´yvka Vojtˇech, Mrazek Ondˇrej, Novotna´ Marie Pˇredmˇ et: PLIN08 Projekty II Semestr: Jaro 2015 ´ Ph.D. Vedouc´ı projektu: Mgr. Marek Grac, ´ ˇ ıc´ı Ukolem tohoto projektu bylo vytvoˇrit program/skript umoˇznuj´ ˇ ´ poˇc´ıtaˇci automaticky zodpov´ıdat nˇekter´e otazky ve hˇre Cesko (jin´ymi slovy: snaha nauˇcit poˇc´ıtaˇc vyhledat v textov´ych souborech jisty´ typ informac´ı a pracovat s nimi). ˇ ´ vˇedomostn´ı hra postavena´ na t´ymov´em Cesko je stoln´ı (deskova) ´ ı otazek ´ ˚ soupeˇren´ı v zodpov´ıdan´ vztahuj´ıc´ıch se nˇejak´ym zpusobem ˇ ´ k Cesk´e republice. Otazek existuje ve hˇre velk´e mnoˇzstv´ı (tedy se da´ ´ ´ a´ a je nahodn ´ ´ Ve hˇre existuje tvrdit, zˇe otazka nen´ı dopˇredu znam a). ´ nˇekolik okruhu˚ otazek. ´ s ukol ´ Naˇ spoˇc´ıval ve vytvoˇren´ı skriptu, ktery´ by umˇel excerpovat ´ e osobnosti (coˇz je jeden z textov´eho vstupu datum narozen´ı znam´ ˚ z frekventovan´ych hern´ıch dotazu).
1
Pˇr´ıpravn´a f´aze
´ ´ r´ıme, pracuje se surov´ymi Zakladn´ ı program, pro kter´y skript vytvaˇ daty z´ıskan´ymi na internetu. Tzn. bylo nutn´e zjistit, jaky´ v´ysledek ´ c po zadan´ ´ ı dotazu na jm´eno osobnosti. Podle toho pˇreda´ vyhledavaˇ bylo pozdˇeji moˇzn´e navrhnout algoritmus. ˚ jmen osobnost´ı se nam ´ podaˇriPo zkouˇsen´ı velk´eho poˇctu dotazu ´ lo zjistit, jak´e vysledky se zobrazuj´ı nejˇcastˇeji. ´ ´ U v´ıce neˇz 90 % vyhledavan ych osobnost´ı se jako prvn´ı ve vy´ ci zobrazuj´ı odkazy na portal ´ Wikipedie.org. Zbyl´ych asi hledavaˇ ´ 10 % v´ysledku˚ odkazuje na osobn´ı webov´e stranky osobnost´ı (vˇet´ e velmi znam´ ´ e osoby). sˇ inou se jednalo o zˇij´ıc´ı a medialnˇ ´ ´ cu˚ Google i Seznam. Dotazy jsme zadavali do vyhledavaˇ
1
2
Wikipedie
´ ach ´ ´ opˇet zadavali ´ Na strank Wikipedie jsme v dalˇs´ı fazi jm´ena cˇ es´ kych osobnost´ı. Pozorovali jsme, zˇe jednotliv´e v´ysledky, respektive ´ informace o datech narozen´ı, b´yvaj´ı napsany ve velmi podobn´e ˚ formˇe. To je zpusobeno t´ım, zˇ e dnes jiˇz na Wikipedii existuj´ı pravi´ ´ enych ´ dla o podobˇe jednotlivych uvadˇ informac´ı. D´ıky tomu se lze ˚ ze mˇenit obsah jednotliv´ych wiki spolehnout na to, zˇe i kdyˇz se muˇ ´ ´ zustane ˚ stranek, format t´emˇerˇ nezmˇenˇen. ´ bylo tak´e potˇreba zjistit, zda neexistuj´ı osobnosti, V t´eto fazi u nichˇz se standardn´ı podoba informace o datu narozen´ı diferencuje. ´ an´ ´ ı muselo byt ´ z podstaty informace intuitivn´ı. (Toto vyhledav ´ e probl´emov´ych osobnost´ı (z hleZnalost existence tˇechto potencialnˇ ´ ´ ´ diska formy zapisu) je totiˇz zavisl a´ na empirickych zkuˇsenostech, tzn. nelze algoritmizovat.)
2.1
Form´at informac´ı
˚ Z pruzkumu vyplynulo, zˇ e standardn´ı podoba informace o datu ´ ach ´ narozen´ı na wiki strank ma´ tento charakter: ´ ´ • cela´ informace je uzavˇrena v kulat´ych zavork ach ´ • v samotn´e zavorce jsou uvedeny informace o dobˇe narozen´ı ´ (den, mˇes´ıc, rok), m´ıstˇe narozen´ı, datu umrt´ ı (den, mˇes´ıc, rok) ´ a m´ıstˇe umrt´ ı1 ´ tˇechto jednotliv´ych oblast´ı (data, m´ısta), tedy struktura • format ´ textu v zavorce, je t´emˇerˇ shodn´y ´ Pˇr.: Alois Jirasek (23. srpna 1851 Hronov (1) – 12. bˇrezna 1930 ˇ esk´y prozaik, dramatik a politik, autor ˇrady historick´ych Praha) byl c ´ u˚ a pˇredstavitel realismu. roman ´ bylo sestaven´ı regularn´ ´ ıho vy´ razu, ktery´ by akC´ılem t´eto faze ´ ceptoval co nejv´ıce variant moˇzn´ych forem zapis u˚ (pokud moˇzno vˇsechny). 1
Pokud osoba zˇ ije, pak tyto informace pochopitelnˇe nejsou.
2
2.2
Probl´emov´e jevy
´ ach ´ Pokud by byly informace o datu narozen´ı na vˇsech strank sku´ ı regularn´ ´ ı teˇcnˇe shodn´e, nebylo by pˇr´ıliˇs obt´ızˇn´e sestavit adekvatn´ v´yraz. ´ ´ Museli jsme ale zohlednit i to, zˇe nˇekter´y z udaj u˚ v zavorce chyb´ı ´ jinou formou. nebo je realizovan ´ Pokud hledana´ osoba zˇ ije, je obsah textu v zavorce v podstatˇe poloviˇcn´ı. ˚ ze problematizovat napˇr. m´ısto narozen´ı Sestaven´ı dotazu muˇ ´ nebo umrt´ ı osoby. Tˇreba tehdy, je-li jm´eno mˇesta v´ıceslovn´e, obsahuje-li spojovn´ık aj. (Fr´ydek-M´ıstek, Borova´ u Pˇribyslavi).
´ ˚ Pˇr´ıklady probl´emovych jevu: • uveden´ı symbolu˚ * u narozen´ı osoby ´ ´ ´ • rozd´ıln´e padov´ e formy mˇes´ıcu˚ (leden, ledna, unor, unora, ...) ´ • redundatn´ı vyrazy asi, nebo“ (u osob, kdy nen´ı dana´ infor” mace dostateˇcnˇe doloˇzena) ´ • uveden´ı jin´ych informac´ı v zavorce (napˇr. cel´e jm´eno osoby) ´ ı m´ısta narozen´ı nebo umrt´ ´ • v´ıceslovn´e pojmenovan´ ı • ...
2.3
Sestaven´ı regul´arn´ıho vyrazu ´
´ se zm´ınˇen´e probl´emov´e jevy nejsou jedin´e, se kterymi ´ Vyˇ jsme se ´ setkali. Pouze ilustruj´ı velkou variantnost moˇzn´ych zapis u˚ v (na ´ prvn´ı pohled) homonymn´ı podobˇe obsahu zavorky. ´ ı v´yraz pak byl sestaven pro mnoˇzinu nˇekolika Samotn´y regularn´ ´ ´ ´ tak, aby vyhovoval i tˇr´ıstandardn´ıch zapis u˚ a naslednˇ e rozˇsiˇrovan ´ samostatn´ych probl´emovych ´ ˚ dam jevu. ´ I bˇehem t´eto faze jsme se pokouˇseli rozˇs´ırˇit okruh osob s ne´ vhodnou podobou zapisu. Jm´ena obsahuj´ıc´ı pˇr´ıdomky (ˇslechtick´y ´ ´ predikat), dvˇe data narozen´ı nebo umrt´ ı aj. a tyto opˇet otestovat ´ ı regularn´ ´ ı v´yraz. pro aktualn´
3
3
Skript
´ ı v´yraz, bylo potˇreba jej Kdyˇz byl sestaven dostateˇcnˇe siln´y regularn´ ´ efektivnˇe aplikovat v ramci skriptu. ´ s nimi Samotn´y vy´ raz pouze najde konkr´etn´ı informace, ale dale nepracuje. ´ Mohli jsme ale tento v´yraz vyuˇz´ıt v ramci skriptu, ktery´ by pomoc´ı nˇej pˇridal do textu metainformaci o datu narozen´ı. Vy´ sledn´y ´ program pak pouze analyzuje nami obohacen´y text a v´yslednou informaci pˇreda´ na v´ystup. ˇ Jedn´ım z rˇeˇsen´ı byl unixov´y program sed, ktery´ umoˇznuje na´ ı textov´ych rˇetˇezcu˚ jin´ymi rˇetˇezci. hrazovan´ V praxi by to vypadalo tak, zˇ e bychom napˇr. rˇetˇezec 23. srpna ” ´ 1851“ uzavˇreli do parov´ ych tagu˚ s metainformac´ı datum naro” zen´ı“. ´ ı jsme ale zjistili, zˇe program sed nen´ı pro naˇ ´ s uˇ ´ cel Pˇri testovan´ ´ ´ ı. Skript v nˇem zapsany´ byl velmi nepˇrehledn´y a v pru˚ uplnˇ e idealn´ ´ ı se ani zkouˇsen´e regularn´ ´ ı v´yrazy nechovaly podle bˇehu testovan´ ´ an´ ´ ı. oˇcekav Vhodnˇejˇs´ı variantou pak bylo napsat skript v jazyce Python. Tuto metodu jsme nakonec zvolili.
3.1
Popis algoritmu
Skript vyˇzaduje na vstupu textova´ data, ktera´ analyzuje. Pokud ´ najde hledan´e informace, vrac´ı je na vystup doplnˇen´e o metainfor´ ˚ mace. Zakladn´ ı soubor, tak zustane nezmˇenˇen. ´ ıch vy´ razu. ˚ Samotn´y skript je sloˇzen ze dvou hlavn´ıch regularn´ ´ Jeden pokr´yva´ skupinu dat obsahuj´ıc´ıch datum narozen´ı i umrt´ ı osoby. Druh´y vy´ raz zachycuje data u osob maj´ıc´ıch pouze datum narozen´ı. Pˇred tiskem v´ystupn´ıch dat jsou provedeny jeˇstˇe nˇekter´e, sp´ısˇ e ´ ı, upravy ´ ´ vizualn´ (napˇr. je nahrazen slovn´ı udaj mˇes´ıce narozen´ı za ´ jeho cˇ ´ıselnou reprezentaci: leden = 1, unor = 2 atd.) Pˇrestoˇze c´ılem bylo zjistit pouze informaci o narozen´ı osoby, rozhodli jsme se zpracovat i nˇekter´e dalˇs´ı informace (m´ısto narozen´ı, ´ datum a m´ısto umrt´ ı).
4
4 4.1
Z´avˇ er Slabiny skriptu
´ ı na strank ´ ach ´ Jak jiˇz bylo rˇeˇceno, asi 10 % dotazu˚ se nenachaz´ Wikipedie. Zjistili jsme, zˇe tyto v´ysledky jsou natolik rozd´ıln´e (formou ´ zapisu informace o narozen´ı), zˇe je nemoˇzn´e je zahrnout do naˇsich ´ ıch v´yrazu. ˚ regularn´ ´ Zapisy byly dokonce natolik rozd´ıln´e, zˇe by bylo nutn´e sestavit ´ ıch vy´ razu˚ velk´e mnoˇzstv´ı. Nav´ıc nen´ı jist´e, jestli by i tak regularn´ ´ an´ ´ ı uspˇ ´ esˇ n´e. bylo vyhledav ´ Protoˇze pro tˇechto 10 % existuje i stranka na Wikipedii, bylo by ´ e tam, kde by bylo moˇzn´e efektivnˇejˇs´ı pˇresmˇerovat program pravˇ pouˇz´ıt funguj´ıc´ı skript. ´ ı informac´ı u nˇekter´ych Dalˇs´ı slabinou je pak nefunkˇcnost z´ıskan´ osob; napˇr. tehdy, vyskytuj´ı-li se u osoby dvˇe data narozen´ı nebo ´ umrt´ ı. Tyto pˇr´ıpady ale nelze predikovat, takˇze probl´em bude vhodn´e ´ ıho v´yrazu. rˇeˇsit operativnˇe aˇz ve chv´ıli zjiˇstˇen´ı nefunkˇcnosti regularn´
4.2
Vyhody skriptu ´
´ ı v jazyce Python umoˇznuje ˇ ´ Zpracovan´ d´ıky pˇrehledn´emu zapisu (oproti sedu) snadnou manipulaci s obsahem, a t´ım dovoluje rychle ´ ı vyrazy ´ upravit regularn´ nebo podobu v´ystupu. ´ ı i jinych ´ Z´ıskan´ informac´ı, neˇz je datum narozen´ı, zjednoduˇsuje ´ vysledn´ ´ praci eho programu, kter´y v jedn´e iteraci anal´yzy textu z´ıska´ ˚ zit´ych dat. v´ıce duleˇ ´ Oproti sedu je nav´ıc jednoduˇssˇ ´ı prace se zpˇetn´ymi referencemi ´ ´ ıch v´yrazu. ˚ v ramci regularn´
5
