[c++]dizionario con alberi red&black e distanza di levensthei la classica "forse cercavi" di google

[pceweb]

Salve , sono uno studente di informatica...
e devo consegnare un progetto in c++ di Algoritmi e strutture dati ,
Da premettere non cerco aiuti di codice o altro ,
voglio solo porgervi un quesito e vedere se potete aiutarmi,

In pratica devo realizzare un classico dizionario con funzioni di ricerca ,eliminazione e in caso di parola non trovata deve restituire la parole simile , ottenuta grazie alla distanza di levensthein

Per implementare questo dizionario devo usare sia le hash table , e sia la struttura dati Red&Black
quindi in realtà devo creare due dizionari....


Il mio problema è questo ,ragionando sul discorso della ricerca fallita e nel trovare le parole simili....devo per forza di cose scorrere tutte le parole presenti nel dizionario?
e da li verificare la distanza di levensthein con tutte ?

non diventa poi decisamente costoso come programma?
esiste un idea migliore che non riesco magari al momento ad afferrare?

[AmT2k10]

Essendo l' albero "ordinato" alfabeticamente, non credo che tu possa avere un altro metodo per vedere la distanza di levensthein di ogni singolo figlio.
Potresti avere anche un altro albero r&b ordinato - passami il termine -con altri criteri, come la grandezza della stringa (la distanza sarà minore sicuramente con due stringhe di pari lunghezza) ; ma non credo che sia una soluzione computazionalmente migliore.

[pceweb]

Io pensavo a una scelta golosa dove andavo a controllare tutte le parole.... ma la distanza di levenhstein.. la andavo a verificare solo con parole di size che so simile se per esempio devo cercare

"Francesco" : size 9

io verificavo solo le parole che andavano da size -3 e +3
quindi iun questo caso parole di size 5 come "frano" non le consideravo... ma poteva cmq essere una soluzione... mi sa devo solo chiedere al professore se convine effettuare una scelta golosa.. o vuole che scorri tutto l'albero.. e applicare la distanza di levenhstein parola per paorla..

[AmT2k10]

Io pensavo a una scelta golosa dove andavo a controllare tutte le parole.... ma la distanza di levenhstein.. la andavo a verificare solo con parole di size che so simile se per esempio devo cercare

"Francesco" : size 9

io verificavo solo le parole che andavano da size -3 e +3
quindi iun questo caso parole di size 5 come "frano" non le consideravo... ma poteva cmq essere una soluzione... mi sa devo solo chiedere al professore se convine effettuare una scelta golosa.. o vuole che scorri tutto l'albero.. e applicare la distanza di levenhstein parola per paorla..

Ho capito, comunque l'idea di costruirsi parallelamente un altro albero che abbia criterio di ordinamento la dimensione delle stringhe, per poi effettuare una ricerca su esso , forse, potrebbe essere anche meno costosa.
Fammi sapere come andrai ad implementare, sono curioso
Buon lavoro