Ingenito Emiddio - Laboratorio di Algoritmi e Strutture dati - Relazione progetto “Parole”

Progetto "Parole", sviluppato in GoLang per l'esame di laboratorio del corso di "Algoritmi e strutture dati". Appello di Luglio 2025

---

Struttura del progetto

La soluzione proposta, si compone di un solo file sorgente “41461A_Ingenito_Emiddio.go”.

Un modulo Go è già fornito nella directory principale. Per la compilazione del sorgente, è sufficiente eseguire il comando go build

Analisi delle richieste e sotto-problemi

L’obiettivo del progetto “Parole”, è la gestione di un dizionario di parole e schemi.

Gli insiemi di parole e schemi, contenuti all’interno del dizionario, non ammettono duplicati, pertanto è necessaria una gestione che tenga conto di tale caratteristica.

La funzione ricerca(S), richiede la verifica della compatibilità delle parole contenute nel dizionario, con uno schema passato come parametro. Per la sua implementazione, è necessaria la memorizzazione di una o più assegnazioni.

La funzione distanza(x,y), richiede il calcolo della distanza di editing tra due parole, definita come il minimo numero di operazioni elementari necessarie per passare da x a y, in cui le operazioni elementari considerate sono quelle di inserzione, eliminazione, trasposizione e rimpiazzamento di un carattere.

Il problema di determinazione di tale distanza, detta anche “distanza di Damerau-Levenshtein”, può essere risolto tramite programmazione dinamica, facendo uso di una matrice di dimensioni (m+1) x (n+1), dove m e n sono rispettivamente le lunghezza delle stringhe x e y, per la memorizzazione dei risultati intermedi.

Lo spazio aggiuntivo necessario per l’applicazione di tale approccio, potrebbe arrivare ad occupare dimensioni molto elevate all’aumentare delle lunghezze delle due stringhe. E’ pertanto necessario identificare una strategia di ottimizzazione di tale algoritmo.

Date due parole x e y, si vuole determinare una catena di parole da x a y di lunghezza minima.

Per risolvere tale problema, è necessario esplorare le parole del dizionario, partendo dalla stringa x, e proseguendo per parole simili ad essa.

Data una parola x, bisogna poter ricavare le parole simili ad essa in maniera efficiente.

La stessa considerazione può esser fatta per quanto riguarda l’implementazione della funzione gruppo.

Definizione del tipo “dizionario”

Dalla traccia, un dizionario deve permettere la memorizzazione di due insiemi senza duplicati di parole e schemi.

Le operazioni di inserimento, eliminazione, ricerca di elementi nei due insiemi, potrebbero essere molto frequenti, ed è pertanto necessario ridurre al minimo i costi di tali operazioni.

Per garantire quanto discusso, è stato scelto di definire i due insiemi di parole e schemi utilizzando l’ADT Set, non disponibile direttamente nel linguaggio Go, implementandolo utilizzando il tipo map.

type StringSet map[string]struct{}

La chiave della mappa è di tipo string, perfetta per la memorizzazione di parole e schemi, come valore invece utilizzo il tipo struct{} come placeholder, in quanto occupa 0 bytes in memoria.

In esso, le operazioni di inserimento, eliminazione, ricerca, avvengono in tempo costante.

Per ogni parola, ho deciso di tener traccia delle parole ad essa simili in una mappa avente per chiave una parola, e per valore uno StringSet di parole simili ad essa, al fine di permetterne una più semplice ed immediata estrazione.

Il tipo dizionario risulta infine definito come una struttura che include i due insiemi di parole e schemi, e la mappa delle parole simili tra loro:

type dizionario struct {
	parole StringSet
	schemi StringSet
	simili map[string]StringSet
}

Popolare la mappa di parole simili

La mappa “simili”, definita all’interno del tipo dizionario, deve permettere di tener traccia, per ogni parola del dizionario, delle parole del dizionario simili ad essa.

Per far si che tale mappa sia tenuta aggiornata, ad ogni operazione di inserimento di una parola nel dizionario, bisogna:

• Verificare se esistono parole già presenti che sono simili alla nuova parola inserita, e aggiornare i rispettivi insiemi di parole simili (aggiungendo la nuova parola)
• Aggiungere una nuova voce in simili, con la nuova parola come chiave, e l’insieme delle parole simili già presenti come valore.

