Come ridurre le dimensioni di un database sqlite3 per iPhone?

Question

modifica: molte grazie per tutte le risposte. Ecco i risultati dopo aver applicato le ottimizzazioni finora:

• Passaggio all'ordinamento dei caratteri e alla codifica della lunghezza di esecuzione - nuova dimensione DB 42M
• Eliminazione degli indici sui valori booleani - nuova dimensione DB 33M

La parte davvero bella è che non ha richiesto alcuna modifica al codice iPhone

Ho un'applicazione per iPhone con un dizionario di grandi dimensioni in formato sqlite (sola lettura). Sto cercando idee per ridurre le dimensioni del file DB, che al momento è molto grande.

Ecco il numero di voci e le dimensioni risultanti del DB sqlite:

franks-macbook:DictionaryMaker frank$ ls -lh dictionary.db
-rw-r--r--  1 frank  staff    59M  8 Oct 23:08 dictionary.db
franks-macbook:DictionaryMaker frank$ wc -l dictionary.txt
  453154 dictionary.txt

... una media di circa 135 byte per voce.

Ecco il mio schema DB:

create table words (word text primary key, sowpods boolean, twl boolean, signature text)
create index sowpods_idx on words(sowpods)
create index twl_idx on words(twl)
create index signature_idx on words(signature)

Ecco alcuni dati di esempio:

photoengrave|1|1|10002011000001210101010000
photoengraved|1|1|10012011000001210101010000
photoengraver|1|1|10002011000001210201010000
photoengravers|1|1|10002011000001210211010000
photoengraves|1|1|10002011000001210111010000
photoengraving|1|1|10001021100002210101010000

L'ultimo campo rappresenta le frequenze delle lettere per il recupero degli anagrammi (ogni posizione è compresa nell'intervallo 0..9). I due booleani rappresentano i dizionari secondari.

Devo fare domande come:

select signature from words where word = 'foo'
select word from words where signature = '10001021100002210101010000' order by word asc
select word from words where word like 'foo' order by word asc
select word from words where word = 'foo' and (sowpods='1' or twl='1')

Un'idea che ho è quella di codificare le frequenze delle lettere in modo più efficiente, ad es. binario li codifica come un BLOB (forse con RLE in quanto ci sono molti zeri?). Qualche idea su come raggiungere questo obiettivo o altre idee per ridurne le dimensioni? Sto costruendo il DB in ruby ??e leggendolo al telefono nell'obiettivo C.

C'è anche un modo per ottenere statistiche sul DB in modo che io possa vedere ciò che sta usando più spazio?

Answer 1

Non sono chiaro su tutti i casi d'uso per il campo della firma, ma sembra che salvare una versione alfabetica della parola sarebbe utile.

Answer 2

Hai provato a digitare il " vuoto " comando per assicurarti di non avere spazio extra nel db che hai dimenticato di ricominciare?

Answer 3

Rimuovi gli indici su sowpods e twl - probabilmente non stanno aiutando i tempi delle tue query e stanno sicuramente occupando molto spazio.

Puoi ottenere statistiche sul database usando sqlite3_analyzer dalla pagina dei download di SQLite .

Answer 4

Come approccio completamente diverso, potresti provare a utilizzare un filtro bloom anziché un completo Banca dati. Fondamentalmente, un filtro bloom è costituito da un gruppo di funzioni hash, ognuna delle quali è associata a un bitfield. Per ogni parola legale, viene valutata ogni funzione hash e viene impostato il bit corrispondente nel campo bit corrispondente. Lo svantaggio è teoricamente possibile ottenere falsi positivi, ma questi possono essere minimizzati / praticamente eliminati con abbastanza hash. Il lato positivo è un enorme risparmio di spazio.

Answer 5

Il creatore di SQLite vende una versione di SQLite che include la compressione (e la crittografia) del database. Questo sarebbe perfetto.

Answer 6

La soluzione migliore è utilizzare la compressione, che purtroppo SQLite non supporta nativamente a questo punto. Fortunatamente, qualcuno si è preso il tempo di sviluppare una estensione di compressione che potrebbe essere ciò di cui hai bisogno.

