Applicazione dizionario: suggerimenti per il formato di serializzazione e la struttura dei dati

1

Voglio creare un'applicazione dizionario. Una delle linee guida di progettazione è la prestazione nell'interrogazione e nella visualizzazione delle definizioni di parole.

Vorrei alcuni suggerimenti su due scelte di design:

  1. Quale formato di serializzazione dovrei scegliere? Sto pensando a JSON (o YAML) che ho controllato su popolari applicazioni del dizionario opensource (stardict, freedict, goldendict ecc.) Nessuno dei software sopra menzionati sceglie questo formato. Molto spesso usano il loro formato specifico. Qualcuno potrebbe spiegare perché è così?
  2. Quale struttura dati posso scegliere? Qualunque sia il formato del dizionario scelto, dopo aver caricato il file del dizionario in memoria, dovrebbe essere memorizzato in una sorta di struttura dati. Per una ricerca veloce presumo che questo potrebbe essere hash table o tree ?
posta McBear Holden 10.11.2018 - 17:35
fonte

1 risposta

1

Per prima cosa, considera un sistema di database esistente come SQLite. Ciò consente di ottenere strutture di dati di ricerca efficienti senza un grande sforzo di programmazione e può anche richiedere i dati senza doverli caricare completamente in memoria. I dati sono anche memorizzati in un formato binario efficiente da caricare.

Se questa non è un'opzione e devi implementare tutto da solo (ad esempio per un progetto di studio), chiediti come saranno modificati i file.

  • Se i file possono essere modificati da umani, preferisci un formato facile da modificare come YAML o XML.
  • Se i file verranno modificati dal tuo programma, preferisci un formato facile da manipolare come JSON, XML o CSV. Puoi anche utilizzare un formato di file personalizzato.

Perché?

  • YAML è un formato estremamente complesso con casi limite molto complicati. Nessun parser supporta precisamente le specifiche. Tuttavia, le parti più importanti della sintassi sono molto evidenti per gli esseri umani e il formato consente commenti. Tuttavia, questi commenti non fanno parte del modello di documento e non effettuano il round trip: se l'applicazione legge un file con commenti, modifica la struttura dei dati e li scrive nuovamente, eventuali commenti vanno persi.
  • JSON sembra un formato semplice e amichevole, ma ha alcuni trucchi. Per esempio. non consente alcun commento, l'ordine delle chiavi non è specificato e il supporto JSON per i numeri è sottodescritto (ad es. non distingue necessariamente tra numeri interi e float).
  • XML è un formato abbastanza complesso, ma offre un ottimo supporto software ed è OK come formato modificabile dall'uomo. XML potrebbe non essere la scelta migliore, ma non sarà la scelta sbagliata.
  • Un formato di file personalizzato può essere un'ottima soluzione se hai esperienza con la progettazione di formati di file e analisi. Ma usando un formato esistente ottieni un parser gratis, che evita anche molti argomenti difficili come i caratteri Unicode. Mentre molte applicazioni specificano il proprio formato, questo non è generalmente consigliabile.

Una volta che hai i dati, ti consigliamo di organizzarli in un modo facile da interrogare. Che tipo di query è necessario eseguire determina la struttura dei dati. Alcuni esempi:

  • Se vuoi mostrare un elenco alfabetico di tutte le voci del dizionario, una struttura dati ordinata come un array ordinato o un albero binario di ricerca sarebbe appropriata. Questo aiuterà anche se hai bisogno di cercare per il prefisso di un termine esatto.
  • Se hai bisogno di una rapida ricerca di un termine, dato il nome esatto di quel termine, allora sarebbe opportuna una tabella hash o un albero binario di ricerca.
  • Le cose diventano più difficili per le ricerche fuzzy, ad esempio con un nome di voce approssimativo o durante la ricerca nel corpo di una voce di dizionario. Questo è qualcosa in cui l'utilizzo del software esistente sarà molto utile.
  • Nel peggiore dei casi dovrai solo scansionare tutti i tuoi dati. Questo potrebbe non essere poi così male a meno che tu non abbia bisogno di risposte molto veloci o di avere enormi quantità di dati.

Puoi combinare diverse strutture di dati. Per esempio. è possibile mantenere i record principali in una struttura dati ordinata, ma anche indicizzarli con una tabella hash o precomporre un indice per ricerche full-text. Una struttura di dati molto utile per alcune applicazioni è un filtro di fioritura, che è una struttura di dati di set probabilistici con un tasso di errore sintonizzabile. Prima di eseguire una query costosa, puoi chiedere al filtro bloom se tale elemento esiste anche e risponderà "no" o "forse".

    
risposta data 10.11.2018 - 20:08
fonte