In una prima versione della funzione aggiungi(s), una volta inserita la nuova parola s, si scorreva tutto l’insieme delle parole esistenti e si calcolava per ognuna di esse x la distanza da s tramite la funzione distanza(s, x). Se la distanza era pari a 1, allora le due parole venivano considerate simili e aggiunte reciprocamente ai rispettivi StringSet in simili.

Questa soluzione risultava inefficiente in presenza di molte parole.

Ho deciso allora di tentare un approccio inverso: la funzione aggiungi(s), aggiunge la parola s a dizionario.parole, successivamente effettua una chiamata alla funzione aggiornasimili(s). Quest’ultima utilizza la funzione similiDi(s) per generare tutte le possibili parole che distano una sola operazione (inserzione, cancellazione, sostituzione o trasposizione) da s. Per ognuna di queste parole simili x, si verifica se è già presente nel dizionario: se sì, s e x vengono aggiunte reciprocamente nei rispettivi insiemi in simili.

Confronto delle complessità:

• Soluzione 1: per ogni parola x nel dizionario (contenente un numero $n$ di parole), si calcola distanza(s, x)con costo $O(len(s)^2)$,ipotizzando parole s tutte di pari lunghezza.

  Complessità totale: $O(n⋅len(s)^2)$

• Soluzione 2: si generano tutte le parole a distanza 1 da s, e per ciascuna si verifica la presenza nel dizionario. Se presente, si aggiornano le relative strutture in simili.

  Complessità totale: $O(len(s)^2).$

La seconda soluzione è quindi nettamente più efficiente, soprattutto quando il numero di parole nel dizionario cresce.

Funzioni

Le operazioni indicate nella sezione “Specifiche di progettazione” della traccia del progetto, sono state implementate per mezzo di apposite funzioni.

Ulteriori chiarimenti sulle implementazioni delle funzioni più significativi, sono esposti in paragrafi successivi:

• newDizionario() dizionario - Crea e restituisce un nuovo dizionario vuoto. L’operazione avviene in tempo costante $O(1)$

• (d *dizionario) crea() - Svuota un dizionario già esistente. L’operazione richiede di scorrere singolarmente, gli insiemi di parole, schemi, e parole simili, con una complessità pari alla somma della lunghezza dei 3 insiemi

  $O( ∣ d.parole ∣ + ∣ d.schemi ∣ + ∣ d.simili ∣ )$

• similiDi(w string) []string - Data una parola, genera un insieme di parole simili ad essa. Utilizzata dalla funzione aggiornasimili. Complessità $O(len(w)^2)$

• (d *dizionario) aggiornasimili(w string) - Aggiorna la mappa d.simili, al fine di tenerla consistente a fronte di un’operazione di aggiunta della nuova parola w. Utilizzata dalla funzione aggiungi. La complessità è $O(len(w)^2)$, in quanto la parte dominante è la chiamata a similiDi(w)

• (d *dizionario) aggiungi(w string) - Aggiunge una nuova parola o schema al dizionario d. La complessità dell’operazione è $O(len(w)^2)$, data la chiamata ad aggiornasimili(w), in caso w fosse una parola.

• (d *dizionario) elimina(w string) - Rimuove una parola o schema dal dizionario. Complessità totale $O(len(w) + k)$, dove $k$ è il numero di parole simili a $w$, data la necessità di eliminare la parola $w$ dagli insiemi di parole simili di tutte le altre parole contenute all’interno del dizionario.

