Il Motore Anagrammatico del Gaunt
Anagrammatica 2: gli anagrammi multiparola
Intelligiochi, MCmicrocomputer n° 126, febbraio 1993
Lo scorso dodici dicembre si è svolta a Roma, presso i locali dell'associazione socio-culturale "La Maggiolina", una interessante manifestazione ludica incentrata sui giochi di parole. Denominata appunto "Giochi di Parole a Roma" tale manifestazione, organizzata dall'associazione Top Games e sponsorizzata tra l'altro dall'Associazione Rebussistica Italiana, ha visto la partecipazione di enigmisti ed esperti del settore i quali hanno intrattenuto il pubblico sia con giochi dal vivo sia con conferenze e seminari. In particolare Marco Danè, conduttore del Paroliamo televisivo, ha svolto una sessione di Paroliamo dal vivo e poi ha presentato un suo nuovo gioco denominato Syncro; Ennio Peres, noto giocologo ed eccellente anagrammista, ha parlato dei rapporti fra enigmistica ed umorismo; ed il sottoscritto ha discusso dell'uso del calcolatore per giocare con le parole, con speciale riferimento alla generazione automatica di anagrammi.
Chi mi segue con maggiore costanza sa bene che quello degli anagrammi è un tema che mi solletica parecchio e del quale oltretutto mi sono già occupato un paio di volte su queste pagine. Preparando l'intervento per La maggiolina mi sono però reso conto con sgomento che il tempo passa più in fretta di quanto sembri: infatti la più recente puntata di Intelligiochi dedicata agli anagrammi risale a più di tre anni fa, essendo stata pubblicata su MC 90 del novembre 1989; mentre quella precedente è ormai poco più che un sedimento nella memoria archeologica della rivista in quanto risalente addirittura al numero 48, oltre sette anni fa! Tutto sommato dunque i tempi sono maturi per riprendere in mano l'argomento, dato che dubito fortemente che molti di voi abbiano letto o ricordino gli articoli precedenti. E c'è di più: l'intervento alla Maggiolina mi ha infine costretto a fare una cosa che da anni rimandavo per mancanza di tempo e di motivi immediati per farlo: e cioè scrivere un programma "serio" per la generazione degli anagrammi multiparola, ovvero degli "anagrammi a frase" come si indicano con terminologia enigmistica. Nella puntata del 1989 indicavo infatti come si potesse preparare un programma in grado di generare anagrammi di singole parole, e davo alcuni cenni su come lo si sarebbe potuto estendere al caso ben più complesso degli anagrammi a più parole. Da allora mi ero ripromosso molte volte di completare il lavoro ma la mia innata pigrizia me lo aveva sempre impedito, fino ovviamente ad un paio di giorni prima della programmata manifestazione quando, all'ultimo minuto come mio solito, ho necessariamente dovuto buttare giù in quattro e quattr'otto le poche manciate di linee di C necessarie alla bisogna.
A questo punto prendo due piccioni con una fava ed eccomi così a presentarvi infine la "seconda parte" dell'articolo di tre anni fa: questo mese ritorneremo dunque a parlare della generazione automatica di anagrammi (quella che io chiamo "anagrammatica") e vedremo come il computer possa diventare un potente strumento di aiuto e supporto all'enigmista in questa antica e nobile arte.
Ovviamente dovrò ripetere per completezza un minimo di cose già dette nelle precedenti occasioni, a beneficio di chi non le avesse seguite; e comunque ciò sarà un utile ripasso anche per gli altri. Tuttavia molte sono le cose che non ripeterò, e per esse vi rimando senza indugio alle citate puntate passate.
Dizionario delle firme e dizionario degli anagrammi
Il concetto principale che occorre stabilire per poter parlare di giochi con gli anagrammi è quello di un "dizionario degli anagrammi": ossia un elenco alfabetico di tutte e sole quelle parole che ammettono un anagramma, ciascuna elencata assieme all'anagramma stesso.
Non crediate che libri del genere non ne esistano: in USA ne sono stati pubblicati diversi (il più vecchio risale agli anni '60 e comprendeva circa 20.000 parole lunghe fino a sette lettere) e recentemente anche qui da noi ne è stato pubblicato uno dalla Zanichelli (e grazie, con lo Zingarelli in linea...). Naturalmente un dizionario del genere differisce dai normali dizionari cui siamo abituati, quanto meno perché in esso compaiono solo le parole e non le definizioni; tuttavia in mancanza di un termine più preciso lo si continua a chiamare "dizionario" nel senso più ampio di "collezione di parole ordinate alfabeticamente".
Cosa ci si fa con un dizionario degli anagrammi? Beh, essenzialmente ci si tolgono un sacco di curiosità lessicografiche e poco più. In realtà, infatti, la generazione automatica degli anagrammi non viene fatta col dizionario degli anagrammi ma con una sua speciale variante detta "dizionario delle firme". Niente paura, stiamo proprio per vedere da vicino come possano essere costruiti entrambi.
Il primo passo è, purtroppo, il più problematico: occorre infatti avere sottomano un dizionario vero e proprio! In verità anche in questo caso le definizioni non servono, per cui continuiamo a considerare anche questo dizionario come una semplice collezione di parole; tuttavia ciò non semplifica molto il compito a chi tenti di costruirne uno. Va bene, per il momento sorvoliamo sullo scottante problema di come mettere le mani su un dizionario del genere e andiamo avanti. Dando come assunta la sua presenza possiamo dunque passare da questo dizionario al dizionario degli anagrammi mediante un semplice ma efficace algoritmo che prevede il passaggio intermedio per l'utile dizionario "delle firme".
Il concetto di "firma" di una parola è stato pubblicato per la prima volta (a quanto mi consta) nel 1973 dal "solito" Martin Gardner, il quale però ne attribuiva la paternità a tal Nicholas Temperley. Una descrizione precisa dell'algoritmo di costruzione del dizionario degli anagrammi tramite il metodo della firma fu invece pubblicata sulle "Communications of the ACM" del settembre 1983 da Jon Bentley nella sua rubrica fissa di algoritmi, e ripresa poi un anno dopo da "Scientific American" nella rubrica "Mathematical (Re)creations".
Ma che cos'è questa benedetta "firma" di cui stiamo parlando? In pratica essa non è altro che un particolare anagramma della parola cui si riferisce, precisamente quello in cui le lettere della parola stessa sono riordinate in modo da trovarsi in ordine alfabetico. La si potrebbe definire pertanto "anagramma principale" o "forma canonica" della parola, ma viene comunemente detta "firma" sia per brevità che per sottolineare come essa sia unica ed univoca per ogni parola (ossia ogni parola possiede una ed una sola firma). Va da sè che se due parole diverse hanno la medesima firma allora sono l'una l'anagramma dell'altra. La firma ci permette dunque di riconoscere rapidamente gli anagrammi di una parola, ossia tutte le altre parole formate dalle stesse lettere della parola data.
Ma come facciamo in pratica a sfruttare questa proprietà della firma? Presto detto. Torniamo al nostro dizionario ed elaboriamolo in questo modo: per ogni parola presente calcoliamone la firma e scriviamola nel dizionario accanto alla parola stessa (meglio se davanti ad essa); dopodiché riordiniamo il dizionario mettendolo in ordine alfabetico rispetto alle firme. Cosa abbiamo ottenuto? Evidentemente tutte le parole avente la medesima firma si sono raggruppate assieme in questo che è il famoso "dizionario delle firme" che citavo prima. A questo punto basta far "collassare" su una medesima riga tutti quei gruppi di due o più parole aventi uguale firma (scartando le parole che rimangono singole) per ottenere il tanto sospirato "dizionario degli anagrammi".
Nelle figure che accompagnano l'articolo è illustrato passo passo il metodo fin qui descritto, che ho effettivamente realizzato nella pratica. In figura 1 vediamo uno stralcio del dizionario originale dal quale sono partito: si tratta di un file contenente circa centocinquantamila parole italiane ivi comprese le forme declinate e coniugate. Quello di figura 2 è invece il "dizionario delle firme" da esso ricavato; come si vede ciascuna parola originale è preceduta dalla relativa firma, ed il tutto è ordinato alfabeticamente sulla firma stessa. Ed ecco finalmente il nostro bravo "dizionario degli anagrammi" derivato direttamente da quello delle firme: le parole sono state raggruppate e le firme, ormai inutili, eliminate; a titolo di esempio gli anagrammi così isolati sono pochi più di ventinovemila. Per puro spirito di ricerca ho poi provveduto a separare il dizionario degli anagrammi in più parti, ciascuna delle quali comprendesse tutte quelle parole aventi un determinato numero di anagrammi: e così nelle figure da 3 a 11 vedete rispettivamente i dizionari degli anagrammi a due, tre, quattro... dieci parole. È incredibile che vi siano parole italiane con un così alto numero di anagrammi, vero?
Ricerca di anagrammi
Supponiamo ora di voler fare un programma di generazione di anagrammi a parola singola. Vogliamo in pratica un programma che, se gli forniamo in ingresso una parola, ci produca in uscita tutti i suoi anagrammi (se esistono). Come fare? La cosa più semplice è quella di ricorrere al dizionario delle firme. L'algorittmo è banale: si genera la firma della parola ricevuta in ingresso e la si compara con tutte le firme del dizionario, stampando le parole corrispondenti alle firme uguali. A questo scopo non serve neppure che il dizionario sia ordinato, anche se ovviamente si può sfruttare la caratteristica dell'ordinamento per minimizzare sostanzialmente i tempi di ricerca.
Passiamo invece al caso, assai più interessante, degli anagrammi a frase. Un'applicazione tipica di questi anagrammi, risalente perlomeno al rinascimento se non oltre, è quella di generare frasi spiritose o descrittive a partire dal nome e cognome di una persona. Ad esempio, citando due capolavori di Ennio Peres, "Michele Sindona: indole meschina" e "Alessandro Natta: non salta a destra". È possibile che il calcolatore generi "chicche" come queste? Forse no, però ci si può almeno provare. L'algoritmo non è molto complesso, solo un po' complicato. Vediamolo da vicino.
Riprendiamo dunque il nostro bravo dizionario delle firme, sul quale confronteremo la firma della stringa costituita da tutte le parole fornite in ingresso. La prima cosa da fare è dunque concatenare assieme tali parole e generare la firma della stringa risultante. Dopodiché si tratterà di confrontare tale firma ("sorgente") con le firme del dizionario ("oggetto") per vedere quante e quali lettere della firma sorgente si trovano nella firma oggetto. Si danno due casi: (1) la sorgente contiene l'oggetto (o al limite coincide con esso); (2) la sorgente è contenuta nell'oggetto. Nel primo caso la parola corrispondente alla firma oggetto fa parte dell'anagramma e quindi viene messa da parte; parallelamente i caratteri della firma oggetto vengono "sottratti" alla firma sorgente. Ciò che rimane da questa "sottrazione" è una stringa costituita da tutti i caratteri della sorgente per i quali ancora non si è trovato un anagramma; se essa coincide con la stringa nulla allora allora la ricerca si è conclusa con successo: basta stampare l'elenco di parole via via accantonate e prepararci ad una nuova ricerca; altrimenti tale stringa diventa una nuova sorgente e con essa si riparte per una successiva "passata" nel dizionario. Nel secondo caso, invece, ci troviamo in una situazione per cui la sorgente a questo punto non ammette anagrammi e dunque è inutile proseguire su questa linea di ricerca; occorre dunque aprirne un'altra.
Appare chiaro a questo punto che quando si giunge ad un vicolo cieco, o si conclude una ricerca positivamente, occorre tornare indietro fino ad un certo punto e poi ripartire in avanti secondo una linea diversa; occorre, cioè, fare uso del backtracking. Per questo motivo conviene implementare l'algoritmo di ricerca in modo ricorscivo, in modo che l agestione del backtracking venga effettuata implicitamente dallo stack delle chiamate. Ciò permette così di ottenere un programma assai più compatto ed elegante.
CI si potrebbe domandare a questo punto del perché si faccia uso per le ricerche del dizionario delle firme e non di quello delle parole. Tutto sommato le operazioni descritte vanno bene anche in quest'ultimo caso. Il motivo è solo uno: l'efficienza. Lavorando sulle firme si ottengono due grandi vantaggi: ci si accorge subito di quando un ramo di ricerca diventa infruttuoso e si possono utilizzare algoritmi più efficienti per localizzare rapidamente le firme da cercare. Nel caso specifico, ad esempio, ho scelto di fare uso di un indice parziale del file delle firme, così da poter evitare lunghe ed inutili scansioni preliminari. Naturalmente il tutto si basa sulle proprietà di ordinamento delle firme e del dizionario, e sul fatto che la citata "sottrazione" di due firme dà come risultato ancora una firma.
Dimostrazione pratica
Naturalmente a questo punto non posso fare a meno di "dimostrare" le capacità di un siffatto anagrammatore, per vedere come si comporta e cosa ci si può aspettare da lui. Vediamo dunque in figura 12 alcuni anagrammi generati a partire dal nome dell'attuale Presidente della Repubblica. Da notare che i quattro presentati sono stati scelti fra un mare di anagrammi sintatticamente corretti ma semanticamente insignificanti; e che comunque ho bloccato il programma dopo pochi minuti di elaborazione, mentre potrebbe andare avanti per ore ed ore. Il problema è infatti questo: l'anagrammatore automatico può produrre centinaia se non migliaia di anagrammi, dei quali solo una ristrettissima minoranza ha un qualche valore estetico o semantico; il compito dell'uomo è a questo punto quello di scegliere tra tanta "immondizia" le poche perle che vale la pena di conservare.
Ovviamente poi il risultato dell'elaborazione dipende direttamente dalla qualità e dalla vastità del dizionario utilizzato. La macchina non può infatti produrre parole che non si trovino nel dizionariodi partenza. Nel mio caso ho utilizzato per questa prova un dizionario di circa centocinquantamila parole che ho trovato nel Pubblico Dominio (sta anche su MC-link). Si tratta di una notevole massa di parole anche se, a mio avviso, risulta ancora carente in qualche aspetto. L'alternativa all'usare un dizionario già fatto è quella di costruirsene uno a misura di ciò che si vuole fare. Chi ha seguito le precedenti puntate di Intelligiochi sul tema dell'elaborazione del linguaggio ricorderà che da qualche anno sto esattamente facendo questo, ossia costruendomi un dizionario personale a partire dall'insieme di testi che scrivo per MC (mediamente oltre un MByte l'anno). Attualmente tale dizionario comprende circa cinquantamila parole, e nel suo piccolo (beh, si fa per dire...) è un'ottima base per la costruzione di anagrammi. Quello che a questo punto dovrei fare, ma per pigrizia sto rimandando, è ovviamente la fusione del mio dizionario con quello generale per ottenerne uno ancora più ricco. Ma insomma, per ora mi accontento di quello che passa il convento, anche perché nel momento in cui dovessi intervenire sul dizionario lo farei pesantemente, ad esempio per inserirvi modificatori quali i diminutivi, i vezzeggiativi, gli accrescitivi e via dicendo, che ora per la maggior parte mancano. Insomma, un lavoro niente male...
Conclusione
E vorrei chiudere, a questo punto, con una considerazione forse ovvia ma che vale comunque la pena di fare. Qualcuno potrebbe avere l'impressione, al termine di questo articolo, che con l'introduzione degli "anagrammatori automatici" la figura dell'anagrammista umano perda di valore e di significato. Ovviamente non è così: il senso estetico dell'uomo, il sottile piacere del gioco di parole, l'ammirazione per la costruzione elegante o il doppio senso nascosto non possono essere rimpiazzati da scelte meccaniche. L'uomo e la sua creatività sono insostituibili, nell'arte come nell'enigmistica. La macchina può essere tutt'al più un sussidio dell'uomo ma mai un suo sostituto.
E per dimostrarvi cosa è capace di fare un abile anagrammista chiudo la puntata proponendovi in figura 13 un eccezionale componimento poetico di Ennio Peres, dedicato all'anno da poco entrato. Per chi non se ne fosse accorto, ogni strofa è l'anagramma della parola millenovecentonovantatre. Con buona pace dei computer...
Arrivederci al prossimo mese.
Figura 1:
a
abate
abati
abbacchia
abbacchiai
abbacchiammo
abbacchiamo
abbacchiando
abbacchiano
abbacchiarono
(...)
zucchini
zucchino
zuccone
zucconi
zuffa
zuffe
zuppa
zuppe
zuppi
zuppiera
a a
aaaaacdeprttuv paracadutavate
aaaaacdmoprtuv paracadutavamo
aaaaacdnoprtuv paracadutavano
aaaaacdprttu paracadutata
aaaaacdprtuv paracadutava
aaaaaceilpssstv lasciapassavate
aaaaacilmopsssv lasciapassavamo
aaaaacilnopsssv lasciapassavano
aaaaacilpssst lasciapassata
(...)
ost sto
osu suo
osu uso
otttu tutto
otu tuo
psu pus
rsttu trust
su su
ttuu tutu
tu tu
abate beata
abati abita
abbacchiero abboccherai
abbagliare abbagliera
abbagliati abbigliata
abbagliavi abbigliava
abbaiare abbaiera
abbaini abbinai
abbandonare abbandonera
abbandonavo abbondavano
(...)
zampillare zampillera
zappare zappera
zappe zeppa
zappo zoppa
zavorrare zavorrera
zeppo zoppe
zompare zompera
zuccherare zuccherera
zucchererai zuccheriera
zucchererei zuccheriere
abbaino abbiano abbonai
abbandono abbonando abbondano
abbatterono abbottonare abbottonera
abile balie belai
accerta cercata taccera
accertasti stracciate tracciaste
accertate accettare accettera
accerti cercati treccia
accettai eccitata tacciate
accetteranno accontentare accontentera
(...)
terremo tremero tremore
tingevi vigenti vigneti
tiravo travio trovai
torve verto vetro
traevo votare votera
turera urtare urtera
valgono volgano vongola
vanterai vanteria variante
vaticinare vaticinera verniciata
violare violera volerai
accertai caricate taccerai tacciare
accertarsi scarcerati straccerai stracciare
acerrime cremerai marcerei merceria
adatto adotta datato dotata
addestrino disertando distraendo ridestando
addice decadi decida dedica
aderire arderei diarree raderei
aderiremo adireremo modererai radieremo
aderiro adirero radiero roderai
aderisti disertai disterai ridestai
(...)
snidavo snodavi sondavi sviando
snodare snodera sondare sondera
sostati sottasi tosasti tossita
sottana stanato stonata tastano
stantio stonati tastino tastoni
stature sturate turaste urtaste
stirava travasi travisa varasti
stornati stranito tornasti transito
sturati turasti turista urtasti
traevi verita virate vitrea
accerto accorte cercato taccero toccare
acerrima marcerai marciare ricamare ricamera
acre care cera crea reca
aderenti dentiera dreniate rendiate tenderai
aderireste adirereste estraderei radiereste sdraierete
aderiresti adireresti diserterai radieresti ridesterai
aderirete adirerete ereditare ereditera radierete
aderita adirate ardiate daterai radiate
aderite daterei eredita tediare tediera
adiri ardii aridi diari dirai
(...)
riaveresti riserviate riversiate traviserei varieresti
riservato riversato rovistare rovistera travisero
risorte ritorse ritrose stirero terrosi
rivesto servito svitero vestiro vetrosi
salve selva slave svela valse
snervate sventare sventera svernate versante
stamperete stemperate temperaste tempestare tempestera
stavi stiva svita vasti vista
taravi tirava travia varati virata
torretta trattero trattore trottare trottera
aderiranno adireranno radieranno rannoderai riannodare riannodera
adorni indora ordina radino riando ridano
agresti gestira giraste regista rigaste stregai
andremo mandero moderna mondare mondera remando
andrete ardente drenate radente redenta tendera
aprirete praterie rapirete reperita ripetera tarperei
apriro porrai priora rapiro riapro riparo
aprito patiro patrio portai potrai rapito
aravi avari avrai riava varai varia
ardevi deriva radevi rideva riveda vedrai
(...)
maritino minatori minorati minorita rimontai rinomati
mentiro mentori morenti rimonte termino tremino
meritare meritera riemerta temerari tramerei tremerai
ornaste rasento restano stanero stonare stonera
paresi saprei separi sperai spiare spiera
partiste prestati rispetta spartite spretati strepita
perisca precisa rapisce ripesca sciarpe sprecai
persista pressati sapresti spariste sperasti spiraste
retto rotte terto tetro torte trote
riavesti sviterai vestiari vestirai visitare visitera
aderira adirera arderai diarrea raderai radiare radiera
arderesti ardireste disertare disertera raderesti ridestare ridestera
attinse estinta intesta istante sentita stantie stentai
covare covera creavo recavo revoca vocera vorace
dragoni girando gradino gridano grondai ingorda rigando
esportai operasti ospitare ospitera pietrosa riposate saporite
esporti estirpo posteri protesi riposte stipero storpie
esternavi intravese snerviate svanirete sventerai sverniate venerasti
estinto insetto intesto ostenti sentito sonetti testoni
estorta restato rosetta sottrae tastero tostare tostera
intasero onerasti orinaste ostinera risonate senatori stonerai
irto orti otri rito tiro tori trio
meritavo morivate motivare motivera vertiamo vomitare vomitera
parasti piastra rapasti raspati sparati sparita spirata
partireste rispettare rispettera spartirete strepitare strepitera tarperesti
permeasti premiaste spremiate stamperei stamperie stemperai stempiera
aprendo padrone parendo perdano perdona pondera predano rapendo
arrestavi arrivaste riservata riversata traversai traversia travisare
travisera
aspro parso prosa raspo sapro sopra sparo spora
avresti restavi rivesta servita svitare svitera versati vestira
castrino cronista incrosta scartino scontrai scornati stroncai trascino
enormita entriamo meritano minatore minorate monetari monterai rinomate
maestri miraste remasti rimaste rimesta stimare stimera stremai
aperti aprite pareti patire patrie perita pietra rapite ripeta
aprireste estirpare estirpera pareresti presterai raperesti rapireste
respirate sparirete
aprita parati parita patira patria pirata rapati rapita tarpai
estirpano insperato pensatori ripensato riposante speronati spiantero
sproniate strapieno
apriste estirpa piastre prestai rapiste sparite sperati spirate stipare
stipera
ardesti ardiste daresti diserta distare distera distrae estradi radesti
ridesta
Oscar Luigi Scalfaro
------------------------
Lui fracassa col rigo.
Corso su calligrafia.
Fracassai, giù crollo.
Lì il rogo fu carcassa.
Giuro, fracassa colli!
MILLENOVECENTONOVANTATRE
------------------------
Certo, vivo l'anno lentamente;
tento, ma conto nell'avvenire.
La morente volontà vincente
vola nel vento con tante mire;
il vento non vola, certamente,
ma l'evento incontra l'evento...
attorno vive l'anno clemente?
L'anno tace, vive nel tormento;
in TV c'è tanto veleno normale,
con il vento vanno altre mete!
Noto l'avvenimento centrale:
l'anno conta mentre lo vivete!
Intelligiochi, MCmicrocomputer n° 126, febbraio 1993
Copyright © 1993, Corrado Giustozzi. Tutti i diritti riservati.
Ultima modifica: 25 marzo 2012
Visitatori dal 6 maggio 2003: 26,597
Torna alle informazioni tecniche sul Motore Anagrammatico
Vai alla Pagina dei Commenti