Curs de Doctorat: Algorismes de cerca

Curs de Doctorat: Algorismes de cerca

Algorismes de cerca: definició del problema (text,patró)

depèn de què coneixem al principi:• Cerca exacta:

• Cerca aproximada:

• 1 patró ---> L’algorisme depèn de la llargada i ||

• k patrons ---> L’algorisme depén del nombre k, la llargada i ||

• Només el text ----> Estructurar el text (suffix tree)

• Només el/s patró/ns ---> Estructurar el/els patró/ns

depèn de la llargada del patró• l<w (llargada paraula) ---> Algorisme Myers • l>w (llargada paraula) ---> Programació dinàmica

Alg. Cerca exacta d’un patró (text on-line)

Algorismes més eficients (Navarro & Raffinot)

2 4 8 16 32 64 128 256

64

32

16

8

4

2

| |

Long. patró

Horspool

BNDMBOM

BNDM : Backward Nondeterministic Dawg Matching

BOM : Backward Oracle Matching

w

Algorisme de Horspool

Text :

Patró :Compara sufixes

• Com es determina la següent posició de la finestra?

• Com fa la comparació?

Patró :

Text : a

Salta fins a la primera aparició de la lletra “a” a partir del segon lloc:

aa a

a a a

Es necessari fer un preprocés que determini el salt per a cada símbol.

Exemple algorisme de Horspool

Suposem que el patró és ATGTA

• La taula de salts seria:

A 4C 5G 2T 1

I la cerca sobre el text : G T A C T A G A G G A C G T A T G T A C T G ...A T G T A

A T G T A

A T G T A

A T G T A A T G T A

A T G T A A T G T A



2 4 8 16 32 64 128 256

64

32

16

8

4

2

| |

Long. patró

Horspool

BNDMBOM



w

Text :

Patró :

Llegeix anotant sufixos de T que són factors de P

Algorisme BNDM



I ho anota de la forma

D = 1 0 0 0 1 0 0I pel següent símbol fa

D = D<<1 & B(x) B(x): máscara del símbol següent x al patró P. Si fos B(x) = ( 0 0 1 1 0 0 0)

D = (0 0 0 1 0 0 0) & (0 0 1 1 0 0 0 ) = (0 0 0 1 0 0 0 )

El tres ultims simbols de T apareixen a P a la posició indicada

Si surt un 1 a es fa coincidir el prefix de P amb el sufix de T

Si no passa, es que cap prefix de P es sufix de T, llavors es salta tota la finestra.

Exemple algorisme BNDM

Suposem que el patró és ATGTA

• I la cerca sobre el text : G T A C T A G A G G A C G T A T G T A C T G ...A T G T A

A T G T A

A T G T A

A T G T A

• La màscara de bits per a cada símbol és:

B(A) = ( 1 0 0 0 1 )B(C) = ( 0 0 0 0 0 )B(G) = ( 0 0 1 0 0 )B(T) = ( 0 1 0 1 0 )

D1 = ( 1 1 1 1 1 ) & ( 0 1 0 1 0 ) = ( 0 1 0 1 0 )D2 = ( 1 0 1 0 1 ) & ( 0 0 0 0 0 ) = ( 0 0 0 0 0 )

D0 = ( 1 1 1 1 1 )

D0 = ( 1 1 1 1 1 ) D1 = ( 1 1 1 1 1 ) & ( 0 0 1 0 0 ) = ( 0 0 1 0 0 )D2 = ( 0 1 0 0 0 ) & ( 0 0 1 0 0 ) = ( 0 0 0 0 0 )

D0 = ( 1 1 1 1 1 ) D1 = ( 1 1 1 1 1 ) & ( 1 0 0 0 1 ) = ( 1 0 0 0 1 )D2 = ( 0 0 0 1 0 ) & ( 0 1 0 1 0 ) = ( 0 0 0 1 0 )D3 = ( 0 0 1 0 0 ) & ( 0 0 1 0 0) = ( 0 0 1 0 0 )D4 = ( 0 1 0 0 0 ) & ( 0 0 0 0 0) = ( 0 0 0 0 0 )

Exemple algorisme BNDM

A T G T A

• El patró és ATGTA

• La màscara de bits per a cada símbol és:

• I la cerca sobre el text continua: G T A C T A G A G G A C G T A T G T A C T G ...A T G T A

