Implementazione efficiente di Trie per stringhe Unicode

Question

Implementazione efficiente di Trie per stringhe Unicode

Naviga le tue risposte

#1 da (4 voti)
#2 da (2 voti)

11

Ho cercato un'efficiente implementazione di trie String. Per lo più ho trovato un codice come questo:

Implementazione referenziale in Java (per wikipedia)

Non mi piacciono queste implementazioni principalmente per due motivi:

Supportano solo 256 caratteri ASCII. Ho bisogno di coprire cose come il cirillico.
Sono estremamente inefficienti nella memoria.

Ogni nodo contiene una matrice di 256 riferimenti, che è 4096 byte su a Macchina a 64 bit in Java. Ciascuno di questi nodi può avere fino a 256 sottonodi con 4096 byte di riferimenti ciascuno. Quindi un Trie completo per ogni stringa di caratteri ASCII 2 richiederebbe un po 'più di 1MB. Tre stringhe di caratteri? 256 MB solo per gli array nei nodi. E così via.

Naturalmente non intendo avere tutti i 16 milioni di stringhe di tre caratteri nel mio Trie, quindi molto spazio è solo sprecato. La maggior parte di questi array sono solo riferimenti null poiché la loro capacità supera di gran lunga il numero effettivo di chiavi inserite. E se aggiungo unicode, gli array diventano ancora più grandi (il char ha 64k valori invece di 256 in Java).

C'è qualche speranza di creare un trie efficiente per archi? Ho preso in considerazione un paio di miglioramenti rispetto a questi tipi di implementazioni:

Invece di usare una matrice di riferimenti, potrei usare una matrice di tipo intero primitivo, che indicizza in una matrice di riferimenti a nodi la cui dimensione è vicina al numero di nodi effettivi.
Potrei interrompere le stringhe in parti a 4 bit che consentirebbero array di nodi di dimensione 16 al costo di un albero più profondo.

unicode trie

posta U Mad 05.07.2012 - 13:25

fonte

2 risposte

4

se si codificano le stringhe in UTF8 è possibile utilizzare il trie di 256 ramificazioni standard e ancora compatibile con Unicode

inoltre dovresti notare che solo circa 70 caratteri tra i 128 caratteri ascii possibili (che codificano tutti a 1 byte in UTF8) saranno ottimizzati per questo (come includere i comuni digrammi al posto del caratteri di controllo non utilizzati)

risposta data 05.07.2012 - 14:12

fonte

Leggi altre domande sui tag unicode trie

Entity Framework Entity - Alcuni dati dal servizio Web - La migliore architettura? Const C ++ DRY Strategies

score 2 · Accepted Answer

Per cosa stai usando questo trie? Qual è il numero totale di parole che si intende tenere e qual è la scarsità dei loro personaggi costitutivi? E, cosa più importante, un trie è anche appropriato (rispetto a una semplice mappa di prefisso per l'elenco di parole)?

La tua idea di una tabella intermedia e la sostituzione dei puntatori con gli indici funzioneranno, a condizione che tu abbia un set relativamente piccolo di parole brevi e un set di caratteri sparsi. Altrimenti rischi di rimanere senza spazio nel tuo tavolo intermedio. E a meno che tu non stia guardando un insieme di parole estremamente piccolo, non risparmierai molto spazio: 2 byte per un breve contro 4 byte per un riferimento su un computer a 32 bit. Se stai utilizzando una JVM a 64 bit, i risparmi saranno maggiori.

La tua idea di rompere i personaggi in blocchi di 4 bit probabilmente non ti farà risparmiare molto, a meno che tutti i tuoi personaggi attesi siano in un intervallo estremamente limitato (forse OK per parole limitate a maiuscole US-ASCII, probabilmente con un corpus generale Unicode).

Se hai un set di caratteri sparsi, un HashMap<Character,Map<...>> potrebbe essere la tua migliore implementazione. Sì, ogni voce sarà molto più grande, ma se non hai molte voci otterrai una vittoria generale. (come nota a margine: ho sempre pensato che fosse divertente che l'articolo di Wikipedia su Tries mostrasse - forse lo fa ancora - un esempio basato su una struttura dati hash, ignorando completamente i compromessi spazio / tempo di quella scelta)

Infine, potresti voler evitare un trie del tutto. Se stai guardando un corpus di parole normali in un linguaggio umano (10.000 parole in uso attivo, con parole di 4-8 caratteri), probabilmente sarai MOLTO meglio con un HashMap<String,List<String> , dove la chiave è intero prefisso.