Newsgroup: it.comp.programmare
Titolo: Fast Pattern Matching (spec. per Azimuth)

Ho appena finito l'algo. di PM e direi che puň andare.
Innanzitutto svolge una ricerca sequenziale quindi puň essere usato in
qualsiasi editor di testo dove l'utente vuole di volta in volta trovare il
successivo.
Supportare i caratteri speciali ? * [], ecc... non č un problema...
Sia la stringa S lunga s e il pattern P lungo p.
Il caso peggiore č O(s), mentre quello migliore č O(s/p).
A questo si aggiunge il calcolo di una tabella dipendente esclusivamente da
P e lunga p+1. Adesso sto cercando un algoritmo per calcolarla in modo
efficiente, comunque il tempo impiegato č trascurabile per S molto lunghi.
Il metodo peggiore per calcolare la tavola č O(p(p+1)/2).
Kiuhnm

 Il metodo peggiore per calcolare la tavola è O(p(p+1)/2).
Nel mio caso, sia o il numero di occorrenze (cioe' il numero di volte che P
viene trovato in S).
Il caso esatto e':
Sola ricerca: O( p / o + s )
Fase di preparazione: O( p ) (precalcolata e messa da una parte, quindi
"cached")
In realta', credo che le equazioni esatte siano:
Sola ricerca: t = a * ( p / o ) + b * s (con a e b nell'ordine di 10^-3 -
10^-4 s).
Fase di preparazione: t = c * p (con c dell'ordine di 10^-3 s)
Il punto interrogativo e l'asterisco non modificano l'ordine di grandezza
delle costanti a, b e c.
D'altronde, l'algoritmo da il meglio di se con molteplici patterns. Supponi
di avere n patterns, lunghi p(0), p(1), ..., p(n-1). Allora il costo e'
cosi' definito:
Sola ricerca: O( ( p(x) / o ) + s ) (con x il numero ordinale del pattern
trovato)
Fase di preparazione: O( sommatoria( p( i ) ) con 0 <= i < n ) (precalcolata
e messa da una parte, quindi "cached")
Tutte le costanti di tempo si intendono sulla seguente configurazione:
    PIII 1000 Mhz con 256 Mb di RAM
    Windows NT 4.0 SP6
    Visual C++ 6.0 SP3
Ciao!
*** Azimuth ***

     Visual C++ 6.0 SP3
Io ho anche un Athlon 800 Mhz con 768 Mb di RAM (lenta :-) ) su Win 98 SE e
Visual C++ 6.0, quindi direi che le configurazioni sono simili.
Kiuhnm

Dimenticavo: il tuo metodo è sequenziale?
Non mi dicevi che ti trovava tutte le stringhe contemporaneamente?
Kiuhnm

: Il caso esatto e':
: 
: Sola ricerca: O( p / o + s )
: Fase di preparazione: O( p ) (precalcolata e messa da una parte, quindi
: "cached")
FAmmi capire... la complessita' del tuo algoritmo è INVERSAMENTE PROPORZIONALE 
al numero di pattern che trovi nel testo???? NON CI CREDO!!! Ma sei sicuro del 
risultato??? CIoè, voglio dire... se io ho ad esempio un testo con 1000 
pattern e 20000 caratteri, mi aspetto che impieghi piu' tempo a trovarli che 
non se ci sono solo 10 pattern... Come è possibile? Hai dei numeri???
Fed.


Guarda meglio!
O(s + p/o) -> O(s) per o->inf. (caso migliore)
Il mio caso migliore è invece
O(s/p)
(il peggiore è O(s))
Kiuhnm

: Guarda meglio!
: O(s + p/o) -> O(s) per o->inf. (caso migliore)
: 
: Il mio caso migliore è invece
: O(s/p)
: (il peggiore è O(s))
SI, ma il tuo vale per un solo pattern! Se il testo contiene, ad esempio, 
1000 pattern uguali, il tuo algoritmo ha costo O( o * ( s / p ) )! Per 
o->inf., il tuo algoritmo ha costo infinito!
Direi che l'unica è che azimuth ci risponda ad un quesito: ma quell'O( s ) 
è un costo di che tipo?
Fed.

 p ) )! Per o->inf., il tuo algoritmo ha costo infinito!
Stai scherzando?
Se il testo ha 1000 pattern uguali si ha il mio caso peggiore e quindi ho
O(s).
Sarebbe bella che valesse per un solo pattern!!!
Kiuhnm

:: SI, ma il tuo vale per un solo pattern! Se il testo contiene, ad

Allora c'è qualcosa che non mi torna... vabbuoh, magari ci penso 
'stanotte... ;-)
Fed.

 Visual C++ 6.0, quindi direi che le configurazioni sono simili.
Direi di si'. Facciamo un test sul campo?
*** Azimuth ***

 Non mi dicevi che ti trovava tutte le stringhe contemporaneamente?
Infatti la complessita' e' O( s + ( p / o ) ) o, se preferisci, che il tempo
di esecuzione lo devi vedere "distribuito" su tutte le occorrenze trovate.
*** Azimuth ***

 Come è possibile? Hai dei numeri???
Certo, magari segui il thread con Khiunm...
Ciao!
*** Azimuth ***

 Il caso peggiore è O(s), mentre quello migliore è O(s/p).
(N e` la lunghezza del testo e M quella del pattern)
"""
Proprieta` 19.2: Una ricerca di Knuth-Morris-Pratt non confronta mai piu` 
di M+N caratteri
[cut]
Proprieta` 19.3: Una ricerca di una stringa con il metodo di Boyer-Moore 
non confronta mai piu` di M+N caratteri, richiedendo circa N/M passi se 
l'alfabeto non e` piccolo ed il pattern non e` lungo
"""
Robert Sedgewick, "Algoritmi in C"
ciao Anto
-- 
"Computer science is not about computers any more than astronomy
is about telescopes." -- EW Dijkstra

 l'alfabeto non e` piccolo ed il pattern non e` lungo
Come faccio a fare queste misure se il mio sistema NON confronta caratteri?
*** Azimuth ***