Follow That Page stuurt u een email wanneer deze pagina wordt gewijzigd.
|
Anagrammenalgoritmes (1)
Sjaak Priester is de maker van Ragmania, een programma om anagrammen te vinden. Een voorbeeld hierbij was onder andere Maanrag, hersenspinsel van Onnoot, die tot meer anagramsoftware heeft geïnspireerd. Maanrag is echter nogal verouderd en schijnt op systemen met veel RAM in de war te raken.
Onnoot werd zeer getroffen door een citaat op Sjaak's website uit het boek Opperlans van Hugo Brandt Corstius (Battus), de kampioen der Nederlandse taalacrobatiek.
"Daar had ik iets moois voor verzonnen. Ik gaf aan elke letter een getalwaarde, altijd een priemgetal. (...) Bij elk woord vermenigvuldig je de getalwaarden van de letters met elkaar. (...) Woorden met dezelfde getalwaarde zijn anagrammen van elkaar, want producten van dezelfde priemgetallen."
Het gaat erom: hoe weet een computer of twee woorden anagrammen van elkaar zijn? Onnoot heeft daarvoor het volgende recept gehanteerd:
1. Voor elke letter van het origineel wordt gekeken of die letter bestaat in het mogelijke anagram. (De letters mogen eerst gesorteerd worden maar in de meeste gevallen is dat onnodig.)
2. Komt de letter in zowel origineel als anagram voor, dan wordt de letter uit beide gewist.
3. Het resultaat is twee lettergroepen. Een lettergroep die resteert van het origineel, en een lettergroep die resteert van het anagram. Zijn beide groepen leeg, dan zijn de twee woorden anagrammen van elkaar.
Het mooie met deze methode is dat je meteen weet welke letters er te veel of te weinig zijn gebruikt.
De methode met priemgetallen van Hugo Brandt Corstius is echter van een ongerepte wiskundige schoonheid. Onnoot moet dan ook met schaamte bekennen dat 's mans boek "Opperlans" nog niet in de boekenkast van Onnoot prijkt. Helaas heeft de priemmethode een nadeel: bij grote anagrammen is deze methode waarschijnlijk trager dan Onnoot's simpele wegstreepmethode, doordat de getallen heel groot worden en de microprocessor omslachtige truuks moet uitvoeren om de nodige berekeningen uit te voeren.
Ik zou daarom nog een idee willen toevoegen: als de meest voorkomende letters de laagste priemgetallen krijgen en de minst voorkomende letters de grotere priemgetallen, dan blijven de producten gemiddeld gesproken het kleinst.
Welke methode het snelst is hangt van veel factoren af, waaronder de architectuur van de gebruikte microprocessor en de grootte van het anagram.
Onno -
31 okt 2004, 17:10 -
Nog geen reacties
|
