Univerzita Karlova v Praze Matematicko-fyzikální fakulta
BAKALÁŘSKÁ PRÁCE
Jan Bureš
Rozpoznávání číslovek v českém textu Ústav formální a aplikované lingvistiky Vedoucí bakalářské práce: RNDr. Jaroslava Hlaváčová Studijní program: Informatika, Programování
2007
Poděkování Na tomto místě bych chtěl poděkovat své vedoucí bakalářské práce paní RNDr. Jaroslavě Hlaváčové za podnětné připomínky a pomoc při tvorbě této práce a za poskytnutí testovacích dat a podkladů pro tvorbu.
Prohlášení Prohlašuji, že jsem svou bakalářskou práci napsal samostatně a výhradně s použitím citovaných pramenů. Souhlasím se zapůjčováním práce. V Praze dne 24. 5. 2007
Jan Bureš
Obsah OBSAH
3
KAPITOLA 1 – ÚVOD
6
1.1
Cíl
6
1.2
Zvolený jazyk
7
1.3
Přehled dalších kapitol
7
KAPITOLA 2 – ANALÝZA A NÁVRH
8
2.1
Dva způsoby zápisu číslovek
8
2.2
Číslovky psané číslicemi
8
2.2.1
Správné formátování číslovek psaných číslicemi
2.2.2
Rozpoznávání a sdružování číslovek psaných číslicemi
9 10
2.3
Číslovky psané slovy
11
2.4
Lexikální analýza
11
2.5
2.4.1
Morfologické značky
12
2.4.2
Seznam kořenových číslovek
13
2.4.3
Návrh automatu
17
Gramatická analýza
18
2.5.1
Možné zápisy složených číslovek
18
2.5.2
Použitý algoritmus
22
KAPITOLA 3 – IMPLEMENTACE 3.1
3.2
24
Lexikální analýza
24
3.1.1
Automat
24
3.1.2
Podrobný popis implementace stavby automatu
25
3.1.3
Vlastní lexikální analýza
26
3.1.4
Podrobný popis implementace lexikální analýzy
27
Gramatická analýza
28
3.2.1
Automat
28
3.2.2
Podrobný popis implementace stavby automatu
29
3
3.2.3
Samotná gramatická analýza
30
3.2.4
Podrobný popis implementace
31
KAPITOLA 4 – DOKUMENTACE 4.1
4.2
33
Uživatelská dokumentace
33
4.1.1
Systémové požadavky
33
4.1.2
Spouštění
33
4.1.3
Vstup
33
4.1.4
Výstup
34
Programátorská dokumentace
34
4.2.1
Formát souboru s tvary číslovek
34
4.2.2
Formát souboru s pravidly pro gramatickou analýzu
35
KAPITOLA 5 – ZÁVĚR
38
5.1
Shrnutí
38
5.2
Možnosti dalšího vývoje
39
PŘÍLOHY A
Obsah přiloženého CD
40
B
Příklad vstupu a výstupu
41
4
Název práce: Rozpoznávání číslovek v českém textu Autor: Jan Bureš Katedra (ústav): Ústav formální a aplikované lingvistiky Vedoucí diplomové práce: RNDr. Jaroslava Hlaváčová e-mail vedoucího:
[email protected] Abstrakt: Účelem práce bylo sestrojit nástroj, který by byl schopen rozpoznávat základní číslovky v česky psaném textu, a to jak číslovky zapsané číslicemi, tak složené číslovky zapsané slovy. Důraz je kladen hlavně na rozpoznávání číslovek zapsaných pomocí slov a jejich korektní spojování do složených číslovek. Při rozpoznávání slovy zapsaných číslovek a jejich spojování jsou rozpoznávány a brány v potaz i hovorové, nespisovné či jinak nesprávné, ale přesto používané tvary či spojení. Výstupem je pak pro každou číslovku její hodnota zapsaná pomocí číslic a množina možných morfologických značek. Program sám provádí lexikální i gramatickou analýzu na základě souboru tvarů slov a pravidel, která jsou mu poskytnuta. Klíčová slova: číslovky, rozpoznávání, nástroj
Title: Recognition of numerals in Czech text Author: Jan Bureš Department: Institute of Formal and Applied Linguistics Supervisor: RNDr. Jaroslava Hlaváčová Supervisor's e-mail address:
[email protected] Abstract: Purpose of this work is to create a tool capable of recognizing cardinal numerals in Czech text, both written with the use of digits and written with the use of words. Emphasis is placed on recognizing numerals written with words and their correct combining. Not only grammatically correct, but also other expressions and their combinations, that are quite frequent in the use of the language, were taken into account. Output is a numeric value of recognized numeral, and a set of possible morphological tags for each numeral. The program performs its own lexical and grammatical analysis based on a set of given numeral forms and rules. Keywords: numerals, recognition, tool
5
Kapitola 1 Úvod 1.1 Cíl Cílem této bakalářské práce je vytvoření jednoduchého nástroje, který bude schopen samostatně rozpoznat základní číslovky v elektronickém česky psaném textu, a převést je na jednotný a korektní styl zápisu. Nástroj bude schopen lexikální analýzy, tedy rozpoznání jednotlivých slov, které označují základní číslovky. Hlavní důraz bude ale kladen na analýzu gramatickou, tedy správné určení skupin slov označujících jedno číslo.
První částí bude rozpoznávání číslovek psaných číslicemi. To znamená nalezení všech číslic, desetinných čárek, lomítek a dalších znaků, které se mohou při tomto zápisu použít. Následně pak jejich správné spojení do celků a výstup v korektním tvaru dle platných norem pro zápis číslovek číslicemi.
Druhou částí bude rozpoznávání číslovek psaných slovy – nejprve se vyhledají všechna slova označující číslovky (homonyma nebudou brána v potaz) a poté se sloučí do správných celků. Budou vyhledávána i slova nespisovná či hovorová.
Součástí bakalářské práce bude shromáždění pravidel, týkajících se zápisu, skloňování a tvorby číslovek i norem pro jejich zápis a jejich sepsání do ucelené formy. Při shromažďování těchto pravidel se bude vycházet z korpusů, budou tak brány v potaz nejen korektní zápisy, ale i často používané znesprávné zápisy. Toto musí předcházet tvorbě samotného nástroje, neboť ten bude z těchto pravidel vycházet a bude muset být použit algoritmus vhodný pro tato pravidla.
Cíl bakalářské práce vychází z neexistence komplexního nástroje pro rozpoznávání číslovek. Krom toho je ve většině mluvnic problematika číslovek řešena pouze okrajově, a tak může bakalářská práce posloužit i jako zdroj informací o tomto slovním druhu. 6
Některé dílčí úlohy této práce byly řešeny v diplomové práci J. Ptáčka [1]. V této práci byly řešeny nezávisle a na rozdíl od výše uvedené práce na rovině surového textu.
1.2 Zvolený jazyk Program byl naimplementován pomocí jazyka Perl. Tento jazyk byl vybrán z mnoha důvodů. Byly to kupříkladu jeho podpora práce s regulárními výrazy a řetězci, jeho snadná přenositelnost mezi různými systémy a v neposlední řadě i to, že byl a je používán k implementaci jiných lingvistických nástrojů na Ústavu formální a aplikované lingvistiky.
1.3 Přehled dalších kapitol Druhá kapitola se zabývá analýzou a návrhem aplikace. V kapitole je stručně nastíněno skloňování a spojování číslovek a všechny kroky a rozhodnutí, která byla vykonaná před započetím implementace.
Třetí kapitola popisuje implementační fázi vývoje aplikace. Některé části kapitoly volně navazují na příslušné části druhé kapitoly a doplňují je o implementační detaily, které nebyly v době analýzy a návrhu aplikace ještě známé.
Čtvrtá kapitola obsahuje informace potřebné ke správnému použití programu a pokyny pro jeho spouštění.
V páté kapitole je zhodnoceno splnění cílů bakalářské práce, shrnuty možnosti výsledného programu a zmíněny možnosti dalšího vývoje.
7
Kapitola 2 Analýza a návrh 2.1 Dva způsoby zápisu číslovek Číslovky můžeme dělit podle několika kritérií. Vzhledem k tomu, že tato práce se zaměřuje pouze na číslovky základní, můžeme vynechat dělení podle významu či určitosti číslovek. Zbývá nám tak dělení podle zápisu, tedy na číslovky vyjádřené číslicemi (např. 13 či 1500) a číslovky vyjádřené slovy (např. sto nebo tři). Zadání této práce bylo navíc vymezeno pouze na základní číslovky označující celá čísla, nejsou v ní tedy řešena čísla desetinná ani zlomky, které jsou navíc často zařazovány mezi podstatná jména.
Toto dělení nám dělí i problém vyhledávání číslovek. Číslovky zapsané číslicemi se budou vyhledávat a zpracovávat jinak, než číslovky zapsané pomocí slov. Jejich vyhledání je jednodušší, protože mimo číslovek se v běžném textu číslice takřka nepoužívají. Jelikož u nich nelze bez znalosti kontextu určit pád ani rod, tak i rozpoznávání k sobě náležejících číslovek se bude implementovat odlišně, než u číslovek psaných slovy.
2.2 Číslovky psané číslicemi V běžném česky psaném textu se číslice vyskytují téměř výhradně při zápisu číslovek, přestože se mohou vyskytnou jako součást některých přídavných jmen (např. 4metrový) či příslovcí (např. 100procentně). Tento fakt by výrazně zjednodušil problém vyhledání číslovek zapsaných číslicemi, nebýt několika častých neduhů. Jedním z nejčastějších je zlozvyk psát jakési „pádové koncovky“ i za číslovky zapsané číslicemi, je tedy možno velmi často v textu najít zápisy jako od 5ti metrů. Jmenovitě se jedná o tyto koncovky: -ti, -mi, -em, -emi, -ech, -ma, -náct, -nácti, -cet, -ceti, -sát a -sáti.
8
Další častou chybou, při které se k číslovce připojí jedno nebo několik písmen, je vynechávání mezer po číslovkách. Číslovka zapsaná číslicí je stále samostatné slovo a měla by tedy po ní i před ní stát mezera, nebo jiný oddělovač slov. Bohužel, v mnoha případech je tato mezera nesprávně vynechávána – typicky při psaní časů (např. 18h), jednotek (např. 150km) nebo peněžních obnosů (např. 15Kč nebo ₤15).
2.2.1 Správné formátování číslovek psaných číslicemi Správné formátování číslicemi zapsaných číslovek závisí na významu. Při psaní matematických vyjádření nebo vyjádření počtu se číslice seskupují do skupin po třech, a to na obě strany od desetinné čárky, přičemž skupiny se oddělují mezerami (např. 3 512 631,015 21) nebo z důvodů bezpečnosti či přehlednosti v některých případech tečkami (např. 3.512.631,50). Pro oddělování celé a desetinné části se v češtině používá čárka. Před desetinou čárku ani za ni se mezera nevkládá. V případě, že zapisované číslo má pouze čtyři číslice, je možno mezeru vynechat (např. 3512).
Při psaní data se také často zapomíná na mezery. Správný zápis data má po každé tečce mezeru (např. 21. 4. 1984). Výjimkou je zkrácený formát zápisu s lomítkem, kdy se mezery i tečky vynechávají (např. 21/4).
U zápisu časů se u nás projevuje vliv angličtiny, která mezi minuty a hodiny klade dvojtečku. Čeština používá místo dvojtečky obyčejnou tečku (např. 15.50), přesto se velice často setkáme se zápisem s dvojtečkou. Dvojtečka se klade až mezi minuty a sekundy, přičemž v tom případě se používá dvojtečka i pro oddělení hodin a minut (např. 11:43:02). Mezi sekundy a jejich zlomky pak píšeme desetinnou čárku (např. 0:12,96).
Při uvádění peněžních částek s haléři se číslovka zapisuje vždy s dvěma desetinnými místy, přičemž Kč se může uvádět jak před číslovkou, tak i za ní (např. 18,50 Kč, ale i Kč 18,50). Pokud se jedná o obnos bez haléřů, je možno ji zapsat buď bez desetinných míst ve tvaru 18 Kč, ve tvaru Kč 18,- či 18,- Kč.
Uvedené způsoby psaní časů, dat a obnosů odpovídají typografickým zvyklostem v českém jazyce. Pro jejich psaní totiž neplatí v České Republice žádná pravidla –
9
zápis časů, dat a finančních obnosů sice upravují normy ČSN, ty ale nejsou nikterak závazné [2]. Některé případy jsou pak ošetřeny v Pravidlech českého pravopisu [3]. Při psaní výše uvedených pravidel byly informace čerpány z těchto norem a z jiných zdrojů z těchto norem vycházejících [4].
Z výše uvedených faktů pak plyne, že je třeba vyhledat v textu nejen číslice samotné, ale i jejich kontext (oddělovače tisíců, desetinnou tečku a čárku).
2.2.2 Rozpoznávání a sdružování číslovek psaných číslicemi V zájmu zrychlení běhu programu bude rozpoznávání číslic označujících číslovky, slov a zkratek sdruženo s lexikální analýzou číslovek psaných slovy a jejich správné sdružování a formátování bude probíhat souběžně s gramatickou analýzou číslovek psaných slovy.
Pravidla pro formátování v předchozí kapitole byla uvedena pouze pro úplnost. Bez znalosti kontextu není možné určit, co která skupina číslic či slov označuje, zda čas, počet či částku a ani to není úkolem programu. Není tedy ani možné aplikovat výše uvedená pravidla a všechny číslovky jsou tak formátovány jako obyčejná čísla.
Vzhledem k velkému množství různých používaných jmen a fyzikálních veličin byl nakonec zvolen postup, kdy se rozpoznávají, označují a formátují všechny číslovky psané číslicemi. Zvláštní přístup byl zvolen pouze u nesprávně uváděných koncovek, kdy byla rozpoznávaná slova rozšířena o nejčastěji používané koncovky (jejich úplný seznam lze nalézt v kapitole 2.2) a při rozpoznávání číslovek psaných číslicemi jsou brány v potaz a dle nich měněny hodnoty mluvnických kategorií.
Jako oddělovače tisíců jsou rozpoznávány apostrofy, tečky a mezery, tedy v češtině nejčastěji používané korektní i nekorektní oddělovače. Jako oddělovač desetinné části je rozpoznávána správná čárka a nesprávná, ale přesto používaná tečka. Pokud se v souvislém úseku textu vyskytne více teček, které jsou příliš blízko či daleko od sebe než aby mohly být oddělovači tisíců, jsou považovány za oddělovače slov, jako takové označeny a každá část čísla pak zpracována zvlášť.
10
2.3 Číslovky psané slovy K dalšímu rozdělení problému na dvě samostatné části dojde u číslovek psaných slovy. Jednou částí je lexikální analýza, tedy správné rozpoznání slov, označujících číslovky, a druhou částí je analýza gramatická, určující k sobě náležející slova a spojující je do funkčních celků – složených číslovek. Složená číslovka je víceslovný útvar vyjadřující větší číslo.
2.4 Lexikální analýza Lexikální analýza, někdy též označována jako slovní, je v podstatě identifikací slov v textu. Jedná se o proces, kdy je každému slovu přiřazena značka, určující v našem případě zda se jedná o číslovku či nikoliv a další potřebné informace, například hodnotu této číslovky. Zároveň se při tomto procesu může text předem upravit pro snazší zpracování při gramatické analýze – například odstraněním přebytečných mezer či nevhodných znaků.
Pokud se číslovka skládá z více slov, píše se každé slovo samostatně (např. dvě stě nebo třicet dva). Výjimkou je spojení desítek a jednotek, kde je možno napsat celou číslovku jako jedno slovo, ve kterém číslovka označující jednotky stojí před číslovkou označující desítky a je s ní spojena spojkou a (např. dvaatřicet). K této výjimce se dále připojuje častý zlozvyk spojovat i jiné číslovky. Nejčastější je tento jev u spojování dvou slov označujících stovky (dvěstě místo dvě stě), ačkoliv je možné se s ním setkat i u jiných číslovek (stopadesát místo sto padesát).
Kdybychom měli při lexikální analýze rozpoznávat všechna takováto slova, zjistili bychom, že jejich počet je v podstatě totožný s počtem všech možných čísel a tudíž skutečně obrovský. Při velkém počtu možných slov by nám neúměrně narůstala jak implementační, tak výpočetní složitost lexikální analýzy.
Řešením tohoto problému je úprava lexikální analýzy tak, aby nezpracovávala pouze celá slova, ale i části slov. Poté se nám kupříkladu nesprávný tvar dvěstě rozpadne na dvě části – dvě a stě, analogicky to bude platit i pro správný tvar dvaatřicet. Díky tomuto kroku se nám rapidně sníží počet číslovek, které bude muset lexikální analýza muset umět rozpoznat. Tyto číslovky si pro potřeby této práce budu označovat jako
11
kořenové číslovky. Jejich seznam lze nalézt v kapitole Seznam kořenových číslovek (viz 2.4.2).
Mezi tyto číslovky je vhodné pro potřeby rozpoznávání delších složených čísel (např. sto pět) zařadit i podstatná jména sto, tisíc, milion, miliarda, bilion, biliarda, trilion, triliarda, kvadrilion a kvadriliarda, neboť určení slovních druhů těchto slov je nejasné a názory na to se různí. Kupříkladu Pravidla českého pravopisu uvádějí tisíc pouze jako podstatné jméno [3]. K dalšímu zmatení přispívá více možných skloňování těchto číslovek. Je možno je skloňovat buď jako podstatné jméno (bez sta mužů, se stem mužů), nebo mohou zůstávat nesklonné (bez sto mužů, se sto muži). Pohled na tuto problematiku se různí, přesto se lze většinou setkat s názorem, že sto, tisíc a další a všechny jejich tvary jsou číslovky. Rozhodnutí není úkolem této práce, proto jsou zde oba pohledy alespoň zmíněny. Určování slovních druhů program provádí na základě dat z Českého národního korpusu [5].
2.4.1 Morfologické značky Před uvedením seznamu kořenových číslovek je zde uveden formát značek, které bude program používat pro označování číslovek v textu. Ke každému slovu nebo části slova přiřadí lexikální analýza lemma, neboli takzvaný slovníkový tvar slova a morfologickou značku. Jedná se o pražské poziční morfologické značky [6]. Morfologická značka je řetězcem 15 znaků složeným z písmen, číslic a pomlček. Každá pozice odpovídá jedné morfologické kategorii a každé hodnotě v dané kategorii odpovídá jeden znak. Pomlčka se pak uvádí v případech, kdy se určitá kategorie u daného slovního druhu neurčuje nebo neexistuje.
Protože tato práce se zabývá pouze číslovkami základními, ve zkratce uvedu ty kategorie a jejich hodnoty, které se jich týkají. Protože se při zápisu složených číslovek používají i podstatná jména jako sto, tisíc nebo bilion, do seznamu jsou zařazeny i hodnoty vztažené k těmto číslovkám.
První pozice udává slovní druh, v našem případě tedy hlavně C – numerál (číslovka), případně N – substantivum (podstatné jméno).
12
Druhá pozice reprezentuje detailní určení slovního druhu. Možné hodnoty pro základní číslovky jsou = - číslovka psaná číslicemi, l – číslovka základní 1-4; sto a tisíc v nesubstantivním skloňování, n – číslovka základní větší nebo rovna 5, h – číslovky druhové (např. jedny) a N – substantivum (obyčejné).
Třetí pozice určuje jmenný rod. Může nabývat hodnot F – femininum (ženský rod), H – femininum nebo neutrum (ženský nebo střední rod), I – maskulinum inanimatum (rod mužský neživotný), M – maskulinum animatum (rod mužský životný), N – neutrum (střední rod), X – libovolný rod, Y – maskulinum (rod mužský, životný i neživotný) a Z – maskulinum nebo neutrum (rod mužský nebo střední).
Na čtvrté pozici najdeme hodnotu označující číslo. U číslovek mohou nastat tři varianty: S – singulár (číslo jednotné), P – plurál (číslo množné) a D – duál (pouze u 7.pádu feminin).
Pátá pozice udává pád s tím, že pokud je zde uvedeno číslo, jedná se o přímé uvedení čísla pádu a je-li zde X, pak se jedná o libovolný pád.
Šestá až čtrnáctá pozice reprezentují hodnoty, které se u číslovek neurčují nebo nedávají smysl.
Poslední pozicí je 15. pozice, určující variantu, stylový příznak nebo další doplňující informace. U číslovek může nabývat hodnot 1 – méně častá varianta slova, víceméně rovnocenná, 2 – řídká, archaická nebo knižní varianta, 6 – hovorový tvar a 8 – zkratky.
2.4.2 Seznam kořenových číslovek Tvary kořenových číslovek a klasifikace hodnot mluvnických kategorií byly čerpány z České mluvnice [7] a dat poskytnutých z morfologického slovníku vytvářeného v ÚFALu.
13
První kořenovou číslovkou je číslovka jeden. Tato číslovka má nejvíce možných tvarů, na rozdíl od většiny ostatních číslovek má totiž různé tvary pro většinu kombinací rodu a pádu. Možné tvary viz tabulka 1.
maskulinum a. maskulinum i.
femininum
neutrum
1. pád č.j.
jeden
jeden
jedna
jedno
2. pád č.j.
jednoho
jednoho
jedné / jedný*
jednoho
3. pád č.j.
jednomu
jednomu
jedné / jedný*
jednomu
4. pád č.j.
jednoho
jeden
jednu
jedno
5. pád č.j.
jeden
jeden
jedna
jedno
6. pád č.j.
jednom
jednom
jedné / jedný*
jednom
7. pád č.j.
jedním
jedním
jednou
jedním
1. pád č.mn.
jedni
jedny
jedny
jedna
2. pád č.mn.
jedněch
jedněch
jedněch
jedněch
3. pád č.mn.
jedněm
jedněm
jedněm
jedněm
4. pád č.mn.
jedny
jedny
jedny
jedna
5. pád č.mn.
jedni
jedny
jedny
jedna
6. pád č.mn.
jedněch
jedněch
jedněch
jedněch
7. pád č.mn.
jedněmi
jedněmi
jedněmi/
jedněmi
jedněma (duál) Tvary označené * jsou tvary hovorové či nespisovné Tabulka 1: Skloňování číslovky jeden
maskulinum
femininum / neutrum
1. pád
dva
dvě
2. pád
dvou
dvou
3. pád
dvěma / dvoum*
dvěma / dvoum*
4. pád
dva
dvě
5. pád
dva
dvě
6. pád
dvou
dvou
7. pád
dvěma
dvěma
Tvary označené * jsou tvary hovorové či nespisovné Tabulka 2: Skloňování číslovky dva
14
Další kořenovou číslovkou je číslovka dva. Tato číslovka už ve většině pádů nerozlišuje rod, má tedy méně tvarů. Správné skloňování viz tabulka 2.
Dalšími kořenovými číslovkami jsou číslovky tři a čtyři. Protože mají analogické tvary, uvádíme je společně v tabulce 3. Vedle korektních tvarů jsou rozpoznávány i hovorové tvary číslovky čtyři, které vzniknou ze správných tvarů přeměnou ř na r (např. čtyrem místo správného čtyřem).
Tři
čtyři
1. pád
tři
čtyři
2.pád
tří / třech
čtyř
3. pád
třem
čtyřem
4. pád
tři
čtyři
5. pád
tři
čtyři
6. pád
třech
čtyřech
7. pád
třemi / třema (duál)
čtyřmi / čtyřma (duál)
Tabulka 3: Skloňování číslovky tři
Po nich následují kořenové číslovky pět, šest, sedm, osm, devět, deset, jedenáct, dvanáct, třináct, čtrnáct, patnáct, šestnáct, sedmnáct, osmnáct, devatenáct, dvacet, třicet, čtyřicet, padesát, šedesát, sedmdesát, osmdesát a devadesát. Protože pravidla pro jejich skloňování jsou stejná, jsou zde uvedena společně. Skloňování je ukázáno na příkladu číslovek pět a osm v tabulce 4. Vedle korektních tvarů jsou rozpoznávány i méně časté, ale správné tvary číslovek deset, dvacet, třicet a čtyřicet a sice tvary 2., 3., 6. a 7. pádu, kdy je koncovka –eti nahrazena koncovkou –íti (např. desíti místo deseti). Dále jsou rozpoznávány i hovorové tvary číslovek sedm, osm, sedmnáct, osmnáct, sedmdesát a osmdesát a sice sedum, osum, vosm, vosum, sedumnáct, vosmnáct, vosumnáct, osumnáct, sedumdesát, osumdesát, vosmedesát a vosumdesát.
pět
Osm
1., 4. a 5. pád
pět
osm
2., 3., 6. a 7. pád
pěti
osmi
Tabulka 4: Skloňování slov pět a osm
15
Kořenová číslovka sto pokrývá jak číslovku sto tak i podstatné jméno sto. Vzhledem k tomu, že z důvodu nejasného rozdělení slovních druhů (více o tomto viz kapitola 2.4) mohou být konkrétní tvary označeny jako číslovka i jako podstatné jméno, jsou v tabulce uvedeny pouze tvary pro jednotlivé kombinace pádu a čísla bez uvedení, zda se jedná o číslovku či podstatné jméno (viz tabulka 5).
č. j.
č. mn.
1. pád
sto
sta / stě
2. pád
sto / sta
set / stě
3. pád
sto / stu
stům / stě
4. pád
sto
sta / stě
5. pád
sto
sta / stě
6. pád
sto / stu
stech / stě
7. pád
sto / stem
sty / stě
Tabulka 5: Skloňování slova sto
Č. j.
č. mn.
1. pád
tisíc
tisíce
2. pád
tisíce
tisíců
3. pád
tisíci
tisícům
4. pád
tisíc
tisíce
5. pád
tisíci
tisíce
6. pád
tisíci
tisících
7. pád
tisícem
tisíci
Tabulka 6: Skloňování slova tisíc
Tisíc je další kořenovou číslovkou, která zahrnuje jak číslovku tak i podstatné jméno. Jako číslovka je tisíc nesklonná a má ve všech pádech tvar tisíc. Skloňování podstatného jména tisíc je pak uvedeno v tabulce 6. Kromě těchto tvarů jsou rozpoznávány navíc i hovorové tvary 3. pádu čísla množného tisícum a 7. pádu čísla množného tisícema.
Posledními kořenovými číslovkami, které program rozpoznává, jsou podstatná jména milion, miliarda, bilion, trilion a kvadrilion. Navíc k těmto podstatným jménům 16
jsou rozpoznávána ještě slova biliarda, triliarda a kvadriliarda, kteréžto tvary sice nelze nalézt ani v Pravidlech českého pravopisu [3], ani nejsou definovány žádnými mezinárodními či národními normami, přesto se občas vyskytují. Milion, bilion, trilion a kvadrilion je možno psát i s dlouhým ó jako milión, bilión, trilión a kvadrilión, což se vztahuje i na všechny jejich dále uvedené tvary. Milion, bilion, trilion a kvadrilion se skloňují stejně, jsou zde proto uvedeny pouze tvary pro milion (viz tabulka 7.). Miliarda, biliarda, triliarda a kvadriliarda se skloňují taktéž stejně, jsou zde tedy opět uvedeny pouze tvary pro miliardu (viz tabulka 7.).
milion, č.j.
milion, č.mn.
miliarda, č.j.
miliarda, č.mn.
1. pád
milion
miliony
miliarda
miliardy
2. pád
milionu
milionů
miliardy
miliard
3. pád
milionu
milionům /
miliardě
miliardám
milionum* 4. pád
milion
miliony
miliardu
miliardy
5. pád
milione
miliony
miliardo
miliardy
6. pád
milionu
milionech
miliardě
miliardách
7. pád
milionem
miliony /
miliardou
miliardami /
milionama*
miliardama*
Tvary označené * jsou tvary hovorové či nespisovné Tabulka 7: Skloňování slov milion a miliarda
2.4.3 Návrh automatu Pro implementaci lexikální analýzy se běžně využívá automatů. Ani tento program není výjimkou a proces nahrazování slov morfologickými značkami je prováděn pomocí automatu.
Konstrukce automatu se provádí na základě souboru se seznamem rozpoznávaných slov a znaků – číslovek, spojek, interpunkčních znamének a dalších. Jedná se o jednoduchý konečný automat, kde všechny stavy, do kterých se dá dostat posloupností znaků tvořících některé ze slov ze seznamu, jsou koncové a odkazují na morfologickou značku a lemma (případně morfologické značky a lemmata) k tomuto slovu náležející.
17
Jak bylo zmíněno na začátku této kapitoly, automat nebude zpracovávat celá slova, ale libovolné části vstupu. K odlišení slov, která v sobě pouze obsahují číslovku jako podřetězec (např. šetřit) a složených číslovek (např. dvěstě), bylo třeba automatu přidat ještě jednu funkčnost – rozpoznávání složených číslovek od jiných slov. K tomuto byl zvolen přístup, kdy se soubor se seznamem slov rozšířil o znaky, které běžně oddělují slova (např. mezera, středník nebo tečka). Automat pak automaticky sdružuje výstup do celků oddělených těmito znaky. Pokud se v takovém celku vyskytují pouze číslovky a spojka a, jedná se s největší pravděpodobností o číslovku a celek je odeslán dál. Pokud se v takovém celku vyskytuje nějaká posloupnost neznámých znaků, zneplatní se celé slovo, neboť se zřejmě jedná o jiný slovní druh, obsahující číslovku jako podřetězec.
Podrobnější popis funkce a stavby automatu lze nalézt v části Implementace (viz 3.1).
2.5 Gramatická analýza Gramatickou analýzou je v tomto případě míněn proces, při kterém se korektně spojují jednotlivá slova do složených číslovek na základě daných pravidel. Během tohoto procesu program navíc určuje velikost takto vyjádřených čísel a jejich možné hodnoty mluvnických kategorií na základě číselných hodnot a hodnot mluvnických kategorií dílčích členů.
Počítá se s tím, že při zápisu číslovek se velice často chybuje. Gramatická analýza tedy bude prováděna nejen s ohledem na pravopisná a mluvnická pravidla, ale i s ohledem na nejčastější nesprávné zápisy a chyby.
Gramatická analýza navazuje na analýzu lexikální a pracuje s jejím výstupem, tedy posloupností morfologických značek.
2.5.1 Možné zápisy složených číslovek V této části je uveden popis pravidel tvorby složených číslovek. Každé součásti složených číslovek, jako jsou například desítky, stovky či tisíce, je věnován samostatný odstavec. V každé části jsou popsána pravidla pro zápis daného výrazu, stručný nástin pravidel pro skloňování a rozšířené chyby při jeho zápisu. Při tvorbě
18
této kapitoly byly pravidla pro správný zápis i příklady nesprávných zápisů čerpány z mnoha tištěných i elektronických zdrojů [3, 5, 7, 8]. 2.5.1.1 Typ dvacet jedna (desítky a jednotky) Nejmenší složené číslovky jsou složené z desítek a jednotek. Jako jedny z mála umožňují více správných způsobů zápisu. Základním způsobem je zápis, kdy nejprve uvádíme číslovku označující desítky a za ní následuje číslovka označující jednotky oddělena mezerou (např. dvacet tři). Častým neduhem je vynechávání mezer mezi desítkami a jednotkami (např. dvacettři). Skloňuje se vždy celý výraz, tedy všechny součásti složené číslovky (např. bez dvaceti tří). 2.5.1.2 Typ jednadvacet (desítky a jednotky) Druhým možným správným zápisem desítek a jednotek je zápis ve tvaru obráceném, kdy tedy stojí jednotky před desítkami a mezi ně se vkládá spojka a (např. tři a dvacet). V tomto případě se mezera psát nemusí a může nám tak vzniknout jedno slovo (např. třiadvacet). Lze se často setkat i s nesprávnými zápisy, kdy jsou mezery nahrazeny pomlčkami (např. tři-a-dvacet), méně často pak se zápisy, kdy je vynechána spojka - zde jde ale nejspíše o překlepy (např. třidvacet). Skloňuje-li se taková složená číslovka, skloňuje se pouze část označující desítky – kupříkladu bez třiadvaceti nebo o tři a dvaceti. 2.5.1.3 Typ dvě stě (násobky stovek) Složené číslovky označující celé násobky stovek se zapisují vždy tak, že nejprve se uvádí číslovka označující počet stovek a pak podstatné jméno nebo číslovka sto v příslušném tvaru, oddělena mezerou (např. dvě stě). Číslovka označující počet stovek může být jakákoliv číslovka od jedné až do devatenácti (např. jedno sto nebo devatenáct set). V psaném projevu je běžným jevem nesprávné spojování tohoto výrazu do jednoho slova (např. dvěstě). Skloňujeme vždy všechny části složené číslovky (např. bez devatenácti set mužů).
2.5.1.4 Typ dvě stě dvacet jedna (stovky, desítky a jednotky) Při skládání stovek, desítek a jednotek pak vždy stavíme stovky před výraz označující desítky a jednotky. Všechny členy takto vzniklého výrazu pak oddělujeme opět mezerou (např. dvě stě padesát dva nebo dvě stě dvaapadesát). Mezi nesprávné zápisy v tomto případě patří opět zápis s vynecháním některých nebo všech mezer 19
a pak přidávání spojky a v případě, že spojujeme pouze stovky a jednotky (např. dvě stě a dva). Při skloňování máme dvě možnosti – buď skloňovat všechny dílčí součásti složené číslovky (např. bez dvou set padesáti dvou) nebo skloňovat pouze koncovou část výrazu, tedy typicky tu, která označuje desítky a jednotky (např. bez dvě stě padesáti dvou). 2.5.1.5 Typ dva tisíce (celé násobky tisíců) Zápis číslovek označujících celé násobky tisíců je analogický zápisu stovek – nejprve je složená číslovka označující počet tisíců a po ní odděleno mezerou je podstatné jméno nebo číslovka tisíc (více viz kapitola 2.4) ve správném tvaru (např. dvě stě padesát dva tisíc nebo dvě stě padesát dva tisíce). Častým nesprávným zápisem je pak vynechání mezery (např. dvatisíce). Při skloňování pak skloňujeme jak číslovku označující počet tisíců, tak podstatné jméno tisíc (např. bez dvou set padesáti dvou tisíců, bez dvě stě padesáti dvou tisíců ale i bez dvou set padesáti dvou tisíc). 2.5.1.6 Typ dva tisíce sto dvacet dva (tisíce, stovky, desítky a jednotky) U spojení tisícovek a menších složených číslovek vždy stavíme výraz vyjadřující tisícovky před výraz vyjadřující menší číslovku a oddělujeme jej mezerou (např. dva tisíce) nebo v případě, kdy spojujeme tisícovky a jednotky, pak spojkou a (např. tisíc a jedna nebo dva tisíce a pět). Občasnou chybou je opět vypouštění mezer (např. dvatisícedvěstěpět). Při skloňování máme dvě možnosti – buď skloňovat každou část složené číslovky (např. o dvou tisících pěti stech dvaceti mužích) nebo pouze koncovou část této číslovky, typicky desítky a jednotky (např. o dva tisíce pět set dvaceti mužích). 2.5.1.7 Typ dva miliony (celé násobky větších číslovek) Při tvoření složených číslovek tvořících celé násobky větších číslovek, jako jsou například milion nebo biliarda se řídíme podobnými pravidly, jako při vytváření celých násobků tisíců – nejprve stojí výraz označující počet a po ní ve správném tvaru podstatné jméno označující větší číslovku oddělené mezerou (např. patnáct milionů). Často je v psaném projevu opět nesprávně vypuštěna mezera (např. pětmilionů). Skloňujeme vždy všechny součásti složené číslovky (např. bez pěti milionů).
20
V rámci implementace byla tato pravidla zpracována pro všechny větší číslovky až do kvadriliardy, tedy milion, miliarda, bilion, biliarda, trilion, triliarda, kvadrilion a kvadriliarda. 2.5.1.8 Typ dva miliony dva tisíce sto dvacet jedna (větší složené číslovky) Při vytváření delších složených číslovek postupujeme podobně jako u spojování tisíců a menších číslovek. Odleva postupně píšeme členy od největšího a všechny oddělujeme mezerami (např. dvě miliardy pět set tři miliony šest set sedmnáct tisíc dvacet tři). V běžném písemném projevu se opět často mezery chybně vypouštějí. Při skloňování buď skloňujeme každou dílčí část složené číslovky (např. bez dvou miliard tří set milionů dvou tisíc dvaceti pěti) nebo pouze koncovou část výrazu – typicky desítky a jednotky (např. bez dvě miliardy tři sta milionů dvě stě tisíc třiadvaceti).
V rámci implementace byla tato pravidla zpracována pouze pro číslovky složené z násobků miliard a menších, od implementace pravidel pro spojování s násobky větších číslovek bylo kvůli nízké frekvenci využití takto složitých složených číslovek ustoupeno. 2.5.1.9 Ostatní zápisy Speciální místo pak zaujímá zápis ve formě tisíc tisíců nebo milion milionů. Tento způsob lze nalézt zpravidla v historických či náboženských textech. V závislosti na kontextu se pak většinou jedná o hyperbolu nebo multiverbizaci, jen ve výjimečných případech pak o číslovku. Přesto program rozpoznává následující tvary: tisíc tisíců, tisíc milionů, milion milionů a všechny jejich tvary a kombinace až do délky pěti slov.
Posledním zmíněným spojením je pak spojování dvou různých zápisů číslovek – pomocí slov a pomocí číslic. Tento zápis se často používá při označování větších celých násobků tisíců, milionů a dalších velkých číslovek (např. 15 tisíc nebo 2,3 milionu). Nejprve se píše číslovka psaná čísly, po ní následuje mezera a číslovka či podstatné jméno označující některou z velkých číslovek. Při skloňování takto vzniklé složené číslovky skloňujeme pouze část psanou slovy a to stejně, jako by
21
před ní ležící číslovka byla zapsána také slovy - například bez 5 tisíců nebo s 23 miliony.
2.5.2 Použitý algoritmus Při tvorbě nástroje pro gramatickou analýzu se nabízí mnoho možných postupů. Vzhledem k výše nastíněným pravidlům, na kterých je jasně vidět vcelku snadná tvorba složených číslovek z menších celků, je logickým řešením takzvaný postup „zdola nahoru“.
Tento postup spočívá ve spojování menších dílčích celků dohromady podle daných pravidel. Na počátku je typicky posloupnost morfologických značek a lemmat, které se spojí do logických celků zahrnujících víc těchto značek, v tomto případě složených číslovek. V další iteraci se pak tyto složené číslovky spojují do větších složených číslovek a tento proces pokračuje, dokud je možno aplikovat nějaká pravidla.
Díky spojování „zdola nahoru“ se bude také snáze zjišťovat a vypočítávat číselná hodnota složené číslovky a možné hodnoty určovaných mluvnických kategorií. Pokud jako dílčí složené číslovky budeme používat součásti popsané v předchozí kapitole (tedy například pro číslovku dvě stě dvacet jedna jsou dílčími složenými číslovkami dvě stě a dvacet jedna, přičemž každá z nich se ještě dále rozkládá), pak číselnou hodnotu výsledné složené číslovky získáme snadno buď vzájemným vynásobením hodnot dílčích číslovek (např. u tvaru dvě stě vynásobením hodnoty číslovky dvě hodnotou číslovky sto: 2 x 100 = 200) nebo jejich součtem (např. u tvaru dvacet tři součtem hodnot číslovky dvacet a číslovky tři: 20 + 3 = 23). Podobně je tomu u hodnot mluvnických kategorií – jejich hodnota se zpravidla dá u menších složených číslovek vcelku přesně určit, zvláště končí-li na číslovky jedna, dvě, tři nebo čtyři, neboť tyto číslovky mají více různých tvarů, z nich každý lze označit pouze několika málo morfologickými značkami. Oproti tomu číslovky vyšší (např. pět nebo dvacet) mají tvarů méně a ke každému z nich náleží větší množství morfologických značek. Při skládání těchto útvarů do větších složených číslovek se pak jednoduše hodnoty mluvnických kategorií předávají dále a výsledná hodnota kategorie se získá zpravidla průnikem hodnot dílčích částí složené číslovky.
22
Vzhledem k tomu, že jednotlivá pravidla budou tvořena různým počtem členů, k očekávanému vysokému počtu těchto pravidel a v neposlední řadě také k faktu, že v souvislém bloku číslovek se může vyskytovat mnoho nezávislých složených číslovek, byl pro implementaci v zájmu rychlosti a modifikovatelnosti zvolen opět automat. Tento automat se konstruuje na základě sady pravidel, která je uložena ve zvláštním souboru a předávána programu při jeho spouštění, čímž se dosahuje snadné modifikovatelnosti chování gramatické analýzy a možnosti úpravy pravidel v případě jejich změny.
Při běhu programu se automatu předkládají v textu nalezené souvislé úseky číslovek. Ty jsou pak zpracovávány automatem v několika iteracích – zpravidla do té doby, dokud není dosaženo nejvyšších rozpoznávaných složených číslovek nebo dokud již není možné aplikovat žádná pravidla. V průběhu zpracování automatem jsou také průběžně určovány číselné hodnoty výsledných složených číslovek a hodnoty jejich mluvnických kategorií.
Podrobnosti o funkci a stavbě automatu lze nalézt v kapitole Implementace (viz 3.2). Formát zápisu pravidel a způsob jejich tvorby je podrobněji popsán v kapitole Dokumentace (viz 4.2.2).
Ilustrační příklad: Mějme složenou číslovku dva tisíce tři sta padesát. Program nejprve spojí slova do menších celků, tedy slova označující desítky a jednotky, slova označující počty stovek a stovky a slova označující počet tisíců a tisíce. Po prvním kroku tedy budou spojeny následující celky (spojení je znázorněno uzavřením do závorek): (dva tisíce) (tři sta) (padesát). V dalším kroku dojde ke spojení stovek a desítek: (dva tisíce) ((tři sta) (padesát)). V posledním kroku pak připojíme k takto vzniklé složené číslovce i část označující tisíce: ((dva tisíce) ((tři sta) (padesát))). Dále již nepokračujeme, protože již není co spojovat – celý výraz se nám sloučil do jedné složené číslovky.
23
Kapitola 3 Implementace 3.1 Lexikální analýza 3.1.1 Automat Při implementaci automatu pro lexikální analýzu se bylo nutno rozhodnout mezi dvěma možnostmi – automat zkonstruovat předem, ať již ručně nebo pomocí k tomuto účelu vytvořeného jednorázového nástroje, nebo ho konstruovat na začátku každého běhu programu. Každý z těchto přístupů má svá pro a proti. První přístup je časově méně náročný, automat se zkonstruuje pouze jednou a pak se při každém běhu již jen načítá – ať už z externího zdroje nebo přímo z kódu - a používá, přičemž čas potřebný k této operaci je prakticky nulový. Na druhou stranu je při každé změně seznamu rozpoznávaných slov potřeba znovu zkonstruovat automat pomocí jiného nástroje nebo dokonce provést zásah přímo do zdrojového kódu programu. Druhý přístup pak sice usnadňuje změnu rozpoznávaných slov, kterou stačí zanést pouze do souboru, na jehož základě se automat staví, ale tato výhoda je za cenu větší časové náročnosti běhu programu.
K usnadnění modifikovatelnosti a aktualizovatelnosti programu byl nakonec zvolen druhý přístup, kdy se automat pro lexikální analýzu konstruuje při každém běhu programu na základě souboru se seznamem rozpoznávaných posloupností znaků a k nim náležejících lemmat a morfologických značek. Formát tohoto souboru je blíže popsán v kapitole Dokumentace. V průběhu implementace se ani nevyplnily obavy z předpokládané časové náročnosti této operace – ve srovnání s časem potřebným ke zpracování rozumně objemného vzorku zkušebních dat je čas spotřebovaný na tvorbu automatu zanedbatelný, a zvolený přístup se tak ukázal jako lepší.
Samotný automat je jednoduchý konečný automat. Cestu z počátečního stavu do koncového vždy tvoří jedno rozpoznávané slovo (tomuto slovu ovšem může náležet více morfologických značek). V koncovém stavu jsou pak uloženy návratové 24
hodnoty, v tomto případě lemmata, morfologické značky a další doplňující informace, jejichž potřeba vyplynula až v průběhu implementace dalších částí programu (více viz 3.2). Automat je koncipován co nejjednodušeji, proto v něm nejsou žádné přechody zpět kromě těch z koncových stavů – připomíná tak svou stavbou spíše strom (viz Obrázek 1).
Obrázek 1: Stavba automatu pro lexikální analýzu
3.1.2 Podrobný popis implementace stavby automatu Díky neexistenci vícerozměrných polí nebo objektů v Perlu byl nakonec automat realizován formou pole ukazatelů na jednotlivé stavy, přičemž prvek s indexem 0 je počáteční stav. Každý stav je pak pole dvou ukazatelů, kde první je ukazatelem na asociativní pole, které obsahuje jako klíče všechny znaky, pomocí kterých lze přejít do dalších stavů a jako hodnoty pak indexy těchto stavů v primárním poli automatu. Druhý ukazatel ukazuje na pole odkazů na struktury s uloženým lemmatem, morfologickou značkou a dalšími potřebnými hodnotami. V případě, že je toto pole prázdné, jedná se o nekoncový stav – tento fakt také během implementace sloužil k rozpoznání koncových stavů, nebylo tak třeba je jinak odlišovat.
Stavba automatu se odehrává souběžně se čtením souboru se seznamem rozpoznávaných posloupností znaků a k nim příslušejících lemmat a morfologických značek. Specifikaci formátu tohoto souboru je možno nalézt v kapitole Dokumentace (viz 4.2.1).
25
Při stavbě automatu program ze souboru průběžně načítá data. Pokud jsou načtená data informacemi o lemmatech, morfologických značkách nebo hodnotách rozpoznávaných znaků, program jejich hodnoty uloží do pomocných proměnných. V této fázi také vytváří v rámci zrychlení běhu pozdějších součástí neterminály náležející k jednotlivým slovům. Tyto neterminály slouží pro účely gramatické analýzy a jejich formát, použití i tvorba jsou blíže popsány v kapitole věnované implementaci gramatické analýzy (viz 3.2).
Pokud program načte některou z posloupností znaků, které by měl rozpoznávat, projde automatem z počátečního stavu postupně do dalších stavů pomocí přechodů podle jednotlivých znaků z dané posloupnosti. Pokud některé stavy ještě neexistují, jsou v této fázi vytvořeny. Ve chvíli, kdy se program dostane do koncového stavu, uloží do něj z pomocných proměnných informace o lemmatu, morfologické značce, numerické hodnotě a neterminálu.
3.1.3 Vlastní lexikální analýza Lexikální analýza při svém běhu využívá vytvořený automat. S jeho pomocí prochází vstup a převádí známé řetězce na ekvivalentní morfologické značky a lemma. Slova, která neoznačují číslovky pak zřetězuje a označuje jako nečíslovky – tento název pro podobné úseky textu je používán i v dalších kapitolách.
Ilustrační příklad: Mějme jako vstup větu Byli tam tři. Program zpracovává větu od začátku. Protože žádné z prvních dvou slov není číslovkou a ani v sobě neobsahuje část žádného tvaru některé z číslovek, budou tato slova postupně označena jako nečíslovky a odložena, přičemž program je spojí do jednoho souvislého úseku textu. Až poté, co program narazí na slovo tři, rozpozná v něm tvar číslovky tři a označí ho příslušným lemmatem a morfologickými značkami.
Původně bylo zamýšleno, že při lexikální analýze se její výstup bude ukládat do fronty v paměti, odkud si jej po jejím skončení bude odebírat pro svůj běh analýza gramatická. Ukázalo se, že v Perlu není tento přístup vhodný – vkládání položek do dlouhých polí a jejich udržování má velkou výpočetní i časovou složitost a s rostoucí délkou textu vedlo k exponenciálnímu prodlužování doby běhu. Musel se
26
tak hledat jiný způsob. Nakonec byl zvolen přístup s meziuložením, kdy se výstup z lexikální analýzy zapisuje do dočasného souboru na pevném disku. Odtud si jej při svém běhu odebírá analýza gramatická. Tento přístup přinesl zlepšení výpočetní složitosti na lineární, a tedy i výrazné zkrácení doby běhu programu.
3.1.4 Podrobný popis implementace lexikální analýzy Při svém běhu lexikální analýza bere vstup po znacích a zpracovává jej pomocí automatu. Dokud je možno v automatu přecházet pomocí získaných znaků do jiných stavů, program tak činí a průběžně si ukládá do zásobníku informace o stavech, kterými prošel. Ve chvíli, kdy již nemůže dál a je v koncovém stavu, pošle na výstup příslušné informace o daném slově nebo odkaz na tyto informace – pro ukládání do souboru je vhodnější ukládat pouze číslo stavu (které se v jednom běhu programu již nemůže změnit) a nikoliv všechny informace, které, zvláště u některých tvarů s mnoha možnými morfologickými značkami, mohou býti rozsáhlé. Navíc přístup na známou adresu v poli se provádí v konstantním čase, nedojde tak ani ke zpomalení běhu programu. Pokud není v koncovém stavu, vrací se podle zásobníku prošlých stavů, dokud nenajde koncový stav. Pokud takový nenajde, pošle potřebný počet znaků ze vstupu na výstup jako nerozpoznané.
Vzhledem k tomu, že při základním procházení program označí jako číslovky i části slov, které číslovkami nejsou (např. šetřit), lexikální analýza zajišťuje i správné označení těchto součástí jako nerozpoznaných. Spojení s lexikální analýzou bylo dosaženo tak, že výstup není posílán přímo do souboru, ale nejprve ukládán do paměti. Když program narazí na nějaký oddělovač slov (např. mezeru, čárku, tečku, pomlčku a další podobné znaky), zkontroluje obsah zásobníku v paměti. Pokud obsahuje pouze rozpoznaná slova, pošle jej v nezměněné podobě na výstup. Jestliže v něm jsou nějaké nerozpoznané úseky, je celý označen jako nerozpoznaný.
Ilustrační příklad: Mějme větu Ušetřil jednadvacet korun. Program první tři znaky (Uše) nerozpozná, označí jako nečíslovku a odloží na zásobník. Poté zpracuje další tři znaky (tři) a rozpozná v nich tvar číslovky tři, jemuž odpovídající lemma a morfologické značky taktéž odloží na zásobník. Další znak (l) bude opět označen jako nečíslovka a odložen na zásobník. Protože poté program narazí na oddělovač slov, zkontroluje obsah
27
zásobníku. Zjistí, že se v něm vyskytují nečíslovky, a tak celý obsah zřetězí, označí jako nečíslovku a odešle na výstup. U dalšího slova (jednadvacet) program nejprve rozpozná prvních pět znaků (jedna) jako tvar číslovky jeden a příslušné lemma a morfologické značky odloží na zásobník. Poté rozpozná i zbytek slova, tentokrát jako tvar číslovky dvacet a odloží odpovídající lemma a morfologické značky na zásobník. Protože dalším znakem je opět oddělovač slov, program překontroluje obsah zásobníku. Po zjištění, že v něm nejsou žádné nečíslovky, se obsah v nezměněné formě odešle na výstup.
3.2 Gramatická analýza 3.2.1 Automat Z důvodů nastíněných v části 2.5.2 byl pro gramatickou analýzu textu využit opět automat. Po zkušenostech s implementací a konstrukcí automatu pro analýzu lexikální přímo za běhu byla stejná implementace, tedy konstrukce automatu při běhu programu na základě souboru pravidel použita i pro tento automat. Navíc toto opět přináší snadnou upravovatelnost pravidel v případě nutnosti takových úprav. Tento přístup také usnadní možnou úpravu programu na rozpoznávání jiných druhů číslovek, například číslovek řadových nebo zlomků.
Automat je opět jednoduchý konečný automat, svou stavbou analogický s automatem pro lexikální analýzu (viz. 3.1.1). Spouští se nad výstupem lexikální analýzy. Jediným rozdílem, kromě výstupu tohoto automatu, jsou přechody. Přechody se nemůžou dít na základě znaků, musí to být na základě kompletních informací o každém slově. Na druhou stranu při použití kompletních informací o každém slově, tedy lemmatu a morfologické značky, nám vyvstávají jiné problémy. Kupříkladu mnohoznačnost některých tvarů, které se dají označit několika různými morfologickými značkami, která v důsledku vede k výraznému nárůstu počtu pravidel i zbytečným komplikacím při implementaci běhu gramatické analýzy. Proto se jako vhodné ukázalo zavedení neterminálů – posloupnosti znaků nesoucí podstatné informace o daném slově.
Dalším krokem pak bylo určení toho, co to jsou podstatné informace. Je vcelku jasné, že potřebujeme znát pád, rod a číslo daného slova. V průběhu implementace pravidel dále vyplynula potřeba znát 15. znak morfologické značky, a sice příznak označující 28
hovorové či archaické tvary číslovek. Poslední informací, kterou je potřeba znát, je lemma. Ve skutečnosti však nepotřebujeme znát konkrétní lemma – například číslovky označující násobky desítek (dvacet až devadesát) mají všechny stejný způsob skloňování (1., 4. a 5. pád mají stejný tvar, 2., 3., 6. a 7. pád taktéž) a všechny se v zápise složených číslovek chovají ekvivalentně (objevují se na stejných místech ve stejných tvarech nezávisle na konkrétní číslovce). Pro účely gramatické analýzy tak můžeme pro všechny použít ekvivalentní neterminály, které by se tedy daly považovat za vzory.
Skupiny číslovek, které se dají takto sdružit jsou: •
tři a čtyři
•
pět, šest, sedm, osm, devět
•
deset, jedenáct, dvanáct, třináct, čtrnáct, patnáct, šestnáct, sedmnáct, osmnáct, devatenáct
•
dvacet, třicet, čtyřicet, padesát, šedesát, sedmdesát, osmdesát, devadesát
Ostatní číslovky se chovají každá jinak, nebo v pravidlech stojí na různých místech, nelze je proto sdružovat.
Neterminály pro speciální znaky či slova (např. a, mezera či dvojtečka) musí nést jedinou informaci, a sice o který konkrétní speciální znak se jedná.
Neterminály pro složené číslovky již mohou mít jakýkoliv tvar, jediným požadavkem je, aby každý neterminál byl tvořen unikátní posloupností znaků. Jinak je jejich tvar zcela v kompetenci autora pravidel.
Podrobnější informace o tvarech neterminálů lze nalézt v kapitole Dokumentace (viz 4.2.2).
3.2.2 Podrobný popis implementace stavby automatu Implementace automatu pro gramatickou analýzu je v podstatě stejná, jako u automatu pro lexikální analýzu. Automat samotný je opět realizován formou pole odkazů na další strukturu, která obsahuje jak údaje o neterminálech, kterými se přechází do dalších stavů ve formě asociativního pole, tak údaje potřebné pro samotnou gramatickou analýzu. Koncové stavy jsou od nekoncových stavů 29
odlišeny tak, že koncové stavy obsahují návratovou hodnotu (jedná se o neterminál a další doplňující informace), zatímco nekoncové stavy mají tyto proměnné prázdné. Počátečním stavem je opět stav s indexem 0.
Tvorba probíhá souběžně se čtením souboru obsahujícího definice pravidel a návratové hodnoty (více o jeho formátu lze nalézt v kapitole 4.2.2). Program vždy po načtení pravidla prochází automatem od počátečního stavu postupně podle neterminálů do dalších stavů. Pokud odpovídající stavy neexistují, jsou v průběhu procházení vytvořeny. Do koncového stavu pak uloží odpovídající návratové a pomocné hodnoty.
3.2.3 Samotná gramatická analýza Gramatická analýza se provádí s pomocí automatu vytvořeného při běhu programu. Jejím vstupem je výstup lexikální analýzy, tedy posloupnost označkovaných číslovek, speciálních znaků a nerozpoznaných úseků textu. Automat zpracovává tento vstup na složené číslovky a při tomto procesu určuje i jejich hodnoty a hodnoty mluvnických kategorií.
Výstupem gramatické analýzy je tedy posloupnost složených číslovek s příslušnými informacemi a nečíslovek.
Při návrhu implementace byla zvažována možnost spojit gramatickou analýzu s analýzou lexikální a provádět obě v rámci jednoho složitého procesu. Toto by nejspíše přineslo mírné zrychlení programu. Nakonec je gramatická analýza prováděna nezávisle na analýze lexikální. Hlavními důvody rozdělení je udržení snadné modifikovatelnosti programu, ať již při změně pravidel pro číslovky nebo při úpravách programu pro jiné druhy číslovek, výrazně snazší implementace, údržba a čitelnost takovéhoto programu. V době tohoto rozhodnutí ještě nebyla známa vhodnost předávání výstupu mezi lexikální a gramatickou analýzou ve formě souboru (viz 3.1.3), v důsledku čehož je časová ztráta výraznější, přesto se stále jedná o krátké navýšení ve srovnání s časem běhu obou procesů. Navíc se předpokládá, že se program rozpoznávání číslovek bude používat jako dodatečný po morfologické analýze, která rozpoznávání kořenových číslovek také dělá.
30
Hlavní působení na výsledek a spolehlivost gramatické analýzy mají navržená pravidla. Více o jejich formátu a tvorbě je možno se dočíst v kapitole Dokumentace (viz 4.2.2). Pravidla byla tvořena podle pravidel popsaných v kapitole Možné zápisy složených číslovek (viz 2.5.1).
3.2.4 Podrobný popis implementace V průběhu gramatické analýzy je postupně načítán výstup analýzy lexikální, tedy posloupnost řetězců, ke kterým jsou přiřazena čísla stavů či jsou označeny jako nerozpoznané (viz 3.1.4). Gramatická analýza načítá vstup do zásobníku, dokud nenarazí na nečíslovku. V tu chvíli zásobník předá ke zpracování pomocí automatu.
Toto zpracování probíhá v iteracích. V každé iteraci jsou nahrazeny podle pravidel některé skupiny neterminálů jinými terminály nebo neterminály. V případě, že již nelze aplikovat žádná pravidla, je běh ukončen a vypsán výstup, tedy konečná posloupnost neterminálů, upravená do uživateli srozumitelné formy. Více o tomto procesu a ilustrační příklad je možno nalézt v kapitole 2.5.2.
V každé iteraci je postupně zpracovávána posloupnost neterminálů, které jsou průběžně získávány z automatu pro lexikální analýzu na základě čísel stavů. Dokud je možno přecházet do dalších stavů automatu pomocí neterminálů, pokračuje se v zpracovávání automatem a prošlé stavy i neterminály použité k přechodu jsou ukládány do paměti pro účely pozdějšího návratu. Pokud již není přechod do dalšího stavu možný a automat se nachází v koncovém stavu, je do zásobníku odeslán příslušný neterminál a další potřebné informace. Pokud se nenachází v koncovém stavu, zkouší program použít další neterminály pro dané slovo - neboť některá slova mohou mít neterminálů více. Pokud ani pomocí jiných neterminálů není možno dostat se do koncového stavu, dochází k návratu pomocí zapamatovaných stavů a přechodů.
V průběhu ukládání ještě tento proces zajišťuje výpočet hodnoty složené číslovky. U každého pravidla je uvedeno, zdali se mají členy sčítat či násobit. Pokud pak dochází ke spojování dílčích členů do složené číslovky, program proběhne pomocí iterátoru všechny spojované členy, spojí řetězce vyjadřující tyto členy do jednoho dlouhého označujícího celou složenou číslovku a sčítá či násobí hodnoty těchto
31
členů, přičemž vynechává speciální znaky (např. mezera, čárka, a a další), které jsou odlišeny hodnotou -1.
Ilustrační příklad: Mějme opět složenou číslovku dva tisíce tři sta padesát. Gramatická analýza dostane již ke každému slovu kromě lemmatu a morfologických značek i jeho hodnotu – (dva, 2) (tisíce, 1000) (tři, 3) (sta, 100) (padesát, 50). Po prvním kroku tedy budou spojeny následující celky a budou jim přiřazeny hodnoty na základě dílčích hodnot: (dva tisíce, 2000) (tři sta, 300) (padesát, 50). V dalším kroku dojde ke spojení stovek a desítek a opětovnému sečtení dílčích hodnot: (dva tisíce, 2000) ((tři sta) (padesát), 350). V posledním kroku pak připojíme k takto vzniklé složené číslovce i část označující tisíce a opět sečteme dílčí hodnoty: ((dva tisíce) ((tři sta) (padesát)), 2350).
32
Kapitola 4 Dokumentace 4.1 Uživatelská dokumentace 4.1.1 Systémové požadavky Pro spuštění programu je třeba mít nainstalovaný interpret Perlu. Tento je obsažen ve většině Linuxových a Unixových distribucí, pro Windows je pak potřeba si některý interpret naistalovat (na přiloženém CD je k dispozici ActivePerl).
Program sám sestává ze 3 souborů – k správnému běhu jsou potřeba všechny tři. •
cislovky.pl - samotný skript
•
tvary.num – soubor s rozpoznávanými tvary číslovek a oddělovači slov (podrobnější popis v kapitole 4.2.1)
•
pravidla.num – soubor s pravidly, podle kterých sdružuje gramatická analýza složené číslovky (podrobnější popis v kapitole 4.2.2)
Pokud některý ze souborů chybí, program vydá místo výstupu chybové hlášení.
Je potřeba, aby výše uvedené soubory byly v kódování používaném na daném operačním systému z důvodů správného převodu znaků s diakritikou. Na přiloženém CD jsou připraveny verze v různých kódováních pro různé operační systémy, jmenovitě v kódováních ISO 8859-2 a Windows-1250.
4.1.2 Spouštění Program se spouští jako běžný Perlovský skript, tedy pomocí příkazu perl cislovky.pl. Vstup a výstup si bere ze standardního vstupu a výstupu, oboje je možno klasicky dále zpracovávat pomocí rour nebo přesměrovat z/do souboru.
4.1.3 Vstup Program si vezme data ke zpracování ze standardního vstupu. Program zpracovává holý text. Vstup musí být ve stejném kódování, v jakém jsou uloženy soubory
33
tvary.num a pravidla.num (tedy v kódování používaném na daném operačním systému).
4.1.4 Výstup Program vypíše svůj výstup na standardní výstup. Program vypisuje souvisle veškerý nerozpoznaný text ve stejném tvaru, v jakém ho obdržel ze vstupu. Pokud je v textu číslovka, program ji vypíše na nový řádek ve formátu:
číslovka<MMn>hodnota číslovky<MMt>příslušný tag
Příklad výstupu: Byli tam všichni kromě dvaceti tří<MMn>23<MMt>Cn-P2----------<MMt>Cn-P3---------<MMt>Cn-P6---------<MMt>-Cn-P7---------mužů, kteří museli odjet.
4.2 Programátorská dokumentace 4.2.1 Formát souboru s tvary číslovek V souboru tvary.num se nacházejí všechny tvary číslovek, které program rozpoznává spolu s odpovídajícími lemmaty, morfologickými značkami a hodnotami. V souboru se může používat následujících tagů: •
- za touto značkou následuje lemma, které platí pro všechna slova až do následující značky
•
- za touto značkou následuje morfologická značka, která platí pro všechna slova až do následující značky
•
- za touto značkou je tvar slova, který odpovídá před ním uvedenému lemmatu, morfologické značce a hodnotě
•
- za touto značkou je číselná hodnota, která platí pro všechna slova až do následujícíc značky
Jakýkoliv text, který je na samostatném řádku a není uvozen žádnou značkou, je brán jako poznámka a nemá žádný vliv na množinu rozpoznávaných slov.
34
Pomocné znaky, oddělovače slov a další slova, která se sice mají pro účely spojování číslovek rozpoznávat, ale nemají mít vliv ani na hodnotu, ani na výsledné morfologické značky, se označují pomocí hodnoty –1. Pádové koncovky a další slova, která se mají pro účely spojování rozpoznávat a mají mít vliv na výsledné morfologické značky, ale ne na výslednou hodnotu, se označují pomocí hodnoty 0.
Ilustrační příklad dvanáct12 Cn-P7----------dvanácti Cn-P6----------dvanácti Cn-P3----------dvanácti Cn-P2----------dvanácti Cn-S5----------dvanáct Cn-S4----------dvanáct Cn-S1----------dvanáct Poznámka 1 třináct13 Cn-P7----------třinácti Poznámka 2 Cn-P6----------třinácti Cn-P3----------třinácti Cn-P2----------třinácti Cn-S5----------třináct Cn-S4----------třináct Cn-S1----------třináct
4.2.2 Formát souboru s pravidly pro gramatickou analýzu V souboru pravidla.num se nachází soubor pravidel, podle kterých se spojují složené číslovky v průběhu gramatické analýzy. Formát je podobný souboru s tvary číslovek, opět používá formu uvozování hodnot pomocí tagů: •
- udává neterminál, kterým se mají nahradit množiny neterminálů odpovídající některému z pravidel. Platí pro všechna pravidla až po další značku
35
•
- za touto značkou následuje pravidlo. Pravidlo sestává z řetězce neterminálů oddělených znakem #.
•
- za touto značkou následuje informace o operátoru, používaném při výpočtu hodnoty výsledné složené číslovky. Možné hodnoty jsou * nebo +. Operátor platí pro všechna pravidla až do další značky .
•
- tato značka uvozuje informaci o tom, jaké morfologické značky se mají přiřadit výsledné číslovce. Morfologické značky se oddělují pomocí středníku (;). Platí pro všechna pravidla až do další značky
Na počátku jsou všem číslovkám přiřazeny následující neterminály: •
oddělujícím znakům, pomocným slovům a všem rozpoznávaným útvarům s hodnotou 0 a menší je přiřazen neterminál Sx, kde x je nahrazeno samotným znakem (např. S. pro tečku, S; pro středník či Sa pro a).
•
číslovkám zapsaným číslicemi je jako jednotný neterminál přiřazeno DIGIT
•
číslovkám zapsaným slovy je přiřazen neterminál ve tvaru Txrčpz, kde rčpz jsou znaky z morfologické značky označující rod, číslo, pád a pak poslední znak morfologické značky určující variantu, stylový příznak nebo další doplňující informace. Místo x je pak dosazen znak určující o jakou konkrétní číslovku se jedná, přičemž číslovky jsou pro potřeby pravidel sdruženy do skupin se stejným chováním (viz 3.2.1). Tyto skupiny mají následující označení: 1 – tvary číslovky jeden, 2 – tvary číslovky dva, 3 – tvary číslovek tři a čtyři, j – tvary číslovek pět až devět, D – tvary číslovek deset až devatenáct, d – tvary číslovek dvacet až devadesát, s – tvary číslovky a podstatného jména sto, t – tvary číslovky a podstatného jména tisíc, m – pro tvary číslovky a podstatného jména milion, M – pro tvary číslovky a podstatného jména miliarda, b – pro tvary číslovky a podstatného jména bilion a B – pro tvary číslovky a podstatného jména biliarda
Ilustrační příklad Nsto1/4/5*Cn-P1----------;Cn-P4----------;Cn-P5---------T1NS5-#S #TsNS5T2HP1-#S #TsXP72 T3XP5-#S #TsNP5-
36
Tj-S5-#S #TsXP71 TD-S5-#S #TsXP71 TD-S56#S #TsXP71
Jedná se o pravidlo spojující slovo označující počet stovek a stovky do jednoho celku, který může být v 1., 4. nebo 5. pádě (např. dvě stě). Vzniklý neterminál je proto pojmenován jako Nsto1/4/5 – pojmenování se uvádí uvozené tagem . Při spojování těchto dvou slov se hodnota vzniklé složené číslovky získá vynásobením dílčích hodnot, proto je jako operátor za teagem uveden operátor násobení. Dále jsou uvedeny morfologické značky pro vzniklý výraz uvozené tagem .
Dále je seznam pravidel, z nichž každé je uvozeno tagem . První pravidlo pokrývá případ jedno sto – neterminál T1NS5- zastupuje slovo jedno, „S „ pak zastupuje mezeru a TsNS5- je neterminál pro slovo sto. Znak # odděluje v pravidle jednotlivé neterminály.
Další pravidla jsou po řadě následující případy: dvě stě, tři sta – čtyři sta, pět set – devět set a jedenáct set – devatenáct set.
37
Kapitola 5 Závěr 5.1 Shrnutí Aplikace je schopna rozpoznávat slovy i číslicemi zapsané číslovky a správně je spojovat do celků. Ukázalo se, že celý systém zápisu číslovek se dá rozdělit a specifikovat podle vcelku jednoznačných pravidel a díky tomu je program schopen podávat správný výstup i při ne zcela korektním nebo hovorovém stylu zápisu.
Vzhledem k tomu, že se nejedná o statistické metody a pravidla pro spojování číslovek jsou v podstatě deterministická, nebylo použito žádné měření úspěšnosti běžně používané právě u statistických metod. Úspěšnost programu a kvalita výstupu byla kontrolována na souboru 155 předem zpracovaných větách s označenými číslovkami, 500 větách z Českého národního korpusu [5] a několika stech větách posbíraných z různých medií a publikací. Tyto jsou spolu s odpovídajícími výstupy k nahlédnutí na přiloženém CD.
Program dokázal správně označit takřka sto procent vyskytnuvších se číslovek. Selhává pouze na místech, kde je zápis už více nekorektní (např. spojování neslučitelných tvarů číslovek či překlepy dvě stům, osmaadvacet). Také je omezen svým bezkontextovým pojetím. Není tak schopen rozpoznat nesprávně oddělené nebo dokonce neoddělené celky, které k sobě nenáleží - například zápis „devět set devadesát devět set devadesát pět tisíc“, který byl zamýšlen ve významu „990, 995, 1000“ program rozpozná jako „990, 995 000“. Správné rozpoznání takových případů by však již vyžadovalo širší znalost kontextu a výskyt takovýchto anomálií v textu je velice malý.
Větší překážkou se neznalost kontextu ukázala být překvapivě u rozpoznávání číslovek zapsaných číslicemi. Tečka totiž může sloužit jako oddělovač tisíců, desetinná tečka i jako oddělovač slov. Tentýž zápis 538.107 může v závislosti na kontextu být korektním zápisem čísla pět set třicet osm tisíc sto sedm, číslem pět 38
set třicet osm celých sto sedm tisícin s nesprávným oddělovačem desetin či dokonce dvěma nezávislými čísly pět set třicet osm a sto sedm. Odhalení správného výkladu není často jasné ani při znalosti kontextu či významu věty.
5.2 Možnosti dalšího vývoje Program byl již během vývoje koncipován tak, aby byl co nejsnáze rozšiřitelný i na další druhy číslovek.
Rozšíření na řadové, druhové či násobné číslovky by si tak vyžádalo pouze přidání příslušných tvarů číslovek do sady rozpoznávaných slov a úpravu pravidel, která jsou naštěstí až na drobné odchylky prakticky totožná s pravidly pro zápis základních číslovek.
Rozšíření o zlomky či desetinná čísla by si vyžádalo úpravy větší, protože už se řídí poněkud odlišnými pravidly a program ve své stávající podobě ani nepodporuje operátory, které by byly potřebné pro správné určení numerické hodnoty takových složených číslovek.
39
Příloha A Obsah přiloženého CD Složka ActivePerl obsahuje instalační soubory freewarového interpretu perlu ActivePerl pro operační systém Windows a jeho licenční ujednání.
Složka Windows-1250 obsahuje skript a všechny potřebné soubory pro jeho spuštění v kódování Windows-1250. V podložce testy lze najít sadu souborů využívaných při testování a jim odpovídající výstup v tomtéž kódování.
Složka ISO-8859-2 obsahuje skript a všechny potřebné soubory pro jeho spuštění v kódování ISO-8859-2. V podložce testy lze najít sadu souborů využívaných při testování a jim odpovídající výstup v tomtéž kódování.
Složka Dokumetace obsahuje dokumentaci k programu ve formátu HTML.
40
Příloha B Příklad vstupu a výstupu Vstup Podíval jsem se na hodinky , bylo za deset devět . Určitě neměří víc než sto padesát pět centimetrů . Obrazovka ukazovala jedenáct hodin čtyřicet šest minut .
Výstup Podíval jsem se na hodinky , bylo za deset<MMn>10<MMt>Cn-S5----------<MMt>Cn-S4---------<MMt>Cn-S1----------
devět<MMn>9<MMt>Cn-S5----------<MMt>Cn-S4---------<MMt>Cn-S1---------. Určitě neměří víc než sto padesát pět<MMn>155<MMt>Cn-P1----------<MMt>Cn-P4---------<MMt>Cn-P5---------centimetrů . Obrazovka ukazovala jedenáct<MMn>11<MMt>Cn-S5----------<MMt>Cn-S4---------<MMt>Cn-S1---------hodin čtyřicet šest<MMn>46<MMt>Cn-P1----------<MMt>Cn-P4---------<MMt>Cn-P5---------minut .
41
Literatura [1]
Ptáček, Jan: Diplomová práce: Generování vět z tektogramatických stromů Pražského závislostního korpusu, Univerzita Karlova v Praze, MFF, Praha, 2005, str.10-12, 22-26.
[2]
Český
normalizační
institut:
ČSN
01
6910
Úprava
písemností
zpracovaných textovými editory nebo psaných strojem, Český normalizační institut, Praha, 2002, str.12-13. [3]
Kolektiv autorů: Pravidla českého pravopisu, Fin, Olomouc, 1996.
[4]
Behún, Dalibor: Hříchy pro šíleného korektora - člověk versus psaní číslovek, World Wide Web, http://interval.cz/clanky/hrichy-pro-silenehokorektora-clovek-versus-psani-cislovek/.
[5]
Český národní korpus - korpusy SYN2000, SYN2005 a SYN2006pub, Ústav Českého národního korpusu FF UK, Praha, 2005, http://ucnk.ff.cuni.cz
[6]
Hajič, Jan: Disambiguation of rich inflection (Computational Morphology of Czech), Karolinum, Praha, 2004, str.32-88.
[7]
Havránek, Bohuslav; Jedlička, Alois: Česká mluvnice, Státní pedagogické nakladatelství, Praha, 1986, st.212-218.
[8]
Jazyková poradna Ústavu pro jazyk český AV ČR: Často kladené otázky, World
Wide
http://www.ujc.cas.cz/oddeleni/index.php?page=poradna
42
Web,
