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
Document Outline
Wyszukiwarka
Podobne podstrony:
algorytmy sortujace id 57762 Nieznany
Algorytmy obliczen id 57749 Nieznany
Algorytmy zadania id 51150 Nieznany (2)
3 3 BK Algorytmy parsingu id 34 Nieznany (2)
Algorytmy genetyczne 2 id 57672 Nieznany (2)
Cw1 excel f tekstowe id 122815 Nieznany
Algorytmy wyklad 1 id 57804 Nieznany
algorytmy ewolucyjne id 57660 Nieznany
Algorytm Simplex id 57544 Nieznany (2)
Algorytmy wyklad 6 7 id 57806 Nieznany
Algorytm RSA id 57542 Nieznany
Algorytmy wyklad 4 5 id 57805 Nieznany
algorytm simplex 3 id 57546 Nieznany
algorytm lvq id 57514 Nieznany (2)
ALGORYTM BANKOMATU id 57487 Nieznany (2)
algorytmy sortujace id 57762 Nieznany
Algorytmy obliczen id 57749 Nieznany
ALGORYTM id 57461 Nieznany
algorytmika id 57568 Nieznany (2)
więcej podobnych podstron