Nový open-source projekt Křížovkáč

Ukázková křížovka

Distribuce open source aplikace Křížovkáč obsahuje tři generátory křížovek. Toto oznámení pojednává o otestované verzi 0.0.1. Další, experimentální, neotestovaná verze 0.0.1+ s drobně upraveným algoritmem zostřuje na úkor svižnosti výpočtu parametry v algoritmu tak, aby se omezil výskyt krátkých výrazů. U další experimentální úpravy 0.0.1RT, jež se hodí na velmi velké křížovky, se tyto parametry zmírňují vždy při zadrhávání výpočtu, což částečně garantuje čas výpočtu (soft real-time aplikace).

Řešení ukázkové křížovky

Náhodná křížovka se vygeneruje prostě spuštění skriptu. Skript uloží výstižně pojmenované soubory křížovka a řešení, oba ve formátu html. Jako fakultativní argument se zadává rozměr křížovky a u verze 0.0.1RT i rychlost zpracování. Detailněji konfigurovat skript lze jen zásahem do zdrojových kódů.

Proběhnuvší skript

Různě velké křížovky

Skript pracuje stochasticky, proto statistické veličiny fluktuují. U křížovek značně kolísá střední délka výrazů či doba nutná k navržení křížovky, dále se též proměňuje poloha popisných políček a křížovky se různí použitými výrazy. Důkazem budiž následující ilustrace.

Neselektovaná řada křížovek

Průměrné délky výrazů

Spotřeba výpočetního času

Skript byl nastaven na hodnotu 4.35 mediánu délkového průměru výrazů, protože ručním přepočtením křížovek z několika časopisů mi tato hodnota vyšla jako hodnota nejobvyklejší. Svaz českých hádankářů a křížovkářů (SČHaK) doporučuje hodnotu 4.5. Vyladěný skript 0.0.1+ dosahuje typicky hodnot okolo 4.8. Extrémnější optimalizace algoritmu, aby průměr překračoval hodnotu pět, se mi zdá samoúčelnou, poněvadž zpřísněním kritéria na délku výrazů se mimo jiné ochudíme o slova s méně frekventovanými písmeny.

Chabá křížovka s dlouhými výrazy (průměrně 5.24)

Křížovky u většiny komerčních tiskovin navrhují placené proprietární programy, především populární CWD Studio. Křížovkáč není zamýšlen pro tuto profesionální sféru, neboť (zatím) přehlíží klíčové potřeby publikační praxe křížovkářských periodik:

Nepodporuje tajenku.
Nezvládne generovat křížovku libovolného tvaru.
Absentují pokročilá typografické funkce, nastavitelnost vzhledu křížovky, možnosti exportu do různých formátů, podpora obrázků a grafických prvků.
Rovněž se ignorují estetická hlediska (např. pravidelnost rozložení popisků).
Nelpí se na konvencích, jak je sankcionuje zmíněný SŠHaK.
Popisky jsou sice stručné, nikoliv však vysloveně minimalistické. Musely by být ještě konciznější, aby se při zmenšení křížovky na běžný formát daly tisknout nejen titěrným fontem.

Zlepšení typografie přinesou až budoucí verze Křížovkáče. U současné verze, hrozí-li, že se do jednoho políčka legenda nevměstná, jednoduše se vysází jen odkaz na vlastní text popisku, který se vypíše pod křížovku do vnější legendy. Dále křížovku nezřídka znehodnocuje nadužívání těžkého výraziva a překlepy. Proto se přikládá jako řešitelská pomůcka abecedně řazený soupis, v němž naleznete všechna použitá slova promíchaná s matoucím balastem.

Křížovka s řešitelskou pomůckou

Kompletní křížovka s několika vnějšími popisky

Chystaná vylepšení

Nevalná úroveň Křížovkáče vyplývá z poměrně krátké doby jeho vývoje. Záměr naprogramovat návrháře křížovek mne napadl loni při psaní tohoto článku. Křížovkář je vyvíjen volnočasově zhruba od letošního března jedním člověkem. (Chcete-li se podílet na vývoji, napište mi na mail@frantisekbartikcz). Překlepy z slovníku odstraňuji a zabývám se různými nevyváženostmi, zejména nutností redukovat skupiny křížících se obtížných výrazů.

Těžké výrazy

Nevyvážená křížovka z obrázku potrápí zapeklitým levým horním růžkem. Podobně komplikované oblasti jsou nežádoucí, leda že by si uživatel takové oříšky přál. Současná verze obtížnosti slov nedbá; nedovoluje pouze smyšlená slova a blokuje vkládání mnoha krátkých slov vedle sebe. Smyšlená slova se vyřazují tak, že se existence slova ověřuje v slovníku. Kumulaci nedlouhých výrazů se předchází jednoduchou podmínkou na lokální průměr délek, jenž se kalkuluje rekurzivní formulí.

Bez podmínky kladené na délky výrazů se generují nehezké křížovky

