Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
salve
ho un progetto da fare a fini didattici per l'università in cui mi viene richiesto di:
passato il path di una cartella contenente files di testo, cercare una parola specificata dall'utente da input. Il tutto in ambiente windows.
Essendo un progetto per algoritmi e strutture dati mi viene ovviamente richiesto di effettuare la ricerca in modo estremamente efficiente.
La mia idea era quella di :
creare una lista in cui ogni nodo memorizza il nome del file e una struttura dati in cui caricare tutte le parole contenute nel file preso in analisi.
come struttura vorrei usare un albero binario cosi da avere ricerche nell'ordine di O(log n), e ogni nodo dell'albero deve contenere un codice hash ottenuto dalla parola che considero di volta in volta.
ora il problema è che non so come impostare una funzione hash in grado di non generare collisioni, o il minimo possibile.
quindi avrei bisogno di un bel metodo hash, non il codice ma semplicemente le linee guida o pseudocodice che dir si voglia, e se qualcuno ha un'idea migliore per fare il tutto mi farebbe molto piacere discuterne.
Vi ringrazio anticipatamente.
non c'è un modo efficiente, e non puoi utilizzare una tabella hash in quanto le parole si possono ripetere all'interno di un testo.
ad ogni modo la cosa più furba che si può fare, senza caricarsi ogni file in memoria e lanciare una strstr su tutto il contenuto, è creare uno shift register della dimensione della stringa da cercare e scorrere i files uno per uno char per char. ogni char viene aggiunto allo shift register (che ovviamente scarterà il primo char) e si va di strcmp sullo shift register e la stringa che stai cercando.
un esempio: stringa da cercare "ciao", il testo è il seguente: "bella! ciao a tutti!"
la procedura funzionerebbe così
1) inizializzo lo shift register con i primi 4 bytes della stringa, quindi
shiftregister = "bell"
2) confronto lo shift register con la stringa: strcmp(str, shiftregister)
N.B: in realtà se vuoi utilizzare la strcmp devi assicurarti che le stringhe abbiano il terminatore, altrimenti puoi utilizzare la strncmp che confronta solo uno specifico numero di caratteri.
questo è uno stratagemma che ti permette di cercare qualcosa all'interno di un file senza doverne leggere tutto il contenuto in una volta.
bisognerebbe poi provare se è più conveniente prelevare chunks di dati più grossi di un singolo char e fare al loro interno questo lavoro che ho illustrato, o lanciare una serie di strstr sequenziali fino a non trovare più match (ricordiamoci che una parola può essere trovata più volte).
Se vuoi invece proseguire la strada delle strutture dati, potresti creare un dizionario che ha per chiavi la parola e per valori un'array di indici, che sono appunto gli indici delle parole all'interno del testo. In questo modo puoi fare una tabella di hash tra le parole trovate e da questa risalire alla lista degli indici all'interno del testo. Ma anche qui, con che criterio separi una parola dall'altra? lo spazio? il punto? l'apostrofo, virgola, duepunti? cioè se ho
"ciao a tutti. bella!"
una strtok su ' ' ti darebbe "ciao", "a", "tutti.", "bella!"
quindi devi effettuare una split più furba, su un'insieme di separatori e scartare le stringhe risultate vuote.
inoltre ricordati che ci sono parole tipo "po'" che hanno volutamente l'apostrofo, mentre "l'apostrofo" è "l"(il), "apostrofo" qui invece è un separatore
se percorri questa strada devi scrivere una funzione di tokenizing parecchio furba
PS: Ma sei bruno e hai perso la pass dell'account?
Ultima modifica effettuata da HeDo il 17/12/2010 alle 1:37
per prima cosa grazie per la risposta e mi dispiace ma non sono bruno ritornando a noi...
il primo metodo, quello dello shifter, che alla fine si riduce ad un ricerca lineare , sembrerebbe buona se la ricerca verrebbe fatta su file con poche parole, ma capisci sicuramente meglio di me che se la ricerca deve essere fatta in una cartella contenente 200 file con in media 5000 parole per ciascuno di esso ,i tempi per avere una risposta sarebbero molto lunghi.
Detto ciò credo che l'impiego di una struttura di supporto sia quasi obbligatoria.
Ne consegue che necessito di una buona funzione hash per ricavare le chiavi da associare alle parole che abbia la minore probabilità possibile di generare collisioni perchè, come hai sottolineato anche tu, utilizzando una struttura avrei delle difficoltà nella gestione delle collisioni generate. Per questo motivo avevo pensato di includere nel mio progetto la funzione per generare codici MD5 , ma non so fino a che punto mi convenga utilizzarlo.
per quanto riguarda il tokenzing avevo pensato ad un controllo,prima di generare il codice hash, per l'esclusione dei caratteri "particolari".
Ultima modifica effettuata da sigturk il 17/12/2010 alle 10:56
considera che prima di poter eseguire ricerche all'interno dell'albero di directory dovrai prevedere una fase di indicizzazione che potrebbe anche essere lunga in quanto vai ad analizzare tutto il contenuto di tutti i files e crei la tua struttura dati, questo approccio paga quando poi andrai a cercare una parola, con complessità prossima a O(1)
Non mi pongo il problema del tempo per il caricamento perché il punto centrale del mio esercizio è proprio quello di eseguire la ricerca nel tempo minore.
Dato che mi dai conferme credo che userò proprio MD5 come funzione di hash cosi da potermi concentrare sulla funzione di tokenizing.
Grazie per il supporto e per il tempo dedicatomi
Per questo motivo avevo pensato di includere nel mio progetto la funzione per generare codici MD5 , ma non so fino a che punto mi convenga utilizzarlo.
