Costruire un TRIE
L'algoritmo di ricerca
Forse, la prima cosa a cui pensare è l'algoritmo di ricerca.
Il campo di testo dello username contiene una stringa.
L'autocompletamento deve confrontare questa stringa con tutte le stringhe contenute nella lista degli username noti al sistema e restituire, se esiste, almeno un completamento utile.
Si potrebbe confrontare la stringa di input con ogni singolo elemento della lista degli username.
Questa strategia, però, è poco efficiente, perché obbliga a ripetere la ricerca ad ogni singolo passo, senza riutilizzare le informazioni raccolte con le ricerche precedenti. Algoritmi di questo genere possono impegnare il sistema per più di qualche secondo dopo che ogni singola lettera è stata digitata - si dice che hanno un costo di computazione O2-.
Il Trie
Per ridurre questo costi è opportuno organizzare la lista degli username in una struttura dati.
Il trie può essere una soluzione.
Si tratta di una struttura dati non molto conosciuta, tanto che non possiede neppure una pagina di wikipedia in lingua italiana, ma molto appropriata per la nostra applicazione.
Nel trie, ogni singola lettera è una foglia di un albero bidimensionale.
Le lettere di ogni parola sono collegate sequenzialmente in profondità.
Ogni singola foglia, inoltre, può essere legata in orizzontale a una lettera di un'altra parola se le due parole condividono la stessa radice, cioè se tutte le lettere che la precedono sono uguali tra loro, mentre le lettere collegate sono diverse.
Usando una struttura ad albero TRIE si ottengo due vantaggi:
- si risparmia spazio (prezioso in memoria RAM)): le desinenze comuni di un gruppo di parole sono sempre contenute una sola volta;
- una ricerca non deve mai essere ripetuta due volte. Una volta digitata la lettera a, ad esempio, tutte le parole che non cominciano con a sono escluse automaticamente dalle ricerche successive.