• (d *dizionario) stampa_parole() - Stampa l’insieme delle parole del dizionario d. Complessità totale $O(len(d.parole)$

• (d *dizionario) stampa_schemi() - Stampa l’insieme degli schemi del dizionario d. Complessità totale: $O(len(d.schemi))$

• (d *dizionario) wordIsIn(value string) - Restituisce true o false, in base a se la parola value è nel dizionario d. Complessità totale: $O(1)$

• (d *dizionario) ricerca(s string) - Stampa lo schema $s$ e poi l’insieme di tutte le parole nel dizionario che sono compatibili con lo schema $s$.

  Iterando su tutte le parole di lunghezza pari alla lunghezza di $s$ nel dizionario, ed eseguendo per ognuna di esse un confronto carattere per carattere con lo schema s passato come parametro, la complessità totale è $O(m*n)$, dove $m$ è il numero di parole nel dizionario, $n$ la lunghezza dello schema $s$, ipotizzando un caso peggiore in cui tutte le $m$ parole nel dizionario hanno lunghezza pari a $n$.

• (d *dizionario) distanza(x, y string) - Restituisce la distanza di Damerau-Levenshtein tra le parole x e y.

  Eseguendo un confronto carattere per carattere sulle due parole x e y, di lunghezza $m$ ed $n$, il risultato viene computato con complessità temporale $O(m * n)$, ed una complessità spaziale pari ad $O(m)$.

• (d *dizionario) catena(start string, end string) - Cerca il percorso più breve tra due parole (start e end), collegandole tramite trasformazioni di distanza uno, già precomputate nel dizionario nella struttura d.simili.

  Il problema viene modellato come una ricerca di cammino minimo su un grafo non orientato, in cui ogni nodo rappresenta una parola, e un arco collega due parole se sono a distanza 1.

  La funzione implementa una BFS (ricerca in ampiezza), che visita ogni nodo al massimo una volta e per ciascun nodo visita tutti i vicini.

  Complessità totale: $O(V+E)$, dove $V$ è il numero di parole nel dizionario, $E$ è il numero di relazioni di similitudine effettivamente presenti.

  In pratica, l’esplorazione si ferma non appena viene raggiunta la parola di destinazione, quindi nella maggior parte dei casi reali la funzione è molto più efficiente del caso pessimo.

• (d *dizionario) gruppo(start string) - Stampa il gruppo delle parole che contiene la parola start. Se start non è nel dizionario, stampa “non esiste”.

  Anche questa funzione utilizza una BFS per esplorare il grafo delle parole, rappresentato implicitamente dalla struttura d.simili. Il grafo è non orientato e ha come nodi le parole del dizionario, con un arco tra due parole se sono a distanza 1.

  L’obiettivo è visitare tutti i nodi raggiungibili a partire da start, ovvero determinare la componente connessa del grafo in cui essa si trova.

  Complessità totale: $O(V+E)$, dove $V$ è il numero di parole nel dizionario, $E$ è il numero di relazioni di similitudine effettivamente presenti.

  A differenza della funzione catena, che può terminare non appena raggiunge il nodo di destinazione, gruppo visita sempre tutta la componente connessa, quindi la probabilità che essa esplori l’intero grafo è più elevata.

Rappresentazione delle assegnazioni in “ricerca”

La funzione ricerca, riceve uno schema S come parametro, e scorre l’insieme delle parole contenute nel dizionario, al fine di identificare le parole compatibili con tale schema.

Per eseguire tale operazione, è necessario tener traccia delle assegnazioni definite per ogni parola da verificare.

Essendo un’assegnazione una corrispondenza tra un carattere maiuscolo ed uno minuscolo, la soluzione più semplice è rappresentarle con una mappa assegnazioni:=map[rune]rune

Funzione “distanza”

Il calcolo della distanza di Damerau-Levenshtein tra due parole, è un classico problema di programmazione dinamica, nella cui soluzione classica, che si basa sull’algoritmo di Wagner–Fischer si mantiene in memoria una matrice bidimensionale di dimensione (m+1) x (n+1), dove m e n sono rispettivamente le lunghezza delle parole considerate.

Sono riuscito a migliorare l’efficienza di tale soluzione attraverso due strategie principali: la memorizzazione parziale e il controllo dei casi banali.

La funzione “distanza” implementata, evita il calcolo della distanza completa quando per le due parole x e y esiste un valore in dizionario.simili[x][y], restituendo subito il valore 1.

Inoltre, per calcolare la distanza di Damerau-Levenshtein, non viene mantenuta in memoria l’intera matrice bidimensionale dei costi, ma solo tre righe.

Questo consente di ridurre l’uso di memoria da $O(n·m)$ a $O(n)$, dove $n$ è la lunghezza della parola più corta, mantenendo la correttezza anche in presenza di trasposizioni.

Entrambe le ottimizzazioni rendono la funzione più efficiente sia in termini di tempo che di spazio.

Funzione “catena”

La funzione catena ha lo scopo di stampare una catena di lunghezza minima tra due parole x e y, entrambe presenti nel dizionario. Per risolvere questo problema, consideriamo un grafo non orientato costruito in questo modo:

• Ogni nodo del grafo rappresenta una parola del dizionario.
• Esiste un arco tra due nodi se le parole corrispondenti sono a distanza 1, cioè differiscono per una singola trasformazione.

Questo grafo è rappresentato implicitamente nella mappa simili, definita come map[string]StringSet, che funziona come una lista di adiacenza: per ogni parola a, l'insieme d.simili[a] contiene tutte le parole b tali che a e b sono simili (ovvero distanza(a, b) == 1).

Per trovare il cammino minimo tra x e y, si utilizza una ricerca in ampiezza (BFS), che si basa su due strutture dati fondamentali:

• una coda FIFO per gestire l'ordine di esplorazione;
• un insieme dei nodi visitati per evitare visite ripetute e cicli infiniti.

La coda FIFO, è implementata usando una slice di stringhe, nella quale gli elementi vengono aggiunti in coda mediante l’operazione append. Al posto di rimuovere la parola visitata ad ogni passo d’esecuzione dell’algoritmo di ricerca, ho deciso di evitare l’operazione di subslicing, tenendo conto di un indice che, incrementato ad ogni passo d’esecuzione dell’algoritmo di ricerca, permetta di tener traccia della prossima parola da visitare.

L’insieme delle parole visitate, è gestito tramite uno StringSet, definito come precedentemente indicato, al fine di trarre vantaggio dei costi unitari per le operazioni di aggiunta e ricerca di parole al suo interno.

La visita inizia dalla parola x, e si propaga esplorando tutte le parole simili, cioè a distanza 1, fino a raggiungere la parola y. La BFS garantisce che il primo cammino trovato verso y sia anche il più corto possibile.

Per ricostruire il cammino minimo alla fine della ricerca, si utilizza una “tabella dei padri”, implementata tramite una mappa da stringhe a stringhe padri. Una volta raggiunta y, il cammino viene ricostruito all’indietro, risalendo da y fino a x seguendo i padri, e stampato in ordine inverso, da x a y

Funzione “gruppo”

La funzione gruppo permette di individuare tutte le parole appartenenti alla componente connessa del grafo introdotto nella funzione catena, a cui appartiene la parola fornita in input.

Anche in questo caso, il problema viene modellato come l’esplorazione di un grafo non orientato, rappresentato implicitamente dalla mappa simili, che funge da lista di adiacenza indicando quali parole sono collegate da un arco.

La soluzione viene nuovamente realizzata tramite una ricerca in ampiezza (BFS), che fa uso di una coda FIFO, e un insieme di nodi già visitati, implementati e gestiti come indicato per la funzione “catena”.

La visita inizia dalla parola passata alla funzione come parametro, quindi procede esplorando tutte le parole simili (cioè i nodi adiacenti nel grafo, contenuti in d.simili) non ancora visitate, fino a visitare tutte le parole del gruppo connesso.

Casi limite

Facendo riferimento al file “100k_parole.txt”, nella quale sono contenute 100000 parole generate casualmente di dimensione massima pari a 26 caratteri, l’operazione di inserimento delle parole contenute al suo interno mostra i suoi limiti:

PS C:\Users\ingen\Desktop\UniMI\Algorithm & data structures\41461A_Ingenito_Emiddio_Parola_ADS> Measure-Command {.\41461A_Ingenito_Emiddio.exe}
c 100k_parole.txt
t

Days              : 0
Hours             : 0
Minutes           : 0
Seconds           : 13
Milliseconds      : 437
Ticks             : 134378495
TotalDays         : 0,000155530665509259
TotalHours        : 0,00373273597222222
TotalMinutes      : 0,223964158333333
TotalSeconds      : 13,4378495
TotalMilliseconds : 13437,8495

Il file “test_grande.txt”, contiene i comandi per l’inserimento di 1000 parole da 50 caratteri l’una, e per l’esecuzione di 10 operazioni “catena”, 10 “distanza”, 10 “gruppo”.

La soluzione implementata, permette di terminare l’esecuzione in circa 1 secondo.

Measure-Command {Get-Content .\test_grande.txt | .\41461A_Ingenito_Emiddio.exe >> output.txt}       

Ticks             : 10971731
TotalDays         : 1,26987627314815E-05
TotalHours        : 0,000304770305555556
TotalMinutes      : 0,0182862183333333
TotalSeconds      : 1,0971731
TotalMilliseconds : 1097,1731

Esempi d’esecuzione

Input:

i abcdef i ghijkl i mnopqr r AAAAAA

Output:

AAAAAA:[ ]

(Lo schema richiede che tutte e 6 le lettere siano uguali, nessuna parola soddisfa questa condizione)

Input:

c i alfa i alfb i alfc i beta i betb i betc g alfa g beta t

Output:

[ alfa alfb alfc ] [ beta betb betc ]

Input:

c i aa i ab i bb i bc i cc i cd i dd c aa dd t

Output:

( aa ab bb bc cc cd dd )

Input:

c i luna i sole i stella g luna g sole t

Output:

[ luna ] [ sole ]