Come faccio a scegliere tra una tabella hash e un trie (albero dei prefissi)?

Question

Quindi, se devo scegliere tra una tabella hash o un albero di prefisso quali sono i fattori discriminanti che mi porterebbero a scegliere l'uno rispetto all'altro. Dal mio punto di vista ingenuo sembra che l'uso di un trie abbia un sovraccarico aggiuntivo poiché non è archiviato come un array ma che in termini di tempo di esecuzione (supponendo che la chiave più lunga sia la parola inglese più lunga) può essere essenzialmente O (1) (in relazione al limite superiore). Forse la parola inglese più lunga è di 50 caratteri?

Le tabelle hash sono una ricerca istantanea una volta ottenuto l'indice . Hashing la chiave per ottenere l'indice sembra tuttavia che potrebbe facilmente richiedere quasi 50 passaggi.

Qualcuno può fornirmi una prospettiva più esperta su questo? Grazie!

Answer 1

Vantaggi dei tentativi:

Le basi:

• Tempo di ricerca O (k) prevedibile in cui k è la dimensione della chiave
• La ricerca può richiedere meno di k tempo se non è presente
• Supporta l'attraversamento ordinato
• Non c'è bisogno di una funzione hash
• La cancellazione è semplice

Nuove operazioni:

• Puoi cercare rapidamente i prefissi delle chiavi, enumerare tutte le voci con un determinato prefisso, ecc.

Vantaggi della struttura collegata:

• Se ci sono molti prefissi comuni, lo spazio richiesto è condiviso.
• I tentativi immutabili possono condividere la struttura. Invece di aggiornare un trie sul posto, puoi crearne uno nuovo diverso solo lungo un ramo, altrove puntando al vecchio trie. Questo può essere utile per la concorrenza, più versioni simultanee di una tabella, ecc.
• Un trie immutabile è comprimibile. Cioè, può condividere la struttura anche sui suffissi , mediante hash-consing.

Vantaggi degli hashtables:

• Tutti conoscono gli hashtable, giusto? Il tuo sistema avrà già un'implementazione ben ottimizzata, più veloce di quella per la maggior parte degli scopi.
• Le tue chiavi non devono avere alcuna struttura speciale.
• Più efficiente in termini di spazio rispetto all'ovvia struttura trie collegata ( vedi commenti sotto )

Answer 2

Tutto dipende dal problema che stai cercando di risolvere. Se tutto ciò che devi fare sono inserimenti e ricerche, scegli una tabella hash. Se devi risolvere problemi più complessi come le query relative ai prefissi, allora un trie potrebbe essere la soluzione migliore.

Answer 3

Tutti conoscono la tabella hash e i suoi usi ma non è esattamente un tempo di ricerca costante, dipende da quanto è grande la tabella hash, dalla complessità computazionale della funzione hash.

La creazione di enormi tabelle hash per una ricerca efficiente non è una soluzione elegante nella maggior parte degli scenari industriali in cui contano anche piccole latenze / scalabilità (ad es. trading ad alta frequenza). Devi preoccuparti delle strutture di dati da ottimizzare per lo spazio che occupa anche in memoria per ridurre la mancanza di cache.

Un ottimo esempio in cui trie soddisfa meglio i requisiti è il middleware di messaggistica. Hai un milione di abbonati ed editori di messaggi in varie categorie (in termini JMS - Argomenti o scambi), in questi casi se vuoi filtrare i messaggi in base agli argomenti (che sono in realtà stringhe), non vuoi assolutamente creare una tabella hash per il milione di abbonamenti con milioni di argomenti. Un approccio migliore è archiviare gli argomenti in trie, quindi quando il filtro viene eseguito in base alla corrispondenza degli argomenti, la sua complessità è indipendente dal numero di argomenti / sottoscrizioni / editori (dipende solo dalla lunghezza della stringa). Mi piace perché puoi essere creativo con questa struttura di dati per ottimizzare i requisiti di spazio e quindi avere una mancanza di cache inferiore.

Answer 4

Usa un albero:

1. Se hai bisogno della funzione di completamento automatico
2. Trova tutte le parole che iniziano con 'a' o 'ax' e così via.
3. Un albero di suffisso è una forma speciale di un albero. Gli alberi dei suffissi hanno un intero elenco di vantaggi che l'hash non può coprire.

Answer 5

L'implementazione

HashTable è efficiente in termini di spazio rispetto all'implementazione di base Trie . Ma con le stringhe, l'ordinamento è necessario nella maggior parte delle applicazioni pratiche. Ma HashTable disturba totalmente l'ordine lessicale. Ora, se la tua applicazione sta eseguendo operazioni basate sull'ordine lessicale (come la ricerca parziale, tutte le stringhe con prefisso specificato, tutte le parole in ordine ordinato), dovresti usare Tries. Per la sola ricerca, è necessario utilizzare HashTable (come probabilmente, fornisce un tempo di ricerca minimo).

P.S .: Oltre a questi, Alberi di ricerca ternaria (TST) sarebbe una scelta eccellente. Il tempo di ricerca è più che HashTable, ma è efficiente in tutte le altre operazioni. Inoltre, è più efficiente dello spazio rispetto ai tentativi.

Answer 6

C'è qualcosa che non ho visto nessuno menzionare esplicitamente che penso sia importante tenere a mente. Sia le tabelle hash che i tentativi di vario tipo avranno tipicamente operazioni O (k) , dove k è la lunghezza della stringa in bit (o equivalentemente in caratteri).

Questo presuppone che tu abbia una buona funzione hash. Se non vuoi " farm " e "animali da fattoria" per eseguire lo hash con lo stesso valore, quindi la funzione hash dovrà utilizzare tutti i bit della chiave, quindi hashing "animali da fattoria" dovrebbe impiegare circa il doppio del tempo di "farm" (a meno che tu non sia in una sorta di scenario di hash rolling, ma ci sono anche scenari simili di salvataggio delle operazioni con try). E con un tentativo alla vaniglia, è chiaro perché inserire " animali da fattoria " impiegherà circa il doppio della durata di "fattoria". A lungo termine è vero anche con i tentativi compressi.

Answer 7

L'inserimento e la ricerca in un trie sono lineari con la lunghezza della stringa di input O (s).

Un hash ti darà una O (1) per la ricerca e l'inserimento, ma prima devi calcolare l'hash in base alla stringa di input che è di nuovo O (s).

Conclusa, la complessità temporale asintotica è lineare in entrambi i casi.

Il trie ha un certo sovraccarico dal punto di vista dei dati, ma puoi scegliere un trie compresso che ti metterà di nuovo, più o meno in pareggio con la tabella hash.

Per spezzare il pareggio, poniti questa domanda: devo cercare solo parole intere? O devo restituire tutte le parole corrispondenti a un prefisso? (Come in un sistema di scrittura intuitivo). Per il primo caso, scegli un hash. È un codice più semplice e più pulito. Più facile da testare e mantenere. Per un caso d'uso più elaborato in cui i prefissi o i suffissi contano, scegli un trie.

E se lo fai solo per divertimento, l'implementazione di un trie renderebbe utile una domenica pomeriggio.

Answer 8

Alcune applicazioni (solitamente incorporate, in tempo reale) richiedono che il tempo di elaborazione sia indipendente dai dati. In tal caso, una tabella hash può garantire un tempo di esecuzione noto, mentre un trie varia in base ai dati.