Struttura dati efficiente in termini di spazio per la memorizzazione di un elenco di parole?

C’è qualcosa di meglio di un Trie per questa situazione?

  • Memorizzare un elenco di ~ 100k parole inglesi
  • Ha bisogno di usare una memoria minima
  • Le ricerche devono essere ragionevoli, ma non devono essere velocissime

Sto lavorando con Java, quindi il mio primo tentativo è stato quello di usare solo un Set . Tuttavia, sto prendendo di mira un dispositivo mobile e sto già esaurendo la memoria. Dal momento che molte parole inglesi condividono prefissi comuni, un trie sembra una buona scommessa per risparmiare un po ‘di memoria – qualcuno conosce altre buone opzioni?

MODIFICA – Altre informazioni – La struttura dei dati verrà utilizzata per due operazioni

  • Risposta: c’è qualche parola XYZ nella lista?
  • Generare il vicinato di parole attorno a XYZ con una lettera diversa

Grazie per i buoni suggerimenti

Cosa fai? Se si esegue il controllo ortografico, è ansible utilizzare un filtro bloom: vedere questo codice kata .

Una struttura che ho visto per ridurre al minimo lo spazio in un dizionario di ortografia era codificare ogni parola come:

  • il numero di caratteri (un byte) in comune con l’ultimo; e
  • il nuovo finale.

Quindi la lista delle parole

HERE would encode as THIS sanctimonious 0,sanctimonious sanction 6,on sanguine 3,guine trivial 0,trivial 

Stai salvando 7 byte direttamente lì (19%), ho il sospetto che il salvataggio sarebbe simile per un dizionario di 20.000 parole solo a causa delle distanze minime tra (prefissi comuni di) parole adiacenti.

Per velocizzare la ricerca, c’era una tabella di 26 voci in memoria che conteneva gli offset iniziali per le parole che iniziano con a, b, c, …, z. Le parole a questi offset avevano sempre 0 come primo byte in quanto non avevano lettere in comune con la parola precedente.

Questo sembra essere una sorta di trie, ma senza i puntatori, che sicuramente costerebbe molto spazio se ogni personaggio nell’albero avesse un puntatore a 4 byte ad esso associato.

Intendiamoci, questo era il mio CP / M giorni in cui la memoria era molto più scarsa di adesso.

Un trie Patricia potrebbe essere più appropriato:

http://en.wikipedia.org/wiki/Patricia_tree

La mia memoria (fuzzy) mi dice che sono stati utilizzati in alcuni dei primi motori di ricerca full-text …

Paolo.

Devi ancora mantenere la struttura ad albero con Trie. Huffman che codifica l’alfabeto o N-letters (per forms comuni come “tion”, “un”, “ing”) può sfruttare la frequenza di occorrenza nel tuo dizionario e comprimere la voce in bit.

Idea completamente selvaggia … (probabilmente molto sbagliata)

Che ne dici di memorizzare le parole come un albero di tutte le possibili combinazioni di lettere?

Quindi ogni “parola” costa solo un singolo char e due puntatori (uno per il char e uno per un terminatore). In questo modo più lettere hanno in comune meno il costo per ogni parola.

  . . / / rps-. /\\ a \s-. / t-. c \ s-. 

car car carps cars car carrelli

Quindi per 9 caratteri e 14 puntatori otteniamo 6 “parole” per un totale di 25 lettere.

Le ricerche sarebbero veloci (ricerca dei puntatori invece dei confronti dei caratteri) e potresti eseguire alcune ottimizzazioni dello spargimento per risparmiare ancora più spazio …?

EDIT: Sembra che ho reinventato la ruota. 😉

Correlato al post di Paul:

Qualche motivo per cui non puoi considerare un Trie nel tuo caso? Se si tratta solo di un problema di implementazione, ecco una rigorosa implementazione di Patricia trie insert e ricerca in C (da NIST):

Patricia Insert in C

Patricia cerca in C