Trovare la percentuale di differenze tra due stringhe senza averle.

[cdimauro]

Originariamente inviato da Oceans11

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 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 ).

Originariamente inviato da das

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.

Originariamente inviato da gugoXX

Io conosco ed ho usato un algoritmo abbastanza, simile a quello esposto da cdimauro. Viene attualmente usato da qualche engine di spiders.

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.

[gugoXX]

Originariamente inviato da cdimauro

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.

[skp]

Originariamente inviato da gugoXX

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 ?

[gugoXX]

Originariamente inviato da skp

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]

Originariamente inviato da gugoXX

...
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

[skp]

Originariamente inviato da gugoXX

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]

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



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]

<off-topic>

Originariamente inviato da gugoXX

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>

[gugoXX]

Originariamente inviato da skp

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"

[shinya]

Originariamente inviato da Vincenzo1968

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]

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.

[shinya]

Originariamente inviato da banryu79

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

Originariamente inviato da banryu79

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...

[skp]

Originariamente inviato da gugoXX

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 ?

[gugoXX]

Originariamente inviato da skp

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?

[skp]

Originariamente inviato da gugoXX

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]

Originariamente inviato da shinya

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.

Originariamente inviato da shinya

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?

[das]

Originariamente inviato da cdimauro

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 ), ma a naso potrebbe andare bene per i tuoi scopi.

Originariamente inviato da gugoXX

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]

Originariamente inviato da das

...
Cos'è esattamente un contest ?

Contest 1

Contest 2

Contest 3

Contest 4

Contest 5

Contest 6

Contest 7

[das]

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.

[cionci]

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