Newsgroup: it.comp.programmare
Titolo: Algoritmo di confronto... AIUTO

Salve,
ho un questito riguardante un le materie di Logica ed Informatica.
Devo inplementare un algoritmo (pseudocodifica o codifica in C++) che faccia
il confonto tra due stringhe di caratteri. Qusta funzione mi deve dire solo
se la seconda è contenuta nella prima.
ES:
stringa 1     ABABAABBAAB
stringa 2     ABBA
la stringa 2 c'è nella 1!
La difficoltà è la seguente: non bisogna utilizzare un semplice algoritmo di
confronto (se c'è la prima lettera leggi la seconda se c'è la seconda leggi
la terza ecc...) ma bisogna utilizzare un qualche teorema di "Algebra e
Logica" come ad esempio utilizzo delle matrici , grafi, o via di lì.
Qualcuno può darmi una mano???  Qualunque consiglio è ben accettato!!
valer...@libero.it

 Qualcuno può darmi una mano???  Qualunque consiglio è ben accettato!!
Bizzarro! Ti scrivo solo perchè hai detto qualunque!!
Addirittura matrici? Beh parti dal teorema dei complementi
dell'algebra di Boole, uno spunto potrebbe essere:
S1=s11s12s13...s1n
S2=s21s22s23...s2m
sia per ipotesi n <= m.
Sappiamo che  S1 è contenuta in S2 se e solo se per i=1..n è vera
s1i=S2i
Il teorema dei complementi dice che A + notA = 0 e A * notA = 0 quindi
possiamo dire che S1 è contenuta in S2 se e solo se per i=1..n s1i AND
nots2i = 0, che forse puoi anche scrivere come una sommatoria per i
che va da uno a n ( non mi ricordo in questo momento se ha senso con
l'algebra booleana!! )
Ma non avevano niente di meglio da chiederti???

 
Veramente, seguendo il ragionamento, si deduce che contiene anche:
17
35
44
53
71
-- 
Valter Minute
vmi...@inwind.it
 (the reply address of this message is invalid)

 matrici , grafi, o via di lì.
Avrei un'idea a dir poco geniale :-)))
Mettiamo d'inventare un algoritmo tipo l'MD5 che calcoli a partire da una
stringa molto lunga una piccolissima stringa che la rappresenti.
A questo punto si calcolerebbero le stringhe rappresentative (anche chiamate
hash) e si confronterebbero quelle.
Se sono diverse le stringhe rappresentative sono sicuramente diverse anche
quelle originali, altrimenti bisogna controllare.
Inefficiente? Sì, se non fosse che possiamo usare particolari funzioni hash.
Proviamo con una funzione Hash semplice semplice, quella della SOMMA:
155267
Contiene 26?
Calcoliamo la mini-rappresentazione di 26: 2+6 = 8
E procediamo:
155267
1+5 = 8? No
5+5 = 8? No
5+2 = 8? No
2+6 = 8? Sì
Che cosa si nota?
Che se la stringa *nella quale* cercare fosse:
28726478237237623723
e quella *da* cercare:
37237
basterebbe calcolare 3+7+2+3+7,
28726478237237623723
2+8+7+2+6 = 25
e in seguito:
8+7+2+6+4 = soltanto 25 - 2 + 4, cioè
basta sottrarre il primo e sommare il successivo.
L'algoritmo è quindi efficiente.
Ovviamente la somma non è forse la più indicata, ma potresti trovare altre
rappresentazioni che godono della stessa proprietà.
Probabilmente, se accuratamente studiato, è perfino più veloce della ricerca
normale...
Kiuhnm

> altrimenti bisogna controllare.
Ciao!
*** Azimuth ***

 stringa molto lunga una piccolissima stringa che la rappresenti.
Il problema di questo algoritmo e' che lo shift per il controllo e' di 1
byte alla volta. Se riuscissimo a migliorarne il "fattore di skip" (cioe'
quanto in avanti possiamo andare senza dover elaborare cio' che sta in
mezzo) potremmo migliorarlo notevolmente.
Per esempio, basterebbe candidare per il controllo con l'hash solo quelle
sottosequenze della stringa originale che finiscono con l'ultimo carattere
da analizzare. In questo modo puoi "saltare" (cioe' non analizzare) tutte le
posizioni tra l'ultima posizione analizzata e la successiva MENO la
lunghezza del pattern da ricercare. In (pseudo) linguaggio:
int where_is( string _original, string _pattern ) {
    int p = 0;
    int pattern_size = _pattern.size();
    char last = _pattern[ pattern_size - 1 ];
    while( p != -1 ) {
        p = _original.find( last, p + 1 );
        if ( p != -1 ) {
            long hash = hash( _original[ p - pattern_size ], pattern_size );
            if ( hash = hash( _pattern ) )
                return p;
        }
    }
    return p;
}
Ciao!
*** Azimuth ***

 bisogna utilizzare un qualche teorema
Cerca in rete l'algoritmo di Knuth-Morris-Pratt o quello di
Boyer-Moore-Horspool.
--------------------------------
Inviato via 
http://usenet.libero.it

 
oopss... l'ho letto troppo in fretta.


 Che cosa si nota?
Che e' del tutto sballato: cerco 51 (1+5) e lo trovo, cerco 25 (5+2) e lo
trovo, cerco 62 (2+6) e lo trovo, nonostante nessuna di esse sia contenuta
nella stringa di partenza.


 nella stringa di partenza.
Si', peccato pero' che:
1) non cerchi ne' "51" ne' "25" bensi' "26" (codice hash 8);
2) se cerchi "51" lo trovi potenzialmente nella posizione 0 solamente
(l'unica con codice hash 6 e l'unica da controllare, ovviamente);
3) se cerchi "25" lo trovi potenzialmente nella posizione 1 solamente
(l'unica con codice hash 6 e l'unica da controllare, ovviamente).
*** Azimuth ***

 }
