Costruire un TRIE: differenze tra le versioni
(→prima versione) |
(→bibliografia) |
||
| Riga 1: | Riga 1: | ||
== L'algoritmo di ricerca == | == L'algoritmo di ricerca == | ||
| − | Forse, la prima cosa a cui pensare è l'algoritmo di ricerca. | + | Forse, la prima cosa a cui pensare è '''l'algoritmo di ricerca'''. |
Il campo di testo dello username contiene una stringa.<br> | Il campo di testo dello username contiene una stringa.<br> | ||
| Riga 22: | Riga 22: | ||
---- | ---- | ||
| − | BIBLIOGRAFIA | + | ===BIBLIOGRAFIA=== |
| + | |||
| + | * [http://www.cs.princeton.edu/%7Ers/AlgsDS07/19Tries.pdf| Una lezione teorica sui trie] | ||
| + | * [http://simplestcodings.blogspot.it/2012/11/trie-implementation-in-c.html| Una implementazione in linguaggio C] | ||
| + | * [https://github.com/cloc3/auC| Il nostro programmino di test in linguaggio C] | ||
[[Appunti_Informatici#Una_patch_ad_SDDM|torna all'indice]] | [[Appunti_Informatici#Una_patch_ad_SDDM|torna all'indice]] | ||
Versione delle 09:07, 11 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-.
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 ad una lettera di un'altra parola se le due parole condividono la stessa radice, cioè se tutte le lettere precedenti sono uguali tra loro e se 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.
