Algorytmy tekstowe
zaj ˛ecia 7.
Bartosz Górski, Tomasz Kulczy ´nski, Bła˙zej Osi ´nski
Algorytmy tekstowe
zaj ˛ecia 7.
Bartosz Górski, Tomasz Kulczy ´nski, Bła˙zej Osi ´nski
Słowa
słowo
dla informatyka to ci ˛
ag znaków
nie musi mie´c sensu w ˙zadnym u˙zywanym j ˛ezyku
Problemy
Najcz ˛e´sciej stawiany problem tekstowy:
wyszukiwanie wzorca w tek´scie
znak
alfabet
– zbiór dost ˛epnych znaków
słowa
– ci ˛
agi znaków
Problemy
Najcz ˛e´sciej stawiany problem tekstowy:
wyszukiwanie wzorca w tek´scie
znak
alfabet
– zbiór dost ˛epnych znaków
słowa
– ci ˛
agi znaków
Problemy
Najcz ˛e´sciej stawiany problem tekstowy:
wyszukiwanie wzorca w tek´scie
znak
alfabet
– zbiór dost ˛epnych znaków
słowa
– ci ˛
agi znaków
Problemy
Najcz ˛e´sciej stawiany problem tekstowy:
wyszukiwanie
wzorca
w
tek´scie
znak
alfabet
– zbiór dost ˛epnych znaków
słowa
– ci ˛
agi znaków
Przykład
Problem
alfabet: {a, b}
tekst: abbbaabaabba
wzorzec: aaba
Przykład
Problem
alfabet: {a, b}
tekst: abbbaabaabba
wzorzec: aaba
Rozwi ˛
azanie
wyst ˛
apienia:
1
abbb
aaba
aabaa
2
abbbaab
aaba
a
Pomysł
Spróbujmy w ka˙zdym miejscu dopasowa´c wzorzec.
Działanie
c
b
ada
bc
baabccdba
bccd
b
ccd
bccd
bccd
bccd
bc
cd
Zło˙zono´s´c
n – długo´s´c tekstu
m – długo´s´c wzorca
O(n · m)
Zło˙zono´s´c
n – długo´s´c tekstu
m – długo´s´c wzorca
O(n · m)
W praktyce
znacznie
lepiej!
Czy rzeczywi´scie O(n · m)?
tekst: aaaaaa . . . aaaa (długo´sci n)
wzorzec: aa . . . aab (długo´sci m)
ile operacji wykonuje algorytm naiwny?
Czy rzeczywi´scie O(n · m)?
tekst: aaaaaa . . . aaaa (długo´sci n)
wzorzec: aa . . . aab (długo´sci m)
liczba operacji: (n − m + 1) · m
Pomysł
Za ka˙zdym razem zaczynamy porównywa´c od pocz ˛
atku –
tracimy cenne informacje!
Pomysł
Za ka˙zdym razem zaczynamy porównywa´c od pocz ˛
atku –
tracimy cenne informacje!
Przykład
ab
aaa
aaaaaaaaa
aaa
b
Pomysł
Za ka˙zdym razem zaczynamy porównywa´c od pocz ˛
atku –
tracimy cenne informacje!
Przykład
ab
aaa
aaaaaaaaa
aba
aa
aaaaaaaaa
aaa
b
aa
ab
Trudne słowa
prefiks
sufiks
prefikso-sufiks
Trudne słowa
prefiks
sufiks
prefikso-sufiks
Trudne słowa
prefiks
sufiks
prefikso-sufiks
Tablica najdłu˙zszych prefikso-sufiksów – P[ ]
P[i] – długo´s´c najdłu˙zszego wła´sciwego prefikso-sufiksu
prefiksu długo´sci i słowa w
Tablica najdłu˙zszych prefikso-sufiksów – P[ ]
P[i] – długo´s´c najdłu˙zszego wła´sciwego prefikso-sufiksu
prefiksu długo´sci i słowa w
słowo w
b
a
a
b
a
b
a
a
i =
0
1
2
3
4
5
6
7
8
P[i] =
0
0
0
0
1
2
1
2
3
Obliczanie P[ ]
P[ ]
0
0
1
1
2
3
słowo
a
b
a
a
b
a
b
a
a
pasuj ˛
acy prefikso-sufiks
a
b
a
Obliczanie P[ ]
P[ ]
0
0
1
1
2
3
słowo
a
b
a
a
b
a
b
a
a
pasuj ˛
acy prefikso-sufiks
a
b
a
kolejna pozycja
a
b
a
a
Obliczanie P[ ]
P[ ]
0
0
1
1
2
3
2
słowo
a
b
a
a
b
a
b
a
a
pasuj ˛
acy prefikso-sufiks
a
b
a
kolejna pozycja
a
b
a
a
a
b
Wyszukiwanie wzorca
Wzorzec i jego tablica P[ ]:
P[ ]
0
0
1
1
2
3
słowo
a
b
a
a
b
a
Wyszukiwanie wzorca:
tekst
a
a
b
a
b
a
a
b
a
a
a
Wyszukiwanie wzorca
Wzorzec i jego tablica P[ ]:
P[ ]
0
0
1
1
2
3
słowo
a
b
a
a
b
a
Wyszukiwanie wzorca:
tekst
a
a
b
a
b
a
a
b
a
a
a
a
b
Wyszukiwanie wzorca
Wzorzec i jego tablica P[ ]:
P[ ]
0
0
1
1
2
3
słowo
a
b
a
a
b
a
Wyszukiwanie wzorca:
tekst
a
a
b
a
b
a
a
b
a
a
a
a
b
Wyszukiwanie wzorca
Wzorzec i jego tablica P[ ]:
P[ ]
0
0
1
1
2
3
słowo
a
b
a
a
b
a
Wyszukiwanie wzorca:
tekst
a
a
b
a
b
a
a
b
a
a
a
a
b
a
Wyszukiwanie wzorca
Wzorzec i jego tablica P[ ]:
P[ ]
0
0
1
1
2
3
słowo
a
b
a
a
b
a
Wyszukiwanie wzorca:
tekst
a
a
b
a
b
a
a
b
a
a
a
a
b
a
Wyszukiwanie wzorca
Wzorzec i jego tablica P[ ]:
P[ ]
0
0
1
1
2
3
słowo
a
b
a
a
b
a
Wyszukiwanie wzorca:
tekst
a
a
b
a
b
a
a
b
a
a
a
a
b
a
a
Wyszukiwanie wzorca
Wzorzec i jego tablica P[ ]:
P[ ]
0
0
1
1
2
3
słowo
a
b
a
a
b
a
Wyszukiwanie wzorca:
tekst
a
a
b
a
b
a
a
b
a
a
a
a
b
Wyszukiwanie wzorca
Wzorzec i jego tablica P[ ]:
P[ ]
0
0
1
1
2
3
słowo
a
b
a
a
b
a
Wyszukiwanie wzorca:
tekst
a
a
b
a
b
a
a
b
a
a
a
a
b
a
Wyszukiwanie wzorca
Wzorzec i jego tablica P[ ]:
P[ ]
0
0
1
1
2
3
słowo
a
b
a
a
b
a
Wyszukiwanie wzorca:
tekst
a
a
b
a
b
a
a
b
a
a
a
a
b
a
a
Wyszukiwanie wzorca
Wzorzec i jego tablica P[ ]:
P[ ]
0
0
1
1
2
3
słowo
a
b
a
a
b
a
Wyszukiwanie wzorca:
tekst
a
a
b
a
b
a
a
b
a
a
a
a
b
a
a
b
Wyszukiwanie wzorca
Wzorzec i jego tablica P[ ]:
P[ ]
0
0
1
1
2
3
słowo
a
b
a
a
b
a
Wyszukiwanie wzorca:
tekst
a
a
b
a
b
a
a
b
a
a
a
a
b
a
a
b
a
Trafienie! aab
abaaba
aa
Wyszukiwanie wzorca
Wzorzec i jego tablica P[ ]:
P[ ]
0
0
1
1
2
3
słowo
a
b
a
a
b
a
Wyszukiwanie wzorca:
tekst
a
a
b
a
b
a
a
b
a
a
a
a
b
a
Trafienie! aab
abaaba
aa
Wyszukiwanie wzorca
Wzorzec i jego tablica P[ ]:
P[ ]
0
0
1
1
2
3
słowo
a
b
a
a
b
a
Wyszukiwanie wzorca:
tekst
a
a
b
a
b
a
a
b
a
a
a
a
b
a
a
Trafienie! aab
abaaba
aa
Wyszukiwanie wzorca
Wzorzec i jego tablica P[ ]:
P[ ]
0
0
1
1
2
3
słowo
a
b
a
a
b
a
Wyszukiwanie wzorca:
tekst
a
a
b
a
b
a
a
b
a
a
a
a
b
a
a
b
Trafienie! aab
abaaba
aa
Wyszukiwanie wzorca
Wzorzec i jego tablica P[ ]:
P[ ]
0
0
1
1
2
3
słowo
a
b
a
a
b
a
Wyszukiwanie wzorca:
tekst
a
a
b
a
b
a
a
b
a
a
a
a
b
Trafienie! aab
abaaba
aa
Wyszukiwanie wzorca
Wzorzec i jego tablica P[ ]:
P[ ]
0
0
1
1
2
3
słowo
a
b
a
a
b
a
Wyszukiwanie wzorca:
tekst
a
a
b
a
b
a
a
b
a
a
a
a
Trafienie! aab
abaaba
aa