A questo punto perň otteniamo un normalissimo metodo di ricerca (solo che tu
usi l'ultimo, mentre solitamente si usa il primo carattere).
* Nel tuo codice hai scordato di controllare che p - pattern_size sia
maggiore o uguale a 0.
(   long hash = hash( _original[ p - pattern_size ], pattern_size );   )
Comunque in questo modo si perde la proprietŕ principale della funzione hash
da usare e cioč che:
hash(elem_a+1...elem_b+1) = hash(elem_a...elem_b) - elem_a + elem_b+1.
Io facevo le somme e tu fai confronti con _original.find.
Non vedo un gran miglioramento, anzi č peggiorato infatti col metodo
classico (quello dove si cerca la prima corrispondenza e poi si guarda se le
sottostringhe corrispondono completamente) č sufficiente proseguire finchč i
caratteri coincidono, mentre ora bisogna calcolare tutta la hash (cioč
controllare tutti i caratteri).
Magari mi sbaglio...
Kiuhnm

 1) non cerchi ne' "51" ne' "25" bensi' "26" (codice hash 8);
Non capisco dove sia la differenza:
Secondo il vostro algoritmo, cerco "26" (codice hash 8) nella stringa
"155267" e quindi faccio i seguenti confronti:
1+5 = 8 ? No
5+5 = 8 ? No
5+2 = 8 ? No
2+6 = 8 ? Si (l'ho trovato)
Secondo lo stesso algoritmo, cerco "51" (codice hash 6) nella stringa
"155267" e quindi faccio i seguenti confronti:
1+5 = 6 ? Si (l'ho trovato, falso)
A parte che il tempo impiegato per calcolare le somme e' sicuramente
maggiore di quello impiegato per scorrere e confrontare la stringa, suppongo
che l'algoritmo in questione si possa applicare solo a stringhe composte da
cifre (e la sua complessita' computazionale diventa tanto peggiore quanto
piu' e' lunga la stringa (perche' immagino che quante piu' e' lunga la
stringa da cercare, tanto piu' e' facile trovare sottostringhe che
collidono), obiettivo esattamente *contrario* alla logica con cui vengono
studiati algoritmi del genere).
Esistono algoritmi che, al contrario di questo, risolvono questo tipo di
problema in modo efficiente.


 caratteri coincidono,
Potrebbe anche darsi.
D'altra parte, l'unica altra tecnica che conosco ha costo costante ma non
posso divulgarla. :)
*** Azimuth ***

Un'altra cosa.
Non dimentichiamo che la somma è modulo 2^n quindi per esempio abbiamo:
n  = 8
12, 87, 241, 98, 53, 95, 168, 4, 65
Cerchiamo:
98, 53, 95 = 246
12, 87, 241 = 84 (% 2^8)
ecc...
Dov'è il vantaggio?
Il vantaggio dovrebbe essere statistico (spesso è così).
Ogni lingua predilige certe forme, ovvero le varie parole tendono ad avere
radici in comune.
Se cerchiamo "casa" incapperemo in tutte le parole con la stessa radice come
"casupola", "casetta", "casolare", ecc...
Quindi usando un metodo normale troveremmo molto spesso corrispondenze fino
a 2-3 o perfino 4 lettere. Per non parlare poi del fatto che molte parole si
accompagnano spesso (tipo "per esempio").
Per esempio la frase: "dfijdf  fgdjaljv uywnnvbw" non viene "sfruttata"
dall'Italiano e sicuramente non la incontreremo all'interno di un testo.
L'hash sfrutta proprio questo!
Se la stringa è lunga e la hash corta, quest'ultima viene modificata
pesantemente da TUTTE le lettere (grazie al modulo N) e se due hash
corrispondono è IMPROBABILE che la prima lettera della stringa e della
sotto-stringa corrispondano perchè le parole alle quali appartengono le due
hash uguali sono due parole qualsiasi, mentre nel caso classico sono due
parole che hanno almeno la stessa radice e quindi è probabile che siano
simili (per es. se la parola inizia con 't' è probabile che la seconda
lettera sia una vocale ed essendo soltanto 5 abbiamo una probabilità del 20%
che coincida anche la seconda lettera).
Probabilmente non mi sono fatto capire, ma pazienza...
Kiuhnm

 Probabilmente non mi sono fatto capire, ma pazienza...
ROTFL... il fatto che tu abbia questa sensazione nei confronti di te stesso
e' sintomatico ;)


 problema in modo efficiente.
Vero. Il mio, ad esempio (tempo pressocche' costante).
*** Azimuth ***

 non posso divulgarla. :)
Sei sicuro di aver calcolato il costo computazionale correttamente?
Comunque è impossibile che sia a costo costante, magari è lineare (O(N)), ma
a costo costante proprio no! (significherebbe controllare sempre lo stesso
numero di caratteri...è assurdo).
Kiuhnm
P.S. Io invece ho un metodo a chiave pubblica migliore dell'RSA che ancora
non voglio divulgare :-)
Diciamo che è in fase di accertamento...(da 2 mesi)...

 Vero. Il mio, ad esempio (tempo pressocche' costante).
Esistono algoritmi migliori del tuo, e' inutile inventare cose inefficienti,
quando ne esistono gia' di efficienti.


 non voglio divulgare :-)