S pomocí údajů o obtížnosti konkrétních výrazu by se šlo s problémem přílišné složitosti vypořádat principiálně stejným způsobem, jakým Křížovkáč brání nakupení krátkých výrazy. Klasifikace obtížnosti výrazů bohužel není čistě strojově proveditelná, nehledě k popiskům, které také spolurozhodují o obtížnosti.

Například výraz ZBROJIT se dá vysvětlit jednoduše multiverbizací jako konat zbrojení, přímočaře jako kupovat zbraně, nepřímo jako doplňovat arzenál, vágně jako investovat do vojska či odborně jako termín pro tankovat parní lokomotivu. Jako řešení je nutno ze strohého slovníku, který pouze přiřazuje křížovkářským výrazům popisky, učinit komplexní křížovkářskou databázi, v níž se položky slovníku sdruží s křížovkářsky relevantními hodnoceními. Pracovní návrh příslušného databázového standardu mám hotový, byť jsem jej nezahrnul do Křížovkáče 0.0.1. Standard počítá s anotacemi, normami, poznámkami a makry:

Anotace budou informovat o originalitě a přesnosti popisku, způsobu popsání (např. iniciály osob), tématické kategorii, aby bylo možné navrhovat tématicky zaměřené křížovky, obecné známosti výrazu, expresivitě, hovorovosti a jiných faktorech, gramatických kategoriích a lemmatech, jimiž se identifikují etymologicky či jinak blízké výrazy.
Editoři kladou různá omezení na vydávané křížovky. Jedny redakce výraz míti strach zadají jako BÁTI, druhé výhradně jako BÁTISE a třetí šmahem odmítají všecka zvratná slovesa. Porušení některého z obvyklých pravidel bude v databázi označeno, aby Křížovkáč dokázal respektovat zvyklosti toho kterého vydavatele.
Poznámky budou usnadňovat editaci a správu slovníku. Půjde mimo jiné o označení strojově pořízených záznamů (např. extrakcí z databáze Wikidata).
Makra zautomatizují zadávání rutinně odvoditelných záznamů. Například výraz DIŮV se dá opsat jako Kronovcův nebo jako spisovně Zeusův. Makro k těmto dvěma záznamům doplní výraz DIOVA s analogickým popiskem Kronovcova a obdobně i zbývající záznamy odvozené podle vzoru otcův. Makra zajistí i případné vyřazení časově relativních popisků (KLAUS náš prezident).

Databázovými dotazy bude možno exaktně vyjádřit rozličná kritéria k individualizaci křížovek. Cílem je, aby si uživatel Křížovkáče vyžádal -řekněme- středně těžkou křížovku prostou nespisovných výrazů a s hojnými výrazy týkajících se biologie, jež mohou být i dosti specializované.

Návrhář křížovek

Smysluplný vývoj generátoru vyžaduje testování reálných dat, tedy dokončenou databázi. Abych postupoval hospodárně, věnuji úsilí hlavně databázi. Práce na vlastním programovém kódu odsouvám, a tak jsem provizorně narychlo „slátal“ primitivní generátor, jenž slouží jen jako technologický demonstrátor.

Prozatímně jsem implementoval prostinký algoritmus. Ve vnitřní abecedě se pomocným znakem mezerou reprezentují políčka před a za slovem, která se vyhrazují popiskům, znakem hvězdičkou se kóduje spřežka ch a kodér čte slova retrográdně (pozpátku), protože u češtiny tato transformace úlohy (středová symetrie) zvyšuje účinnost algoritmu. Konkrétně chalupář se zapíše řetězcem „ řápula* “.

Rastr křížovky lemují vodorovný a svislý řádek, v nichž se připouštějí pouze mezery. Tímto se vynutí splnění okrajové podmínky, že výrazy nepřečnívají za křížovku. Křížovkový rastr se ohodnocuje shora dolů a zleva doprava po jednotlivých písmenkách tak, aby shora i zleva vznikaly začátky známých slov. Některá místa v rastru se vyplňují několikrát. Redundance v postupu (doplňování nanečisto) funguje jako heuristika pro zlepšení konvergence algoritmu.

Při možnosti doplnění odlišných písmenek se varianta zvolí náhodně, přičemž se podle předpočítaných váhových koeficientů upřednostňují obvyklá pokračování začátků slov. Nelze-li doplnit žádné písmenko, ruší se poslední doplnění. Rozsah vracení se periodicky mění. Popsané kroky se opakují, až se podaří úplně vyplnit rastr. Nakonec prezentační část Křížovkáče exportuje výsledek do html.

Konstruování křížovek je jednoduše definovaný problém čistě kombinatorického charakteru řešitelný obecně známými algoritmy. Paradoxně na vývoji generátoru křížovek je nejméně kreativní a nejlehčí tvorba generujicího algoritmu. Hlavní přínos Křížovkáče spatřuji v jeho slovníku.

Slovník

Původně jsem chtěl slovník převzít z některého stávajícího projektu. V tom mi zamezila autorská práva, styl výkladu hesel a nejrůznější drobné překážky. Jedinou cestou se ukázalo pořízení vlastního slovníku. Popisky v databázi jsem vymyslel zcela nově, a eventuální shody nejsou než čistě náhodné.

