implementazione di un motore di ricerca di base con albero di prefisso

Question

Il problema è l'implementazione di un albero di prefissi (Trie) in linguaggio funzionale senza utilizzare alcun metodo di archiviazione e iterativo.

Sto cercando di risolvere questo problema. Come dovrei affrontare questo problema? Puoi darmi un algoritmo o un link esatto che mostri già implementato in qualsiasi linguaggio funzionale?

Perché sto cercando di fare => creazione di un semplice motore di ricerca con una caratteristica di

• aggiungendo parola per albero
• cercare una parola in albero
• eliminare una parola albero

Perché voglio usare il linguaggio funzionale => Voglio migliorare ulteriormente la mia capacità di problem-solving.

NOTA: Poiché si tratta del mio progetto per hobby, implementerò innanzitutto le funzionalità di base.

EDIT:

i) Quello che voglio dire su serie "senza l'utilizzo di storage" => Non voglio utilizzare la memoria di variabili (ex int a), il riferimento a una variabile,.. Voglio calcolare il risultato in modo ricorsivo, quindi mostrare i risultati sullo schermo.

ii.) Ho scritto qualche riga ma poi l'ho cancellato perché quello che ho scritto mi ha fatto arrabbiare. Mi dispiace per non aver mostrato il mio impegno.

Answer 1

Dai uno sguardo a Data.IntMap di haskell.È un'implementazione puramente funzionale di Patricia trie ed è source è abbastanza leggibile.
bytestring-trie pacchetto estende questo approccio ByteStrings

Ci si accompagna carta Fast Mergeable Integer Maps che è anche leggibile e attraverso. Descrive passo per passo l'implementazione: dai tentativi binari agli alberi di patricia big-endian.
Ecco un piccolo estratto dal foglio.

Nel caso più semplice, un albero binario è un albero binario completo della profondità pari al numero di bit nelle chiavi, dove ogni foglia è o vuoto, che indica che la chiave corrispondente è associato o completa, in in quale caso contiene i dati a cui è associata la chiave corrispondente . Questo stile di trie potrebbe essere rappresentata in standard ML come

datatype 'a Dict = 
    Empty 
    | Lf of 'a 
    | Br of 'a Dict * 'a Dict 

di ricercare un valore in un albero binario, abbiamo semplicemente leggere i bit della chiave , andando a sinistra oa destra come indicato, fino a raggiungere una foglia.

fun lookup (k, Empty) = NONE 
    | lookup (k, Lf x) = SOME x 
    | lookup (k, Br (t0,t1)) = 
     if even k then lookup (k div 2, t0) 
       else lookup (k div 2, t1) 

Answer 2

Il punto chiave nelle implementazioni di strutture dati immutabili è condivisione di entrambi i dati e. Per aggiornare un oggetto devi crearne una nuova versione con il maggior numero possibile di nodi condivisi. Può essere usato concretamente per provare l'approccio seguente.

considerazione tale trie (da Wikipedia):

Immaginate di non aver aggiunto la parola "inn" ancora, ma hai già la parola "in". Per aggiungere "inn" devi creare una nuova istanza di tutto il trie con "inn" aggiunto. Tuttavia, non sei obbligato a copiare tutto: puoi creare solo una nuova istanza del nodo radice (questa senza etichetta) e il banch giusto. Il nuovo nodo radice punterà a nuovo banch di destra, ma a vecchi altri rami, quindi con ogni aggiornamento la maggior parte della struttura è condivisa con lo stato precedente.

Tuttavia, le chiavi potrebbero essere piuttosto lunghe, quindi ricreare l'intero ramo ogni volta richiede sempre tempo e spazio. Per ridurre questo effetto, è possibile condividere la struttura all'interno di un nodo. Normalmente ogni nodo è un vettore o una mappa di tutti i possibili risultati (ad esempio in un nodo immagine con etichetta "te" ha 3 risultati - "a", "d" e "n"). Ci sono molte implementazioni per mappe immutabili (Scala, Clojure, vedere i loro repository per altri esempi) e Clojure ha anche un eccellente implementation di un vettore immutabile (che in realtà è un albero).

Tutte le operazioni di creazione, aggiornamento e ricerca dei tentativi risultanti possono essere implementate in modo ricorsivo senza uno stato mutabile.