Cum pot alege între un tabel Hash și un Trie (arbore de prefixe)? (Programare, Algoritm, Structuri De Date, Hashtable, Trie)

Deci, dacă trebuie să aleg între un tabel hash și un arbore de prefixare, care sunt factorii de discriminare care m-ar determina să aleg unul în locul celuilalt. Din punctul meu de vedere naiv, se pare că utilizarea unui trie are unele costuri suplimentare, deoarece nu este stocat ca o matrice, dar în ceea ce privește timpul de execuție (presupunând că cea mai lungă cheie este cel mai lung cuvânt englezesc) poate fi în esență O(1) (în raport cu limita superioară). Poate că cel mai lung cuvânt englezesc este de 50 de caractere?

Tabelele Hash sunt o căutare instantanee odată ce se obține indexul. Cu toate acestea, hashing-ul cheii pentru a obține indexul pare să poată necesita cu ușurință aproape 50 de pași.

Poate cineva să-mi ofere o perspectivă mai experimentată în această privință? Mulțumesc!

Comentarii

  • Este demn de remarcat faptul că un arbore redix este mai eficient decât un trie simplu, deoarece nu aveți nevoie de o nouă ramură pentru fiecare octet de șir. De asemenea, arborii redix oferă suport pentru căutări „fuzzy” mai bine decât tabelele hash, deoarece vă uitați la biți individuali atunci când lucrați în josul căii. De exemplu 00110010 ar putea fi octetul de intrare, dar doriți să includeți corespondența 00111010 care este la doar un bit distanță. –  > Por Xeoncross.
8 răspunsuri

Avantajele încercărilor:

Noțiuni de bază:

  • Timp de căutare predictibil O(k), unde k este dimensiunea cheii.
  • Căutarea poate dura mai puțin de timpul k dacă nu există.
  • Suportă parcurgerea ordonată
  • Nu este nevoie de o funcție hash.
  • Ștergerea este simplă.

Operații noi:

  • Se pot căuta rapid prefixe ale cheilor, se pot enumera toate intrările cu un anumit prefix etc.

Avantajele structurii legate:

  • În cazul în care există multe prefixe comune, spațiul pe care acestea îl necesită este împărțit.
  • Încercările imuabile pot partaja structura. În loc să actualizați o trie pe loc, puteți construi una nouă care este diferită doar de-a lungul unei ramuri, în altă parte arătând spre vechea trie. Acest lucru poate fi util pentru concurență, pentru mai multe versiuni simultane ale unui tabel etc.
  • Un trie imuabil este compresibil. Adică, poate partaja structura pe sufixe de asemenea, prin hash-consumare.

Avantajele tabelelor hash:

  • Toată lumea cunoaște hashtables, nu-i așa? Sistemul dvs. va avea deja o implementare frumoasă și bine optimizată, mai rapidă decât încercările pentru majoritatea scopurilor.
  • Cheile dvs. nu trebuie să aibă o structură specială.
  • Este mai eficientă din punct de vedere al spațiului decât structura evidentă de trie legată (a se vedea comentariile de mai jos)

Comentarii

    30

  • nu pot fi de acord cu „Mai eficientă din punct de vedere al spațiului decât structura evidentă de tip trie legată” — într-o implementare generală a unui tabel hash, se ocupă un spațiu mult mai mare pentru a conține chei, în timp ce în încercări, fiecare nod reprezintă un cuvânt. În acest sens, tries sunt mai eficiente din punct de vedere al spațiului. –  > Por galactica.
  • cum rămâne cu accesarea datelor dintr-o structură față de cealaltă? Mă gândesc la cache și la locație.  > Por Horia Toma.
  • @galactica, asta intră în conflict cu experiența mea: de exemplu, în acest răspuns, dintre toate structurile pe care le-am măsurat pentru spațiu, un trie s-a descurcat cel mai prost. Acest lucru are sens, deoarece un pointer este mult mai mare decât un octet. Da, partajarea prefixelor ajută, dar trebuie să depășească o mulțime de costuri suplimentare pentru a ajunge la paritate. O reprezentare mai eficientă din punct de vedere al spațiului poate ajuta foarte mult, dar atunci nu mai vorbim de structura legată evidentă. –  > Por Darius Bacon.
  • @DariusBacon manipularea planurilor de numerotație telefonică pare un scenariu rezonabil pentru încercări. Exemplu de scenariu: potrivirea numărului de telefon cu operatorul, inclusiv numerele portate de la un operator la altul. Pentru dicționarele obișnuite ar putea depinde de limbă (mandarină vs. engleză), ar fi nevoie de n-grame și/sau alte date statistice. Pentru o carte de rime, un arbore de sufixe pare, de asemenea, o opțiune bună. –  > Por mbx.
  • Diversitatea datelor care trebuie consultate contează foarte mult. Dacă un procent mare din valorile datelor sunt unice, complexitatea spațială va crește în raport cu hash-ul din cauza utilizării unor pointeri nuli suplimentari. –  > Por Găsire de uniune.

