Factor OracleFactor Oracle

Factor Oracle Factor Oracle

A New Structure for Pattern A New Structure for Pattern

Matching Matching

Daniele Contarino Daniele Contarino

Università degli Studi di Catania Università degli Studi di Catania

Facoltà di Scienze Matematiche FF.NN.

Facoltà di Scienze Matematiche FF.NN.

Corso di Laurea in Informatica Corso di Laurea in Informatica

Executive summary Executive summary

• IntroduzioneIntroduzione

• Factor Oracle – L'idea baseFactor Oracle – L'idea base

• Costruzione di Oracle Costruzione di Oracle

– Algoritmo da alto livelloAlgoritmo da alto livello – Costruzione onlineCostruzione online

• String MatchingString Matching

– BOM (Backward Oracle Matching) e Turbo-BOMBOM (Backward Oracle Matching) e Turbo-BOM

• Dati sperimentaliDati sperimentali

• Factor Oracle in real worldFactor Oracle in real world

Introduzione Introduzione

Oracle (Oracolo) …. chi è??

Oracle (Oracolo) …. chi è??

““Nell'era classica, un Nell'era classica, un

oracolo oracolo

considerata come fonte di sagge considerazioni,

considerazioni, previsioni previsioni profetiche

profetiche o precognizioni del o precognizioni del futuro, ispirati dagli dei.”

futuro, ispirati dagli dei.”

Introduzione Introduzione

Per il pattern matching, sarebbe utile un oracolo Per il pattern matching, sarebbe utile un oracolo

che possa indicare,

che possa indicare, anche se non precisamenteanche se non precisamente (come le profezie di un oracolo), dove si possano (come le profezie di un oracolo), dove si possano

trovare i match del nostro pattern all'interno di trovare i match del nostro pattern all'interno di

un testo in tempi ottimi.

un testo in tempi ottimi.

Il Il Factor OracleFactor Oracle importa questa intuizione importa questa intuizione nell'informatica!

nell'informatica!

Factor Oracle – L'idea base Factor Oracle – L'idea base

Il Factor Oracle è un nuovo automa per il pattern Il Factor Oracle è un nuovo automa per il pattern

matching che agisce come un oracolo su tutti i matching che agisce come un oracolo su tutti i

fattori (sotto stringhe) di un stringa.

fattori (sotto stringhe) di un stringa.

Factor Oracle – L'idea base Factor Oracle – L'idea base

L'idea infatti del Factor Oracle è che se una L'idea infatti del Factor Oracle è che se una

stringa viene accettata dal automa

stringa viene accettata dal automa

può essere può essere

un fattore di p (weak factor recognition).

un fattore di p (weak factor recognition).

Ovviamente tutti i match di p su t sono accettati Ovviamente tutti i match di p su t sono accettati

dall'automa.

dall'automa.

Factor Oracle – Definizioni Factor Oracle – Definizioni

Ora diamo alcune definizioni che ci torneranno Ora diamo alcune definizioni che ci torneranno

utili in seguito. Diciamo che utili in seguito. Diciamo che

x ∈Fact ( p) se e solo se p=uxv , u e v ∈Σ * x ∈Pref ( p) se e solo se p= xu , u ∈ Σ *

x ∈Suff ( p) se e solo se p=ux , u ∈Σ * pref _p (i) è il prefisso di p, per 0≤i ≤∣p∣

poccur (u , p)={∣z∣: z=wuetp=wuv}

endpos_p (u)={i | p=wup_{i+ 1} ... p_m}

Factor Oracle Factor Oracle

Build_Oracle (p = p1 p2 ... pm) For i ← 0 to m

Crea un nuovo stato i For i ← 0 to m -1

Costruisci una nuova transizione da i a i + 1 da p i +1 For i ← 0 to m -1

Sia u una parola di lunghezza minima nello stato i For each σ Σ, σ∈ ≠ p i +1

If uσ Fact (p∈ i-| u |+1 ... pm)

Costruisci una nuova transizione da i a i + poccur (pi-| u |+1 ... pm) da σ

Factor Oracle – l'automa Factor Oracle – l'automa

L'automa Factor Oracle di

L'automa Factor Oracle di abbbaababbbaab

Nel Factor Oracle tutti i stati sono terminali.

Nel Factor Oracle tutti i stati sono terminali.

La parola

La parola abbaabba è accettata anche se non è un è accettata anche se non è un fattore di

fattore di abbbaababbbaab

Factor Oracle – Proprietà Factor Oracle – Proprietà

(a)(a) Factor Oracle è un automa deterministico Factor Oracle è un automa deterministico aciclico;

