prova

Trie che memorizza le stringhe Java , Rad , Edge , Rau , Raum e Rose

Un albero trie o prefisso è una struttura di dati utilizzata in informatica per cercare stringhe di caratteri . È uno speciale albero di ricerca per la memorizzazione simultanea di più stringhe di caratteri. I tentativi contengono un tipo di compressione dei dati , poiché i prefissi comuni delle stringhe di caratteri vengono salvati solo una volta.

Un trie è costituito da un insieme di stringhe arbitrarie. Ogni bordo in uscita di un nodo all'interno di un triangolo è dotato di un singolo carattere, in modo che un percorso che inizia dalla radice e termina con una foglia nel triangolo rappresenta una delle stringhe di caratteri da cui è stato costruito l'albero.

I tentativi vengono utilizzati nell'area del recupero delle informazioni . Lì vengono utilizzati per indicizzare i testi al fine di rispondere in modo efficiente a determinate domande sul testo.

I tentativi compatti o Patricia (una variante speciale dei tentativi compatti) sono varianti dei tentativi ottimizzati in termini di consumo di spazio di memoria. Tutti i nodi da cui parte un solo bordo vengono raggruppati con i rispettivi successori.

Il termine trie è stato suggerito da Edward Fredkin sulla base del termine information re trie val . Questo autore lo pronuncia come il termine inglese albero [ 'triː ]. Un'altra pronuncia comune è come il termine inglese prova [ 'traɪ ], che verbalmente distingue trie dalla struttura dati albero . Questa seconda variante si è nel frattempo affermata.

definizione

Sia un insieme di stringhe sull'alfabeto con size = . Un trie over è un albero di forma , dove si trova l'insieme di nodi e l'insieme di bordi, che ha le seguenti proprietà:${\ displaystyle S = \ {S_ {1}, \ dots, S_ {k} \}}$${\ displaystyle k}$${\ displaystyle \ Sigma}$${\ displaystyle \ sigma}$${\ displaystyle | \ Sigma |}$${\ displaystyle S}$${\ displaystyle T = (V, E)}$${\ displaystyle V}$${\ displaystyle E}$

• ${\ displaystyle \ forall e \ in E \ colon e}$ha un'etichetta dell'alfabeto ,${\ displaystyle \ Sigma}$
• ${\ displaystyle \ forall v \ in V \ due punti}$tutti i bordi in uscita del nodo hanno un'etichetta diversa ,${\ displaystyle v}$${\ displaystyle a \ in \ Sigma}$
• ${\ displaystyle \ forall S_ {i} \ in S \ due punti}$c'è un nodo , in modo che un prefisso della concatenazione delle etichette del percorso inizi con la radice fino al nodo (questi nodi sono appositamente contrassegnati nel trie, ad esempio impostando un bit),${\ displaystyle v}$${\ displaystyle S_ {i}}$${\ displaystyle v}$
• ${\ displaystyle \ forall}$Foglie c'è una stringa in modo che il percorso dalla radice alla foglia sia scritto esattamente .${\ displaystyle b \ in V \ due punti}$${\ displaystyle S_ {i} \ in S}$${\ displaystyle b}$${\ displaystyle S_ {i}}$

Un esempio di un trie over = {"Java", "Rad", "Edge", "Rau", "Raum", "Rose"} può essere visto nell'immagine, in cui i nodi a doppio bordo rappresentano le stringhe di caratteri . Si noti in particolare che la parola "grezzo" è un prefisso della parola "spazio"; H. una stringa da può essere il prefisso di un'altra. ${\ displaystyle S}$${\ displaystyle S}$${\ displaystyle S}$

Applicazioni

Con l'aiuto dei tentativi, è possibile eseguire query diverse su un determinato insieme di stringhe di caratteri diverse . Le richieste di esempio potrebbero essere:${\ displaystyle S}$

• Richieste di esistenza del tipo “ Il modello contiene ? ${\ displaystyle S}$${\ displaystyle M}$"
• Query con prefisso del tipo “ Quali stringhe iniziano con il pattern ? ${\ displaystyle S}$${\ displaystyle M}$"
• Richieste successive e predecessori come "In quali stringhe di caratteri sono successori lessicografici o predecessori del modello ? ${\ displaystyle S}$${\ displaystyle M}$"

Un possibile utilizzo di Tries potrebbe essere, ad esempio, l'implementazione di query di ricerca all'interno di un'app di rubrica o rubrica per smartphone. I tentativi possono essere utilizzati per cercare persone per nome (richieste di esistenza). Allo stesso modo, quando si inserisce un nome, è possibile visualizzare i contatti i cui nomi iniziano con le lettere precedentemente inserite (query di prefisso). Inoltre, è possibile trovare i contatti presenti nella rubrica dopo o davanti alla persona ricercata (richieste successore e predecessore).

Tipi di implementazione

Per rispondere alle richieste del trie , viene cercato un percorso a un nodo che corrisponde al pattern richiesto secondo il principio top-down, a partire dalla radice . I tempi di esecuzione di queste interrogazioni, così come lo spazio richiesto dai tentativi, dipendono fortemente da come viene implementata la memorizzazione delle connessioni in uscita. Di seguito vengono presentati alcuni dei possibili tipi di implementazione:${\ displaystyle M}$

1. Una semplice variante consiste nel salvare tutti i bordi in uscita per nodo in un elenco . Ciò si traduce in un tempo di esecuzione di . Il requisito di spazio di questa soluzione è , dove è indicata la lunghezza totale di tutte le stringhe .${\ displaystyle O (| M | \ cdot | \ Sigma |)}$${\ displaystyle O (n)}$${\ displaystyle n = \ sum _ {i = 1} ^ {k} | s_ {i} |}$${\ displaystyle S}$
2. Nella variante successiva, i bordi in uscita sono tenuti in un array ordinato per ogni nodo invece che in un elenco . Utilizzando la ricerca binaria per trovare il bordo successore, si ottiene un tempo di esecuzione di . Lo spazio necessario corrisponde a quello della variante 1 ed è quindi .${\ displaystyle O (| M | \ cdot \ log | \ Sigma |)}$${\ displaystyle O (n)}$
3. I bordi in uscita vengono memorizzati in una matrice di dimensioni per ogni nodo . Questo raggiunge un runtime di . Qui, tuttavia, il fabbisogno di spazio dei Tries aumenta .${\ displaystyle | \ Sigma |}$${\ displaystyle O (| M |)}$${\ displaystyle O (| \ Sigma | \ cdot n)}$
4. Una tabella hash viene utilizzata per memorizzare i bordi in uscita . Questo può essere creato per nodo o globalmente per l'intero trie. Con entrambe le varianti si ottiene un tempo di esecuzione previsto di . Lo svantaggio di questa variante, tuttavia, è che non può rispondere a domande precedenti o successive (poiché le tabelle hash sono di per sé non ordinate). Questa variante raggiunge un requisito di spazio di .${\ displaystyle O (| M |)}$${\ displaystyle O (n)}$

Confronto tra runtime e requisiti di spazio

variante	tempo di esecuzione	Fabbisogno di spazio
1.	${\ displaystyle O (| M | \ cdot | \ Sigma |)}$	${\ displaystyle O (n)}$
2.	${\ displaystyle O (| M | \ cdot \ log | \ Sigma |)}$	${\ displaystyle O (n)}$
3.	${\ displaystyle O (| M |)}$	${\ displaystyle O (| \ Sigma | \ cdot n)}$
4 °	previsto ${\ displaystyle O (| M |)}$	${\ displaystyle O (n)}$

Guarda anche

• Albero dei suffissi
• Patricia Trie

letteratura

• Rene de la Briandais: File Searching Using Variable Length Keys . Atti della Western Joint Computer Conference, 1959, pp. 295-298, doi : 10.1145 / 1457838.1457895
• Edward Fredkin : Trie Memory . Comunicazioni dell'ACM, 3 (9): 490-499, settembre 1960, doi : 10.1145 / 367390.367400
• Donald E. Knuth : The Art of Computer Programming . Vol. 3, 2a ed. Boston 1998. pp. 492-512.

link internet

• Dizionario di algoritmi e strutture dati del NIST: Trie (inglese)
• Lloyd Allison: Tries (inglese)
• An Implementation of Double-Array Trie (inglese)

Prove individuali

1. ↑ Paul E. Black: trie . In: Dizionario di algoritmi e strutture dati . Istituto nazionale di standard e tecnologia . 16 novembre 2009. Archiviato dall'originale il 19 maggio 2010. Estratto il 7 dicembre 2014.
2. ↑ Donald Knuth : 6.3: Ricerca digitale . In: The Art of Computer Programming Volume 3: Sorting and Searching , 2nd. Edizione, Addison-Wesley, 1997, ISBN 0-201-89685-0 , p. 492.
3. ↑ ^{a b c} Johannes Fischer: copione della lezione "Indicizzazione del testo e recupero delle informazioni" . Semestre invernale 2014/2015. URL consultato il 28 novembre 2014.