Vyhledání přesmyček pomocí prvočísel

Kolegu Michala Jirků, který stojí u přesmyčkovače od jeho počátků a díky kterému se z nás stali přátelé, jsem požadavkem na věcnou revizi článku Jak Rumburak hledal přesmyčky inspiroval k novému, geniálně jednoduchému algoritmu pro vyhledávání přesmyček. Založil ho na prvočíslech, tedy přirozených číslech, která jsou – krom jedničky – už dělitelná pouze sama sebou.

Každému písmenu abecedy přiřadíme “jeho” prvočíslo. Tedy a=2, b=3, c=5, …, z=101. Prvočísla odpovídající písmenům v zadaném vstupním výrazu V vynásobíme mezi sebou. Násobení je komutativní, takže jeho výsledek bude shodný pro každé slovo se stejnými písmeny, nezávisle na jejich pořadí ve slově.

Příklad:
REKLAMA = 61*11*31*37*2*41*2 = 126220468

Obdobným způsobem vypočítáme hodnotu každého slova W ve slovníku S a slovník S nově seřadíme sestupně podle těchto hodnot.

Chceme-li najít všechny jedno a víceslovné přesmyčky např. pro uvedený vstup REKLAMA, v 1. kroku “ořízneme” slovník S shora podle výsledného součinu, tedy nově jsou ve slovníku S1 pouze slova s hodnotou <= 126220468.

Pro nalezení přesmyček postupně hodnotu vstupu V (126220468) dělíme hodnotou W každého zbývajícího slova ve slovníku. Je-li vstup V položkou slovníku W dělitelný beze zbytku a výsledek (podíl) P = 1, nalezli jsme přesmyčku jednoslovnou, například:

MAKRELA = 41*2*31*61*11*37*2 = 126220468

V/W = REKLAMA / MAKRELA = 126220468 / 126220468 = 1

Je-li vstup V dělitelný slovem W beze zbytku a výsledek (podíl P) je přirozené číslo > 1, slovo W se ve vstupu V vyskytuje, příklad:

ALE = 2*37*11 = 814
REKLAMA / ALE = 126220468 / 814 = 155062

Nyní opět shora “ořízneme” slovník S1 podle hodnoty aktuálního podílu, ve slovníku S2 už tedy zbydou pouze slova s hodnotou <= 155062, a dále pokračujeme stejným způsobem, příklad:

MRAK = 41*61*2*31 = 155062

Nalezli jsme takto dvouslovnou přesmyčku ALE MRAK.

atd.

P. S.

Dlužno poznamenat, že uvedený přímočarý algoritmus demonstruje jen jednu z mnoha možností, jak přesmyčky nalézat, ale proti algoritmu, který v reálném provozu používá tento webserver, je dětsky jednoduchý a nepříliš efektivní.

Share on FacebookTweet about this on TwitterShare on LinkedInEmail this to someone

Napsat komentář

Vaše emailová adresa nebude zveřejněna. Vyžadované informace jsou označeny *