Qui alzo le mani!
*** Azimuth ***
[1] Non e' proprio vero -- ma e' una buona approssimazione.

 una stringa, piu' e' probabile che tutto si riduca ad una ricerca diretta.
Per assurdo: se P fosse L/2, basterebbe confrontare al piu' ( P - L / 2 )
caratteri. Asintoticamente, il numero di caratteri da confrontare e' L.
*** Azimuth ***
[1] 
http://www.ics.uci.edu/~eppstein/161/960227.html
[2] 
http://www-igm.univ-mlv.fr/~lecroq/string/node18.html#SECTION00180

 numero di caratteri...è assurdo).
Ah, devo aggiungere una cosa: l'algoritmo gestisce tranquillamente pattern
del tipo "AC?TG" (vuol dire qualsiasi sequenza con un carattere arbitrario
tra il prefisso "AC" ed il suffisso "TG"), oppure "AC?CC?CA" (vuol dire
qualsiasi sequenza con due caratteri arbitrari tra "AC", "CC", "CA"), come
pure "A???T", "TT??CC??GA"...
Inoltre, e' in grado di rilevare anche sequenze del tipo "AA*CC" (prefisso
"AA" suffisso "CC" e qualsiasi numero arbitrario di caratteri tra essi),
"A*C*T", "AA*C*TT*A", ecc..
Infine, e' possibile indicare anche una classe di caratteri: tipo "A?[TC]C"
vuol dire che deve trovare solo "ATC" o "ACC".
Il tutto allo stesso costo.
Ciao!
*** Azimuth ***

 ve ne fossero 100![1]
