Trovare la percentuale di differenze tra due stringhe senza averle.

[das]

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]

Originariamente inviato da das

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]

http://it.wikipedia.org/wiki/Distanza_di_Levenshtein

[malocchio]

Originariamente inviato da das

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.

[Tommo]

Originariamente inviato da cdimauro

http://it.wikipedia.org/wiki/Distanza_di_Levenshtein

Si, credo sia indicato... io lo uso per riconoscere le forme nel mio gioco

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

[das]

Originariamente inviato da cdimauro

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]

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.

[The_ouroboros]

Originariamente inviato da cdimauro

Lo so: è particolarmente contorto (qualche giorno chiameranno la neuro, me lo sento ), ma a naso potrebbe andare bene per i tuoi scopi.

Molto interessante invece

[-MiStO-]

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.

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]

Esattamente.

[Tommo]

Veramente interessante

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
Non per niente google ha una decina di Pb di hard disk eh

[The_ouroboros]

Originariamente inviato da Tommo

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
Non per niente google ha una decina di Pb di hard disk eh

in effetti un piccolo suicidio a livello di spazio occupato

[cdimauro]

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]

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.

Similarità coseno
tra una dormitina e l'altra a lezione (.... ) 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]

ma limitando la soluzione di Cdimauro a relativamente poche parole chiavi relative ad un argomento?

[cdimauro]

Originariamente inviato da Oceans11

Similarità coseno
tra una dormitina e l'altra a lezione (.... ) 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 ).

Vabbè non divago oltre OT, dico solo che ci sono libri validi sull'argomento di un certo Ian Witten. Ciao!

Grazie per l'informazione.

Originariamente inviato da Kralizek

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]

Originariamente inviato da cdimauro

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

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

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.

[das]

Originariamente inviato da Tommo

Veramente interessante

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
Non per niente google ha una decina di Pb di hard disk eh

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.

[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

(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?