Automatické dělení slov na konci řádku

Toto je (mírně upravený) výňatek z mojí bakalářské práce.

Podle Sojky (1, s. 183–184) má být algoritmus určený k dělení slov na konci řádku

• přesný, tzn. nesmí slova dělit chybně,
• úplný, tzn. musí ve slově najít všechny možné dělicí body,
• rozšiřitelný, tzn. musí umožňovat specifikaci výjimek,
• adaptabilní, tzn. musí umožňovat jednoduchou úpravu při změně pravidel dělení,
• parametrizovatelný, tzn. musí umožňovat změnu chování podle způsobu užití,
• málo paměťově náročný.

Málokterý algoritmus však všechny tyto podmínky splňuje. Pravidlová řešení, jako je například algoritmus vytvořený nakladatelstvím Academia v roce 1987, nebývají adaptabilní a bývají jazykově závislá. Podle Lianga také bývají náchylná k chybám a zřídka pokrývají všechny možné případy dělení (2, s. 2). Slovníková řešení, tj. systémy pracující se seznamem předem rozdělených slov, jsou jazykově nezávislá. Anglický dělicí slovník lze jednoduše nahradit slovníkem německým, přičemž není třeba nijak měnit samotný dělicí algoritmus. Slovníková řešení jsou ale paměťově náročná a nejsou tedy (kvůli velkému množství různých slovních tvarů) vhodná pro flektivní jazyky, jako je třeba čeština (2, s. 2; 3, s. 139). Udržování a neustálé aktualizování seznamů předem rozdělených slov je navíc sisyfovská práce.

Všechny výše zmíněné požadavky splňuje tzv. Liangův algoritmus, viz dizertační práci F. M. Lianga (2). Ten funguje podobným způsobem jako slovníkové metody dělení slov v tom ohledu, že dělicí body nehledá (nepočítá) až v době spuštění, jak to dělají pravidlové algoritmy, ale pracuje s předem připravenými daty obsahujícími i nformace o tom, kde dělicí body leží. Nepracuje ovšem přímo se seznamem rozdělených slov, ale se seznamem tzv. vzorů (4, s. 242). Stejně jako slovníkové metody Liangův algoritmus sám o sobě jazykově závislý není. Podklady pro dělení (tj. vzory) ovšem jazykově závislé jsou (5, s. 449).

Vzory jsou řetězce písmen — podslova (podřetězce) dané množiny slov —, v nichž je čísly 0 až 9 vyznačeno, kde leží a kde neleží dělicí body. Lichá čísla značí dělicí bod a sudá čísla zákaz dělení, přičemž hodnota čísla určuje váhu daného vzoru. (3, s. 139) Vzor u1m tedy značí, že slova mají být dělena mezi grafémy u a m, například pu-ma. (Ve vzorech se mohou vyskytovat i  speciální znaky, například tečkou bývají značeny hranice slov.) Vzory jsou generovány z rozsáhlého seznamu předem rozdělených slov (7, s. 10). Tento seznam je opakovaně procházen a podle určitého pravidla jsou vybírány možné vzory — v lichých průchodech jsou vybíráni kandidáti na vzory dělící a v sudých průchodech kandidáti na vzory dělení zabraňující (6, s. 4; 8, s. 9). Pro každého kandidáta na vzor je spočteno, kolikrát — spolu s ostatními již zvolenými vzory — dělí správně a kolikrát dělí špatně. Pokud odstraňuje více chyb než jich tvoří, je vzor přijat. V podstatě jde o strojové učení.

Při dělení jsou na dělené slovo postupně aplikovány vzory odpovídající všem jeho podslovům. Vzory se přebíjejí — pro dělení jsou vybrány kombinace vzorů s nejvyšším součtem dělicích bodů, viz diagram níže. Máme-li vzory ne1, ne2j1, e3j2a a 1ný můžeme slovo nejasný ohodnotit těmito třemi způsoby: ne1jas1ný, ne2j1as1ný a ne3j2as1ný. Nejvyšší součet má třetí ohodnocení, slovo nejasný tedy bude děleno jako ne-jas-ný.

.h y p h e n a t i o n.     dělené slovo

          1n a              vzory
              1t i o
           n2a t
                2i o
       h e2n
.h y3p h
       h e n a4
       h e n5a t

.h0y3p0h0e2n5a4t2i0o0n.     vítězný vzor

 h y-p h e n-a t i o n      slovo rozdělené vítězným vzorem

1. SOJKA, Petr. Slovenské vzory dělení: čas pro změnu? In: Zpravodaj Československého sdružení uživatelů TEXu. Brno: Československé sdružení uživatelů TEXu, 2004, roč. 14, č. 3–4, s. 183–189. ISSN 1211 6661.
2. LIANG, Franklin Mark. Word Hy-phen-a-tion by Com-pu-ter. Stanford, 1983. Dizertační práce. Stanford University, Department of Computer Science. Vedoucí práce Donald Ervin Knuth.
3. HRIC, Jan. Automatické dělení slov. In: KARLÍK, Petr; NEKULA, Marek; PLESKALOVÁ, Jana (editoři). Nový encyklopedický slovník češtiny. 1. vyd. Praha: Lidové noviny, 2016, sv. 1 (A–M), s. 139–140. ISBN 978 80 7422 482 9.
4. SOJKA, Petr. Hyphenation on demand. In: TUGboat: The Communications of the TEX Users Group. Portland: TEX Users Group, 1999, vol. 20, no. 3, s. 290–296. ISSN 0896 3207.
5. KNUTH, Donald Ervin. The TEXbook. 7th printing. Reading: Addison Wesley, 1986. ISBN 0 201 13447 0.
6. ANTOŠ, David; SOJKA, Petr. Generování vzorů pomocí knihovny PatLib a programu OPatGen. In: Zpravodaj Československého sdružení uživatelů TEXu. Brno: Československé sdružení uživatelů TEXu, 2002, roč. 12, č. 1, s. 3–12. ISSN 1211 6661.
7. ANTOŠ, David. PATLIB, Pattern Manipulating Library. Brno, 2001. Diplomová práce. Masarykova univerzita, Fakulta informatiky. Vedoucí práce Petr Sojka.
8. ANTOŠ, David; SOJKA, Petr. Pattern Generation Revisited. In: Pepping, Simon (ed.). Proceedings of the Twelfth European TEX Conference. Kerkrade: Nederlandstalige TEX Gebruikersgroep, 2001, s. 7–17.