Anagrammi e linguistica computazionale

Il gioco degli anagrammi affonda probabilmente le radici nella Qabbalah ebraica.

Oggi si dice "algoritmo" e "gamification" ma, nel 1611, quando il religioso corso Giovan Battista Agnesi, pubblicò un migliaio di combinazioni anagrammatiche ad argomento religioso (come Angelus Dei te puram vocat, anima mira -> Alma Virgo et pia Mater, unica munda est) quello degli anagrammi era una vera e propria Ars, probabilmente derivata dai cabbalisti ebrei, atta a scoprire il significato nascosto delle parole.
Oggi il problema degli anagrammi ha perduto ogni connotazione mistica (o quasi) ma continua a dilettare chi cerca di progettare algoritmi efficienti, o chi, come Umberto Eco, si diverte in questo gioco, arrivando a scrivere composizioni i cui versi sono tutti anagrammi.
In particolare, qui ci si domanda se e come sia possibile eseguire quante più permutazioni anagrammatiche, data una frase in una lingua qualsiasi. In altre parole, fissato un dizionario di tutte le parole lecite in una determinata lingua, ci si chiede quale sia il metodo più efficiente per derivare, da una frase che abbia senso compiuto, un'altra frase, anch'essa di senso compiuto e contenente le medesime lettere della prima, con la stessa frequenza.
Il problema può essere scomposto in due parti: la prima in cui, data la frase di partenza assieme a un dizionario della lingua in cui è scritta (che eventualmente includa anche i lemmi inglesi di maggior utilizzo), si cercano tutte le parole derivabili da essa; la seconda in cui, da tutte le parole trovate nel primo step, se ne cerca una combinazione che abbia "senso compiuto" (per il momento per semplicità tralasciamo di definire rigorosamente cosa possa significare avere una frase di senso compiuto nella lungua L). metodologicamente, mentre la prima parte è un problema scacchistico ovvero di "constraint satisfaction", quest'ultima parte, si comprende bene, riguarda l'intelligenza artificiale e la linguistica computazionale.
Sul primo problema, ho trovato utile l'applicazione dell'algoritmo di Backtracking (per intenderci quello che si usa per risolvere in automatico i Sudoku e che usano anche molti simulatori di scacchi). Ad esempio questo sito ne utilizza - per frasi di relativamente poche lettere per ovvi motivi computazionali) una brillante e efficiente versione di Giovanni Resta (ricercatore all'IIT-CNR di Pisa), con un dizionario italiano esteso di 270K lemmi circa.
Sul mio GitHub ho messo una implementazione in Python per i più curiosi.
Resta da affrontare la seconda sfida, generalizzandola il più possibile per le lingue di maggiore utilizzo. In questo ho trovato molto utile il natural Language ToolKit di Python ma c'è tanto da lavorare. Se a qualcuno interessa approfondire, contattatemi in privato!

PS: Il prete GB Agnesi citato all'inizio di questo post era cieco e non aveva processori da sfruttare, eccetto i suoi neuroni. Credo che difficilmente riusciremo a fare meglio di lui ma ci si può provare ;)