Allora c'è il trucchetto :-)
Pensavo che usassi processori quantistici, ma adesso ho capito.
Io mi riferisco non al numero di occorrenze, ma alla lunghezza delle due
stringhe.
O meglio, dato un numero costante di occorrenze, come varia la velocità
dell'algoritmo all'aumentare della lunghezza di una o di entrambe le
stringhe?
Kiuhnm

 Il tutto allo stesso costo.
Mi stai lanciando una sfida? :-)))
Appena ho un po' di tempo ti faccio vedere... :-)
Comunque sei sicuro che non ne esistano già così efficienti?
Kiuhnm

 stringhe?
Costante al variare di L.
Lineare al variare P, ma con coefficiente angolare dell'ordine di 10^-3,
quindi praticamente costante.
*** Azimuth ***

 Comunque sei sicuro che non ne esistano già così efficienti?
Abbastanza[1]. Considera, comunque, che la base di questo algoritmo (diciamo
il "nucleo concettuale") e' in effetti in giro da 15 anni in alcuni software
di nicchia.... Prima funzionava su un M24 con 520Kb di RAM ed un CD-ROM 1x
SCSI e permetteva di trovare un pattern tra 6 milioni in circa 30 secondi.
*** Azimuth ***
[1] Non si puo' mai dire, in effetti...

Potresti fare un test?
Per es. scegli 2-3 testi presi da Internet oppure generi algoritmicamente
(la funzione deve essere nota) un file di n MB e poi mi dici quanto impieghi
a trovare una determinata stringa.
Ovviamente il tempo dovresti dirmelo non in sec (magari anche quello), ma in
numero di operazioni elementari eseguite (confronto, somma se presente,
ecc...).
Se hai paura di rivelare troppi dati, allora lasciamo perdere.
Kiuhnm

 ecc...).
Questo, purtroppo, non e' possibile, dato che NON e' banale fare il calcolo
di quello che dici!
Ciao!
*** Azimuth ***

 Tf) Raddoppio di Te, L = 822116 * 2 = 1644231
Pattern:
(case insensitive)
1) "il"
2) "volta"
3) "preziosa"
4) "abcdefghijklmnopqrstuvwxyz"
(case sensitive)
5) "\x12\x50\x78\x81\x9\x8f\x5f\x12" (stringa C)
Ricerca in Tf (il tuo)
I tempi:
1) 0.016 s, 7690
2) 0.010 s, 266
3) 0.008 s, 10
4) 0.007 s, 0
5) 0.007 s, 0
Ricerca in un "testo" di 50'000'000 bytes creato in questo modo:
int size = 50000000;
BYTE *buf = new BYTE[size];
srand(0x12345678);
for (int i = 0; i < size; i++)
    buf[i] = rand();
I tempi:
1) 0.430 s, 3016
2) 0.260 s, 0
3) 0.210 s, 0
4) 0.200 s, 0
5) 0.200 s, 0
Si nota subito che il mio algo. si comporta meglio con "testi" random (per
es. file WAV, GIF, ecc...) e in generale predilige i pattern lunghi.
Comunque il grande vantaggio sta nel fatto che è sequenziale e quindi la
ricerca può essere ristretta alle prime N occorrenze.
Kiuhnm

 ricerca può essere ristretta alle prime N occorrenze.
