Trie salva spazio, ma come?

Question

Sono confuso su come l'implementazione Trie risparmia spazio & memorizza i dati nella forma più compatta!

Se si guarda l'albero sottostante. Quando si memorizza un carattere su qualsiasi nodo, è inoltre necessario memorizzare un riferimento a quello &, quindi per ogni carattere della stringa è necessario memorizzare il suo riferimento. Ok, abbiamo salvato spazio quando è arrivato un personaggio comune, ma abbiamo perso più spazio nell'archiviazione di un riferimento a quel nodo di caratteri.

Quindi non c'è un sovraccarico strutturale per mantenere questo stesso albero? Invece se fosse stata usata una TreeMap al posto di questa, diciamo di implementare un dizionario, questo avrebbe potuto risparmiare molto più spazio dato che la stringa sarebbe stata mantenuta in un unico pezzo, quindi nessuno spazio sprecato nella memorizzazione dei riferimenti, non è vero?

Answer 1

Si potrebbe dedurne che risparmiare spazio è su una macchina ideale in cui ogni byte è allocato in modo efficiente. Tuttavia le macchine reali allocano blocchi di memoria allineati (8 byte su Java e 16 byte su un C++) e quindi non può salvare spazio.

Java stringhe e collezioni aggiungere quantità relativamente elevata di sopra la testa in modo dalla differenza percentuale può essere molto piccola.

A meno che la struttura è molto grande il valore del vostro tempo fuori pesi il costo della memoria che l'utilizzo il più semplice, più normale e più facile da mantenere collezione è molto più importante. per esempio. il tuo tempo può facilmente valere 1000 volte o più il valore della memoria che stai cercando di salvare.

ad es. dì che hai 10000 nomi che puoi salvare 16 byte ciascuno usando un trie. (Supponendo che ciò possa essere provato senza impiegare più tempo) Questo equivale a 16 KB, che ai prezzi attuali vale 0,1 centesimi. Se il tuo tempo costa $ 30 all'azienda, il costo di scrivere una riga di codice testato potrebbe essere $ 1.

Se hai pensarci un batter d'occhio più per salvare 16 KB, la sua improbabile che sia valsa la pena per un PC. (I dispositivi mobili sono una storia diversa, ma lo stesso ragionamento si applica IMHO)

EDIT: Si hanno ispirato me aggiunga un aggiornamento http://vanillajava.blogspot.com/2011/11/ever-decreasing-cost-of-main-memory.html

Answer 2

spazio viene salvato quando hai un sacco di parole di essere rappresentati da l'albero. Perché molte parole condividono lo stesso percorso nell'albero; più parole hai, più spazio risparmierai.

Ma c'è una struttura dati migliore se si desidera risparmiare spazio. Trie non risparmia tanto quanto fa lo directed acyclic word graph (DAWG), perché condivide il nodo comune in tutta la struttura, mentre trie non condivide i nodi. Lo wiki entry spiega questo dettaglio, quindi dai un'occhiata.

Ecco la differenza (graficamente) tra Trie e DAWG:

Lo stringhe "tap", "rubinetti", "superiore" e "Top" memorizzata in un trie (a sinistra) e un DAWG (a destra), EOW sta per End-of-word.

L'albero sul lato sinistro è Trie e l'albero a destra è DAWG. Confrontali e guarda come DAWG risparmia spazio in modo efficiente. Trie ha nodi duplicati che rappresentano la stessa lettera/sottotabella, mentre DAWG ha esattamente un nodo per ogni lettera/sottotabella.

Answer 3

per risparmiare spazio quando si utilizza un trie, si può usare un compressed trie (noto anche come un trie patricia o un albero radice), per il quale un nodo può rappresentare più caratteri:

In informatica, un radix tree (anche patricia trie o radix trie) è una struttura dati trie ottimizzata per lo spazio in cui ogni nodo con un solo figlio viene unito al figlio. Il risultato è che ogni nodo interno ha almeno due figli. A differenza dei tentativi regolari, i bordi possono essere etichettati con sequenze di caratteri e singoli caratteri. Ciò li rende molto più efficienti per i piccoli set (specialmente se le stringhe sono lunghe) e per gli insiemi di stringhe che condividono i prefissi lunghi.

Esempio di un albero radicato:

noti che un trie viene generalmente utilizzato come struttura dati efficiente per corrispondenza prefisso su un insieme di stringhe. Un trie può anche essere usato come un array associativo (come una tabella hash) in cui la chiave è una stringa.

Answer 4

Non si tratta di uno spazio economico in memoria, è lo spazio su prezioso in un file o su un collegamento di comunicazione. Con un algoritmo che costruisce quel trie, possiamo inviare 'dieci' in tre bit, sinistra-destra-destra. Rispetto ai 24 bit, i "dieci" non occuperebbero spazio non compresso, si tratta di un enorme risparmio di spazio su disco prezioso o di trasferimento della larghezza di banda.

Answer 5

Guava può infatti memorizzare la chiave ad ogni livello, ma il punto da capire è che la la chiave non ha davvero bisogno di essere archiviata perché il percorso del nodo definisce completamente la chiave per quel nodo. Tutto ciò che in realtà deve essere memorizzato in ogni nodo è un singolo booleano che indica se questo è un nodo foglia o no.

Tentativi, come qualsiasi altra struttura, eccellono a memorizzare alcuni tipi di dati. In particolare, i tentativi sono migliori per memorizzare stringhe che condividono una radice comune. Pensa di memorizzare elenchi di directory a percorso completo, ad esempio.