[C] vettorializzazione di un documento...

[}gu|do[z]{®©]

...temo che dal titolo non si capisca molto

devo consegnare l'ultima parte di un progettino dell'uni.. un piccolo motore di ricerca...

quello che ho è uun albero binario di ricerca che costituisce un dizionario contenente tutte le parole contenute in tutti i files del corpus (i files su cui effettuare la ricerca).
A questo punto del progetto devo fare il sistema di ranking.. il prof ci ha suggerito anche il metodo per stabilire la rilevanza del documento rispetto ad una query:

Il dizionario ha N parole.. allora un vettore "query" di N elementi avrà l'elemento i-esimo pari ad 1 se la corrispondente parola del dizionario è presente nella query, 0 altrimenti.
Similmente un file di testo avrà un vettore dello stesso tipo.
Il prodotto scalare tra i due vettori sarà tanto maggiore quanto minore è l'angolo tra i due vettori... ovvero quante più parole in comune abbiano.

Ok.. un po' laborioso ma chiaro...

il problema è come mi conviene implementare la cosa?

Ho l'albero di ricerca... pensavo di farne una lista ordinata delle parole e da quella calcolarmi il vettore dell file di query. Poi per ogni file calcolarne il vettore e calcolare il prodotto scalare con il vettore query memorizzando di volta nomefile e valore del prodotto in struct che mi ordino con una lista...

è la strada giusta?
mi sembra pareeeeeeeeeecchio laborioso..

tnx

[anx721]

Si, direi che va bene.

[}gu|do[z]{®©]

Originariamente inviato da anx721
Si, direi che va bene.

anx721, sei il mio faro in questi giorni.. (ah.. poi ho preso 30 all'esame )

L'unica cosa che mi stranisce un attimo è la lista tratta dal dizionario.
Nel senso: se ho l'albero dizionario, è giusto estrarne una lista ordinata?
Il vantaggio dell'albero è quindi solo nell'aggiunta di parole al dizionario?
Sono un attimo perplesso ma non saprei come fare altrimenti, usando direttamente l'albero.. cioè.. dovrei implementare tuto il codice all'interno della funzione che visita l'albero... e mi pare poco pratico

Vabbè che poi il prof controllerà solo gli output quindi non me ne frega più di tanto.. ma mi faccio paranoie...

danke

[anx721]

Originariamente inviato da }gu|do[z]{®©
anx721, sei il mio faro in questi giorni.. (ah.. poi ho preso 30 all'esame )

Bravo

Originariamente inviato da }gu|do[z]{®©
L'unica cosa che mi stranisce un attimo è la lista tratta dal dizionario.
Nel senso: se ho l'albero dizionario, è giusto estrarne una lista ordinata?
Il vantaggio dell'albero è quindi solo nell'aggiunta di parole al dizionario?
Sono un attimo perplesso ma non saprei come fare altrimenti, usando direttamente l'albero.. cioè.. dovrei implementare tuto il codice all'interno della funzione che visita l'albero... e mi pare poco pratico
danke [/B]

In pratica un ordinamento sulle parole del dizionario ti serve per poter costruire il vettore che rappresenta la query o il vettore di un file, in quanto se hai le parole ordinate, puoi ricercare la posizione occupata da una parola nel dizionario e mettere un 1 nel vattore; la ricerca della parola puo essere fatta in tempo log(n) se n è il numero di tutte le parole. Questo vale per un albero binario o per un vettore ad accesso diretto, cioè, un array, ma non una lista, perchè una lista la puoi scorrere solo sequenzialmente. Per la lista utilizza quindi un array di puntatori a char o alla struct che eventualmente ti rappresenta la parola, in modo da poter utilizzare la ricerca binaria. Volendo potresti crearti un albero in cui ogni nodo porta già il numero d'ordine della parola associata al nodo, in questo modo ti basterebbe scendere lungo l'albero, andando a destra o a sinistra, e quando trovi il nodo con la parola ricercata puoi leggere l'indice della parola nell'ordinamento.

[}gu|do[z]{®©]

allora.. l'albero l'ho fatto nel modulo precedente in cui dovevamo solo creare l'albero e stamparlo ordinato in output.. per questo avevo una funzione che lo visitava in order e stampava l'elemento visitato... adesso l'ho modificata perchè restituisca una lista ordinata che mi spiccio prima...

Intanto penso al resto poi penso a questo..
Poi cmq pensavo: dovendo fare un vettore con una posizione per ogni parola devo per forza avere un algoritmo lineare no?
Non devo cercare una parola [chiaro che lì il tmepo è logaritmico] ma fare qualcosa per ogni elemento.. cioè per ogni parola devo mettere o 0 o 1 nel vettore... [per ogni file faccio una tabella di hash e con una funzione find verifico subito se la parola del dizionario è contenuta nel file]...


Che bello ho quasi finito... se non faccio errori scemi intravedo un altro 30 [:sgrat:]

[anx721]

Originariamente inviato da }gu|do[z]{®©
Che bello ho quasi finito... se non faccio errori scemi intravedo un altro 30 [:sgrat:]

:metallica