Prohlížení slovníku v editoru GVim

Mojí prioritou byla rychlost, chvatu odpovídá množství pravopisných i věcných chyb, jakož i neoriginalita popisků. Zejména jsem excerpoval termíny z Wikipedie, včetně podezřelých tvrzení. Třeba konstatování, že autokoš znamená popelářský vůz, na mne působí dojmem pusté smyšlenky. Vinou přejímání seznamů se stal slovník tématicky nevyváženým, a tak křížovky obsahují neúměrně moc křestních jmen.

Pro každé jmeniny se totiž snadno dohledá početná řada typu MILOŠ (prezidentovo jméno), MILOŠOVÉ (prezidentovi jmenovci), MILOŠŮV (vlastněný Milošem), ..., MILOŠOVY (vlastněny Milošem), MILDA (domácky Miloš), MILOUŠ (hejsek z Saturnina) a tak dále. Též jsem do slovníku zařazoval i příčestí, jichž se běžně křížovky vystříhávají.

Vyčasovaná slovesa

Pochopitelně Křížovkáč se omezuje na pouhý nepatrný zlomek vší slovní zásoby. Pro představu postarší Příruční slovník jazyka českého (dostupné online) jmenuje na čtvrt milionu slov, aniž uvádí notoricky známá slova -namátkou deodorant, tablet, hajlovat, dotčený-, značky a vzorce, zkratky či vlastní jména.

Zveřejněný slovník Křížovkáče obsahuje na 60 000 záznamů. Bez ohýbání slov by zásoba klesla pod 15 000 jednotek, tedy slovní zásobou Křížovkáč výrazně zaostává za Křížovkářským slovníkem či Pravidly českého pravopisu. Častost opakování výrazů v rozlehlých křížovkách je podobná, jako kdyby program rovnoměrně volil z přibližně deseti tisíc výrazů.

Odhady efektivní slovní zásoby

Odhad efektivní slovní zásoby vychází z obřích křížovek, jež zahrnují reprezentativní podmnožinu celkové slovní zásoby Křížovkáče. V grafu, analyzujícím dvacet křížovek o rozměrech 50 na 50, je vynesen počet opakujících se slov proti celkovému počtu slov a jsou znázorněny trojčlenkou spočtené isolinie tří velikostí slovních zásob.

Naznačení způsobu výpočtu

Celková charakteristika

Existuje vícero aplikací pro křížovkářskou obec. Žádný projekt ale nevyhovoval všem požadavkům, jež považuji za fundamentální. Unikátnost Křížovkáče spočívá v tom, že dostojí následujícím pěti bodům. Zaprvé Křížovkáč samočinně generuje klasické švédské křížovky. Generování se obejde bez lidské asistence. Zadruhé Křížovkáč patří mezi open source software.

Jedná se o plnou verzi produktu, takže neexistuje umělý limit velikosti křížovek ani jiné restrikce bezplatných demoverzí. Zájemcům dávám na výběr z licencí GPL2, GPL3 a AGPL3. Licence garantují široká práva nejen k vlastnímu softwaru, ale i k jeho výstupům. Malé křížovky se vůbec nijak licenčně nechrání (de facto volné dílo). Rozsáhlé křížovky a kolekce křížovek, v nichž je vytěžena a zužitkována nezanedbatelná část databáze křížovkářských výrazů (viz úprava zvláštního práva pořizovatele databáze autorským zákonem), podléhají copyleftovým ustanovením.

Zatřetí Křížovkáč je multiplatformní. Generátor křížovek běží v multiplatformním Pythonu řady 2.x. Slovník má formu prostého textového souboru v kódování UTF-16. Hardwarové nároky nepřesahují přijatelných 100 MB RAM a 5 MB HDD. Začtvrté Křížovkáč je zamýšlen pro Čechy. Návrh Křížovkáče ctí český pravopis. U výrazů se podporují všechny české znaky kromě zřídkavého q.

Česká písmena

Podporuje se jak vpisování spřežky ch do jednoho políčka, tak i zrušení spřežky ch (MLÁCHUBA nářečně žvanil, CHO aldehydická skupina). Křížovkáč čerpá z češtiny, jejích nářečí a částečně i ze slovenštiny, ač pro slovenská specifika (spřežky dz/dž, vokáň apod.) chybí podpora. Popisky se nekontrolují, jelikož se ojediněle popisuje i nečeskými znaky (JA znak azbuky ). Snažil jsem se vyhýbat obskurním exotismům vyskytujícím se prakticky jen v křížovkách (AZAPA říčka v Chille). Díky národní perspektivě se adjektivum český může nahrazovat kratším zájmenem náš, což kosmopolitně orientovaná Wikipedie oficiálně zakazuje.

A konečně zapáté, ke Křížovkáči se přikládá nápověda a vývojářské nástroje. K dvěma stávajícím skriptům pro kontrolu slovníku brzy přibude vizuální editor slovníku, statistické nástroje a utility.

Tvůrcem projektu Křížovkář je autor článku. Program si můžete stáhnout ze serveru Slunečnice.