Rumburak potřeboval najít zaklínadlo neznámého znění, aby se mohl vrátit do říše pohádek. Ukázali mu počítač (byť vzhledem k současnosti už poněkud obstarožní model) a okamžitě zavětřil.

Přikázal mu vypisovat, vyslovovat a tisknout všechny existující 12znakové kombinace písmen a brzy tak ucpal místnost papírem. Z 26 znaků abecedy (bez diakritiky) lze totiž sestavit celkem 95428956661682176 (26¹² = 95,4 biliardy; 1 biliarda = 1*10¹⁵) unikátních řetězců v délce jím požadovaných 12 písmen, od AAAAAA AAAAAA až po ZZZZZZ ZZZZZZ. Kdyby každý z nich zabral na papíru pouhý 1 milimetr na výšku, spotřeboval by Rumburak na vytištění roli dlouhou cca 95,5 miliardy kilometrů.

Což je o pořádný kus cesty dál, než co by meteorem dohodil ze Slunce na Pluto, bývalou poslední planetu sluneční soustavy (vzdálenost 5 miliard km). A kdyby jím hledané zaklínadlo bylo třeba až v půli cesty a přečtení jednoho trvalo Kecálkovi pouhou desetinu vteřiny, počkal by si na výsledek jen něco málo přes 150 milionů let.

Mimochodem, sir A. C. Clarke použil shodný motiv v povídce Devět miliard božích jmen), s abecedou neznámé délky a délkou výstupu jen 9 znaků. Takže tam by se to – s rychlotiskárnou schopnou vytisknout 1000 slov za vteřinu – za požadovaných 100 dní jakž takž stihnout dalo.

Povšimněte si prosím, že nelze nijak vyloučit, že se v té Rumburakově hromadě papíru, schopné časem vyplnit celou sluneční soustavu (stačí prodloužit požadovaný výstup o pár písmen), opravdu nenachází funkční zaklínadlo. Nebo boží jméno.

My to naštěstí máme o něco jednodušší. Chceme – na rozdíl od Rumburaka a Clarkových tibetských mnichů – najít jen takové výstupy, které dávají smysl v lidském jazyce. Proto se neobejdeme bez slovníku. Jeho kvalita a rozsah ovlivní výsledky vyhledávání.

Nejdůležitější ze všeho je ale algoritmus (nezávislý na konkrétním programovacím jazyce).

Algoritmus pro výpis všech dvanáctiznakových kombinací je primitivně jednoduchý. Zanoříme do sebe 12 cyklů s celou abecedou v poli a za pár desítek milionů let máme hotovo. Algoritmicky je i velmi snadné vyhledat jednoslovné přesmyčky. Jedna z (více) možností je písmena v zadaném vstupu seřadit podle abecedy, ze slovníku vyndat pouze slova stejné délky, jako má zadání a také jejich znaky seřadit podle abecedy. Kde je shoda, tam je i přesmyčka.

REKLAMA AAEKLMR
MAKRELA AAEKLMR

S tím už ale nevystačíme, když chceme pro zadaný vstup najít přesmyčky víceslovné, složitost řešení vzrůstá. Potřebujeme algoritmus rychlý a efektivní, ať na výsledek nečekáme dlouhé minuty a ať se nám přitom server nepřehřeje jako Kecálek v pohádce. A při vyhledávání nespotřebuje všechny své zdroje (paměť, procesor atd.). Dělí se totiž o ně se všemi dalšími aplikacemi na webovém serveru.

První veřejně dostupnou verzi postavenou na MySQL serveru tehdy začínajícího komerčního hostingu mi tam rychle zařízli, zatížil jsem totiž při vyhledávání přesmyček databázový server víc, než všichni jejich ostatní zákazníci dohromady.

Pro lepší řešení nezbývá než uplatnit nějaká matematicko-informatická kouzla: hashovací tabulky, Bloomovy filtry, prefixové stromy, vektorizované odčítání, rekurze, frekvenční histogramy, regulární výrazy, prvočísla a další. Viz též Kouzelné formule.

A. C. Clarke i Lábusův Rumburak mě bavili shodným použitím počítače pro hledání kouzelného slova a k sestrojení přesmyčkovače mě tak s vysokou pravděpodobností inspirovali.

RABERA TAREGO.