Altrimenti, consiglierei di archiviare i tuoi dati principalmente in formato compresso e non comprimere al volo.

Answer 7

Come campo di testo, firma sta attualmente usando almeno 26 * 8 byte per voce (208 byte) ma se dovessi impacchettare i dati in un campo di bit, probabilmente potresti cavartela solo con 3 bit per lettera (riducendo la frequenza massima per lettera a 7). Ciò significherebbe che potresti impacchettare l'intera firma in 26 * 3 bit = 78 bit = 10 byte. Anche se utilizzassi 4 bit per lettera (per una frequenza massima di 15 per lettera) utilizzeresti solo 104 bit (13 byte).

EDIT: dopo aver pensato un po 'di più, penso che 4 bit per lettera (anziché 3) sarebbe un'idea migliore perché renderebbe più semplice la matematica binaria.

EDIT2: leggendo i documenti su tipi di dati SQLite , sembra che potresti essere in grado di creare semplicemente la "firma" L'estensione del campo 26 colonne di tipo INTEGER e SQLite farà la cosa giusta e utilizzerà solo tutti i bit necessari per memorizzare il valore.

Answer 8

Ritengo correttamente che nel tuo database ci siano circa 450K parole del genere?

Non ho idea di iPhone, né serio su sqlitem ma ... fintanto che sqlite non consente un modo per salvare il file come gz immediatamente (forse lo fa già internamente? no, non sembra così quando dici che è di circa 135 b per voce. nemmeno con entrambi gli indici), mi allontanerei dall'approccio della tabella, salvandolo " manualmente " in un compressione dell'approccio al dizionario e costruisci il resto al volo e in memoria. Ciò dovrebbe funzionare MOLTO bene sul tuo tipo di dati.

Aspetta ... Stai usando quella firma per consentire la ricerca fulltextsearch o il mistyping? ricerca di testo completo su sqlite non obsoleto quel campo?

Answer 9

Come indicato, memorizzazione di " Firma " in modo più efficiente sembra una buona idea.

Tuttavia, sembra anche che tu possa guadagnare un sacco di risparmi di spazio usando una sorta di tabella di ricerca per le parole - dal momento che sembra che tu stia prendendo una parola radice e quindi aggiungendo " er " ;, " ed " ;, " ; es " ;, ecc. perché non avere una colonna con un ID numerico che fa riferimento a una parola radice da una tabella di ricerca separata, e quindi una colonna separata con un ID numerico che fa riferimento a una tabella di suffissi di parole comuni che verrebbero aggiunti alla parola di base .

Se ci fossero dei trucchi nell'archiviare le versioni stenografiche delle firme per più voci con una sola parola radice, potresti anche impiegarle per ridurre le dimensioni delle firme memorizzate (non sei sicuro di quale algoritmo produca quei valori)

Anche questo sembra avere molto senso per me dato che hai la parola "quot" colonna come chiave primaria, ma non indicizzarla, basta creare una colonna numerica separata che sia l'ID principale per la tabella.

Answer 10

mhmm ... un iPhone ... non ha una connessione dati permanente? Penso che sia qui che un'applicazione web / webservice può entrare rapidamente. Sposta la maggior parte della tua logica aziendale sul server web (avrà un vero SQL con FTS e una grande quantità di memoria) e recupera tali informazioni online sul client sul dispositivo.

Answer 11

Come menzionato altrove, perdono gli indici sulle colonne booleane, saranno quasi certamente più lenti (se usati affatto) di una scansione di tabella e useranno lo spazio inutilmente.

Considererei di applicare una semplice compressione alle parole, Huffman coding è abbastanza buono per questo genere di cose. Inoltre, darei un'occhiata alle firme: ordina le colonne in ordine di frequenza delle lettere e non mi preoccupo di memorizzare gli zero finali, il che può essere implicito. Immagino che potresti codificare anche Huffman.

Supponendo sempre che le stringhe codificate non turbino SQLite, ovviamente.