View Full Version : Trovare la percentuale di differenze tra due stringhe senza averle.
Mi servirebbe di qualcosa molto simile ad un hash o un crc con l'unica differenza che applicando questo algoritmo a due stringhe simili dovrei ottenere un risultato simile.
Con il crc invece ottengo ovviamente due risultati completamente diversi.
Questa cosa mi è utile perchè sto cercano di implementare un piccolo motore di ricerca, e ogni volta che lo spider passa da un sito dovrebbe accorgersi se vale la pena di aggiornare il database oppure le variazioni sono così piccole che non è necessario.
Il caso di variazioni piccole sono ad esempio quelle pagine dove c'è scritta la data attuale. Se facessi il crc della pagina vedrei che è diversa, ma di fatto è diversa di una quantità insignificante. D'altro canto andare a scompattare la pagina memorizzata nel database per confrontarla con quella attuale è un operazione inutilmente lenta.
Sapete se esiste un algoritmo di hashing (parola impropria lo so) che mi consenta di fare questo al volo ?
Provvisoriamente sto pensando ad una semplice somma di tutti i valori ascii dei caratteri contenuti nella stringa, ma penso esista qualcosa di più evoluto.
DanieleC88
24-11-2008, 18:24
Provvisoriamente sto pensando ad una semplice somma di tutti i valori ascii dei caratteri contenuti nella stringa, ma penso esista qualcosa di più evoluto.
Sono totalmente ignorante in questo campo, e non so quindi consigliarti una buona soluzione; so solo dirti che questa che stai percorrendo può essere solo una strada provvisoria e che non va bene in generale: immagina di avere una stringa e una sua copia perfetta, poi ribaltata o rimescolata, avresti la stessa somma di valori ASCII per stringhe diverse.
ciao ;)
cdimauro
24-11-2008, 20:23
http://it.wikipedia.org/wiki/Distanza_di_Levenshtein
malocchio
24-11-2008, 22:19
Mi servirebbe di qualcosa molto simile ad un hash o un crc con l'unica differenza che applicando questo algoritmo a due stringhe simili dovrei ottenere un risultato simile.
Con il crc invece ottengo ovviamente due risultati completamente diversi.
Questa cosa mi è utile perchè sto cercano di implementare un piccolo motore di ricerca, e ogni volta che lo spider passa da un sito dovrebbe accorgersi se vale la pena di aggiornare il database oppure le variazioni sono così piccole che non è necessario.
Il caso di variazioni piccole sono ad esempio quelle pagine dove c'è scritta la data attuale. Se facessi il crc della pagina vedrei che è diversa, ma di fatto è diversa di una quantità insignificante. D'altro canto andare a scompattare la pagina memorizzata nel database per confrontarla con quella attuale è un operazione inutilmente lenta.
Sapete se esiste un algoritmo di hashing (parola impropria lo so) che mi consenta di fare questo al volo ?
Provvisoriamente sto pensando ad una semplice somma di tutti i valori ascii dei caratteri contenuti nella stringa, ma penso esista qualcosa di più evoluto.
Quando cerchi algoritmi del genere devi sempre pensare che qualcun'altro c'ha già pensato. E trovato una soluzione migliore di quella che avresti pensato tu.
Non mi ricordo di chi ma è una citazione.
http://it.wikipedia.org/wiki/Distanza_di_Levenshtein
Si, credo sia indicato... io lo uso per riconoscere le forme nel mio gioco :D
Cmq credo che non vada bene a das, perchè:
-richiede di conoscere la stringa, e lui non vuole pescarla dal database
-richiede calcoli su di una matrice num_chars x n, e quindi è inapplicabile per prestazioni su di una pagina web...
Mi sa che quelli che ci hanno pensato stavolta hanno si fatto meglio, ma se lo sono tenuto per sè :asd:
Le tecnologie di ricerca di informazioni ultimamente sono le più ricercate e segrete di tutte... figurati se Google permette ai suoi dipendenti di anche solo accennare gli algoritmi di ricerca...
http://it.wikipedia.org/wiki/Distanza_di_Levenshtein
Grazie, ma questo algoritmo necessita la conoscenza delle due stringhe perciò non fa al caso mio.
cdimauro
25-11-2008, 07:28
A te servirebbe qualcosa di simile a questo: http://en.wikipedia.org/wiki/Soundex
Ma il problema è che "sintetizzare" un'intera pagina in pochi bit d'informazione è praticamente impossibile.
Un'ideuzza ce l'avrei, ma è un po' complicata da implementare. Te la espongo velocemente.
Utilizza un dizionario fisso di parole (es: quello della lingua italiana), e dalla tua pagina estrai tutte le parole che appartengono al dizionario conservandone anche la frequenza.
Supponiamo che tutte le parole del dizionario abbiano una posizione fissa (es: ciao = 4327), per cui anche alle parole del dizionario assocerai il medesimo indice.
Mettiamo che il dizionario sia di n parole, e tu ne abbia trovate m (<= n ovviamente). Costruisci un vettore di dimensione n in cui memorizzi la frequenza delle m parole nella posizione che gli spetta. Quindi se hai trovato ciao 3 volte, allora alla posizione 4327 metterai il valore 3.
A questo punto hai ottenuto un vettore nello spazio (del dizionario). Questo vettore formerà un certo angolo rispetto a un asse di riferimento. Ne calcoli il coseno (o il seno: è indifferente) e lo memorizzi.
D'ora in poi userai il coseno per confrontare la similitudine di una stringa con un'altra.
Lo so: è particolarmente contorto (qualche giorno chiameranno la neuro, me lo sento :D), ma a naso potrebbe andare bene per i tuoi scopi.
The_ouroboros
25-11-2008, 07:53
Lo so: è particolarmente contorto (qualche giorno chiameranno la neuro, me lo sento :D), ma a naso potrebbe andare bene per i tuoi scopi.
Molto interessante invece :eek:
A te servirebbe qualcosa di simile a questo: http://en.wikipedia.org/wiki/Soundex
Ma il problema è che "sintetizzare" un'intera pagina in pochi bit d'informazione è praticamente impossibile.
Un'ideuzza ce l'avrei, ma è un po' complicata da implementare. Te la espongo velocemente.
Utilizza un dizionario fisso di parole (es: quello della lingua italiana), e dalla tua pagina estrai tutte le parole che appartengono al dizionario conservandone anche la frequenza.
Supponiamo che tutte le parole del dizionario abbiano una posizione fissa (es: ciao = 4327), per cui anche alle parole del dizionario assocerai il medesimo indice.
Mettiamo che il dizionario sia di n parole, e tu ne abbia trovate m (<= n ovviamente). Costruisci un vettore di dimensione n in cui memorizzi la frequenza delle m parole nella posizione che gli spetta. Quindi se hai trovato ciao 3 volte, allora alla posizione 4327 metterai il valore 3.
A questo punto hai ottenuto un vettore nello spazio (del dizionario). Questo vettore formerà un certo angolo rispetto a un asse di riferimento. Ne calcoli il coseno (o il seno: è indifferente) e lo memorizzi.
D'ora in poi userai il coseno per confrontare la similitudine di una stringa con un'altra.
Lo so: è particolarmente contorto (qualche giorno chiameranno la neuro, me lo sento :D), ma a naso potrebbe andare bene per i tuoi scopi.
idea brillante!
praticamente ottieni un vettore n dimensionale in cui le parole sono le dimensioni e il valore per ogni dimensione è dato dalle singole occorrenze, ho capito bene?
cdimauro
25-11-2008, 13:26
Esattamente. :)
Veramente interessante :D
Un solo dubbio: quante parole su internet sono italiane ed anche corrette, sul totale?
E tutti i neologismi che si dicono una volta sul forum e poi non li vedi più?
Il dizionario credo te lo dovresti costruire a mano, aggiungendo un index ad ogni "first occurrence" di una parola... ma temo che poi ti serva veramente troppa memoria :D
Non per niente google ha una decina di Pb di hard disk eh :sofico:
The_ouroboros
25-11-2008, 17:22
Il dizionario credo te lo dovresti costruire a mano, aggiungendo un index ad ogni "first occurrence" di una parola... ma temo che poi ti serva veramente troppa memoria :D
Non per niente google ha una decina di Pb di hard disk eh :sofico:
in effetti un piccolo suicidio a livello di spazio occupato :fagiano:
cdimauro
25-11-2008, 20:08
L'idea invece è di utilizzare un dizionario fisso, quindi al quale non aggiungere altre parole (altrimenti per ogni nuova parola bisognerebbe ricalcolare i valori di tutte le altre pagine).
E' chiaro che con questa scelta si perderanno delle informazioni, ma l'obiettivo è quello di sintetizzare buona parte di un'intera pagina, non di rincorrere a tutti i costi una precisione che, per il tipo di problema proposto, non potrà mai esserci.
Ad esempio l'inclusione dell'intero vocabolario della lingua italiana, compresi francesismi ed eventualmente nomi e cognomi, porterebbe una notevole nonché solida base da cui partire.
Anche la memoria non credo sarebbe un problema: quanto possono occupare 150-200mila voci? Non credo tanto. Ovviamente allo scopo terrei sempre attivo un server che ha precaricato in memoria un dizionario con tutte le voci, in modo da facilitare la costruzione del vettore, che avverrebbe grossolanamente così:
Dictionary = {... dizionario ...}
def Vectorize(Text):
Vector = [0] * len(Dictionary) # Inizializza il vettore delle frequenze
Text = Text.lower() # Mette l'intero testo in lowecase
for Word in Text.split(): # Suddivide il testo in parole usando spazi, tabulatori e caratteri speciali come separatori
Index = Dictionary[Word] # Calcola l'indice della parola
if Index >= 0: # Se la parola è stata trovata nel dizionario, prosegui
Vector[] += 1 # Aggiorna la frequenza di questa parola
return Vector # Ritorna il vettore calcolato
Oceans11
25-11-2008, 22:29
A te servirebbe qualcosa di simile a questo: http://en.wikipedia.org/wiki/Soundex
Ma il problema è che "sintetizzare" un'intera pagina in pochi bit d'informazione è praticamente impossibile.
Un'ideuzza ce l'avrei, ma è un po' complicata da implementare. Te la espongo velocemente.
Utilizza un dizionario fisso di parole (es: quello della lingua italiana), e dalla tua pagina estrai tutte le parole che appartengono al dizionario conservandone anche la frequenza.
Supponiamo che tutte le parole del dizionario abbiano una posizione fissa (es: ciao = 4327), per cui anche alle parole del dizionario assocerai il medesimo indice.
Mettiamo che il dizionario sia di n parole, e tu ne abbia trovate m (<= n ovviamente). Costruisci un vettore di dimensione n in cui memorizzi la frequenza delle m parole nella posizione che gli spetta. Quindi se hai trovato ciao 3 volte, allora alla posizione 4327 metterai il valore 3.
A questo punto hai ottenuto un vettore nello spazio (del dizionario). Questo vettore formerà un certo angolo rispetto a un asse di riferimento. Ne calcoli il coseno (o il seno: è indifferente) e lo memorizzi.
D'ora in poi userai il coseno per confrontare la similitudine di una stringa con un'altra.
Lo so: è particolarmente contorto (qualche giorno chiameranno la neuro, me lo sento :D), ma a naso potrebbe andare bene per i tuoi scopi.
Similarità coseno ;)
tra una dormitina e l'altra a lezione (....:D ) mi è sembrato di carpire questo "strano" termine.
Tra le altre cose (vado sul vago perchè non ne so di più) so che un metodo efficace per indicizzare e confrontare documenti testuali è quello di calcolarsi gli autovalori della matrice dei termini e non so che altro.
Vabbè non divago oltre OT, dico solo che ci sono libri validi sull'argomento di un certo Ian Witten. Ciao!
Kralizek
25-11-2008, 22:59
ma limitando la soluzione di Cdimauro a relativamente poche parole chiavi relative ad un argomento?
cdimauro
26-11-2008, 07:25
Similarità coseno ;)
tra una dormitina e l'altra a lezione (....:D ) mi è sembrato di carpire questo "strano" termine.
Dove l'hai sentito? Funziona proprio come ho pensato io?
Tra le altre cose (vado sul vago perchè non ne so di più) so che un metodo efficace per indicizzare e confrontare documenti testuali è quello di calcolarsi gli autovalori della matrice dei termini e non so che altro.
Hum... Mi sembra un tantino oneroso prestazionalmente (già il mio algoritmo lo è abbastanza, e funziona su un vettore lineare :D).
Vabbè non divago oltre OT, dico solo che ci sono libri validi sull'argomento di un certo Ian Witten. Ciao!
Grazie per l'informazione. :)
ma limitando la soluzione di Cdimauro a relativamente poche parole chiavi relative ad un argomento?
Funzionerebbe ugualmente, posto che l'algoritmo più generale che ho descritto prima funzioni. ;)
Oceans11
26-11-2008, 09:02
Dove l'hai sentito? Funziona proprio come ho pensato io?
Sì più o meno come dicevi tu.
L'ho sentito ad una lezione di Basi di Dati Multimediali, ieri sono andato a spulciare tra le dispense ma non ho trovato niente. Se vuoi dare un'occhiata tu ti do il riferimento (http://www-dii.ing.unisi.it/~marco/bdm/) alla pagina del corso.
Ora che ci penso c'ho anche messo mani ad un corso di gestionale, ho corretto il programma di una mia amica che lo doveva calcolare. Se lo trovo lo posto.
PS: ho trovato il nome del libro:
Ian H. Witten, Alistair Moffat,Thimothy C.Bell Managing Gigabytes: Compressing and Indexing Documents and Images.
A te servirebbe qualcosa di simile a questo: http://en.wikipedia.org/wiki/Soundex
Ma il problema è che "sintetizzare" un'intera pagina in pochi bit d'informazione è praticamente impossibile.
Un'ideuzza ce l'avrei, ma è un po' complicata da implementare. Te la espongo velocemente.
Utilizza un dizionario fisso di parole (es: quello della lingua italiana), e dalla tua pagina estrai tutte le parole che appartengono al dizionario conservandone anche la frequenza.
Supponiamo che tutte le parole del dizionario abbiano una posizione fissa (es: ciao = 4327), per cui anche alle parole del dizionario assocerai il medesimo indice.
Mettiamo che il dizionario sia di n parole, e tu ne abbia trovate m (<= n ovviamente). Costruisci un vettore di dimensione n in cui memorizzi la frequenza delle m parole nella posizione che gli spetta. Quindi se hai trovato ciao 3 volte, allora alla posizione 4327 metterai il valore 3.
A questo punto hai ottenuto un vettore nello spazio (del dizionario). Questo vettore formerà un certo angolo rispetto a un asse di riferimento. Ne calcoli il coseno (o il seno: è indifferente) e lo memorizzi.
D'ora in poi userai il coseno per confrontare la similitudine di una stringa con un'altra.
Lo so: è particolarmente contorto (qualche giorno chiameranno la neuro, me lo sento :D), ma a naso potrebbe andare bene per i tuoi scopi.
Però secondo me all'aumentare di n aumenta il numero di seni da memorizzare e Pasqua torna di domenica. Memorizzando gli angoli inoltre potrei risalire a solo la direzione del vettore ma non al modulo. Questo non sarebbe un problema visto che la probabilità di ottenere due direzioni uguali da pagine diverse è comunque bassissima. Il problema è che non mi pare che l'informazione da memorizzare si riduca abbastanza. Cercavo qualcosa che desse in uscita 64 o 128 bit al massimo.
Pensavo comunque che esistesse qualcosa diciamo di 'standard' tipicamente utilizzato per risolvere questo tipo di problemi.
Veramente interessante :D
Un solo dubbio: quante parole su internet sono italiane ed anche corrette, sul totale?
E tutti i neologismi che si dicono una volta sul forum e poi non li vedi più?
Il dizionario credo te lo dovresti costruire a mano, aggiungendo un index ad ogni "first occurrence" di una parola... ma temo che poi ti serva veramente troppa memoria :D
Non per niente google ha una decina di Pb di hard disk eh :sofico:
Per il dizionario non è un problema visto che il mio programmino già ora inserisce in una tabella tutte le parole che trova a giro per internet.
Io conosco ed ho usato un algoritmo abbastanza, simile a quello esposto da cdimauro. Viene attualmente usato da qualche engine di spiders.
Invece di considerare il dizionario completo di tutte le parole, secondo questo algoritmo e' sufficiente utilizzare il dizionario di tutte le possibili terzine di un testo, con lowercase eventualmente pulite da caratteri di controllo (virgole, punti, duepunti, etc.) conservando pero' lo spazio.
Ottieni uno spazio le cui terzine possibili sono
aaa
aab
aac
aaz
a a
a b
bac
bcd
cdz
etc.
ed e' finito e completo (Circa 30^3 entries)
Passi il tuo testo originale attraverso il conto delle terzine ( O (N) )
e conti la distribuzione delle terzine
ES:
Ho rotto un rotore:
ho = 1
o r = 1
ro = 2
rot = 2
ott = 1
tto = 1
to = 1
o u = 1
un = 1
n r = 1
oto = 1
ore = 1
(Ovviamente con testi piccoli non funziona molto bene)
In teoria potrai tenere memorizzato anche solo la distribuzione, neppure la pagina vera e propria.
(A meno che ti servano funzioni di caching)
E anche ovviamente i dati che avrai rilevato e che ti serviranno per le ricerche.
quando ripasserai, ricalcolerai la distribuzione delle nuove terzine, e calcolerai la distanza tra il vecchio dizionario e quello nuovo.
Funzioni per calcolare la distanza ce ne possono essere parecchie, ma viene normalmente usato qualcosa di simile alla Levenshtein.
La distanza tipica e':
quante sono le terzine nuove che prima non c'erano (motliplicate per la loro occorrenza)
+ quante sono le terzine vecchie che non ci sono piu' (di nuovo moltiplicate)
+ la differenza di occorrenza delle terzine preservate.
Prova, a me ha dato abbastanza soddisfazioni.
PS: Ci facciamo un contest?
cdimauro
26-11-2008, 13:19
Sì più o meno come dicevi tu.
L'ho sentito ad una lezione di Basi di Dati Multimediali, ieri sono andato a spulciare tra le dispense ma non ho trovato niente. Se vuoi dare un'occhiata tu ti do il riferimento (http://www-dii.ing.unisi.it/~marco/bdm/) alla pagina del corso.
Ora che ci penso c'ho anche messo mani ad un corso di gestionale, ho corretto il programma di una mia amica che lo doveva calcolare. Se lo trovo lo posto.
PS: ho trovato il nome del libro:
Ian H. Witten, Alistair Moffat,Thimothy C.Bell Managing Gigabytes: Compressing and Indexing Documents and Images.
OK Grazie. Stasera a casa controllo le dispende, perché mi sembra molto interessante (e poi sono curioso di vedere se la mia idea è già stata sfruttata oppure no :p).
Però secondo me all'aumentare di n aumenta il numero di seni da memorizzare e Pasqua torna di domenica. Memorizzando gli angoli inoltre potrei risalire a solo la direzione del vettore ma non al modulo. Questo non sarebbe un problema visto che la probabilità di ottenere due direzioni uguali da pagine diverse è comunque bassissima. Il problema è che non mi pare che l'informazione da memorizzare si riduca abbastanza. Cercavo qualcosa che desse in uscita 64 o 128 bit al massimo.
Pensavo comunque che esistesse qualcosa diciamo di 'standard' tipicamente utilizzato per risolvere questo tipo di problemi.
Veramente con l'algoritmo che ti suggerivo avresti dovuto memorizzare soltanto il valore di un coseno, quindi considerando soltanto un angolo fra gli n possibili. Volendo potresti conservare sia il coseno (o l'angolo a questo punto) che il modulo, ma come osservavi già l'angolo sarebbe sufficiente per i tuoi scopi.
Io conosco ed ho usato un algoritmo abbastanza, simile a quello esposto da cdimauro. Viene attualmente usato da qualche engine di spiders.
:cry: Però sono curioso di vedere se è esattamente lo stesso, e comunque di capire come hanno risolto il problema dell'aggiunta di nuove parole.
Invece di considerare il dizionario completo di tutte le parole, secondo questo algoritmo e' sufficiente utilizzare il dizionario di tutte le possibili terzine di un testo, con lowercase eventualmente pulite da caratteri di controllo (virgole, punti, duepunti, etc.) conservando pero' lo spazio.
Ottieni uno spazio le cui terzine possibili sono
aaa
aab
aac
aaz
a a
a b
bac
bcd
cdz
etc.
ed e' finito e completo (Circa 30^3 entries)
Passi il tuo testo originale attraverso il conto delle terzine ( O (N) )
e conti la distribuzione delle terzine
ES:
Ho rotto un rotore:
ho = 1
o r = 1
ro = 2
rot = 2
ott = 1
tto = 1
to = 1
o u = 1
un = 1
n r = 1
oto = 1
ore = 1
(Ovviamente con testi piccoli non funziona molto bene)
In teoria potrai tenere memorizzato anche solo la distribuzione, neppure la pagina vera e propria.
(A meno che ti servano funzioni di caching)
E anche ovviamente i dati che avrai rilevato e che ti serviranno per le ricerche.
quando ripasserai, ricalcolerai la distribuzione delle nuove terzine, e calcolerai la distanza tra il vecchio dizionario e quello nuovo.
Funzioni per calcolare la distanza ce ne possono essere parecchie, ma viene normalmente usato qualcosa di simile alla Levenshtein.
La distanza tipica e':
quante sono le terzine nuove che prima non c'erano (motliplicate per la loro occorrenza)
+ quante sono le terzine vecchie che non ci sono piu' (di nuovo moltiplicate)
+ la differenza di occorrenza delle terzine preservate.
Prova, a me ha dato abbastanza soddisfazioni.
Sì, ma das voleva più che altro un algoritmo per ottenere la "firma" un certo testo e utilizzare soltanto questa per i confronti, quindi senza avere il testo già memorizzato.
PS: Ci facciamo un contest?
No, ti prego: è seccante vedere trasformato qualcosa di intellettualmente interessante in una corsa finalizzata esclusivamente alle prestazioni misurate al millisecondo.
Sì a idee e algoritmi. No ai cicli di clock.
Però sono curioso di vedere se è esattamente lo stesso, e comunque di capire come hanno risolto il problema dell'aggiunta di nuove parole.
Sì, ma das voleva più che altro un algoritmo per ottenere la "firma" un certo testo e utilizzare soltanto questa per i confronti, quindi senza avere il testo già memorizzato.
Ma infatti, verrebbe tenuta solo la firma, che e' appunto la distribuzione delle terzine invece che la distribuzione delle parole della tua proposta.
Una volta avute le 2 distribuzioni una formula di distanza e' semplice, e si puo' valutare una soglia oltre la quale vale la pena aggiornare.
L'aggiunta di nuove parole non ha alcun impatto, essendo queste a loro volta formate da qualche terzina.
Io l'ho usato proprio calcolare differenza tra frasi, e devo dire che e' abbastanza soddisfacente.
No, ti prego: è seccante vedere trasformato qualcosa di intellettualmente interessante in una corsa finalizzata esclusivamente alle prestazioni misurate al millisecondo.
Sì a idee e algoritmi. No ai cicli di clock.
Mmh. Si potrebbe fare un contest in cui vince la soluzione piu' semplice, che era anche il presupposto inziale dei contest, anche se non saprei come valutarla.
Ma infatti, verrebbe tenuta solo la firma, che e' appunto la distribuzione delle terzine invece che la distribuzione delle parole della tua proposta.
Una volta avute le 2 distribuzioni una formula di distanza e' semplice, e si puo' valutare una soglia oltre la quale vale la pena aggiornare.
L'aggiunta di nuove parole non ha alcun impatto, essendo queste a loro volta formate da qualche terzina.
Io l'ho usato proprio calcolare differenza tra frasi, e devo dire che e' abbastanza soddisfacente.
Mmh. Si potrebbe fare un contest in cui vince la soluzione piu' semplice, che era anche il presupposto inziale dei contest, anche se non saprei come valutarla.
Idea: vedere le due stringhe come sequenze discrete (segnale discreto) e calcolare la crosscorrelazione: se i due segnali sono non correlati (la cross-correlazione è zero) => le due stringhe sono (molto) diverse; se invece la
cc è inifinita sono identiche. Stabilendo una soglia si potrebbe scegliere il grado di similitudine che ci interessa. E' corretto ?
Idea: vedere le due stringhe come sequenze discrete (segnale discreto) e calcolare la crosscorrelazione: se i due segnali sono non correlati (la cross-correlazione è zero) => le due stringhe sono (molto) diverse; se invece la
cc è inifinita sono identiche. Stabilendo una soglia si potrebbe scegliere il grado di similitudine che ci interessa. E' corretto ?
a parte che per calcolarla ti servirebbero entrambe le stringhe sempre, e non solo una loro firma, mi sa che non e' corretto
la stringa
AAAAAA e BBBBBB intese come segnali avrebbero una correlazione
AAAAAA e CCCCC invece ce l'avrebbero piu' bassa, e non ce ne sarebbe motivo.
Vincenzo1968
26-11-2008, 14:48
...
Mmh. Si potrebbe fare un contest in cui vince la soluzione piu' semplice, che era anche il presupposto inziale dei contest, anche se non saprei come valutarla.
Si potrebbe fare che io non partecipo. E il problema è risolto ;)
:bimbo:
a parte che per calcolarla ti servirebbero entrambe le stringhe sempre, e non solo una loro firma, mi sa che non e' corretto
la stringa
AAAAAA e BBBBBB intese come segnali avrebbero una correlazione
AAAAAA e CCCCC invece ce l'avrebbero piu' bassa, e non ce ne sarebbe motivo.
ok, per il discorso che servirebbero le stringhe. ma per il grado di similitudine fra due segnali non penso di aver sbagliato (se vuoi è anche il principio del riconoscimento facciale). confermi ?
Vincenzo1968
26-11-2008, 15:03
Sul problema in questione, segnalo questi due libri:
Christopher D. Manning - Prabhakar Raghavan - Hinrich Schütze
An Introduction to Information Retrieval
Cambridge University Press
Ricardo Baeza-Yates - Berthier Ribeiro-Neto
Modern Information Retrieval
Addison-Wesley
Si veda, in particolare, di quest'ultimo libro, il capitolo 13 : Searching the WEB
:bimbo:
P.S. Idea: si potrebbe fare una specie di concorso di bellezza: una giuria voterà il codice più semplice ed elegante. In fondo, per questo tipo di problemi, la velocità non conta, no? Il team di google sicuramente preferisce codice elegante. Se ne stracatafottono se i risultati della ricerca vengono mostrati dopo un'ora. ;)
DanieleC88
26-11-2008, 15:55
<off-topic>
Mmh. Si potrebbe fare un contest in cui vince la soluzione piu' semplice, che era anche il presupposto inziale dei contest, anche se non saprei come valutarla.
Se si stabiliscono dei parametri di riferimento per la valutazione (che magari possono essere diversi da contest a contest, a seconda delle necessità), direi che lo scontro idea/efficienza implementativa passerebbe in secondo piano, e il problema sarebbe risolto. Io sono favorevole a continuare i contest. :)
</off-topic>
ok, per il discorso che servirebbero le stringhe. ma per il grado di similitudine fra due segnali non penso di aver sbagliato (se vuoi è anche il principio del riconoscimento facciale). confermi ?
Allora, prova a definire cosa significa "Segnale discreto associato ad una stringa"
e poi prendi la definzione fisica di correlazione di segnali.
Prova poi a cercare la correlazione, che e' un valore reale, tra le seguenti:
"Pippo pluto paperino" con "Pippo pluto paperino e mio zio"
e poi
"HHHHH" con "HHHHH"
e poi
"HHHHH" con "TTTTT"
e poi
"HHHHH" con "AAAAA"
P.S. Idea: si potrebbe fare una specie di concorso di bellezza: una giuria voterà il codice più semplice ed elegante. In fondo, per questo tipo di problemi, la velocità non conta, no? Il team di google sicuramente preferisce codice elegante. Se ne stracatafottono se i risultati della ricerca vengono mostrati dopo un'ora. ;)
Io l'avevo proposto durante uno degli ultimi contest, senza ricevere risposta.
Ah, io ero serio però.
banryu79
26-11-2008, 16:43
Fin'ora ho seguito con interesse tutti i contest che ci sono stati. per me sono una bella occasione per vedere codice scritto da gente più esperta, scoprire cose nuove e qualche volta spunti per ragionare.
Il fatto che sia sempre finito in primo piano l'aspetto della velocità di esecuzione è, secondo me, dovuto soprattutto al fatto che i tempi di velocità sono *più o meno* facilmente misurabili e non serve una giuria: i risultati (i tempi) sono subito confrontabili.
Viceversa è un po' più dura giudicare il codice rispetto altri fattori, però si può sempre scegliere qualche parametro di riferimento.
Vedo difficile, se non tramite delle linee guida e una giuria preposta, valutare l'eleganza del codice o lo stile, tanto per fare un esempio estremo (anche perchè in parte sono percezioni che cambiano soggettivamente).
Certo però che si potrebbero prendere in considerazione altri parametri, ne sparo uno: la complessità ciclomatica delle funzioni/metodi che implementano l'algoritmo in oggetto al contest, per esemprio.
Fin'ora ho seguito con interesse tutti i contest che ci sono stati. per me sono una bella occasione per vedere codice scritto da gente più esperta, scoprire cose nuove e qualche volta spunti per ragionare.
Il fatto che sia sempre finito in primo piano l'aspetto della velocità di esecuzione è, secondo me, dovuto soprattutto al fatto che i tempi di velocità sono *più o meno* facilmente misurabili e non serve una giuria: i risultati (i tempi) sono subito confrontabili.
Viceversa è un po' più dura giudicare il codice rispetto altri fattori, però si può sempre scegliere qualche parametro di riferimento.
Vedo difficile, se non tramite delle linee guida e una giuria preposta, valutare l'eleganza del codice o lo stile, tanto per fare un esempio estremo (anche perchè in parte sono percezioni che cambiano soggettivamente).
Scusa ma i concorsi di bellezza come funzionano? E' chiaro che i parametri variano soggettivamente, ma il meccanismo è democratico. Ognuno vota il codice di qualcun'altro, e chi fa di più vince. Io non sono un ingegnere, voglio che l'estetica e l'eleganza abbiano un valore! :P
Certo però che si potrebbero prendere in considerazione altri parametri, ne sparo uno: la complessità ciclomatica delle funzioni/metodi che implementano l'algoritmo in oggetto al contest, per esemprio.
La complessità ciclomatica va bene per i linguaggi "normali". Se scrivo una soluzione in Factor (http://factorcode.org , dato che mi sta appassionando in questi giorni lo tiro fuori), ad esempio, non è molto significativa secondo me...
Allora, prova a definire cosa significa "Segnale discreto associato ad una stringa"
e poi prendi la definzione fisica di correlazione di segnali.
Prova poi a cercare la correlazione, che e' un valore reale, tra le seguenti:
"Pippo pluto paperino" con "Pippo pluto paperino e mio zio"
e poi
"HHHHH" con "HHHHH"
e poi
"HHHHH" con "TTTTT"
e poi
"HHHHH" con "AAAAA"
facco l'autocorrelazione della sequenza originaria (codifica binaria) con un tau di ritardo fissato: ottengo un valore reale X. faccio l'autocorrelazione della suqueza di confronto con stesso tau ottenendo Y. Se X diverso Y => le due sequenze sono diverse. dove sbaglio ?
facco l'autocorrelazione della sequenza originaria (codifica binaria) con un tau di ritardo fissato: ottengo un valore reale X. faccio l'autocorrelazione della suqueza di confronto con stesso tau ottenendo Y. Se X diverso Y => le due sequenze sono diverse. dove sbaglio ?
Ma provalo per cortesia, provalo per quei 4 esempi sopra messi.
La correlazione tra "AAAAA" e "AAAAA"
e poi tra "ZZZZZ" e "ZZZZZ" da valori diversi o uguali? Quale sarebbe la distanza tra queste 2 coppie di stringhe?
Ma provalo per cortesia, provalo per quei 4 esempi sopra messi.
La correlazione tra "AAAAA" e "AAAAA"
e poi tra "ZZZZZ" e "ZZZZZ" da valori diversi o uguali? Quale sarebbe la distanza tra queste 2 coppie di stringhe?
ok, forse troppe ore all'uni mi hanno sballato oggi :) ..... chiederò lumi , ciao
banryu79
26-11-2008, 17:31
Scusa ma i concorsi di bellezza come funzionano? E' chiaro che i parametri variano soggettivamente, ma il meccanismo è democratico. Ognuno vota il codice di qualcun'altro, e chi fa di più vince. Io non sono un ingegnere, voglio che l'estetica e l'eleganza abbiano un valore! :P
Sì, naturalmente, mi sono espresso male: io intendevo appunto sottolineare come nei vari contest passati sia "naturalmente" emersa la comparazione dei tempi di esecuzione perchè più facili da rilevare e postare (e verificare)...
Intendevo dire che non mi sono stupito del fatto che l'attenzione alla fine sia caduta quasi solo sui tempi di esecuzione, non che questi siano gli unici meritevoli di un confronto/miglioramento e quindi gli unici candidati ad essere parametri di valutazione in un generico Contest, non so se mi spiego.
Neanche io sono un ingegnere, diciamo che sono un "praticone" ma la cosa che più mi affascina della programmazione e proprio la possibilità di esprimere una soluzione complessa in un "bel modo": ben venga l'eleganza, l'ordine, la chiarezza, la potenza espressiva di un linguaggio/codice/stile di scrittura dello stesso.
La complessità ciclomatica va bene per i linguaggi "normali". Se scrivo una soluzione in Factor (http://factorcode.org , dato che mi sta appassionando in questi giorni lo tiro fuori), ad esempio, non è molto significativa secondo me...
Ho proposto la prima cosa che conoscevo e che mi è venuta in mente. Ho letto qualcosa di Factor ma non l'ho mai preso in mano; perchè non sarebbe significativa una soluziona scritta con questo linguaggio rispetto ad una valutazione della sua complessità ciclomatica?
A te servirebbe qualcosa di simile a questo: http://en.wikipedia.org/wiki/Soundex
Ma il problema è che "sintetizzare" un'intera pagina in pochi bit d'informazione è praticamente impossibile.
Un'ideuzza ce l'avrei, ma è un po' complicata da implementare. Te la espongo velocemente.
Utilizza un dizionario fisso di parole (es: quello della lingua italiana), e dalla tua pagina estrai tutte le parole che appartengono al dizionario conservandone anche la frequenza.
Supponiamo che tutte le parole del dizionario abbiano una posizione fissa (es: ciao = 4327), per cui anche alle parole del dizionario assocerai il medesimo indice.
Mettiamo che il dizionario sia di n parole, e tu ne abbia trovate m (<= n ovviamente). Costruisci un vettore di dimensione n in cui memorizzi la frequenza delle m parole nella posizione che gli spetta. Quindi se hai trovato ciao 3 volte, allora alla posizione 4327 metterai il valore 3.
A questo punto hai ottenuto un vettore nello spazio (del dizionario). Questo vettore formerà un certo angolo rispetto a un asse di riferimento. Ne calcoli il coseno (o il seno: è indifferente) e lo memorizzi.
D'ora in poi userai il coseno per confrontare la similitudine di una stringa con un'altra.
Lo so: è particolarmente contorto (qualche giorno chiameranno la neuro, me lo sento :D), ma a naso potrebbe andare bene per i tuoi scopi.
Io conosco ed ho usato un algoritmo abbastanza, simile a quello esposto da cdimauro. Viene attualmente usato da qualche engine di spiders.
Invece di considerare il dizionario completo di tutte le parole, secondo questo algoritmo e' sufficiente utilizzare il dizionario di tutte le possibili terzine di un testo, con lowercase eventualmente pulite da caratteri di controllo (virgole, punti, duepunti, etc.) conservando pero' lo spazio.
Ottieni uno spazio le cui terzine possibili sono
aaa
aab
aac
aaz
a a
a b
bac
bcd
cdz
etc.
ed e' finito e completo (Circa 30^3 entries)
Passi il tuo testo originale attraverso il conto delle terzine ( O (N) )
e conti la distribuzione delle terzine
ES:
Ho rotto un rotore:
ho = 1
o r = 1
ro = 2
rot = 2
ott = 1
tto = 1
to = 1
o u = 1
un = 1
n r = 1
oto = 1
ore = 1
Credo che a questo punto la soluzione sia un misto dei due sistemi.
Il primo mi garantisce che la firma ha sempre lo stesso numero di bit (dipende solo dalla precisione con cui calcolo il seno dell'angolo).
Il secondo mi garantisce di operare su un dizionario a dimensione fissa.
Dunque secondo me la cosa migliore è applicare il principio di cdimauro su un dizionario di terzine anzichè di parole.
Credo che inizierò a fare qualche esperimento in questo senso.
L'unica cosa che mi stupisce è che non esista una soluzione preconfezionata come per il crc o l'md5. Ma possibile che questo problema sia capitato solo a me? :)
Cos'è esattamente un contest ?
Vincenzo1968
26-11-2008, 18:12
...
Cos'è esattamente un contest ?
Contest 1 (http://www.hwupgrade.it/forum/showthread.php?t=1784948)
Contest 2 (http://www.hwupgrade.it/forum/showthread.php?t=1785752)
Contest 3 (http://www.hwupgrade.it/forum/showthread.php?t=1787500)
Contest 4 (http://www.hwupgrade.it/forum/showthread.php?t=1791293)
Contest 5 (http://www.hwupgrade.it/forum/showthread.php?t=1799059)
Contest 6 (http://www.hwupgrade.it/forum/showthread.php?t=1850150)
Contest 7 (http://www.hwupgrade.it/forum/showthread.php?t=1839674)
:bimbo:
ah, avevo intuito ch fossero delle specie di gare ma non pensavo che fossero così 'istituzionalizzate'.
Tornando al problema del topic, mi viene però un dubbio: supponiamo che lo spazio sia tridimensionale. Ho dunque in ballo 2 angoli che variano in funzione di tre coordinate. Però se io considero solo 1 angolo, potrebbe essere che una delle 3 coordinate vari tantissimo senza che quell'angolo ne sia minimamente influenzato. La probabilità che ciò avvenga cresce con l'aumentare delle dimensioni.
Dunque la cosa non funziona mi sa.
Secondo me si potrebbe fare qualcosa con la funzione di correlazione.
Mi spiego, visto che per calcolare la correlazione servono avere i dati sotto mano, stabiliamo quindi di calcolare la correlazione con una terza funzione di riferimento.
Forse e dico forse, per la proprietà transitiva se la correlazione fra A e R è simile alla correlazione fra B e R allora il match è positivo.
Ora resta da stabilire come memorizzare la funzione di correlazione di una stringa, meglio sarebbe memorizzarla di un intero documento. Resta anche da stabilire la funzione di riferimento.
Imho insieme ad altri parametri statistici, come media e deviazione standard si potrebbe riuscire a tirare fuori qualcosa ;)
Se non sbaglio la funzione di correlazione è assimilabile ad un integrale di convoluzione, in tal caso si potrebbe fare una trasformata discreta di Fourier in modo da ridurre la convoluzione ad un semplice prodotto.
PS: sono ricordi abbastanza confusi che sto cercando di rimettere insieme...non sono un matematico :asd:
Secondo me si potrebbe fare qualcosa con la funzione di correlazione.
Mi spiego, visto che per calcolare la correlazione servono avere i dati sotto mano, stabiliamo quindi di calcolare la correlazione con una terza funzione di riferimento.
Forse e dico forse, per la proprietà transitiva se la correlazione fra A e R è simile alla correlazione fra B e R allora il match è positivo.
Ora resta da stabilire come memorizzare la funzione di correlazione di una stringa, meglio sarebbe memorizzarla di un intero documento. Resta anche da stabilire la funzione di riferimento.
Imho insieme ad altri parametri statistici, come media e deviazione standard si potrebbe riuscire a tirare fuori qualcosa ;)
Se non sbaglio la funzione di correlazione è assimilabile ad un integrale di convoluzione, in tal caso si potrebbe fare una trasformata discreta di Fourier in modo da ridurre la convoluzione ad un semplice prodotto.
PS: sono ricordi abbastanza confusi che sto cercando di rimettere insieme...non sono un matematico :asd:
La trasformata che ti consente di trasformare una convoluzione in un prodotto è quella di Laplace, non credo che funzioni anche con Fourier.
Nel caso di trasformata di Laplace mi sa che non sarebbe fattibile visto che a disposizione avrei dei numeri non un equazione.
Quella di Fourier è una generalizzazione di quella di Laplace.
Sul fatto che
T{f(x)g(x)} = F(f)*G(f)
con * convoluzione, sono sicuro.
E sono quasi sicuro anche del duale:
T{f(x)*g(x)} = F(f)G(f)
Riguardo alla trasformata, c'è appunto quella discreta di Fourier che lavora su n-uple di dati ;) Non a caso è usata in tutti gli algoritmi di calcolo numerico, anzi è usato un caso particolare della DFT, cioè la Discrete Cosine Transform (DCT)...computazionalmente meno impegnativa.
Vincenzo1968
26-11-2008, 19:11
Quella di Fourier è una generalizzazione di quella di Laplace.
Sul fatto che
T{f(x)g(x)} = F(f)*G(f)
con * convoluzione, sono sicuro.
E sono quasi sicuro anche del duale:
T{f(x)*g(x)} = F(f)G(f)
Riguardo alla trasformata, c'è appunto quella discreta di Fourier che lavora su n-uple di dati ;) Non a caso è usata in tutti gli algoritmi di calcolo numerico, anzi è usato un caso particolare della DFT, cioè la Discrete Cosine Transform (DCT)...computazionalmente meno impegnativa.
Alla faccia der... padre de li santi :D Meno male che non sei un matematico.
:bimbo:
Meno male che non sei un matematico.
Se fossi stato un matematico sarei stato sicuro di quello che dicevo :D
Sono reminescenze di teoria dei segnali :asd:
Vincenzo1968
26-11-2008, 20:55
Ohé Cionci,
forse hai sbagliato discussione:
http://www.hwupgrade.it/forum/showthread.php?t=1841739&page=29
Visto che ne avete parlato, faccio qui la mia proposta per il contest.
L'idea è quella di rendere il più possibile indipendente il contest dal linguaggio e di poter giudicare l'algoritmo migliore e non il programma più veloce.
Come fare ? L'unica soluzione che mi viene in mente è quella di proporre una soluzione di riferimento in pseudo-linguaggio data da chi propone il contest. Ovviamente questa sarà la soluzione più immediata, ma anche computazionalmente meno efficiente (ed esempio la forza bruta).
Per ogni linguaggio che partecipa al contest, il primo che lo usa deve proporre una soluzione che rispecchia fedelmente la soluzione in pseudo-linguaggio, con tanto di struttura e nomi corrispondenti.
Chi crea il contest si occuperà di raccogliere queste soluzioni nel primo post. Queste saranno le soluzioni di riferimento sulle quali il contest si dovrà basare e sulle quali verranno prese le misure di prestazioni delle soluzioni ottimizzate.
Posto 1000 il valore della soluzione di riferimento si dovrà ottenere il coefficiente relativo alla soluzione ottimizzata in questo modo:
X = (TempoEsecuzioneSoluzioneOttimizzata / TempoEsecuzioneSoluzioneRiferimento) * 1000
Vince il contest chi ottiene il coefficiente migliore rispetto alla soluzione di riferimento nel proprio linguaggio.
Dovevi postarlo qui, giusto?
:bimbo:
cdimauro
26-11-2008, 21:03
Ma infatti, verrebbe tenuta solo la firma, che e' appunto la distribuzione delle terzine invece che la distribuzione delle parole della tua proposta.
Una volta avute le 2 distribuzioni una formula di distanza e' semplice, e si puo' valutare una soglia oltre la quale vale la pena aggiornare.
L'aggiunta di nuove parole non ha alcun impatto, essendo queste a loro volta formate da qualche terzina.
Io l'ho usato proprio calcolare differenza tra frasi, e devo dire che e' abbastanza soddisfacente.
Scusami, sono andato di fretta e a questo punto non avevo ben chiaro cosa volevi dire.
Tutto OK, ho capito e sono d'accordo con te.
Mmh. Si potrebbe fare un contest in cui vince la soluzione piu' semplice, che era anche il presupposto inziale dei contest, anche se non saprei come valutarla.
Già. Il presupposto iniziale. Hai detto bene. ;)
P.S. Idea: si potrebbe fare una specie di concorso di bellezza: una giuria voterà il codice più semplice ed elegante. In fondo, per questo tipo di problemi, la velocità non conta, no? Il team di google sicuramente preferisce codice elegante. Se ne stracatafottono se i risultati della ricerca vengono mostrati dopo un'ora. ;)
Perché parli di cose che non conosci? Ecco qui (http://www.sauria.com/~twl/conferences/pycon2005/20050325/Python%20at%20Google.html) e qui (http://mail.python.org/pipermail/python-list/2007-September/458741.html). In particolare, da quest'ultimo:
YouTube (one of Google's most valuable properties) is essentially all-Python (except for open-source infrastructure components such as lighttpd). Also, at Google I'm specifically "Uber Tech Lead, Production Systems": while I can't discuss details, my main responsibilities relate to various software projects that are part of our "deep infrastructure", and our general philosophy there is "Python where we can, C++ where we must". Python is definitely not "just a tiny little piece" nor (by a long shot) used only for "scripting" tasks; if the mutant space-eating nanovirus should instantly stop the execution of all Python code, the powerful infrastructure that has been often described as "Google's secret weapon" would seize up.
:rolleyes:
Scusa ma i concorsi di bellezza come funzionano? E' chiaro che i parametri variano soggettivamente, ma il meccanismo è democratico. Ognuno vota il codice di qualcun'altro, e chi fa di più vince. Io non sono un ingegnere, voglio che l'estetica e l'eleganza abbiano un valore! :P
Non posso che concordare. :)
Credo che a questo punto la soluzione sia un misto dei due sistemi.
Il primo mi garantisce che la firma ha sempre lo stesso numero di bit (dipende solo dalla precisione con cui calcolo il seno dell'angolo).
Il secondo mi garantisce di operare su un dizionario a dimensione fissa.
Dunque secondo me la cosa migliore è applicare il principio di cdimauro su un dizionario di terzine anzichè di parole.
Credo che inizierò a fare qualche esperimento in questo senso.
Mi sembra una buona soluzione, che unisce il meglio delle due idee. :)
L'unica cosa che mi stupisce è che non esista una soluzione preconfezionata come per il crc o l'md5. Ma possibile che questo problema sia capitato solo a me? :)
Beh, io non mi occupo di classificazione e organizzazione delle informazioni modello motore di ricerca, per cui questo campo non mi è noto, ma qualcuno di sicuro c'avrà sbattuto la testa e qualche buon risultato dovrà averlo ottenuto a giudicare dalla proliferazione dei motori di ricerca. :D
ah, avevo intuito ch fossero delle specie di gare ma non pensavo che fossero così 'istituzionalizzate'.
Tornando al problema del topic, mi viene però un dubbio: supponiamo che lo spazio sia tridimensionale. Ho dunque in ballo 2 angoli che variano in funzione di tre coordinate. Però se io considero solo 1 angolo, potrebbe essere che una delle 3 coordinate vari tantissimo senza che quell'angolo ne sia minimamente influenzato. La probabilità che ciò avvenga cresce con l'aumentare delle dimensioni.
Dunque la cosa non funziona mi sa.
Neanche considerando la coppia angolo e modulo, allora.
Vincenzo1968
26-11-2008, 23:28
Perché spacciare per proprie le altrui idee?
Ricerca su google con le chiavi:
"similarità coseno" o "information retrieval" + "modello vettoriale". :)
Ohé Cionci,
forse hai sbagliato discussione:
http://www.hwupgrade.it/forum/showthread.php?t=1841739&page=29
Dovevi postarlo qui, giusto?
:bimbo:
Hai ragione :muro:
L'ho messa qui: http://www.hwupgrade.it/forum/showthread.php?t=1872715
cdimauro
27-11-2008, 08:05
Perché spacciare per proprie le altrui idee?
Ricerca su google con le chiavi:
"similarità coseno" o "information retrieval" + "modello vettoriale". :)
La ricerca l'ho fatta e ho trovato cose interessanti. A questo punto ti giro io la domanda: il thread l'hai letto? Hai capito come funziona l'algoritmo che ho proposto? Se sì, mi DIMOSTRERESTI dove e come avrei copiato un'idea altrui, cortesemente?
Prima di fare un'affermazione gratuita e pesante come questa, che è chiaramente volta a infagarmi visti i precedenti che abbiamo avuto, dovresti quanto meno assicurarti che abbia un minimo di fondamento.
Per inciso: gli spazi vettoriali e relativi calcoli di angoli, modulo, ecc. si studiano in un corso base (in tutti i sensi) di geometria. Di applicazioni pratiche in tanti campi se ne affrontano diverse in altri corsi universitari, e ciò permette di comprendere meglio e affinare l'uso di questi strumenti matematici.
La mia proposta altro non è che un'applicazione, appunto, di queste nozioni, e fortunatamente NON coincide con gli algoritmi di information retrieval che ho trovato seguendo le tue indicazioni.
In ogni caso l'onere della prova sta a te, che hai tirato in ballo la questione della presunta "copia". Sono curioso di leggere la tua "dimostrazione".
Ho proposto la prima cosa che conoscevo e che mi è venuta in mente. Ho letto qualcosa di Factor ma non l'ho mai preso in mano; perchè non sarebbe significativa una soluziona scritta con questo linguaggio rispetto ad una valutazione della sua complessità ciclomatica?
Scusa per i toni nel precedente messaggio... mi sono accorto di aver scritto con la modalità cagacazzo attivata.
Cmq volevo semplicemente dire che è probabile che in una soluzione in factor (o in haskell, per dirne un altro), non siano proprio presenti 'if', 'for', 'switch', ecc... e quindi si, la complessità ciclomatica la puoi sempre calcolare, ma non è molto significativa come misura secondo me.
Vincenzo1968
27-11-2008, 14:23
La ricerca l'ho fatta e ho trovato cose interessanti. A questo punto ti giro io la domanda: il thread l'hai letto? Hai capito come funziona l'algoritmo che ho proposto? Se sì, mi DIMOSTRERESTI dove e come avrei copiato un'idea altrui, cortesemente?
Prima di fare un'affermazione gratuita e pesante come questa, che è chiaramente volta a infagarmi visti i precedenti che abbiamo avuto, dovresti quanto meno assicurarti che abbia un minimo di fondamento.
Per inciso: gli spazi vettoriali e relativi calcoli di angoli, modulo, ecc. si studiano in un corso base (in tutti i sensi) di geometria. Di applicazioni pratiche in tanti campi se ne affrontano diverse in altri corsi universitari, e ciò permette di comprendere meglio e affinare l'uso di questi strumenti matematici.
La mia proposta altro non è che un'applicazione, appunto, di queste nozioni, e fortunatamente NON coincide con gli algoritmi di information retrieval che ho trovato seguendo le tue indicazioni.
In ogni caso l'onere della prova sta a te, che hai tirato in ballo la questione della presunta "copia". Sono curioso di leggere la tua "dimostrazione".
Nel tuo post non c'è traccia di 'corsi di base' e, a giudicare anche dallo stupore col quale hai accolto l'intervento di Oceans11, sembrerebbe che l'idea l'hai partorita interamente per conto tuo:
Dove l'hai sentito? Funziona proprio come ho pensato io?
Per carità, può capitare: io, per esempio, avevo inventato il quicksort. Non ti dico la delusione quando ho saputo che ci aveva già pensato un certo Hoare :bimbo:
Perché parli di cose che non conosci? Ecco qui e qui. In particolare, da quest'ultimo:
YouTube (one of Google's most valuable properties) is essentially all-Python (except for open-source infrastructure components such as lighttpd). Also, at Google I'm specifically "Uber Tech Lead, Production Systems": while I can't discuss details, my main responsibilities relate to various software projects that are part of our "deep infrastructure", and our general philosophy there is "Python where we can, C++ where we must". Python is definitely not "just a tiny little piece" nor (by a long shot) used only for "scripting" tasks; if the mutant space-eating nanovirus should instantly stop the execution of all Python code, the powerful infrastructure that has been often described as "Google's secret weapon" would seize up.
Cosa c'entra l'osservazione che mi hai fatto? Chi aveva parlato di python? che c'entrano quei link a google-python che mi hai postato? E, ciliegina sulla torta, l'attacco personale(a proposito d'infangare): parli di cose che non conosci.
Mi pare che si vada a peggiorare. Prima bastava dar di tocco a una qualche critica su python. Adesso, basta che si parli di inefficienza, che ti senti chiamato per nome, cognome e soprannome.
:bimbo:
EDIT: in un altro thread avevo detto che i clienti della mia azienda si lamentavano per la lentezza di certe applicazioni. Tu hai messo in dubbio la cosa, dandomi praticamente del bugiardo. Ora, ti cito, prima di fare un'affermazione gratuita e pesante come questa, avresti qualche prova da mostrare?
banryu79
27-11-2008, 15:24
Scusa per i toni nel precedente messaggio... mi sono accorto di aver scritto con la modalità cagacazzo attivata.
Ok, grazie di avermi rassicurato, mi era parso di cogliere una reazione "disallineata" sotto il profilo emotivo rispetto ai contenuti che avevo espresso (forse poco chiaramente) nel mio post precedente a quello tuo a cui ti risferisci.
Cmq volevo semplicemente dire che è probabile che in una soluzione in factor (o in haskell, per dirne un altro), non siano proprio presenti 'if', 'for', 'switch', ecc... e quindi si, la complessità ciclomatica la puoi sempre calcolare, ma non è molto significativa come misura secondo me.
Oki, sì come vedi sono totalmente noob sui linguaggi funzionali... so solo che esistono :sofico:
Capito, grazie :)
cdimauro
27-11-2008, 19:50
Nel tuo post non c'è traccia di 'corsi di base'
Ci mancherebbe: proprio perché è di base perché dovrei parlarne? Se applico una trasformata di Fourier, del Coseno, una Wavelet, ecc. c'è bisogno di dire che sto usando delle basi e dei vettori? Qui è lo stesso.
e, a giudicare anche dallo stupore col quale hai accolto l'intervento di Oceans11, sembrerebbe che l'idea l'hai partorita interamente per conto tuo:
Togli pure il "sembrerebbe": l'idea dell'algoritmo che ho esposto è mia.
Per carità, può capitare: io, per esempio, avevo inventato il quicksort. Non ti dico la delusione quando ho saputo che ci aveva già pensato un certo Hoare :bimbo:
Capita. Nel mio caso io aspetto ancora la dimostrazione che l'algoritmo che ho esposto sia frutto di idee altrui.
Mi hai chiesto di fare delle ricerche con delle precise parole chiavi e l'ho fatto. Non mi pare di aver trovato nessuno che abbia descritto un algoritmo come il mio. Visto che sei stato tu a parlare di "spacciare per proprie le altrui idee" (testuali parole), mi aspetto che prendi il mio post con la descrizione dell'algoritmo e posti il link e riporti la descrizione di un algoritmo che sia corrispondente al mio.
In assenza, non dovresti avere difficoltà a scusarti e a rimangiarti quello che avevi detto.
Cosa c'entra l'osservazione che mi hai fatto? Chi aveva parlato di python? che c'entrano quei link a google-python che mi hai postato? E, ciliegina sulla torta, l'attacco personale(a proposito d'infangare): parli di cose che non conosci.
Mi pare che si vada a peggiorare. Prima bastava dar di tocco a una qualche critica su python. Adesso, basta che si parli di inefficienza, che ti senti chiamato per nome, cognome e soprannome.
:bimbo:
EDIT: in un altro thread avevo detto che i clienti della mia azienda si lamentavano per la lentezza di certe applicazioni. Tu hai messo in dubbio la cosa, dandomi praticamente del bugiardo. Ora, ti cito, prima di fare un'affermazione gratuita e pesante come questa, avresti qualche prova da mostrare?
Io non ho alcuna difficoltà a farlo. Ecco da qui (http://www.hwupgrade.it/forum/showpost.php?p=25180739&postcount=27):
P.S. Idea: si potrebbe fare una specie di concorso di bellezza: una giuria voterà il codice più semplice ed elegante. In fondo, per questo tipo di problemi, la velocità non conta, no? Il team di google sicuramente preferisce codice elegante. Se ne stracatafottono se i risultati della ricerca vengono mostrati dopo un'ora.
Se a Google interessasse soltanto la velocità, non utilizzerebbe Python, ma C e/o C++. Visto che la velocità NON è l'unica variabile che gli interessa (tanto per cambiare), usano Python.
Di più: Python è la soluzione preferita, e il C++ è, anzi, usato soltanto se è ritenuto indispensabile, come puoi ben leggere da uno dei più apprezzati ingegneri capo di questa multinazionale.
Il primo link l'ho postato perché snocciola numerosi casi d'uso in cui evidenziano le problematiche affrontate, le soluzioni trovate e le motivazioni.
Questo sempre a dimostrazione che le prestazioni non sono affatto l'unico pensiero di Google.
P.S. Python permette di scrivere codice più elegante di quello C++. Dai un'occhiata al codice rilasciato da Google: http://code.google.com/hosting/projects.html
banryu79
28-11-2008, 08:27
P.S. Python permette di scrivere codice più elegante di quello C++. Dai un'occhiata al codice rilasciato da Google: http://code.google.com/hosting/projects.html
Anche più elegante rispetto a Java.
Ho guardato l'implementazione di questa classe, e la "differenza stilistica" salta all'occhio:
- CheckKeywordTraffic.java (http://code.google.com/p/adwords-api-java-samples/source/browse/trunk/src/CheckKeywordTraffic.java)
- check_keyword_traffic.py (http://code.google.com/p/adwords-api-python-samples/source/browse/trunk/src/check_keyword_traffic.py)
Mi ha colpito soprattutto il fatto che nel leggere questi due sorgenti ho avuto meno "difficoltà di parsing" con l'implementazione in Python, nonostante non conosca questo linguaggio e invece in Java ci lavoro quasi quotidianamente...
P.S.: voglio però far notare che in generale mi sembra che i linguaggi dinamici siano sempre un po' più eleganti/leggibili dei loro fratelli più statici.
cdimauro
28-11-2008, 14:04
La mia impressione è che i linguaggi dinamici siano soltanto più sintetici (generalmente), ma non anche più elegnati. Per me concetti come eleganza e leggibilità sono determinati più che altro dalla sintassi (e ovviamente dal programmatore, ma questo è pacifico).
Se hai trovato Python più leggibile, credo sia dovuto al fatto che la sua sintassi sia semplice e facilmente assimilabile. Diciamo che gradevole all'occhio e alla mente.
Ma non sono caratteristiche che ritrovi in altri linguaggi. Se prendiamo Perl (che è un altro linguaggio dinamico), vediamo che che ha fatto della (estrema) sintesi il suo punto di forza, ma a costo della leggibilità e dell'eleganza.
P.S. Bello l'esempio che hai preso: utilissimo al confronto e a quello che volevo dire prima. :)
banryu79
28-11-2008, 15:35
La mia impressione è che i linguaggi dinamici siano soltanto più sintetici (generalmente), ma non anche più elegnati. Per me concetti come eleganza e leggibilità sono determinati più che altro dalla sintassi (e ovviamente dal programmatore, ma questo è pacifico).
Sì, forse è meglio se specifico un po' di più quello che intendevo dire: nell'esempio che ho portato, la sensazione di "maggiore eleganza e semplicità" nella lettura del codice che ho provato, in realtà è dovuta, per me abituato a leggere codice Java, nella mancanza di ridondanze del codice Python (dovuto principalmente alla omissione dello specificatore di tipo in fase di dichiarazione/inizializzazione delle variabili).
Ho anche avuto una sensazione maggiore "di leggerezza" nel colpo d'occhio sulla pagina intera, rispetto a codice Java (con cui, ripeto, mi trovo benissimo e ci lavoro normalmente), data credo dalla mancanza di parentesi in Python per la definizione di inizio e fine di uno scope e l'uso invece di keyword (anche se devo dire che in parte è dovuto al fatto che io sono abituato ad usare le parentesi in Java con uno stile simile a quello che si usa in C++, lo trovo più chiaro).
Non l'avrei mai detto ma 'sta cosa mi ha dato la sensazione di poter identificare a colpo d'occhio dove stanno le varie cose con semplicità e da questo la piacevole sensazione di aver più controllo rispetto al sorgente che mi trovo di fronte.
Sarà forse dovuto all'ottimo (soggettivo per me questo) modo in cui è scritta quella porzione di codice, comunque è indubbio che tra le due pagine quella in versione Python è più snella.
cdimauro
28-11-2008, 20:32
Il codice è proprio identico, nel senso che fa esattamente le stesse cose. Qui le uniche differenze le fanno le librerie usate per interfacciarsi col server SOAP e... il linguaggio. :)
Secondo me la facilità di lettura la perde tutta quando si vedono cose del tipo:
lesser = qsort([l for l in list if l < pivot])
greater = qsort([l for l in list if l >= pivot])
Certo è facile leggere in italiano quelle righe, ma è difficile capire al volo quello che fanno, soprattutto a prima vista. Cosa che un for esteso invece ti permetterebbe di fare.
P.S. Idea: si potrebbe fare una specie di concorso di bellezza: una giuria voterà il codice più semplice ed elegante. In fondo, per questo tipo di problemi, la velocità non conta, no? Il team di google sicuramente preferisce codice elegante. Se ne stracatafottono se i risultati della ricerca vengono mostrati dopo un'ora. ;)
Mi risulta che in google si preoccupino anche di fornire risultati corretti.
Negli ultimi contest mi sembrava che la preoccupazione fosse di fornire risultati nel modo piu' veloce. Magari non quelli richiesti, ma in un nientesimo di secondo.
Per questo nell'altro thread ho proposto che nuovi contest fornissero un modo per validare l'output, o usare l'output stesso come metro di misura.
Negli ultimi contest mi sembrava che la preoccupazione fosse di fornire risultati nel modo piu' veloce. Magari non quelli richiesti, ma in un nientesimo di secondo.
Ovviamente dovevano essere quelli richiesti, altrimenti non aveva validità il codice.
Chiaro una validazione sarebbe interessante, oppure basterebbe l'output di prova e un bel diff ;)
Ovviamente dovevano essere quelli richiesti, altrimenti non aveva validità il codice.
Chiaro una validazione sarebbe interessante, oppure basterebbe l'output di prova e un bel diff ;)
Il confronto sull'output va bene, ma l'input per la validazione dovrebbe essere diverso da quello usato per la valutazione, o ancora meglio generabile automaticamente. Altrimenti si verifica solo che il programma butta fuori l'output richiesto per quell'input, non che risolve il problema.
Il confronto sull'output va bene, ma l'input per la validazione dovrebbe essere diverso da quello usato per la valutazione, o ancora meglio generabile automaticamente. Altrimenti si verifica solo che il programma butta fuori l'output richiesto per quell'input, non che risolve il problema.
Però quanti input devi verificare ? Anche se ti fermi a 100.000 diversi input non sei comunque sicuro che al 100.001 il programma non sbagli ;) Su una mole di dati in input notevole (come ad esempio era per il lotto), già il fatto che la soluzione venga verificata è molto valido come test.
L'unico modo è esplorare tutto lo spazio degli input, ma per la maggior parte dei programmi è impensabile.
Ti rispondo sull'altro thread che qua siamo un pelo OT
cdimauro
29-11-2008, 23:24
Secondo me la facilità di lettura la perde tutta quando si vedono cose del tipo:
lesser = qsort([l for l in list if l < pivot])
greater = qsort([l for l in list if l >= pivot])
Certo è facile leggere in italiano quelle righe, ma è difficile capire al volo quello che fanno, soprattutto a prima vista. Cosa che un for esteso invece ti permetterebbe di fare.
Le list comprehension (e le "duali", le generator expression) sono degli strumenti che è possibile decidere di usare o meno a seconda del problema da risolvere.
Hanno una certa eleganza, e per chi ha un background di matematica sono di facile assimilazione.
Va valutato caso per caso il loro uso, fermo restando che usando nomi autoesplicativi migliora la leggibilità e si capisce meglio quello che fanno:
Lesser = QuickSort([Value for Value in List if Value < Pivot])
Greater = QuickSort([Value for Value in List if Value >= Pivot])
Comunque c'è chi preferisce non usarle in ogni caso quando c'è di mezzo una condizione (per "selezionare" alcuni elementi) ricorrendo alla classica forma del ciclo for che, come dicevi, risulta più familiare (a chi proviene da altri linguaggi più "tradizionali").
The_ouroboros
30-11-2008, 09:27
Le list comprehension (e le "duali", le generator expression) sono degli strumenti che è possibile decidere di usare o meno a seconda del problema da risolvere.
Hanno una certa eleganza, e per chi ha un background di matematica sono di facile assimilazione.
molto eleganti e compatti :ave: :ave:
Boh, io sinceramente eleganza non ce ne vedo, compattezza sì, ma trovo solo che peggiorino la leggibilità. Anche se ho un certo background di matematica ;)
Mi spiego, quando uno scorre un codice e deve vederne la struttura ad un primo sguardo, lì dentro è difficile anche notare che c'è un for, non solo capirlo al volo. Dicasi la stessa cosa per l'operatore if ternario (:?) di Java e C/C++.
Quando la struttura è messa verticalmente se ne notano meglio le varie parti.
The_ouroboros
30-11-2008, 09:57
a me invece, dopo 2 anni di matematica all'università, mi sembra molto logica come costruzione...ma magari la trovo "bella" e quindi la mia visione d'intero si perde un po...
a me invece, dopo 2 anni di matematica all'università, mi sembra molto logica come costruzione...ma magari la trovo "bella" e quindi la mia visione d'intero si perde un po...
Non dico che non sia logica eh...anzi, letta in orizzontale è leggibile, ma all'interno della struttura di un programma in cui solitamente il codice è strutturato in verticale, una struttura orizzontale come quella imho non risalta adeguatamente come dovrebbe. Quella parte di codice potrebbe essere anche fondamentale per l'esecuzione del programma.
E' lo stesso motivo per cui si preferisce non richiamare consecutivamente molti metodi o funzioni in cascata.
Se io scrivo:
a.fai(b.leggi(f.apri(z.getNome())))
imho è sicuramente meno leggibile di
file fileDescriptor = f.apri(z.getNome())
a.fai(b.leggi(fileDescriptor))
Comunque siamo andati per l'ennesima volta off-topic, anche per colpa mia :D
Ritorno all'argomento iniziale: chi ha creato il thread come ha deciso di proseguire ?
cdimauro
11-12-2008, 21:50
Togli pure il "sembrerebbe": l'idea dell'algoritmo che ho esposto è mia.
Capita. Nel mio caso io aspetto ancora la dimostrazione che l'algoritmo che ho esposto sia frutto di idee altrui.
Mi hai chiesto di fare delle ricerche con delle precise parole chiavi e l'ho fatto. Non mi pare di aver trovato nessuno che abbia descritto un algoritmo come il mio. Visto che sei stato tu a parlare di "spacciare per proprie le altrui idee" (testuali parole), mi aspetto che prendi il mio post con la descrizione dell'algoritmo e posti il link e riporti la descrizione di un algoritmo che sia corrispondente al mio.
In assenza, non dovresti avere difficoltà a scusarti e a rimangiarti quello che avevi detto.
Up
Vincenzo1968
11-12-2008, 22:49
A te servirebbe qualcosa di simile a questo: http://en.wikipedia.org/wiki/Soundex
Ma il problema è che "sintetizzare" un'intera pagina in pochi bit d'informazione è praticamente impossibile.
Un'ideuzza ce l'avrei, ma è un po' complicata da implementare. Te la espongo velocemente.
Utilizza un dizionario fisso di parole (es: quello della lingua italiana), e dalla tua pagina estrai tutte le parole che appartengono al dizionario conservandone anche la frequenza.
Supponiamo che tutte le parole del dizionario abbiano una posizione fissa (es: ciao = 4327), per cui anche alle parole del dizionario assocerai il medesimo indice.
Mettiamo che il dizionario sia di n parole, e tu ne abbia trovate m (<= n ovviamente). Costruisci un vettore di dimensione n in cui memorizzi la frequenza delle m parole nella posizione che gli spetta. Quindi se hai trovato ciao 3 volte, allora alla posizione 4327 metterai il valore 3.
A questo punto hai ottenuto un vettore nello spazio (del dizionario). Questo vettore formerà un certo angolo rispetto a un asse di riferimento. Ne calcoli il coseno (o il seno: è indifferente) e lo memorizzi.
D'ora in poi userai il coseno per confrontare la similitudine di una stringa con un'altra.
Lo so: è particolarmente contorto (qualche giorno chiameranno la neuro, me lo sento :D), ma a naso potrebbe andare bene per i tuoi scopi.
Invece di scherzarci su ti consiglio di pensarci seriamente: fatti visitare :)
Up
Invece di scherzarci su ti consiglio di pensarci seriamente: fatti visitare :)
L'argomento sembrava chiuso, che motivo c'era di tirarlo fuori nuovamente ? Chiarite i vostro screzi in privato, a noi non interessano. Quindi passo ai provvedimenti:
2gg per provocazioni/flame a cdimauro
5gg per provocazioni/flame e offese a Vincenzo1968
vBulletin® v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.