Nel mio caso non ho questo vantaggio (cioe' i miei problemi mi chiedono di
trovare TUTTE le occorrenze).
Ciao!
*** Azimuth ***

 chiedono di trovare TUTTE le occorrenze).
A questo punto sono molto curioso e voglio provare a fare un algoritmo di
pattern matching che non usi i confronti.
Adesso ci provo poi ti farò sapere. Se i risultati saranno inferiori li
posterò lo stesso, tanto per discutere su qualcosa di interessante.
Devo confessarti che mi sono stancato molto presto di seguire e specialmente
intervenire nei thread sul Python.
Kiuhnm

 intervenire nei thread sul Python.
Anche perche' non hai niente di utile da dire ;)
Anche noi ci siamo abbastanza stancati di sentire le vostre idiozie.
Speditevele per e-mail, per cortesia.


 intervenire nei thread sul Python.
Dillo a me... comunque ho seguito il tuo consiglio di plonkare...
*** Azimuth ***

 Dillo a me... comunque ho seguito il tuo consiglio di plonkare...
Hai fatto bene.
Kiuhnm

 originale. Non sarebbe molto corretto!
D'accordo, d'accordo!!! :)
Ciao!
*** Azimuth ***

Sto provando ad usare la correlazione (è praticamente una convoluzione tra
due segnali) per il pattern matching!
In realtà i confronti sono delle sottrazioni che non modificano gli operandi
ma soltanto i flag (mi riferisco all'asm Intel, ma vale un po' in tutte le
CPU), quindi costano pochissimo.
Il vero problema sono i salti!
Il codice:
cmp   eax, ebx
cmp    ecx, edx
cmp    edx, eax
ecc...
è velocissimo, invece il seg:
here1:
cmp    eax, ebx
je    here1
here2:
cmp    ecx, eax
jb    here1
ecc...
è molto lento perchè i jxx (anche i jmp [non condizionali]) svuotano la
pipeline.
Il mio obiettivo è di trovare un metodo che non necessiti salti
condizionali....forse è impossibile, ma ci voglio provare ugualmente...
Che cosa ne pensi?
Kiuhnm

 pipeline.
E fare una cosa del genere (non mi ricordo benissimo gli opcode ASM 80x86):
    and eax, ebx
    and ecx, edx
    and eax, ecx
    cmp eax, ebx
    je all_the_same
Cosi' salti solo se sono tutti uguali... (solo in quel caso, infatti, il
passaggio attraverso 3 applicazioni di AND non modifica nulla).
*** Azimuth ***

 il passaggio attraverso 3 applicazioni di AND non modifica nulla).
Il problema è che i jxx invalidano la pipeline anche se non sono "presi".
Comunque adesso ci penserò su...ci vorrebbe un metodo che eseguite
moltiplicazioni o somme sempre nello stesso ordine, restituisca le posizioni
dei pattern :-)
Kiuhnm
P.S. Dimenticavo: in quel messaggio dandoti del *coglione* ho voluto in
realtà farti un complimento...comunque forse ho esagerato...

 realtà farti un complimento...comunque forse ho esagerato...
L'ho immaginato, che fosse una sottile presa in giro di chi ti leggeva.
D'altro canto, che di ci vuoi fare... come diceva il Mahatma Gandhi:
"Prima ti ignorano, poi di deridono, poi ti combattono. Poi vinci."
Ciao!
*** Azimuth ***

 Ma va?!?!? E' proprio quello che faccio io... :-)))
Davvero?
Magari esiste un altro metodo simile al tuo con meno operazioni...non si sa
mai.
Il tuo algo modifica il testo? (cioè è necessario lavorare su una copia?)
Kiuhnm

 Il tuo algo modifica il testo? (cioè è necessario lavorare su una copia?)
Se parli dell'algoritmo di PM, no.
Ciao!
*** Azimuth ***