In un'intervista mi è stato chiesto come avrei progettato l'Oxford English Dictionary.Progettazione del dizionario inglese di Oxford
Gli ho detto che avrei usato una struttura dati TREE, ma lui mi ha risposto che ci sarebbe voluta molta memoria. Quindi quale altra struttura dati dovrebbe essere usata?
struttura Uno dei dati che ho sentito è stato utilizzato in passato nei telefoni cellulari per la memorizzazione dizionari T9 è la seguente (beh, questo affronta solo la questione chiave, ma non l'archiviazione definizione):
voci sono ordinati, e ogni voce dovrebbe iniziare con un offset nella voce precedente da dove dovrebbe essere continuato, e anche la continuazione. Ad esempio:
apple
4icable
7tion
decodifica a mela, applicabile, applicazione. Tuttavia questo potrebbe non essere molto diverso da tentativi con catene unite, vedi
appl -> e
-> ica -> ble
-> tion
Wikipedia scoperto il Directed acyclic word graph, che differisce da alberi che non solo i rami, ma rami possibile unire, in cui le parole hanno lo stesso suffisso. Questo potrebbe davvero essere uno storage superiore.
a
/\
pplic utom
\/
ation
A proposito, wikipedia mi ha appena detto che "se la memorizzazione delle parole del dizionario è tutto ciò che è richiesto, un automa finito deterministico minimo aciclico userebbe meno spazio di un trie". Aggiunto per rispondere. – ron
Non userebbe molta memoria. La tua risposta andava bene. Forse nel 1995. Considerati fortunato.
Come altri hanno già detto, se non c'è abbastanza sul tetto per un trie ben progettato, probabilmente non ci sia spazio per qualsiasi altro tipo di indice, neanche. Dato che si tratta di una domanda di intervista, sembra che stia cercando di indirizzarti verso le classiche strutture datate fuori dal comune come gli alberi B.
In alternativa, una buona risposta avrebbe potuto essere chiedere maggiori informazioni, come "che tipo di operazioni vuoi fare su questa infrastruttura e che tipo di prestazioni hai bisogno?" Se vuoi solo un controllo ortografico, allora un filtro Bloom potrebbe essere il più efficiente "datastructure" ...
solo una cosa stupida, ma Oxford Dictionary non usa mappare il mondo in un'altra parola il significato della parola in poche frasi/frasi? In tal caso, le parole che codificano sono l'ultimo dei tuoi problemi e dovresti pensare a rappresentare il significato (parole con la grammatica e così via) o anche considerare l'imballaggio basato sul dizionario come LHARC. Fortunatamente per te l'inglese non è molto complesso in questo modo ... – Spektre