Algoritmo di compressione per la codifica di elenchi di parole

Question

Sto cercando suggerimenti o riferimenti specifici a un algoritmo e / o strutture di dati per codificare un elenco di parole in quello che sarebbe effettivamente un dizionario di controllo ortografico. Gli obiettivi di questo schema porterebbero a un rapporto di compressione molto elevato dell'elenco di parole non elaborate nella forma codificata. L'unico requisito di output che ho nel dizionario codificato è che qualsiasi parola di destinazione proposta può essere testata per l'esistenza contro l'elenco di parole originale in modo relativamente efficiente. Ad esempio, l'applicazione potrebbe voler controllare 10.000 parole con un dizionario di 100.000 parole. È non un requisito per il modulo del dizionario codificato per poter essere [facilmente] convertito nuovamente nel modulo originale dell'elenco di parole - un risultato binario sì / no è tutto ciò che è necessario per ogni parola testata rispetto al dizionario risultante.

Suppongo che lo schema di codifica, per migliorare il rapporto di compressione, trarrebbe vantaggio da strutture note in un determinato linguaggio come forme singolari e plurali, forme possessive, contrazioni, ecc. Sono specificamente interessato a codificare principalmente parole inglesi, ma per essere chiari, lo schema deve essere in grado di codificare qualsiasi testo ASCII "parole".

La particolare applicazione che ho in mente si può presumere sia per i dispositivi embedded in cui lo spazio di archiviazione non volatile è un premio e il dizionario sarebbe un'area di memoria di sola lettura accessibile in modo casuale.

EDIT : per riassumere i requisiti del dizionario:

• zero falsi positivi
• zero falsi negativi
• rapporto di compressione molto elevato
• nessuna necessità di decompressione

Answer 1

Vedi di McIlroy " Sviluppo di un elenco di ortografia " all'indirizzo la sua pagina dei pub . Classica vecchia carta sul controllo ortografico su un minicomputer, i cui vincoli sono sorprendentemente ben associati a quelli che hai elencato. Analisi dettagliata dell'eliminazione dell'affisso e due diversi metodi di compressione: filtri Bloom e uno schema correlato Huffman che codifica un bitset sparse; Preferirei i filtri Bloom preferibilmente al metodo che ha scelto, che spinge qualche altro kB a un costo significativo in termini di velocità. ( Programming Pearls ha un breve capitolo su questo documento.)

Vedi anche i metodi utilizzati per memorizzare il lessico nei sistemi di ricerca full-text, ad es. Introduzione al recupero delle informazioni . A differenza dei metodi di cui sopra, questo non ha falsi positivi.

Answer 2

A Bloom Filter ( http://en.wikipedia.org/wiki/Bloom_filter e http://www.coolsnap.net/kevin/?p=13 ) è una struttura di dati utilizzata per memorizzare le parole del dizionario in modo molto compatto in alcuni correttori ortografici. Esiste tuttavia il rischio di falsi positivi.

Answer 3

Suggerirei un albero di suffisso imbottito. Buona compressione negli elenchi di parole e tempi di ricerca eccellenti.

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

Answer 4

Per riassumere:

• zero falsi positivi
• zero falsi negativi
• alto rapporto di compressione
• nessuna necessità di inversa (cioè nessuna decompressione necessaria)

Stavo per suggerire filtri Bloom, ma questi hanno falsi positivi diversi da zero.

Invece, Programming Pearls parla di un insieme simile di requisiti ( / usr / share / dict / words in 41K).

Questo ha preso l'approccio della contrazione degli steli: Ad esempio: inviato era il root, quindi potrebbero essere state aggiunte correzioni pre e post:

• presente
• rappresentare
• Rappresentanza
• false dichiarazioni

Answer 5

È possibile ottenere un rapporto di compressione del 30% + dalla memorizzazione delle parole come suffissi successivi in ??formato a 7 bit. Non sono sicuro di come si chiama, ma si traduce abbastanza efficacemente in una struttura ad albero.

es .: a + n + d + s | an + d + y | e + ES + roid

è di 26 caratteri, rispetto a:

una un anno Domini come e qualunque ande Android

che è 33.

Fattorizzazione con un rapporto di compressione del 12,5% per l'archiviazione come contenuto a 7 bit, ovvero circa il 31% di compressione totale. Il rapporto di compressione dipende, ovviamente, dalle dimensioni e dal contenuto del tuo elenco di parole.

Trasformandolo in una struttura ad albero a 26 radici si otterrebbero probabilmente ricerche più veloci di un confronto di sottostringhe in testo normale rispetto a un file flat.

Vieni a pensarci bene, se usi solo 26 caratteri più due per i delimitatori, puoi fare tutto in 5 bit, ovvero una compressione del 37,5% in sé e per sé, portando l'esempio sopra a una compressione superiore al 50% tasso.

Answer 6

Penso che la tua scommessa migliore sia un Albero dei suffissi compressi / Array di suffissi compressi . Puoi trovare molte informazioni nei link sopra. Questa è un'area di ricerca in corso, davvero molto interessante.

Answer 7

Non sono un esperto in questo, ma non è prefix tree praticamente soluzione standard a questo? Ciò memorizza i prefissi comuni di parole una sola volta.

Answer 8

Per pura compressione, il sito Compressione massima offre alcuni risultati per 4 MB elenco di parole inglesi, il miglior programma lo comprime a circa 400 KB. Alcune altre risorse di compressione per la compressione di testi / parole sono la pagina del premio Hutter e la Benchmark di compressione di testi di grandi dimensioni .

Answer 9

Knuth menziona un " Patricia trie " in L'arte della programmazione informatica vol. 3 . Non l'ho mai usato per nessun vero lavoro, ma forse sarebbe utile.

modifica: qual è il tuo vincolo RAM? Se hai molta più RAM della ROM disponibile, forse la compressione dei dati nella ROM (che richiede la decompressione nella RAM) è la strada giusta da percorrere. Suppongo che se hai una quantità media, ma non grande, di RAM, tecnicamente potresti anche memorizzare parti della struttura dei dati come BLOB compressi in memoria e una cache utilizzata meno di recente per mantenerne diverse, quindi decomprimere dinamicamente l'appropriata BLOB quando non è nella cache.