Ho una lista enorme di sequenze multi-byte (chiamiamole parole) che ho bisogno di memorizzare in un file e che devo essere in grado di cercare rapidamente. Mezzi enormi: circa 2 milioni di quelli, ogni 10-20 byte di lunghezza.Compressione e ricerca di un enorme elenco di parole
Inoltre, ogni parola deve avere un tag valore associato con esso, in modo che possa utilizzare che per fare riferimento più dati (esterna) per ogni elemento (quindi, dizionario del controllo ortografico non funziona qui che fornisce solo hit-test).
Se questo fosse solo nella memoria, e se la memoria fosse un sacco, ho potuto semplicemente memorizzare tutte le parole in una mappa hash (aka dizionario, alias coppie chiave-valore), o in una lista ordinata per una ricerca binaria.
Tuttavia, mi piacerebbe comprimere i dati molto, e preferirei anche non dover leggere i dati in memoria, ma piuttosto cercare all'interno del file.
Poiché le parole si basano principalmente sulla lingua inglese, c'è una certa probabilità che alcuni "sillable" nelle parole si presentino più spesso di altri - il che è probabilmente utile per un algoritmo efficiente.
Qualcuno può indicarmi una tecnica efficiente o un algoritmo per questo?
O anche esempi di codice?
Aggiornamento
Ho capito che DAWG o niente percorsi simili il percorso nella suffissi comuni in questo modo non funziona per me, perché allora non sarò in grado di etichettare ogni percorso parola completa con un individuo valore. Se dovessi rilevare i suffissi comuni, dovrei inserirli nel loro dizionario (tabella di ricerca) in modo che un trie node possa farvi riferimento, tuttavia il nodo manterrebbe il proprio nodo finale per memorizzare il valore del tag di quel percorso.
In realtà, che è probabilmente la strada da percorrere:
Invece di costruire i nodi della struttura per soli singoli caratteri, potrei cercare di trovare sequenze di caratteri utilizzati più spesso, e fare un nodo per quelli pure. In questo modo, i singoli nodi possono coprire più caratteri, forse portando a una compressione migliore.
Ora, se ciò è fattibile, come troverei effettivamente sotto-sequenze spesso utilizzate in tutte le mie frasi? Con circa 2 milioni di frasi composte di solito 1-3 parole, sarà difficile eseguire tutte le permutazioni di tutte le sottostringhe possibili ...
20 byte * 2 milioni = 40 MB. Questo è minuscolo rispetto alla tipica quantità di memoria in un computer. Se li si archivia in una matrice ordinata, si utilizzerà la ricerca binaria per la ricerca e difficilmente sarà necessaria alcuna memoria aggiuntiva. – jkff
Sì, 40 MB non è molto. E se è la velocità che ti preoccupa, allora tieni i dati in memoria il più semplice possibile. – ruslik
Come scritto di seguito, i 40 MB devono venire con l'app, e mi piace mantenere la dimensione del download dell'app molto più piccola. Inoltre, non è l'unica parzialità. C'è una porzione più ampia di un altro set di "parole", che non ha bisogno di essere ricercabile ma comunque comprimibile perché ammonterà a circa 1 GB nelle stringhe non elaborate. Una volta trovato un algo adatto a quanto sopra, spero di usarlo anche su quest'altro, più grande, insieme. –