Costruire un TRIE: differenze tra le versioni
m (→ritorno) |
(→nuovo sottotitolo) |
||
| (Una versione intermedia di uno stesso utente non è mostrata) | |||
| Riga 9: | Riga 9: | ||
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-. | 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'''.<br> | Per ridurre questo costi è opportuno organizzare la lista degli username in una '''struttura dati'''.<br> | ||
Il [http://en.wikipedia.org/wiki/Trie| trie] può essere una soluzione.<br> | Il [http://en.wikipedia.org/wiki/Trie| trie] può essere una soluzione.<br> | ||
| Riga 15: | Riga 16: | ||
Nel trie, ogni singola lettera è una '''foglia''' di un albero bidimensionale.<br> | Nel trie, ogni singola lettera è una '''foglia''' di un albero bidimensionale.<br> | ||
Le lettere di ogni parola sono collegate sequenzialmente ''in profondità''.<br> | Le lettere di ogni parola sono collegate sequenzialmente ''in profondità''.<br> | ||
| − | Ogni singola foglia, inoltre ''può'' essere legata | + | 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: | Usando una struttura ad albero TRIE si ottengo due vantaggi: | ||
Versione attuale delle 05:21, 12 ago 2016
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.