Totul depinde de problema pe care încercați să o rezolvați. Dacă tot ceea ce trebuie să faceți sunt inserții și căutări, optați pentru un tabel hash. Dacă aveți nevoie să rezolvați probleme mai complexe, cum ar fi interogările legate de prefixe, atunci o trie ar putea fi o soluție mai bună.

Comentarii

  • Dacă tabela hash și trie au aceeași complexitate la interogare, O(k) pentru șiruri de lungime k, de ce ar trebui să alegem hash? Puteți să explicați? –  > Por Sazzad Hissain Khan.
  • După părerea mea, un tabel hash are calculele asupra șirului de caractere de intrare, în timp ce un trie face căutări de adrese la intrarea șirului de caractere. Căutările de adrese ar putea rata memoria cache, în timp ce calculele sunt efectuate mult mai rapid, deoarece nu ating memoria cache. Aceasta este raționamentul meu, haha. –  > Por Lance Pollard.

Toată lumea cunoaște tabela hash și utilizările sale, dar timpul de căutare nu este chiar constant, ci depinde de cât de mare este tabela hash, de complexitatea de calcul a funcției hash.

Crearea unor tabele hash uriașe pentru o căutare eficientă nu este o soluție elegantă în majoritatea scenariilor industriale în care chiar și o latență/scalabilitate mică contează (de exemplu: tranzacționarea de înaltă frecvență). Trebuie să aveți grijă ca structurile de date să fie optimizate și pentru spațiul pe care îl ocupă în memorie pentru a reduce ratarea cache-ului.

Un exemplu foarte bun în care trie se potrivește mai bine cerințelor este middleware-ul de mesagerie . Aveți un milion de abonați și editori de mesaje la diferite categorii (în termeni JMS – subiecte sau schimburi) , în astfel de cazuri, dacă doriți să filtrați mesajele pe baza subiectelor (care sunt de fapt șiruri de caractere), cu siguranță nu doriți să creați un tabel hash pentru milioanele de abonamente cu milioane de subiecte. O abordare mai bună este stocarea subiectelor în trie , astfel încât, atunci când filtrarea se face pe baza potrivirii subiectelor, complexitatea acesteia este independentă de numărul de subiecte/abonamente/editori (depinde doar de lungimea șirului). Îmi place pentru că puteți fi creativi cu această structură de date pentru a optimiza cerințele de spațiu și, prin urmare, pentru a avea rateuri mai mici în cache.

Utilizați un arbore:

  1. Dacă aveți nevoie de funcția de completare automată
  2. Găsiți toate cuvintele care încep cu „a” sau „axe” și așa mai departe.
  3. Un arbore de sufixe este o formă specială a unui arbore. Arborii de sufixe au o listă întreagă de avantaje pe care hash nu le poate acoperi.

Există un lucru pe care nu am văzut pe nimeni să-l menționeze în mod explicit și pe care cred că este important să-l rețineți. Atât tabelele hash, cât și încercările de diferite tipuri vor avea de obicei O(k) operații, unde k este lungimea șirului în biți (sau, în mod echivalent, în caractere).

Aceasta presupunând că aveți o funcție hash bună. Dacă nu doriți ca „fermă” și „animale de fermă” să aibă aceeași valoare, atunci funcția hash va trebui să utilizeze toți biții cheii, astfel încât hashing-ul „animale de fermă” ar trebui să dureze de două ori mai mult decât „fermă” (cu excepția cazului în care vă aflați într-un scenariu de hash cu rulaj, dar există scenarii de economisire a operațiunilor similare și în cazul încercărilor). Și cu un trie vanilla, este clar de ce inserarea „animale de fermă” va dura aproximativ de două ori mai mult decât doar „fermă”. Pe termen lung, acest lucru este valabil și în cazul încercărilor comprimate.