B(A) = ( 1 0 0 0 1 )B(C) = ( 0 0 0 0 0 )B(G) = ( 0 0 1 0 0 )B(T) = ( 0 1 0 1 0 )

D0 = ( 1 1 1 1 1 ) D1 = ( 1 1 1 1 1 ) & ( 1 0 0 0 1 ) = ( 1 0 0 0 1 )D2 = ( 0 0 0 1 0 ) & ( 0 1 0 1 0 ) = ( 0 0 0 1 0 )D3 = ( 0 0 1 0 0 ) & ( 0 0 1 0 0 ) = ( 0 0 1 0 0 )D4 = ( 0 1 0 0 0 ) & ( 0 1 0 1 0 ) = ( 0 1 0 0 0 )D5 = ( 1 0 0 0 0 ) & ( 1 0 0 0 1 ) = ( 1 0 0 0 0 )D6 = ( 0 0 0 0 0 ) & ( * * * * * ) = ( 0 0 0 0 0 ) Trobat!



2 4 8 16 32 64 128 256

64

32

16

8

4

2

| |

Long. patró

Horspool

BNDMBOM



w

Algorisme BOM (Backward Oracle Matching)



Text :

Patró : Autòmata: Factor Oracle

Comproba si el sufix és factor del patró

a

• Si la a no s’ha trobat

• Si arriben a l’estat final de l’autòmat amb la a

a

Autòmata Factor Oracle: propietats

Factor Oracle del mot G T A T G T A

GG AT T ATTA

G

Tots els estats són finals ==> Reconeix tots els factors …. i més

GG AT T ATTA

G

Hip: reconeix tots factors de GTA

L’estat reconeix tots els factors que acaben a la quarta lletra T que no eren reconeguts:GTAT, TAT, AT perque T ja ho era.

Reconeix tots els factors de de les primeres 4 lletres

Autòmata Factor Oracle: algorisme

Algorisme: per a i=1 fins p fer Afegir transicions que reconeguin factors acabats a i;

?


Que passa si el següent caràcter existeix?

TT


Que passa si el següent caràcter no existeix?

TT

Autòmata Factor Oracle: exemple d’algorisme

GG AT T ATTA

G

i reconeix mots que no són factors com GTGTA.

Però, si no el reconeix ==> no és factor!

Es l’estratègia de l’algorisme BOM

Algorisme BOM



Text :

Patró :

Compara sufixes

Autòmata invers

a




• Es construeix l’autòmata del patró invers: Suposem que el patró és ATGTATG

• I la cerca sobre el text : G T A C T A G A G G A T G T A G A T A T G A G G T G A...A T G T A T G


GG AT T ATTA

G

* *

A T G T A T G

* * *

A T G T A T G A T G T A T G

Alg. Cerca exacta de molts patrons

5 10 15 20 25 30 35 40 45

8

4

2

| |

Wu-Manber

SBOMLong. mínima

(5 mots)

5 10 15 20 25 30 35 40 45

8

4

2

Wu-Manber

SBOM(10 mots)

5 10 15 20 25 30 35 40 45

8

4

2

Wu-Manber

SBOM

(100 mots)

Alg. Cerca exacta de molts patrons

5 10 15 20 25 30 35 40 45

8

4

2

| |

Wu-Manber

SBOM

5 10 15 20 25 30 35 40 45

8

4

2

Wu-Manber

SBOM

5 10 15 20 25 30 35 40 45

8

4

2

SBOM

Long. mínima

(5 mots)

(10 mots)

(100 mots)(1000 mots)

Autòmata Multi-Factor Oracle

GG AT TTTA

G

Tenim el Factor Oracle de GTATGTA

Com serà el de GTATGT, TAATA

T A

AGG AT TT

TA

G A

Autòmata Multi-Factor Oracle

Multi Factor Oracle de GTATGT, TAATA, TGTAA

GG AT TTTA

G A

T A

AA A

Algorisme SBOM

Text :

Patrons:

Compara sufixes



a


Autòmata invers



• Es construeix l’autòmata dels patrons inversos: TGTATG, ATAAT, AATGT

• I la cerca sobre el text : G T A C T A G A G G A T G T A G A T A T G A G G T G A...


** ** *

GG AT TTTA

G A

T A

AA A

* ** * *

Documents

Curs de Doctorat: Algorismes de cerca