Newsgroup: it.comp.programmare
Titolo: Algoritmi di ricerca stringhe con pattern matching

Salve!
Volevo sapere se qualcuno di voi si è dilettato con algoritmi di questo
tipo, ovvero algoritmi di ricerca di sottostringhe espresse con espressioni
regolari all'interno di testi di lunghezza arbitraria. In particolare, ho
necessità che la complessità di ricerca sia O(L) con L lunghezza del testo
da analizzare. Quindi l'algoritmo non dovrebbe risentire se sono presenti
migliaia di patterns.
Qualcuno di voi si è mai interessato alla cosa?
Ciao!
*** Azimuth ***

 migliaia di patterns.
IMHO penso che al massimo puoi arrivare a O(nLOGn), dove n e' il tuo L.
 Raffaello

> migliaia di patterns.
 > IMHO penso che al massimo puoi arrivare a O(nLOGn), dove n e' il tuo L.
Magari! Hai qualche riferimento (URL), a riguardo?
Ovviamente, la complessità rispetto al numero di pattern dovrebbe essere
perloppiù costante...
*** Azimuth ***

 Magari! Hai qualche riferimento (URL), a riguardo?
No, ma al riguardo e' stato pubblicato molto.
Prova a usare l'amico GOOGLE ... ;)
 Raffaello

 Prova a usare l'amico GOOGLE ... ;)
L'amico Google ignora i problemi di complessità, anche se è molto ferrato in
quelli di catalogazione degli algoritmi stessi. <g>
Ho trovato questo link:
http://www-igm.univ-mlv.fr/~lecroq/string/index.html
Ci dovrebbero essere tutti, ma speravo di non dovermeli studiare tutti per
trovare quello che mi interessa!
Ciao!
*** Azimuth ***

 
http://www-igm.univ-mlv.fr/~lecroq/string/index.html
Cerca l'algoritmo di Knut-Pratt, aveva complessità poco più che lineare (se
non ricordo male O(n+km)). Cerca anche sotto la voce pattern prefix
function!
Ciao

 function!
Grazie per l'hint! Comunque li ho studiati un po' tutti e non mi soddisfano.
Ne sto progettando uno che, se funziona bene, avrebbe complessità O(w) con w
lunghezza media del pattern (quindi indifferente a lunghezza del testo da
analizzare e numero di patterns).
Ciao!
*** Azimuth ***

 ha scritto nel messaggio
news:al5edl$cud$1...@newsreader1.mclink.it...

Beh, se funziona fammelo sapere che mi interessa!
Ciao
--
----------------------------
Fulvio Esposito
WWW: 
http://digilander.libero.it/fesposito
E-Mail: 
ful...@libero.it
----------------------------

 risentire se sono presenti migliaia di patterns.
perche` iventare la ruota? Prenditi i sorgenti di grep e usa quelli: 
difficilmente riuscirari a far di meglio.
Oppure, ancora meglio, usa python e dai una occhiata al modulo re: e` 
quello che ti serve.
ciao Anto
-- 
Antonio Cuni, 20 anni, studente
Brainbench C++ Master: 4.73, higher than 99% of all previous test takers.
C Language: 3.79, higher than 92% of all previous test takers.
Guida C/C++ di Programmazione.it: 
http://cpp.programmazione.it

, 
azi...@nadir.com
 
says...

Sei sicuro?
Io credo che sia stato dimostrato da qualche parte che tutti gli 
algoritmi di pattern matching debbano essere Omega(n-m) (con m lunghezza 
del pattern ed n lunghezza del testo).
Maurizio

 quello che ti serve.
Naa... ho bisogno di performances...
Ciao!
*** Azimuth ***

 del pattern ed n lunghezza del testo).
Faccio come diceva Einstein: tutti dicono che una cosa non si può fare, poi
arriva quello che non lo sa e la fa. :)
Ciao!
Marco.

 Naa... ho bisogno di performances...
il modulo re e` scritto in C...


 il modulo re e` scritto in C...
Non mi sono spiegato bene: ho bisogno di performance sull'algoritmo, non
sulla sua implementazione. Sono due cose leggermente differenti. :)
Ciao!
*** Azimuth ***
P.S. Ovviamente, posso anche ottimizzare l'implementazione, ma se
l'algoritmo ha dei limiti computazionali accertati... è come cercare di
migliorare le performances in velocità e accelerazione di una Gold GT per
farla volare. :) Per quanto ci provi, comunque resta a terra! :)))