Inserția și căutarea într-un trie este liniară cu lungimea șirului de intrare O(s).

Un hash vă va oferi un O(1) pentru căutare și inserție, dar mai întâi trebuie să calculați hash-ul pe baza șirului de intrare, ceea ce, din nou, este O(s).

Concluzia: complexitatea asimptotică a timpului este liniară în ambele cazuri.

Trie are ceva mai multe costuri suplimentare din punctul de vedere al datelor, dar puteți alege o trie comprimată care vă va pune din nou, mai mult sau mai puțin la egalitate cu tabela hash.

Pentru a rupe egalitatea, puneți-vă următoarea întrebare: Am nevoie să caut doar cuvinte complete? Sau trebuie să returnez toate cuvintele care corespund unui prefix? (ca într-un sistem de introducere a textului predictiv). În primul caz, optați pentru un hash. Este un cod mai simplu și mai curat. Mai ușor de testat și de întreținut. Pentru un caz de utilizare mai elaborat, în care prefixoanele sau sufixele sunt importante, alegeți un trie.

Iar dacă o faceți doar pentru distracție, implementarea unui trie ar fi o bună utilizare a unei după-amieze de duminică.

Comentarii

  • „Un hash vă va oferi un O(1) pentru căutare și inserție, dar mai întâi trebuie să calculați hash-ul pe baza șirului de intrare, ceea ce, din nou, este O(s).” Vă mulțumim pentru explicații! –  > Por abadawi.
  • Calcularea funcției hash nu este O(s). De fapt, este O(1). Nu aveți nevoie de toți biții șirului de caractere pentru a o calcula, o parte dintre ei (un număr constant) este suficient. –  > Por Nicola Amadio.

HashTable este eficientă din punct de vedere spațial în comparație cu cea de bază Trie de bază Trie. Dar în cazul șirurilor de caractere, ordonarea este necesară în majoritatea aplicațiilor practice. Dar HashTable perturbă total ordinea lexografică. Acum, dacă aplicația dvs. efectuează operații bazate pe ordinea lexografică (cum ar fi căutarea parțială, toate șirurile cu un anumit prefix, toate cuvintele în ordine ordonată), ar trebui să utilizați Tries. Doar pentru căutări, ar trebui să se utilizeze HashTable (deoarece se poate spune că oferă un timp de căutare minim).

P.S.: În afară de acestea, Arbori de căutare ternari (TST) ar fi o alegere excelentă. Timpul său de consultare este mai mare decât HashTable, dar este eficient în timp pentru toate celelalte operațiuni. De asemenea, este mai eficient din punct de vedere al spațiului decât încercările.

Unele aplicații (de obicei, integrate, în timp real) necesită ca timpul de procesare să fie independent de date. În acest caz, un tabel hash poate garanta un timp de execuție cunoscut, în timp ce un trie variază în funcție de date.

Comentarii

  • Majoritatea tabelelor hash nu garantează un timp de execuție cunoscut – cel mai rău caz este O(n), dacă fiecare element se ciocnește și se înlănțuie -.  > Por Adam Rosenfield.
  • Pentru orice set de date, se poate calcula o funcție hash perfectă care va garanta căutări O(1) pentru datele respective. Desigur, calcularea funcției hash perfecte nu este gratuită. –  > Por George V. Reilly.
  • De asemenea, înlănțuirea nu este singura modalitate de a gestiona coliziunile; există tot felul de modalități interesante și inteligente de a gestiona acest lucru – hashing cucuieresc (ro.wikipedia.org/wiki/Cuckoo_hashing), de exemplu, iar cea mai bună alegere depinde de nevoile codului client. –  > Por Hank Gay.
  • nu știam despre cuckoo hashing și relația sa cu filtrul bloom, va fi o lectură interesantă, mulțumesc! –  > Por Horia Toma.
  • Nu uitați de Robin-hood Hashing, care este superior pentru cache și varianță. sebastiansylvan.com/2013/05/08/… codecapsule.com/2013/11/11/11/robin-hood-hashing –  > Por Jarred Nicholls.