Chaos82
25-02-2011, 19:17
Salve a tutti,
Vi scrivo per chiedere il vostro aiuto per la risoluzione di un problema che è una parte di un progetto, un'idea più ampia che ho avuto in questi giorni.
Giusto per fare una piccola introduzione e capire un po' meglio il problema vi presento in sintesi la mia idea.
Io sono un grande lettore di Libri di Narrativa e attraverso Emule, la rete e via discorrendo ho trovato delle grandi collezioni di libri.
Il problema è che questi libri non sono in alcun modo classificati e quindi a meno di sapere a priori cosa si vuole leggere non si riesce a trovare un bel niente.
Se sò il titolo di un libro posso andare a vedere la trama su internet, ma se io per esempio volessi leggermi un nuovo libro fantasy cercando tra quelli a disposizione dovrei prima trovare la trama di ogni libro, dividerli per categoria( non ci sono solo fantasy ) e poi andare a vedere che leggere.
Ora questo è facile se i libri sono 10... un po' più estenuante se sono 100... e se fossero 1000 o 4000?? Capite il problema?
Da qui la mia idea, semplice ma allo stesso tempo potente anche per una particolarità intrinseca alla stessa : Questo procedimento che ora vado a spiegare può essere applicato a tutti i generi di documento, non solo ai libri, e quindi permetterebbe di catalogare tutti i documenti presenti sul nostro PC e questo con l'avvento degli Ebook, dei manuali PDF e via discorrendo che abbiamo sul PC indubbiamente sarebbe una grande cosa.
Unico difetto : questa soluzione non è infallibile, ma comunque permetterebbe sicuramente una prima scrematura che aiuterebbe moltissimo a risparmiare tempo e fatica. Nel tempo poi sarebbe possibile incrementare le funzionalità, migliorare i metodi di ricerca etc etc, ma questi sono considerazioni future.
Se la cosa prende piede sarebbe bello fare un bel freeware o open source da distribuire in giro, ma questo è un'altro discorso.
Riguardo alla parte di programmazione mi riferisco a voi, ma ho coinvolto altre persone e un'altro paio di forum di "letteratura" per altre parti di questo progetto.
Passiamo ora alla spiegazione dell'idea che è di una semplicità mostruosa :
Partiamo da una file di testo(txt) come sorgente (Altri formati vogliono solo dire usare librerie diverse per andarli a leggere e non c'è alcuna differenza ai fini dell'implementazione dell'algoritmo centrale)
Come Dizionario di riferimento usiamo un bel array di strutture. Ogni elemento dell'array composta da due campi:
char parola[20]
long int numero_ripetizioni
Questo dizionario ha all'interno le parole chiave che secondo noi definiscono ogni tipo di documento che vogliamo catalogare!
Per fare un esempio il genere Narrativa -> Fantasy sarà definito da X parole tra cui Elfo, Nano, Cavaliere, Mago, Orco, Magia...
Il Genere Narrativa -> Fantascienza sarà definito da Y parole tra cui Astronave, Razzo, Pianeta, Sistema, Solare, Stelle...
Il dizionario di riferimento è l'insieme di tutte queste parole messe in ordine alfabetico crescente o decrescente.
Procedimento :
1) In maniera iterativa vado a leggere ogni parola all'interno del documento;
2) Una volta letta la parola vado a vedere se questa è presente nel dizionario di riferimento e se si incremento il relativo contatore.
Ordinando in modo decrescente l'array "Dizionario" è possibile usare una ricerca attraverso l'algoritmo di bisezione in modo da velocizzare la ricerca all'interno dello stesso.
Avevo anche pensato a usare qualche tabella di Hash anche se devo ammettere che non mi è venuto in mente nulla di abbastanza performante e con un rapporto prestazioni/spazio occupato non esorbitante.
Col metodo di bisezione, supponendo per facilità che il nostro "Dizionario di riferimento" contenga 4096 termini per cercare ogni parola impiegheremo 12 iterazioni e quindi mi sembra accettabile.
Naturalmente bisognerà prevedere alcune regole, per esempio : mago, maghe, maghi andranno tutte ad incrementare solo la parola "mago"; la ricerca non sarà case sensitive; sotto le Z lettere(Z è la lunghezza della parola più corta del "Dizionario di Riferimento") la parola non verrà considerata e idem per la lunghezza massima e così via altre regole che si individueranno e si implementeranno col tempo.
3) Ripeto fino alla fine del documento per ogni parola.
4) Ordino l'array con riferimento al numero di ripetizioni di ogni parola.
5) Prendo le 20-40 parole che si ripetono maggiormente
6) Salvo in matrice di stringhe i risultati ottenuti
La matrice di stringhe funziona da database ed è così composta :
riga 1 : percorso del file analizzato 1 ; stringa con maggior freq; stringa con maggior freq-1; stringa con maggior freq-2; ...; stringa con maggior freq-n;
riga 2 : percorso del file analizzato 2 ; stringa con maggior freq; stringa con maggior freq-1; stringa con maggior freq-2; ...; stringa con maggior freq-n
.
.
.
riga n : percorso del file analizzato n ; stringa con maggior freq; stringa con maggior freq-1; stringa con maggior freq-2; ...; stringa con maggior freq-n
7) Ripeto il procedimento per tutti i file che voglio ( o tutta una cartella o tutti i documenti che trovo sul PC )
8) Ora ho la nostra matrice di stringhe che da ora in avanti chiamerò "Matrice di Riferimento"
9) Le operazioni sulla "Matrice di Riferimento" sono molteplici indubbiamente, ma prima di tutte viene quella di ricerca: questa potrà essere implementata in modo da poter cercare più parole in and o in or.
10) un'altra funzione interessante sarà quella di dividere i documenti per che abbiamo analizzato in diversi generi/gruppi a seconda delle prime, per esempio 10, parole con maggior frequenza in ogni documento.
Questo ci permetterà di classificare all'inizio i libri e pian piano il "Dizionario di Riferimento" potrà essere ampliato fino a riconoscere e dividere tantissimi tipi di documenti.
NB: la cosa interessante è che basta cambiare la lingua dei termini presenti nel "Dizionario di riferimento" per poter usare lo stesso programma per catalogare file scritti in qualsiasi lingua e questo è sicuramente molto interessante non trovate?
Questa è la mia idea di base.... e ora veniamo a noi e alle mie domande... :D
1) Qualcuno di voi sarebbe interessato a creare un gruppo per sviluppare tale progetto tutti assieme, senza alcun scopo di lucro e via discorrendo?
2) Io purtroppo opere nel campo dell'acquisizione dati e del condizionamento dei segnali e i SW che uso per programmare non mi permettono di costruire un'applicazione del genere in modo semplice.
Potrei scrivere quest'applicazione in C che è l'unico linguaggio che conosco abbastanza bene : faccio una bella DLL e poi mi imparo qualcosa per tirar su un po' di grafica e mi costruisco l'interfaccia grafica.
Ma visto che tanto qualche linguaggio in più non fà mai male.... Voi che linguaggi mi consigliereste per scrivere un'applicazioni di questo genere?
Dalle mie scarse conoscenze in C++ esso sarebbe abbastanza performante per l'algoritmo di ricerca e forse con le nuove librerie QT della Nokia anche la grafica verrebbe benino anche se personalmente non le ho mai viste ne usate...
Purtroppo il C++ è difficile e... Voi potete consigliarmi qualcosa di più semplice, ma allo stesso tempo potente e perfetto per questo scopo?
... o come dicevo anche 2 linguaggi diversi, uno per l'algoritmo e l'altro per l'interfaccia grafica?
3) Questa è la mia idea come ho già detto e a costo di imparare tutto da solo e di passare le notti del prossimo anno insonni la realizzerò, ma volevo chiedervi... Vi sembra tanto campata in aria come idea?
A me non sembra altrimenti non l'avrei proposta, ma mi piacerebbe conoscere il vostro parere!
4) Ho fatto una ricerca su internet, diverse ricerche per la precisione, ma non ho trovato assolutamente nulla che faccia già quello che io propongo di realizzare... Voi conoscete qualcosa del genere?
Lo chiedo perchè sbattersi per fare qualcosa e poi scoprire a metà progetto che c'è già un altro Sw che lo fà non è mai bello e lascia sempre un po' di amaro in bocca...
Che dire...
Per il momento vi ringrazio per l'attenzione che avete dimostrato leggendomi fin qui e...
Spero di avere presto vostre notizie... ;)
Davide
Vi scrivo per chiedere il vostro aiuto per la risoluzione di un problema che è una parte di un progetto, un'idea più ampia che ho avuto in questi giorni.
Giusto per fare una piccola introduzione e capire un po' meglio il problema vi presento in sintesi la mia idea.
Io sono un grande lettore di Libri di Narrativa e attraverso Emule, la rete e via discorrendo ho trovato delle grandi collezioni di libri.
Il problema è che questi libri non sono in alcun modo classificati e quindi a meno di sapere a priori cosa si vuole leggere non si riesce a trovare un bel niente.
Se sò il titolo di un libro posso andare a vedere la trama su internet, ma se io per esempio volessi leggermi un nuovo libro fantasy cercando tra quelli a disposizione dovrei prima trovare la trama di ogni libro, dividerli per categoria( non ci sono solo fantasy ) e poi andare a vedere che leggere.
Ora questo è facile se i libri sono 10... un po' più estenuante se sono 100... e se fossero 1000 o 4000?? Capite il problema?
Da qui la mia idea, semplice ma allo stesso tempo potente anche per una particolarità intrinseca alla stessa : Questo procedimento che ora vado a spiegare può essere applicato a tutti i generi di documento, non solo ai libri, e quindi permetterebbe di catalogare tutti i documenti presenti sul nostro PC e questo con l'avvento degli Ebook, dei manuali PDF e via discorrendo che abbiamo sul PC indubbiamente sarebbe una grande cosa.
Unico difetto : questa soluzione non è infallibile, ma comunque permetterebbe sicuramente una prima scrematura che aiuterebbe moltissimo a risparmiare tempo e fatica. Nel tempo poi sarebbe possibile incrementare le funzionalità, migliorare i metodi di ricerca etc etc, ma questi sono considerazioni future.
Se la cosa prende piede sarebbe bello fare un bel freeware o open source da distribuire in giro, ma questo è un'altro discorso.
Riguardo alla parte di programmazione mi riferisco a voi, ma ho coinvolto altre persone e un'altro paio di forum di "letteratura" per altre parti di questo progetto.
Passiamo ora alla spiegazione dell'idea che è di una semplicità mostruosa :
Partiamo da una file di testo(txt) come sorgente (Altri formati vogliono solo dire usare librerie diverse per andarli a leggere e non c'è alcuna differenza ai fini dell'implementazione dell'algoritmo centrale)
Come Dizionario di riferimento usiamo un bel array di strutture. Ogni elemento dell'array composta da due campi:
char parola[20]
long int numero_ripetizioni
Questo dizionario ha all'interno le parole chiave che secondo noi definiscono ogni tipo di documento che vogliamo catalogare!
Per fare un esempio il genere Narrativa -> Fantasy sarà definito da X parole tra cui Elfo, Nano, Cavaliere, Mago, Orco, Magia...
Il Genere Narrativa -> Fantascienza sarà definito da Y parole tra cui Astronave, Razzo, Pianeta, Sistema, Solare, Stelle...
Il dizionario di riferimento è l'insieme di tutte queste parole messe in ordine alfabetico crescente o decrescente.
Procedimento :
1) In maniera iterativa vado a leggere ogni parola all'interno del documento;
2) Una volta letta la parola vado a vedere se questa è presente nel dizionario di riferimento e se si incremento il relativo contatore.
Ordinando in modo decrescente l'array "Dizionario" è possibile usare una ricerca attraverso l'algoritmo di bisezione in modo da velocizzare la ricerca all'interno dello stesso.
Avevo anche pensato a usare qualche tabella di Hash anche se devo ammettere che non mi è venuto in mente nulla di abbastanza performante e con un rapporto prestazioni/spazio occupato non esorbitante.
Col metodo di bisezione, supponendo per facilità che il nostro "Dizionario di riferimento" contenga 4096 termini per cercare ogni parola impiegheremo 12 iterazioni e quindi mi sembra accettabile.
Naturalmente bisognerà prevedere alcune regole, per esempio : mago, maghe, maghi andranno tutte ad incrementare solo la parola "mago"; la ricerca non sarà case sensitive; sotto le Z lettere(Z è la lunghezza della parola più corta del "Dizionario di Riferimento") la parola non verrà considerata e idem per la lunghezza massima e così via altre regole che si individueranno e si implementeranno col tempo.
3) Ripeto fino alla fine del documento per ogni parola.
4) Ordino l'array con riferimento al numero di ripetizioni di ogni parola.
5) Prendo le 20-40 parole che si ripetono maggiormente
6) Salvo in matrice di stringhe i risultati ottenuti
La matrice di stringhe funziona da database ed è così composta :
riga 1 : percorso del file analizzato 1 ; stringa con maggior freq; stringa con maggior freq-1; stringa con maggior freq-2; ...; stringa con maggior freq-n;
riga 2 : percorso del file analizzato 2 ; stringa con maggior freq; stringa con maggior freq-1; stringa con maggior freq-2; ...; stringa con maggior freq-n
.
.
.
riga n : percorso del file analizzato n ; stringa con maggior freq; stringa con maggior freq-1; stringa con maggior freq-2; ...; stringa con maggior freq-n
7) Ripeto il procedimento per tutti i file che voglio ( o tutta una cartella o tutti i documenti che trovo sul PC )
8) Ora ho la nostra matrice di stringhe che da ora in avanti chiamerò "Matrice di Riferimento"
9) Le operazioni sulla "Matrice di Riferimento" sono molteplici indubbiamente, ma prima di tutte viene quella di ricerca: questa potrà essere implementata in modo da poter cercare più parole in and o in or.
10) un'altra funzione interessante sarà quella di dividere i documenti per che abbiamo analizzato in diversi generi/gruppi a seconda delle prime, per esempio 10, parole con maggior frequenza in ogni documento.
Questo ci permetterà di classificare all'inizio i libri e pian piano il "Dizionario di Riferimento" potrà essere ampliato fino a riconoscere e dividere tantissimi tipi di documenti.
NB: la cosa interessante è che basta cambiare la lingua dei termini presenti nel "Dizionario di riferimento" per poter usare lo stesso programma per catalogare file scritti in qualsiasi lingua e questo è sicuramente molto interessante non trovate?
Questa è la mia idea di base.... e ora veniamo a noi e alle mie domande... :D
1) Qualcuno di voi sarebbe interessato a creare un gruppo per sviluppare tale progetto tutti assieme, senza alcun scopo di lucro e via discorrendo?
2) Io purtroppo opere nel campo dell'acquisizione dati e del condizionamento dei segnali e i SW che uso per programmare non mi permettono di costruire un'applicazione del genere in modo semplice.
Potrei scrivere quest'applicazione in C che è l'unico linguaggio che conosco abbastanza bene : faccio una bella DLL e poi mi imparo qualcosa per tirar su un po' di grafica e mi costruisco l'interfaccia grafica.
Ma visto che tanto qualche linguaggio in più non fà mai male.... Voi che linguaggi mi consigliereste per scrivere un'applicazioni di questo genere?
Dalle mie scarse conoscenze in C++ esso sarebbe abbastanza performante per l'algoritmo di ricerca e forse con le nuove librerie QT della Nokia anche la grafica verrebbe benino anche se personalmente non le ho mai viste ne usate...
Purtroppo il C++ è difficile e... Voi potete consigliarmi qualcosa di più semplice, ma allo stesso tempo potente e perfetto per questo scopo?
... o come dicevo anche 2 linguaggi diversi, uno per l'algoritmo e l'altro per l'interfaccia grafica?
3) Questa è la mia idea come ho già detto e a costo di imparare tutto da solo e di passare le notti del prossimo anno insonni la realizzerò, ma volevo chiedervi... Vi sembra tanto campata in aria come idea?
A me non sembra altrimenti non l'avrei proposta, ma mi piacerebbe conoscere il vostro parere!
4) Ho fatto una ricerca su internet, diverse ricerche per la precisione, ma non ho trovato assolutamente nulla che faccia già quello che io propongo di realizzare... Voi conoscete qualcosa del genere?
Lo chiedo perchè sbattersi per fare qualcosa e poi scoprire a metà progetto che c'è già un altro Sw che lo fà non è mai bello e lascia sempre un po' di amaro in bocca...
Che dire...
Per il momento vi ringrazio per l'attenzione che avete dimostrato leggendomi fin qui e...
Spero di avere presto vostre notizie... ;)
Davide