&DS&RQFRUGkQFLDGH0RGHORV
_________________________________________________________________________________________
Capítulo 2 : Concordância de Modelos
(pesquisa de padrões) (pattern matching)
•
(PJUDQGHSDUWHGRVFDVRVGHSHVTXLVDRTXHVHSUHWHQGHHQFRQWUDUQmRp
XPHOHPHQWRVLPSOHVPDVVLPXPDGHWHUPLQDGDVHTXrQFLD
❒ 3UREOHPD 1XPDFDGHLDGHFDUDFWHUHVSURFXUDURFRUUrQFLDV FRQFRUGkQFLDVGHXPGDGRSDGUmRPRGHOR
p r o c u r a r o m o d e l o
c a s o e
x i s t a
XPDFRQFRUGkQFLDRFRUUHDSDUWLUGHL
ƒ
$SOLFDo}HV 7RGRRWLSRGHSHVTXLVDVHPHVWUXWXUDVVHTXHQFLDLV
SDODYUDVRXIUDVHVHPWH[WRV
VXEOLVWDVHPOLVWDV
SURFHVVDGRUHVGHWH[WRPRWRUHVGHEXVFD
ELRORJLDPROHFXODUELEOLRWHFDVGLJLWDLVFULPLQRORJLD
ILOWURVGHVSDP LPDJHQVGLJLWDLV
❒ (VSHFLILFDomR
'DGRV
5HVXOWDGR
FDGHLD
SDGUmR
s[1..n]
p[1..m]
( onde n >> m )
ORFDOL]DomRGRLQtFLRGRSDGUmRQDFDGHLD
{ i ± [1..n] : k ± [1..m] Á s[i + k – 1] = p[k] }
_________________________________________________________________________________________
7LSRV$EVWUDFWRVGH'DGRV5RViOLD5RGULJXHV
&DS&RQFRUGkQFLDGH0RGHORV
_________________________________________________________________________________________
❒ 6ROXomR 7ULYLDO ,UGHVORFDQGRRPRGHORDRORQJRGDFDGHLD
FRPSDUDQGRFDUDFWHUDFDUDFWHU
L‘
…
Q
a b c a b c a b d a b c
N‘
…
P
a b c a b d a b c
a b c a b d a b c
a b c a b d a b c
a b c a b d a b c
ƒ
IDOKRXSDUDN
IDOKRXSDUDN IDOKRXSDUDN
FRQFRUGkQFLD
&RPSOH[LGDGH GD 6ROXomR 7ULYLDO
•
•
•
•
1RSLRUFDVRVmRUHDOL]DGDVP l Q FRPSDUDo}HV
4XDODLQVWkQFLDTXHJHUDRSLRUFDVR"
4XDLVVmRRVPRGHORV³GLItFHLV´"
1HFHVVLGDGHGHXPDOJRULWPROLQHDUHPQ
_________________________________________________________________________________________
7LSRV$EVWUDFWRVGH'DGRV5RViOLD5RGULJXHV
&DS&RQFRUGkQFLDGH0RGHORV
_________________________________________________________________________________________
{ solução trivial }
SURFHGXUH PesquisarModelo ( s, p : cadeia; m, n : integer;
YDU indice : integer; YDU achou : boolean);
YDU i, j, k : integer;
iguais : boolean;
EHJLQ i := 0;
achou:= IDOVH;
ZKLOH QRW achou DQG ( i < n–m+1) GR
EHJLQ { QmR começa em [1..i–1] H achou = (começa em i) }
{ QmR começa em [1..i] }
{ avançar modelo na cadeia }
i = i + 1;
k := 0;
iguais := WUXH;
ZKLOH iguais DQG ( k < m ) GR
EHJLQ { concordância até k–1
H iguais = (s[i + k – 1] = p[k]) }
{ concordância até k }
{ avançar no modelo }
k := k + 1 ;
iguais := s[i + k –1] = p[k]
{ concordância até k–1
H iguais = (s[i + k – 1] = p[k]) }
HQG;
{ QmR iguais RX (k • P} { iguais = (s[i + k – 1] = p[k]) }
achou := iguais
{ QmR começa em [1..i–1] H achou = (começa em i) }
HQG;
{ achouRX (i • n–m+1) } { achou = (começa em i) }
{ achou = ( i ± [1..n] : k ± [1..m] Á s[i + k – 1] = p[k]) }
LI achou
WKHQ indice := i { indice ± [1..n] : k ± [1..m] Á s[indice + k – 1] = p[k]) }
HOVH indice := 0 { indice ² [1..n] }
HQG; { PesquisarModelo }
_________________________________________________________________________________________
7LSRV$EVWUDFWRVGH'DGRV5RViOLD5RGULJXHV
&DS&RQFRUGkQFLDGH0RGHORV
_________________________________________________________________________________________
❒ $OJRULWPR GH .QXWK ± 0RUULV ± 3UDWW .03 ƒ
$ LGHLD
•
$QDOLVHPRVXPH[HPSORGRSLRUFDVR
Q
V a a a a a a a a a a a a a a a a a a a a b
S a a a a a b
a a a a a b
P
•
•
•
•
•
6HULDPHIHFWXDGDVQ±Pl P FRPSDUDo}HV
$SyVDFRPSDUDomRV>@S>@
RDOJRULWPRWULYLDODYDQoDULDRSDGUmRHYROWDULDDFRPSDUDU
V>@ S>@V>@ S>@V>@ S>@V>@ S>@V>@ S>@
'HYHULDFRPSDUDUDSHQDVV>@ S>@
3UHWHQGHPRVXPDOJRULWPRRQGHFRQFRUGkQFLDVDQWHULRUHVQmR
YROWHPDVHUWHVWDGDV6yDVVLPSRGHUiVHUOLQHDUHPQ
2VFDVRV³PDXV´VmRSURYRFDGRVSRUFRQFRUGkQFLDVSDUFLDLV
$VFRQFRUGkQFLDVSDUFLDLVVmRSURYRFDGDVSRUUHSHWLo}HV
GHQWURGRPRGHOR
3UHWHQGHPRVXPDOJRULWPRTXH³FRQKHoD´DVUHSHWLo}HV
H[LVWHQWHVQRPRGHOR
_________________________________________________________________________________________
7LSRV$EVWUDFWRVGH'DGRV5RViOLD5RGULJXHV
&DS&RQFRUGkQFLDGH0RGHORV
_________________________________________________________________________________________
•
&RPRUHJLVWDUDVUHSHWLo}HV"
•
9ROWDQGRDRSULPHLURH[HPSOR
V
...
L
a b c a b c a b d a b c
...
S a b c a b d a b c
N
•
$SyVDFRPSDUDomRV>L@S>@RDOJRULWPR
GHYHULDFRPSDUDU V>L@ S>@
3RUTXHQRSDGUmRH[LVWHPDVUHSHWLo}HVS>@ S>@HS>@ S>@
$V5HSHWLo}HVHPSYmRVHUUHJLVWDGDVQXPYHFWRUDX[LOLDU
S
5
D
E F D E G D E F
0
0
0
1
2
0
1
2
3
S>@ S>@Á 5>@ S>@ S>@Á 5>@ S>@S>@Á 5>@ S>@ S>@Á 5>@ S>@ S>@Á 5>@ S>@ S>@Á 5>@ _________________________________________________________________________________________
7LSRV$EVWUDFWRVGH'DGRV5RViOLD5RGULJXHV
&DS&RQFRUGkQFLDGH0RGHORV
_________________________________________________________________________________________
S
5
D
D D D D E
0
1
2
3
4
0
S>@ S>@ S>@ S>@ S>@
ƒ
$OJRULWPR SDUD D FRQVWUXomR GR YHFWRU 5
R[1]  0
k1
para i = 2 .. m
se p[i] = p [k]
então R[i]  k
kk+1
senão R[i]  0
k1
SURFHGXUH construirR ( p : cadeia; m : integer; YDU R : vector);
YDU i, k : integer;
EHJLQ IRUi := 1 WR m GR
R[i] := 0;
k := 1;
IRUi := 2 WR m GR
LIp[i] = p[k]
WKHQEHJLQ R[i] := k;
k := k + 1
HQG
HOVH k := 1
HQG; { construirR }
_________________________________________________________________________________________
7LSRV$EVWUDFWRVGH'DGRV5RViOLD5RGULJXHV
&DS&RQFRUGkQFLDGH0RGHORV
_________________________________________________________________________________________
ƒ
2 DOJRULWPR .03
•
6HIRLYHULILFDGDXPDGHVLJXDOGDGHSDUDN
...
D
L
E F
S
•
•
E F D E G D E F
ii+1
&RPRFRQWLQXDURSURFHVVRDSyVXPDFRQFRUGkQFLDSDUFLDO"
6HIRLYHULILFDGDXPDLJXDOGDGHs[i] = p[k] FRPRSDUDN
S
D
D E F D E G D E F ...
R PRGHORDYDQoDQDFDGHLDFRQWLQXDQGRN ...
D
E
F
D
E
F D E G D E F ...
D
E
F
D
E
G D E F
GHYHUmRVHUFRPSDUDGRVRVGRLVFDUDFWHUHVVHJXLQWHV
ii+1
kk+1
_________________________________________________________________________________________
7LSRV$EVWUDFWRVGH'DGRV5RViOLD5RGULJXHV
&DS&RQFRUGkQFLDGH0RGHORV
_________________________________________________________________________________________
•
6HIRLYHULILFDGDXPDGHVLJXDOGDGHs[i]  S>N@ WDOFRPRSDUD
N S
5
D
E F D E G
D E F
0
0
0
1
2
0
1
2
3
N ‘ e QHFHVViULRUHJUHVVDUDRFDUDFWHU³FRUUHVSRQGHQWH´QRVXE
SDGUmRDQWHULRU2XVHMD
k  R[k-1] + 1
•
•
( SURFHVVRFRQWLQXDULDSDUDRPHVPRL YROWDQGRDFRPSDUDU
V>L@FRPS>N@
3DUDRRXWURH[HPSOR
S
5
D
D D D D E
0
1
2
3
4
0
N ‘ _________________________________________________________________________________________
7LSRV$EVWUDFWRVGH'DGRV5RViOLD5RGULJXHV
&DS&RQFRUGkQFLDGH0RGHORV
_________________________________________________________________________________________
•
( PDLVXPH[HPSOR
...
D
L
F
S
D
E
D E F G
0
0
1
2
0
0
5
E D F E D F E ...
N ‘ V>L@S>@ L L •
2 L DYDQoDTXDQGRDGHVLJXDOGDGHpYHULILFDGDSDUDN •
3RUWDQWR
V>L@S>@ N 5>N@ 5>@ se k = 1
então i  i + 1
senão k  R[k-1] + 1
_________________________________________________________________________________________
7LSRV$EVWUDFWRVGH'DGRV5RViOLD5RGULJXHV
&DS&RQFRUGkQFLDGH0RGHORV
_________________________________________________________________________________________
•
( DSyVXPDFRQFRUGkQFLDWRWDO"
L
...
D
E
F
D
E
F
S
D
E
F
D
E
F
0
0
0
1
2
3
5
•
•
V>L@ S>@ L L N N N !P
D E F ...
N ‘ GHWHFWDGDXPDFRQFRUGkQFLD
p QHFHVViULRUHFXDUQRPRGHOR
XWLOL]DQGRDPHVPDIyUPXOD
1RWHVHTXHQHVWHFDVRH[LVWHPGXDVFRQFRUGkQFLDVWRWDLV
3DUDXPDFDGHLDGHFRPSULPHQWRQ RDOJRULWPR.03QXQFD
HIHFWXDPDLVGHGXDVFRPSDUDo}HVSRUHOHPHQWR$VVLPR
Q~PHURWRWDOGHFRPSDUDo}HVYDULDHQWUHQHQVHQGR
SRUWDQWRXPDOJRULWPROLQHDU
_________________________________________________________________________________________
7LSRV$EVWUDFWRVGH'DGRV5RViOLD5RGULJXHV
&DS&RQFRUGkQFLDGH0RGHORV
_________________________________________________________________________________________
{ Algoritmo KMP }
SURFHGXUH ContarConcordancias ( s, p : cadeia; m, n : integer;
YDU R : vector; YDU conc : integer );
YDU i, k : integer;
EHJLQ construirR(p, m, R);
conc := 0;
i := 1;
k := 1;
ZKLOH i <= n GR
LI s[i] = p[k]
WKHQEHJLQ { concordância parcial }
i := i + 1;
k := k + 1;
HQG
LI k > m
WKHQ{ concordância total }
EHJLQ conc := conc + 1;
k := R[k-1] + 1
HQG
HOVH{ desigualdade }
LI k = 1
WKHQ i := i + 1
HOVH k := R[k-1] + 1
HQG; { ContarConcordancias }
H[HUFtFLR $GDSWDUHVWHPyGXORSDUDDXWLOL]DomRHPILFKHLURVGH
WH[WR3RUH[HPSORSURFXUDUXPDIUDVHFRQWDUDV
RFRUUrQFLDVGHXPDSDODYUD
_________________________________________________________________________________________
7LSRV$EVWUDFWRVGH'DGRV5RViOLD5RGULJXHV
&DS&RQFRUGkQFLDGH0RGHORV
_________________________________________________________________________________________
❒ 2 0RGHOR 0DWHPiWLFR GR $OJRULWPR .03
'HILQLomR 8P$XWyPDWR)LQLWR'HWHUPLQLVWD$)' pXP
TXtQWXSORRUGHQDGR
RQGH
•
•
•
$
4È G T )
4 p XPFRQMXQWRILQLWRQmRYD]LRGHHVWDGRV
È p XPFRQMXQWRILQLWRDOIDEHWR GHVtPERORVGH
HQWUDGD
G 4— È| 4 p DIXQomRSDUFLDOGHWUDQVLomRRX
GHPXGDQoDGHHVWDGR
• T ± 4 p RHVWDGRLQLFLDO
• ) ° 4 p RFRQMXQWRGRVHVWDGRVILQDLVRXGH
DFHLWDomR
LQSXW
HVWDGR
•
•
( DFHLWD/ UHMHLWD )
3DUDFDGDPRGHORDSHVTXLVDURDOJRULWPR.03FRQVLVWHQD
FRQVWUXomRGHXP$)'HQDVLPXODomRGRVHXIXQFLRQDPHQWR
DRORQJRGDFDGHLDLQSXW GHSHVTXLVD
8PHVWDGRGHDFHLWDomRGRDXWyPDWRFRUUHVSRQGHDXPD
FRQFRUGkQFLDWRWDO
_________________________________________________________________________________________
7LSRV$EVWUDFWRVGH'DGRV5RViOLD5RGULJXHV
&DS&RQFRUGkQFLDGH0RGHORV
_________________________________________________________________________________________
•
$ FDGDPRGHORFRUUHVSRQGHXP$)'FXMDIXQomRGHWUDQVLomR
IRLUHSUHVHQWDGDSHORYHFWRU5
3RUH[HPSOR
S
5
D
E F D E F
RXQDUHSUHVHQWDomRKDELWXDOGHDXWyPDWRV
SRUH[HPSOR
•
•
•
R[5] = 2 ¾
G (q5, F) = q6
G (q5, x) = q2 , x œ F
3DUWLQGRGRHVWDGRLQLFLDO0DOHLWXUDGDVHTXrQFLDDEFDEF
FRQGX]DRHVWDGRGHDFHLWDomR6)
$SyVXPDGHVLJXDOGDGHRXXPDFRQFRUGkQFLDWRWDOR
DXWyPDWRUHJUHVVDDXPGRVHVWDGRVDQWHULRUHV
(VVH³UHJUHVVR´HUDUHSUHVHQWDGRSHODIyUPXODk := R[k-1] + 1
_________________________________________________________________________________________
7LSRV$EVWUDFWRVGH'DGRV5RViOLD5RGULJXHV
&DS&RQFRUGkQFLDGH0RGHORV
_________________________________________________________________________________________
❒ 8PD YDULDQWH GR $OJRULWPR .03
•
•
1RDOJRULWPR.03EDVHRYHFWRU5pVHPSUHXWLOL]DGRDWUDYpVGD
IyUPXODk := R[k-1] + 1
8PDDOWHUDomRVLPSOHVSDUDHYLWDUDVXEWUDFomRHDVRPD
FRQVLVWHHPUHJLVWDUQXPYHFWRU6RUHVXOWDGRGHVVDIyUPXOD
3RUH[HPSOR
S
5
6
D
E F D E F
8WLOL]DomRGHPDLVXPHOHPHQWRN P
SDUDRFDVRGDFRQFRUGkQFLDWRWDO
SURFHGXUH construirS ( p : cadeia; m : integer; YDU S : vector);
YDU i, k : integer;
EHJLQ S[1] := 1;
k := 1;
IRUi := 2 WR m GR
EHJLQ S[i] := k;
LIp[i] = p[k]
WKHQk := k + 1
HOVHk := 1
HQG;
S[m+1] := k
HQG; { construirS }
_________________________________________________________________________________________
7LSRV$EVWUDFWRVGH'DGRV5RViOLD5RGULJXHV
&DS&RQFRUGkQFLDGH0RGHORV
_________________________________________________________________________________________
•
1RH[HPSORVHJXLQWHpXWLOL]DGDXPDIXQomR
$ SHVTXLVDpUHDOL]DGDQXPILFKHLUR)GHWH[WRFRQVLGHUDGR
JOREDOjIXQomRHRYHFWRU6pORFDO
IXQFWLRQ concordancias ( p : cadeia; m : integer ) : integer;
YDU k, c : integer;
car : char;
S : vector;
EHJLQ construirS(p, m, S);
c := 0;
k := 1;
reset(F);
read(F, car);
ZKLOH QRW eof(F) GR
LI car = p[k]
WKHQEHJLQ { concordância parcial }
read(F, car);
k := k + 1;
HQG
LI k > m
WKHQ{ concordância total }
EHJLQ c := c + 1;
k := S[k]
HQG
HOVH{ desigualdade }
LI k = 1
WKHQ read(F, car)
HOVH k := S[k];
close(F);
concordancias := c
HQG; { concordancias }
_________________________________________________________________________________________
7LSRV$EVWUDFWRVGH'DGRV5RViOLD5RGULJXHV
&DS&RQFRUGkQFLDGH0RGHORV
_________________________________________________________________________________________
❒ 3HVTXLVD QXPD /LVWD /LQHDU /LJDGD
•
&RQVLGHUHPRVDJRUDTXHRGRPtQLRGHSHVTXLVDpXPDOLVWDOLQHDU
OLJDGDGHILQLGDSRU
W\SH lista = ^elemento;
elemento = UHFRUG letra : char;
prox : lista
HQG;
IXQFWLRQ concordancias ( ponta : lista; p : cadeia; m : integer ) : integer;
YDU k, c : integer;
S : vector;
este : lista;
EHJLQ construirS(p, m, S);
c := 0;
k := 1;
este := ponta;
ZKLOH este <> nil GR
LI este^.letra = p[k]
WKHQEHJLQ { concordância parcial }
este := este^.prox;
k := k + 1;
LI k > m
WKHQ{ concordância total }
EHJLQ c := c + 1;
k := S[k]
HQG
HQG
HOVH{ desigualdade }
LI k = 1
WKHQ este := este^.prox
HOVH k := S[k];
concordancias := c
HQG; { concordancias }
_________________________________________________________________________________________
7LSRV$EVWUDFWRVGH'DGRV5RViOLD5RGULJXHV
&DS&RQFRUGkQFLDGH0RGHORV
_________________________________________________________________________________________
❒ 5HSUHVHQWDomR GR 0RGHOR SRU XPD /LVWD /LJDGD
•
3DUDUHSUHVHQWDURPRGHORQXPDIRUPD³VHPHOKDQWH´DXP
$XWyPDWR)LQLWR'HWHUPLQLVWDFRQVLGHUHPRVDVHJXLQWHOLVWD
GXSODPHQWHOLJDGD
W\SH modelo = ^elemento;
elemento = UHFRUG letra : char;
SUR[, UHFXD : modelo
HQG;
•
2 SRQWHLURSUR[pXWLOL]DGRQRFDVRGHXPDLJXDOGDGHGH
FDUDFWHUHVN NHQRFDVRGHXPDGHVLJXDOGDGHRSRQWHLUR
UHFXDVHJXHDVWUDQVLo}HVGHILQLGDVSHORYHFWRU6N 6>N@
3RUH[HPSORDRPRGHOR
S
6
D
E F D E F
FRUUHVSRQGHDOLVWD
•
2 GHVORFDPHQWRGHVWDHVWUXWXUDDRORQJRGRGRPtQLRGHSHVTXLVD
VLPXODRIXQFLRQDPHQWRGHXP$XWyPDWR)LQLWR'HWHUPLQLVWD
_________________________________________________________________________________________
7LSRV$EVWUDFWRVGH'DGRV5RViOLD5RGULJXHV
&DS&RQFRUGkQFLDGH0RGHORV
_________________________________________________________________________________________
•
$VVXPLQGRTXHHVWDUHSUHVHQWDomRGRPRGHORIRLMiFRQVWUXtGD
IXQFWLRQ concordancias ( ponta : lista; inicio : modelo ) : integer;
YDU
c : integer;
este : lista;
p : modelo;
EHJLQ c := 0;
este := ponta;
p := inicio;
ZKLOH este <> nil GR
LI este^.letra = p^.letra
WKHQEHJLQ { concordância parcial }
este := este^.prox;
HQG
LI p^.prox = nil
WKHQ{ concordância total }
EHJLQ c := c + 1;
p := p^. recua
HQG
HOVHp := p^. prox
HOVH{ desigualdade }
LI p = inicio
WKHQ este := este^.prox
HOVH p := p^. recua;
concordancias := c
HQG; { concordancias }
_________________________________________________________________________________________
7LSRV$EVWUDFWRVGH'DGRV5RViOLD5RGULJXHV
&DS&RQFRUGkQFLDGH0RGHORV
_________________________________________________________________________________________
❒ &RQVWUXomR GD 5HSUHVHQWDomR
•
$ SDUWLUGRSDGUmRLQLFLDOHGRYHFWRU6FRPHoDPRVSRUFRQVWUXLU
D OLVWDHGHILQLURVFDPSRVOHWUDHSUR[
3RUH[HPSOR
S
6
•
D
E F D E F
3URFXUHPRVXPDOJRULWPRSDUDDGHILQLomRGRFDPSRUHFXD
_________________________________________________________________________________________
7LSRV$EVWUDFWRVGH'DGRV5RViOLD5RGULJXHV
&DS&RQFRUGkQFLDGH0RGHORV
_________________________________________________________________________________________
ƒ
$OJRULWPR YDUp, ant, aux : modelo;
…
p := inicio;
p^.recua := inicio;
ZKLOH p^.prox <> nil GR
EHJLQant := p;
p := p^.prox;
aux := ant^.recua;
ZKLOH ( aux^.letra <> ant^.letra ) DQG ( aux <> inicio ) GR
aux := aux^.recua;
HQG;
LI ( aux^.letra = ant^.letra ) DQG (ant <> inicio)
WKHQ p^.recua := aux^.prox
HOVH p^.recua := inicio
_________________________________________________________________________________________
7LSRV$EVWUDFWRVGH'DGRV5RViOLD5RGULJXHV
&DS&RQFRUGkQFLDGH0RGHORV
_________________________________________________________________________________________
ƒ
$OJRULWPR •
&RPEDVHQRDOJRULWPRXWLOL]DGRSDUDDFRQVWUXomRGRYHFWRU6
YDU i, k : integer;
…
S[1] := 1;
k := 1;
IRUi := 2 WR m GR
EHJLQ S[i] := k;
LIp[i] = p[k]
WKHQk := k + 1
HOVHk := 1
HQG;
…
H DGDSWDQGRGLUHFWDPHQWH
YDUp, aux : modelo;
…
p := inicio;
aux := inicio;
p^.recua := inicio;
ZKLOH p^.prox <> nil GR
EHJLQp := p^.prox;
p^.recua := aux;
HQG;
LI p^.letra = aux^.letra
WKHQ aux := aux^.prox
HOVH aux := inicio
_________________________________________________________________________________________
7LSRV$EVWUDFWRVGH'DGRV5RViOLD5RGULJXHV
&DS&RQFRUGkQFLDGH0RGHORV
_________________________________________________________________________________________
•
&RPSDUHDHILFLrQFLDGRVGRLVDOJRULWPRVDQWHULRUHVQD
FRQVWUXomRGDVOLVWDVDVVRFLDGDVDRVPRGHORV
S
D
E F D E F
S
D
D D D D E
S
D
D D D E D
5
6
5
6
5
6
_________________________________________________________________________________________
7LSRV$EVWUDFWRVGH'DGRV5RViOLD5RGULJXHV