aciclico;

(b)(b) Riconosce almeno i fattori di p;Riconosce almeno i fattori di p;

(c)(c) Ha il minor numero di stati possibili(per una Ha il minor numero di stati possibili(per una stringa p di lunghezza m ci sono esattamente stringa p di lunghezza m ci sono esattamente

m +1 stati);

m +1 stati);

(d)(d) Ha un numero lineare di transizioni (compresi Ha un numero lineare di transizioni (compresi tra m e 2m-1).

tra m e 2m-1).

Di seguito verrà presentata una versione della Di seguito verrà presentata una versione della costruzione del Factor Oracle leggendo il pattern costruzione del Factor Oracle leggendo il pattern

da sinistra verso destra, aggiornando di volta in da sinistra verso destra, aggiornando di volta in

volta l'automa.

volta l'automa.

Per procedere alla definizione dell'algoritmo Per procedere alla definizione dell'algoritmo

abbiamo bisogno di altre 2 definizioni abbiamo bisogno di altre 2 definizioni

Factor Oracle – Factor Oracle – Costruzione online Costruzione online

• Definiamo Definiamo repeat repeat _pp (i) (i) il più lungo suffisso il più lungo suffisso presente in

presente in prefpref_pp(i)(i) che compare almeno 2 che compare almeno 2 volte;

volte;

• Definiamo la Definiamo la funzione supplementofunzione supplemento che che mappa ogni stato i-esimo dell'automa ed mappa ogni stato i-esimo dell'automa ed

memorizza una transazione dallo stato i-esimo memorizza una transazione dallo stato i-esimo

fino allo stato in cui finisce la lettura della fino allo stato in cui finisce la lettura della

funzione

funzione repeat repeat (i) (i)

Factor Oracle – Factor Oracle – Costruzione online Costruzione online

Function add-letter (Oracle (p = p1 p2 ... pm), σ) Crea un nuovo stato m + 1

Crea una nuova transizione da m a m + 1 etichettata σ k ← S p (m)

While k> - 1 e non c'è passaggio da k per σ Do

Crea una nuova transizione da k per m + 1 per σ k ← Sp (k)

End While

If (k = - 1) Then s ← 0

Else s ← dove conduce la transizione da k per σ.

Spσ (m + 1) ← s

Return Oracle (p = p1 p2 ... pm σ)

Factor Oracle – Factor Oracle – Costruzione online Costruzione online

Oracle-on-line (p = p1 p2 ... pm) Crea Oracle (ε) con:

un singolo stato 0 Sε (0) ← - 1

For i ← 1 to m Do

Oracle (p = p1 p2 ... pi) ← add-letter(Oracle (p = p1 p2 ... pi-1), pi ) End For

Applichiamo

Applichiamo add-letteradd-letter ad ogni lettera del ad ogni lettera del pattern, usando un automa con il solo stato pattern, usando un automa con il solo stato

iniziale iniziale

Factor Oracle – Factor Oracle – Costruzione online Costruzione online

Factor Oracle – Factor Oracle – Costruzione online Costruzione online

Oracle-on-line (p = p1 p2 ... pm) Crea Oracle (ε) con:

un singolo stato 0 Sε (0) ← - 1

For i ← 1 to m Do

Crea un nuovo stato m

Crea una nuova transizione da m-1 a m etichettata pi k ← S p (i-1)

While k> - 1 e non c'è passaggio da k per pi Do Crea una nuova transizione da k per i per pi k ← Sp (k)

End While

If (k = - 1) Then s ← 0

Else s ← dove conduce la transizione da k per pi

Spσ (i) ← s End For

Volendo usare una sola funzione, possiamo implementare Volendo usare una sola funzione, possiamo implementare

tutto come di seguito tutto come di seguito

Factor Oracle – BOM Factor Oracle – BOM

BOM (Backward Oracle Matching) è l'algoritmo BOM (Backward Oracle Matching) è l'algoritmo

che implementa insieme BDM (Backward Dawg che implementa insieme BDM (Backward Dawg

Matching) con il Factor Oracle, sfruttandone Matching) con il Factor Oracle, sfruttandone

entrambe le proprietà.

entrambe le proprietà.

Factor Oracle – BOM Factor Oracle – BOM

L'idea del BDM è quella di creare una finestra, L'idea del BDM è quella di creare una finestra,

nella quale cercare i fattori di p

nella quale cercare i fattori di p_rr (il reverse di p) (il reverse di p) da destra verso sinistra. Appena la ricerca

da destra verso sinistra. Appena la ricerca

fallisce, la finestra si posiziona a partire dalla fallisce, la finestra si posiziona a partire dalla

posizione successiva dove la ricerca è fallita.

posizione successiva dove la ricerca è fallita.

La complessità di BOM nel caso peggiore è La complessità di BOM nel caso peggiore è

O(mn) O(mn)

Factor Oracle – BOM

Factor Oracle – BOM

Factor Oracle – BOM Factor Oracle – BOM

BOM ( p = p1 p2 ... pm, T = t1 t2 ... tn ) Pre-elaborazione

Costruzione dell 'Oracle di pr Cerca

pos ← 0

While (pos <= n - m) do

stato ← stato iniziale di Oracle (pr ) j ← m

While esiste lo stato do

stato ← immagine dello stato da T [pos + j] in Oracle (pr ) j ← j - 1

EndWhile If j = 0 do

contrassegnare una occorenza a pos + 1 j ← 1

EndIf

pos ← pos + j EndWhile

Factor Oracle – Turbo-BOM Factor Oracle – Turbo-BOM

Siccome l'automa Factor Oracle accetta parole Siccome l'automa Factor Oracle accetta parole

che non sono realmente fattori del pattern, è che non sono realmente fattori del pattern, è

ragionevole pensare che il numero di ispezioni ragionevole pensare che il numero di ispezioni

sia maggiore rispetto a quelle effettuate con sia maggiore rispetto a quelle effettuate con BDM.BDM.

Introduciamo allora un nuovo Introduciamo allora un nuovo

algoritmo che dotiamo come algoritmo che dotiamo come

Turbo-BOM

Turbo-BOM che combina che combina insieme gli algoritmi KMP e insieme gli algoritmi KMP e

Factor Oracle – Turbo-BOM Factor Oracle – Turbo-BOM

La posizione critica è posizione d'inizio (partendo La posizione critica è posizione d'inizio (partendo

da destra verso sinistra) di Oracle nella da destra verso sinistra) di Oracle nella

precedente ricerca precedente ricerca

Factor Oracle – Turbo-BOM Factor Oracle – Turbo-BOM

Caso 1 : la posizione critica non viene raggiunta Caso 1 : la posizione critica non viene raggiunta

Factor Oracle – Turbo-BOM Factor Oracle – Turbo-BOM

Caso 2 : la posizione critica viene raggiunta Caso 2 : la posizione critica viene raggiunta

Factor Oracle Factor Oracle

Dati Sperimentali Dati Sperimentali

Risultati sperimentali nel Risultati sperimentali nel

tempo degli algoritmi di tempo degli algoritmi di string matching sul test string matching sul test

casuali di 10 Mb di casuali di 10 Mb di

dimensione su alfabeti di dimensione su alfabeti di dimensione 2, 4, 16 e 32.

dimensione 2, 4, 16 e 32.

L'asse X rappresenta la L'asse X rappresenta la

lunghezza del modello e lunghezza del modello e

l'asse Y il tempo di ricerca l'asse Y il tempo di ricerca

Factor Oracle – Real World Factor Oracle – Real World

• CatBOX (Computer Audition Toolbox)CatBOX (Computer Audition Toolbox)

uso: Factor Oracle for Midi improvisation uso: Factor Oracle for Midi improvisation

http://cosmal.ucsd.edu/cal/projects/CATbox/catboxdownload.htm http://cosmal.ucsd.edu/cal/projects/CATbox/catboxdownload.htm

• Applicazioni per trovare occorrenze in:Applicazioni per trovare occorrenze in:

• Dati compressiDati compressi

• BioinformaticaBioinformatica

Factor Oracle – References Factor Oracle – References

• C. Allauzen, M. Crochemore, and M. Raffinot:C. Allauzen, M. Crochemore, and M. Raffinot: Factor oracle: a Factor oracle: a new structure for pattern matching

new structure for pattern matching, , in SOFSEM’99, J. in SOFSEM’99, J.

Pavelka, G. Tel, and M. Bartosek, eds., LNCS 1725, Pavelka, G. Tel, and M. Bartosek, eds., LNCS 1725,

Milovy,Czech Republic, 1999, Springer-Verlag, Berlin, pp. 291–

Milovy,Czech Republic, 1999, Springer-Verlag, Berlin, pp. 291–

306.306.

• Factor Oracle Suffix Oracle, Factor Oracle Suffix Oracle,

http://www.slideserve.com/ula/factor-oracle-suffix-oracle http://www.slideserve.com/ula/factor-oracle-suffix-oracle

Grazie per l'attenzione

Grazie per l'attenzione