Czech Technical University in Prague Faculty of Information Technology Department of Theoretical Computer Science
´ ANI ´ AUTOMATY VE VYHLEDAV – cviˇ ceni Boˇrivoj Melichar
Evropsk´ y soci´ aln´ı fond. Praha & EU: Investujeme do vaˇs´ı budoucnosti
Obsah 1 Konečné automaty 1.1 Základní pojmy . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Převod nedeterministického konečného automatu na deterministický konečný automat . . . . . . . . . . . . . . . . . . . . 1.3 Vyloučení ε–přechod˚ u . . . . . . . . . . . . . . . . . . . . . . 1.4 Konstrukce konečného automatu pro zadaný regulární výraz .
3 3 5 13 16
2 Konstrukce vyhledávacích automatů pro sousměrné vyhledávání 22 2.1 Přesné a přibližné vyhledávání jednoho vzorku . . . . . . . . 22 2.2 Vyhledávání množiny vzorků . . . . . . . . . . . . . . . . . . 28 3 Faktorové, prefixové a sufixové 3.1 Základní pojmy . . . . . . . . 3.2 Faktorové automaty . . . . . 3.3 Sufixové automaty . . . . . .
automaty 36 . . . . . . . . . . . . . . . . . . 36 . . . . . . . . . . . . . . . . . . 36 . . . . . . . . . . . . . . . . . . 43
4 Hranice, periody a repetice 4.1 Základní pojmy . . . . . . 4.2 Hranice a periody . . . . . 4.3 Přesné repetice . . . . . . 4.4 Přibližné repetice . . . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
45 45 45 48 56
5 Simulace nedeterministických konečných automatů – fail funkce 59 5.1 KM P vyhledávací automaty . . . . . . . . . . . . . . . . . . 59 5.2 AC vyhledávací automaty . . . . . . . . . . . . . . . . . . . . 60 5.3 Přibližné vyhledávací automaty a fail funkce . . . . . . . . . . 62 6 Simulace nedeterministických konečných automatů – dynamické programování a bitový paralelismus 67 6.1 Dynamické programování . . . . . . . . . . . . . . . . . . . . 67 6.2 Bitový paralelismus . . . . . . . . . . . . . . . . . . . . . . . . 71 7 Protisměrné vyhledávání v textu – vyhledávání předpon vzorku 7.1 Sufixový automat pro reverzovaný vzorek . . . . . . . . . . . 7.2 Přesné protisměrné vyhledávání předpon vzorku v textu . . . 7.3 Sufixový automat pro přibližné protisměrné vyhledávání v textu 7.4 Přibližné protisměrné vyhledávání předpon vzorku v textu . .
80 80 81 83 84
8 Protisměrné vyhledávání v textu – vyhledávání opakujících se přípon vzorku 87 8.1 Přesné protisměrné vyhledávání jednoho vzorku . . . . . . . . 87 1
8.2
Protisměrné vyhledávání konečné množiny vzorků
. . . . . .
94
9 Indexové metody 9.1 Faktorové automaty . . . . . . . . . . . . . 9.2 Suffixový automat . . . . . . . . . . . . . . 9.3 Suffixový strom . . . . . . . . . . . . . . . . 9.4 Kompaktní suffixový strom . . . . . . . . . 9.5 Pole přípon – Suffix Array . . . . . . . . . . 9.6 Slovní indexy . . . . . . . . . . . . . . . . . 9.6.1 Uspořádané pole slov . . . . . . . . . 9.6.2 Indexový strom . . . . . . . . . . . . 9.6.3 Booleovské informační systémy . . . 9.6.4 Rozšíření dotaz˚ u v booleovském DIS 9.6.5 Vektorové informační systémy . . . . 9.7 Signatury . . . . . . . . . . . . . . . . . . . 9.7.1 Přiřazení signatury k jednomu termu 9.8 Indexace a Web . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
96 97 99 99 99 100 103 103 103 103 106 107 111 112 113
10 Statistické metody komprese dat 10.1 Základní pojmy . . . . . . . . . . 10.2 Shannon–Fanův kód . . . . . . . 10.3 Huffmanův kód . . . . . . . . . . 10.4 Aritmetické kódování . . . . . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
119 119 120 121 132
11 Slovníkové 11.1 LZ77 . 11.2 LZ78 . 11.3 LZW .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
komprese dat 134 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
12 Kontextové metody komprese dat 142 12.1 Základní pojmy . . . . . . . . . . . . . . . . . . . . . . . . . . 142 12.2 Dynamické Markovovo kódování . . . . . . . . . . . . . . . . 144 12.3 Metoda PPM . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 13 Kontrola textu
152
Literatura
153
2
1
Konečné automaty
1.1
Základní pojmy
Abecedu budeme označovat A a bude to vždy konečná množina symbolů. Definice 1.1 Deterministický konečný automat M je pětice M = (Q, A, δ, q0 , F ), kde Q je konečná množina vnitřních stav˚ u, A je konečná vstupní abeceda, δ je zobrazení z Q × A do Q, q0 ∈ Q je počáteční stav, F ⊂ Q je množina koncových stav˚ u.
2
Tuto definici m˚ užeme modifikovat a získáme tak další třídy konečných automat˚ u, které budou v dalších kapitolách užitečné. Jedná se o tyto třídy a modifikace základní definice: 1. Nedeterministický konečný automat. Modifikace se týká zobrazení δ: δ je zobrazení z Q × A do množiny podmnožin Q. 2. Konečný automat s ε–přechody. Modifikace se týká opět zobrazení δ: δ je zobrazení z Q × (A ∪ {ε}) do množiny Q. 3. Konečný automat s více počátečními stavy. Modifikace se týká definice počátečního stavu. V tomto případě je definována neprázdná množina počátečních stav˚ u I ⊂ Q. Uvedené modifikace, i když rozšiřují definici deterministického konečného automatu, nerozšiřují množinu jazyk˚ u přijímaných těmito automaty. Automaty s uvedenými rozšířeními je možné převést na ekvivalentní deterministické konečné automaty. Potřebné algoritmy jsou uvedeny v [JPR]. Všechna uvedená rozšíření je možné sloučit do jedné definice takto: Definice 1.2 Konečný automat (nedeterministický, s ε–přechody, s více počátečními stavy) je pětice M = (Q, A, δ, I, F ), kde Q je konečná množina vnitřních stav˚ u, A je konečná vstupní abeceda, δ je zobrazení z Q × (A ∪ {ε}) do množiny podmnožin Q, I ⊂ Q je množina počátečních stav˚ u, F ⊂ Q je množina koncových stav˚ u. 2 Dále připomeneme definice základních vlastností konečných automat˚ u. 3
Definice 1.3 Úplný konečný automat. Deterministický konečný automat M = (Q, A, δ, q0 , F ) nazveme úplný, když zobrazení δ(q, a) je definováno pro všechny stavy q ∈ Q a všechny vstupní symboly a ∈ A. 2 Definice 1.4 Dosažitelné stavy automatu. Necht’ je dán konečný automat M = (Q, A, δ, q0 , F ). Stav q ∈ Q nazveme dosažitelný, pokud existuje řetězec w ∈ A∗ takový, že existuje posloupnost přechod˚ u, která vede z počátečního stavu q0 do stavu q: (q0 , w) ⊢∗ (q, ε). Stav, který není dosažitelný, nazveme nedosažitelný stav.
2
Definice 1.5 Užitečné a zbytečné stavy. Necht’ je dán konečný automat M = (Q, A, δ, q0 , F ). Stav q ∈ Q nazveme užitečný, pokud existuje řetězec w ∈ A∗ takový, že existuje posloupnost přechod˚ u, která vede ze stavu q do nějakého koncového stavu: (q, w) ⊢∗ (p, ε), p ∈ F . Stav, který není užitečný, nazveme zbytečný stav. Algoritmy na 1. doplnění konečného automatu na úplný, 2. odstranění nedosažitelných stav˚ u, 3. odstranění zbytečných stav˚ u jsou uvedeny v [JPR].
Definice 1.6 Množina F act(x), x ∈ A+ , je množina všech podřetězců řetězce x: F act(x) = {y : x = uyv, u, v ∈ A∗ , x, y ∈ A+ }. Definice 1.7 Množina Sub(x), x ∈ A+ , je množina všech podposloupností řetězce x: Sub(x) = { a1 a2 . . . am : x = y0 a1 y1 a2 . . . am ym , x ∈ A+ , yi ∈ A∗ , i = 0, 1, 2, . . . , m, aj ∈ A, j = 1, 2, . . . , m, m > 0} Definice 1.8 Množina Suf (x), x ∈ A+ , je množina všech přípon řetězce x: Suf (x) = {y : x = uy, u ∈ A∗ , x, y ∈ A+ }.
4
2
Definice 1.9 Množina P ref (x), x ∈ A+ , je množina všech předpon řetězce x: P ref (x) = {y : x = yu, u ∈ A∗ , x, y ∈ A+ }.
1.2
Převod nedeterministického konečného automatu na deterministický konečný automat
Příklad 1.10 Sestrojme konečný automat, který přijímá řetězce nad abecedou {0, 1} takové, které končí řetězcem 010. Tento automat má přechodový diagram na obr. 1.1. Získaný automat je zkonstruován tak, že je v něm na začátku smyčka pro libovolný řetězec a do koncového stavu vede cesta pro řetězec 010. V tomto případě je automat nedeterministický. Tabulka přechod˚ u tohoto automatu má tvar: 0 0, 1
0 1 2 3
1 0 2
3
0
0
0
1
1
2
0
3
1
Obrázek 1.1: Přechodový diagram nedeterministického konečného automatu z příkladu 1.10 Příklad 1.11 Sestrojme deterministický konečný automat, který je ekvivalentní nedeterministickému konečnému automatu z příkladu 1.10. Tabulka přechod˚ u deterministického konečného automatu má tvar: 0 01 02 013
0 01 01 013 01
5
1 0 02 0 02
Jeho přechodový diagram je na obr. 1.2. Z tohoto příkladu je vidět, že deterministický konečný automat má stejný počet stav˚ u jako ekvivalentní nedeterministický. 2 1
0
0
0 0
1
0 02
01
013 1
1
Obrázek 1.2: Přechodový diagram deterministického konečného automatu z příkladu 1.11
Příklad 1.12 Příklad nedeterministického konečného automatu, jehož deterministický ekvivalent má exponenciální počet stav˚ u. Mějme nedeterministický konečný automat M = ({1, 2, 3}, {a, b}, δ, 1, {3}), kde δ je definováno tabulkou přechod˚ u: δ 1 2 3
a 2 3 1
b ∅ 1, 2 1, 3
Jeho přechodový diagram je na obr. 1.3. Tento automat je nedeterministický a má 3 stavy. Ekvivelentní deterministický konečný automat M ′ má 23 = 8 stav˚ u. M ′ = (Q′ , {a, b}, δ ′ , {1}, F ′ ), kde δ ′ je definováno tabulkou přechod˚ u: δ′ ∅ {1} {2} {3} {1, 2} {1, 3} {2, 3} {1, 2, 3}
a ∅ {2} {3} {1} {2, 3} {1, 2} {1, 3} {1, 2, 3}
b ∅ ∅ {1, 2} {1, 3} {1, 2} {1, 3} {1, 2, 3} {1, 2, 3}
kde F ′ obsahuje stavy {1, 3}, {2, 3}, {1, 2, 3} a {3}. Jeho přechodový diagram je na obr. 1.4 Z tohoto příkladu je vidět, že determinizace konečného automatu m˚ uže mít exponenciální složitost jak časovou tak pamět’ovou, 2
6
Je známo, že počet stav˚ u deterministického konečného automatu, který je ekvivalentní zadanému nedeterministickému konečnému automatu je 2n , kde n je počet stav˚ u zadaného automatu. To je dáno tím, že při obecné konstrukci se nejprve pro množinu stav˚ u Q zadaného automatu vytvoří potenční množina P(Q), jejíž prvky, podmnožiny množiny Q, jsou stavy konstruovaného deterministického konečného automatu. Mohutnost této množiny je právě 2n . V praktických aplikacích se pak často zjistí, že mnoho stav˚ u takto vzniklých je nedosažitelných a množina stav˚ u deterministického konečného automatu má menší mohutnost. Proto byl sestrojen algoritmus, který vytváří jen dosažitelné stavy.
b START
b
a
1
2
b a
b
a 3 b
Obrázek 1.3: Nedeterministický konečný automat z příkladu 1.12 Příklad 1.13 Mějme nedeterministický konečný automat M = ({1, 2, 3, 4}, {a, b}, δ, 1, {4}), kde δ je definováno tabulkou přechod˚ u: δ 1 2 3 4
a 1, 2 ∅ ∅ ∅
b 1 3 4 ∅
Tento automat je nedeterministický a má 4 stavy. Ekvivalentní deterministický konečný automat má 4 dosažitelné stavy. M ′ = (Q′ , {a, b}, δ ′ , {1}, F ′ ), kde δ ′ je definováno tabulkou přechod˚ u: δ′ {1} {1, 2} {1, 3} {1, 4}
a {1, 2} {1, 2} {1, 2} {1, 2} 7
b {1} {1, 3} {1, 4} {1}
a START
a
{1}
a
{2}
b
{3}
b
b b
0
a
b
{1,2}
a
a
a
b
{1,3}
a
b
{1,2,3}
b
Obrázek 1.4: Deterministický konečný automat z příkladu 1.12 2 Z uvedených příklad˚ u je vidět, že determinizace konečného automatu m˚ uže mít na jedné straně lineární složitost a na druhé straně exponenciální složitost. Mezi těmito krajními variantami je veliký rozdíl. Proto je účelné definovat třídy automat˚ u, pro které složitost determinizace je v intervalu n , kde n je počet stav˚ u nedeterministického konečného automatu. Tyto třídy automat˚ u se nazývají: 1. homogenní automaty (HKA), 2. zobecněné homogenní automaty (ZHKA), 3. semihomogenní automaty (SKA). Uvedené množiny konečných automat˚ u jsou nekonečné a tvoří hierarchii podle obr. 1.5.
HKA
SKA
ZHKA
KA
Obrázek 1.5: Hierarchie konečných automat˚ u vzhledem ke složitosti determinizace
8
Příklad 1.14 Je dán homogenní nedeterministický konečný automat M = ({p, q, r, s, t, u}, {a, b}, δ, p, {r, u}), kde zobrazení δ je zadáno tabulkou přechod˚ u: p q r s t u
a b q s r u q, r s, t q u r s t
Přechodový diagram je na obr. 1.6. V tomto případě platí:
a a a
q
b
r
a START
b
a
p
b
a
u
b
b b
s
t b
Obrázek 1.6: Nedeterministický konečný automat z příkladu 1.14 Q(a) = {q, r}, Q(b) = {s, t, u}. Tyto množiny mají prázdný pr˚ unik, a proto deterministický konečný automat M = (Q′ , T, δ ′ , q0 , F ′ ) bude mít počet stav˚ u menší nebo roven než 2|Q(a)| + 2|Q(b)| − |T | + 1 = 22 + 23 − 2 + 1 = 4 + 8 − 2 + 1 = 11. Ekvivalentní deterministický konečný automat je M ′ = ({p, q, qr, s, t, st, stu, u, su, t, tu}, {a, b}, δ, p, {r, qr, u, su, tu, stu}), kde δ je definováno následující tabulkou přechod˚ u:
9
p q s qr st u stu su t tu r
a b q s r u q u qr stu qr su t qr stu q tu r s r st qr st
Z výsledku je vidět, že výsledný deterministický konečný automat má právě 11 stav˚ u. 2 Pojem homogenních automat˚ u je možno zobecnit. Jedno z možných zobecnění vede na situaci, kdy do určité množiny stav˚ u vedou přechody jen pro určité symboly. Jestliže množiny Q(a), a ∈ T , nejsou po dvou disjunktní, m˚ užeme se pokusit najít množiny symbol˚ u, pro které vedou přechody jen do určité podmnožiny stav˚ u. Jinými slovy se jedná o případ nalezení jiného rozkladu množiny stav˚ u, který není tak jemný jako pro homogenní automaty, ale každá množina v tomto rozkladu odpovídá určité množině vstupních symbol˚ u, a tyto množiny jsou po dvou disjunktní. Příklad 1.15 Je dán zobecněný homogenní nedeterministický konečný automat M = ({p, q, r, s}, {a, b, c, d}, δ, p, {q, s}), kde zobrazení δ je zadáno tabulkou přechod˚ u: a
b c d p p, q r, s q p s r q r s Přechodový diagram tohoto automatu je na obr. 1.7. V tomto případě platí: Q({a, b}) = {p, q}, Q({c, d}) = {r, s}. Tyto množiny mají prázdné pr˚ uniky a proto deterministický konečný automat bude mít počet stav˚ u menší nebo roven 2|Q({a,b})| + 2|Q({c,d})| − 2 + 1 = 22 + 22 − 2 + 1 = 4 + 4 − 2 + 1 = 7. 10
b
q
a b
START
p
b c
d
r
d
d s
Obrázek 1.7: Nedeterministický konečný automat z příkladu 1.15 Skutečný automat bude mít jen 6 stav˚ u, protože počáteční stav p ∈ δ(q, a). Ekvivalentní deterministický konečný automat je M ′ = ({p, q, pq, r, s, rs}, {a, b, c, d}, δ, p, {q, pq, s, rs}), kde zobrazení δ je definováno následující tabulkou přechod˚ u: a
b c d p pq rs q p s pq p pq rs r q r s rs q r Přechodový diagram tohoto automatu je na obr. 1.8.
2
a b a
pq
q
b START
d
p
d
b
d b rs
s
r
c
c
Obrázek 1.8: Deterministický konečný automat z příkladu 1.15 11
Příklad 1.16 Necht’ je dán nedeterministický konečný automat M = ({p, q, r, s}, {a, b, c, d}, δ, p, {s}), kde zobrazení δ je dáno tabulkou přechod˚ u: a b c d p q p, q q r r r r p r, s s s r Jeho přechodový diagram je na obr. 1.9. V tomto případě je počáteční pokrytí: Q(a)={p, q, r}, Q(b)={p, q, r}, Q(c)={r, s}, Q(d)={s}. Toto pokrytí není optimální a po vynechání Q(a) (je podmnožinou Q(b)) a Q(d) (je podmnožinou Q(c)) dostaneme optimální pokrytí: C(Q) = ({p, q, r}, {r, s}). Počet stav˚ u deterministického konečného automatu bude: |Q′ | ≤ 2|Q(b)| + 2|Q(c)| − 2 − 2|Q(b)∩Q(c)| + 1 + 1 = 23 + 22 − 2 − 21 + 1 + 1 = 8 + 4 − 2 − 2 + 1 + 1 = 10 Skutečný deterministický automat bude mít nejvýše 9 stav˚ u, protože stav p ∈ Q(b). Deterministický konečný automat je M ′ = ({p, q, pq, pr, qr, pqr, r, s, rs}, {a, b, c, d}, δ, p, {s, rs}), kde zobrazení δ je dáno tabulkou přechod˚ u: p q pq pr qr pqr r s rs
a q r qr pq pr pqr p
b pq r pqr pq r pqr
p
c
d
r r rs rs rs rs r rs
s s s s s 2
12
a
b
c c
b START
a
p
b
q
d c
r
s
c
a
Obrázek 1.9: Nedeterministický konečný automat z příkladu 1.16
1.3
Vyloučení ε–přechod˚ u
Příklad 1.17 Je dán konečný automat M = ({1, 2, 3, 4, 5, 6, 7}, {a, b}, δ, 1, {4, 7}), kde zobrazení δ je zadáno tabulkou přechod˚ u: a b ε 1 2 5 2 5 3 6 3 4 6 7 4 5 6 6 7 7 Přechodový diagram tohoto automatu je na obr. 1.10. START
a
b
a
a
b b
a
Obrázek 1.10: Přechodový diagram konečného automatu s ε–přechody z příkladu 1.17 Provedeme odstranění ε–přechod˚ u. ε − CLOSU RE(1) = {1, 5}, ε − CLOSU RE(2) = {2, 6}, ε − CLOSU RE(3) = {3, 7}, ε − CLOSU RE(4) = {4}, ε − CLOSU RE(5) = {5}, 13
ε − CLOSU RE(6) = {6}, ε − CLOSU RE(7) = {7}, Výsledný konečný automat bez ε–přechod˚ u ′ ′ M = ({1, 2, 3, 4, 5, 6, 7}, {a, b}, δ , 1, {3, 4, 7}) má zobrazení δ’ definováno tabulkou přechod˚ u: a 2 5, 7 4
1 2 3 4 5 6 7
b 6 3 6 6
7
Jeho přechodový diagram je na obr. 1.11. START
a
1
2
b
2
3
a
4
a
7
a a
b
b
b
5
6
Obrázek 1.11: Přechodový diagram konečného automatu z příkladu 1.17 po odstranění ε–přechod˚ u Příklad 1.18 Sestrojme konečný automat, který přijímá řetězec x = abba a všechny jeho neprázdné přípony. MSuf = ({A, B, C, D, E}, {a, b}, δ, A, {E}), kde zobrazení δ je zadáno přechodovým diagramem na obr. 1.12. START
A
a
B
b
C
b
D
a
E
Obrázek 1.12: Přechodový diagram konečného automatu z příkladu 1.18 ε–přechody odstraníme: 14
ε − CLOSU RE(A) = {A, B, C, D}, ε − CLOSU RE(X) = {X}, pro X ∈ {B, C, D, E}. Nedeterministický konečný automat po odstranění ε–přechod˚ u má přechodový diagram na obr. 1.13. Jeho deterministický ekvivalent je na obr. 1.14. 2 START
A
a
b
B
b
C
D
a
E
b b a
Obrázek 1.13: Přechodový diagram nedeterministického konečného automatu z příkladu 1.18 po odstranění ε–přechod˚ u START
A
a
b
B,E
b
C b
b
D
a
E
a
C,D
Obrázek 1.14: Deterministický konečný automat z příkladu 1.18
Příklad 1.19 Sestrojme konečný automat, který přijímá množinu posloupností Sub(abba). MSub = ({A, B, C, D, E}, {a, b}, δ, A, {B, C, D, E}), kde zobrazení δ je zadáno přechodovým diagramem na obr. 1.15. START
A
a
B
b
C
b
D
a
E
Obrázek 1.15: Přechodový diagram konečného automatu z příkladu 1.19 Tento automat obsahuje ε–přechody a v prvním kroku je odstraníme: ε − CLOSU RE(A) = {A, B, C, D, E}, ε − CLOSU RE(B) = {B, C, D, E}, ε − CLOSU RE(C) = {C, D, E}, ε − CLOSU RE(D) = {D, E}, ε − CLOSU RE(E) = {E}. Výsledný nedeterministický konečný automat má přechodový diagram na obr. 1.16. Jeho deterministický ekvivalent je na obr. 1.17. 2 15
a
b START
A
a
b
B
C
b
a
D
b
E
a b a
Obrázek 1.16: Přechodový diagram nedeterministického konečného automatu z příkladu 1.19 a START
A
a
b
B
C,D
b
b
a
D
E
a
Obrázek 1.17: Přechodový diagram deterministického konečného automatu z příkladu 1.19 Počáteční stav není koncový, protože prázdná posloupnost je triviální případ. Viz definice 1.7.
1.4
Konstrukce konečného automatu pro zadaný regulární výraz
Konečný automat m˚ užeme pro zadaný regulární výraz zkonstruovat několika zp˚ usoby. Příklad 1.20 V tomto příkladu uvedeme metodu založenou na pojmu soused˚ u. Sestrojme konečný automat pro regulární výraz V = (a + b)∗ ab(a + b)∗ . Metoda soused˚ u: ′ ∗ V = (a1 + b2 ) a3 b4 (a5 + b6 )∗ , Z = {a1 , b2 , a3 }, P = {a1 a1 , a1 b2 , a1 a3 , b2 a1 , b2 b2 , b2 a3 , a3 b4 , b4 a5 , b4 b6 , a5 a5 , a5 b6 , b6 a5 , b6 b6 }, F = {b4 , a5 , b6 }. Počáteční stav automatu bude q0 , množina koncových stav˚ u F a pro zobrazení δ platí: δ(q0 , x) obsahuje xi pro všechna xi ∈ Z taková, že xi vzniklo očíslováním x, δ(xi , y) obsahuje yj pro všechny dvojice xi yj ∈ P takové, že yj vzniklo očíslováním y.
16
Pro daný regulární výraz tedy sestrojíme konečný automat M1 = ({q0 , a1 , b2 , a3 , b4 , a5 , b6 }, {a, b}, δ, q0 , {b4 , a5 , b6 }), kde zobrazení δ je definováno následující tabulkou: δ q0 a1 b2 a3 b4 a5 b6
a {a1 , a3 } {a1 , a3 } {a1 , a3 } ∅ {a5 } {a5 } {a5 }
b {b2 } {b2 } {b2 } {b4 } {b6 } {b6 } {b6 } 2
Příklad 1.21 Další metoda konstrukce konečného automatu pro zadaný regulární výraz je založena na pojmu derivace regulárního výrazu. Regulární výraz V = (a + b)∗ ab(a + b)∗ a všechny jeho derivace derivujeme podle všech symbol˚ u abecedy. Q = {V }, Q0 = {V } dV ∗ ∗ ∗ da = (a + b) ab(a + b) + b(a + b) = V1 dV ∗ ∗ db = (a + b) ab(a + b) = V Q = {V, V1 }, Q1 = {V1 } dV1 ∗ ∗ ∗ da = (a + b) ab(a + b) + b(a + b) = V1 dV1 ∗ ∗ ∗ db = (a + b) ab(a + b) + (a + b) = V2 Q = {V, V1 , V2 }, Q2 = {V2 } dV2 ∗ ∗ ∗ ∗ da = (a + b) ab(a + b) + b(a + b) + (a + b) = V3 dV2 ∗ ∗ ∗ db = (a + b) ab(a + b) + (a + b) = V2 Q = {V, V1 , V2 , V3 }, Q3 = {V3 } dV3 ∗ ∗ ∗ ∗ da = (a + b) ab(a + b) + b(a + b) + (a + b) = V3 dV3 ∗ ∗ ∗ db = (a + b) ab(a + b) + (a + b) = V2 Q = {V, V1 , V2 , V3 }, Q4 = ∅ Množinu stav˚ u konečného automatu tvoří všechny výrazy vzniklé derivací, množina koncových stav˚ u je tvořena výrazy, jejichž hodnota obsahuje ε, a pro přechodovou funkci δ platí: dU δ( dU dx , a) = d(xa) . Pro daný regulární výraz sestrojíme konečný automat M2 = ({V, V1 , V2 , V3 }, {a, b}, δ, {V2 , V3 }), kde zobrazení δ je definováno tabulkou přechod˚ u:
17
δ V V1 V2 V3
a V1 V1 V3 V3
b V V2 V2 V2
Z této tabulky přechodů je zřejmé, že stavy V2 a V3 jsou ekvivalentní a proto můžeme provést minimalizaci. Přechodový diagram výsledného konečného automatu je na obr. 1.18. Porovnejte tento automat s automatem z příkladu 1.20! 2
b START
a a
V
a b
V1
V2V3 b
Obrázek 1.18: Deterministický konečný automat pro regulární výraz V = (a + b)∗ ab(a + b)∗ z příkladu 1.21
Příklad 1.22 Sestrojme regulární výraz, který popisuje řetězec x = abba a všechny jeho neprázdné předpony: a + ab + abb + abba = a(ε + b(ε + b(ε + a))). Sestrojme konečný automat metodou soused˚ u. ′ V =a1 (ε + b2 (ε + b3 (ε + a4 ))) Z ={a1 } P ={a1 b2 , b2 b3 , b3 a4 } F ={a1 , b2 , b3 , a4 } Výsledný konečný automat M = ({q0 , a1 , b2 , b3 , a4 }, {a, b}, δ, q0 , {a1 , b2 , b3 , b4 }), kde zobrazení δ je definováno přechodovým diagramem na obr 1.19. START
q0
a
a1
b
b2
b
b3
a
Obrázek 1.19: Konečný automat z příkladu 1.22
18
a4
Výsledný konečný automat je deterministický a minimální. Pokud bychom použili jako vstup první tvar regulárního výrazu, dostaneme nedeterministický konečný automat. Zkuste jej sestrojit! 2 Příklad 1.23 Sestrojme regulární výraz, který popisuje řetězec x = abba a všechny jeho neprázdné přípony: abba + bba + ba + a = (((a + ε)b + ε)b + ε)a. Sestrojme konečný automat metodou soused˚ u: V ′ =(((a1 + ε)b2 + ε)b3 + ε)a4 Z ={a1 , b2 , b3 , a4 } P ={a1 b2 , b2 b3 , b3 a4 } F ={a4 } Výsledný konečný automat M = ({q0 , a1 , b2 , b3 , a4 }, {a, b}, δ, q0 , {a4 }), kde zobrazení δ je zadáno přechodovým diagramem na obr. 1.20. Výsledný automat je nedeterministický. b b START
q0
a
a1
b
b2
b
b3
a
a4
a
Obrázek 1.20: Konečný automat z příkladu 1.23 Sestrojte ekvivalentní deterministický konečný automat.
2
Příklad 1.24 Sestrojme regulární výraz, který popisuje množinu F ac(abba). První zp˚ usob vychází z toho, že popisujeme předpony všech přípon: RV1 =
a(ε + b(ε + b(ε + a))) + b(ε + b(ε + a)) + b(ε + a) + a
Druhý zp˚ usob je založen na tom, že popisujeme přípony všech předpon: RV2 =
(((a + ε)b + ε)b + ε)a +((a + ε)b + ε)b +(a + ε)b +a 19
Dokažte ekvivalenci těchto dvou regulárních výraz˚ u. Sestrojíme konečný automat pro regulární výraz RV1 . Použijeme tento postup: 1. Vytvoříme konečné automaty pro jednotlivé alternativy (viz příklad 1.22). 2. S výslednými automaty provedeme sjednocení. Po prvním kroku dostaneme čtyři automaty s přechodovými diagramy na obr. 1.21. Ve druhém kroku provedeme operaci sjednocení těchto automat˚ u START
a
q 01
b
1
START
b
q 02
b
2
b
5
START
7
a
8
START
4
a
6
b
q 03
a
3
q 04
9
a
10
Obrázek 1.21: Konečný automat z příkladu 1.24
q 01
START
q0
a
1
q 02
b
b
2
5
q 03
b
b
b
3
6
8
q 04
a
a
a
a
4
7
9
10
Obrázek 1.22: Konečný automat z příkladu 1.24 po provedení operace sjednocení tak, že vytvoříme nový počáteční stav q0 a z něho povedou ε–přechody 20
do počátečních stav˚ u všech čtyř automat˚ u. Výsledný konečný automat má přechodový diagram na obr. 1.22. Po provedené minimalizaci počtu stav˚ u má konečný automat, který přijímá všechny faktory daného řetězce přechodový diagram na obr. 1.23. 2 START
a
q 01
1
b
2
b
a
3
4
Obrázek 1.23: Konečný automat z příkladu 1.23 po minimalizaci počtu stav˚ u Příklad 1.25 Sestrojme regulární výraz, který popisuje množinu Sub(abba). RV = (a + ε)(b + ε)(b + ε)(a + ε) Sestrojíme automaty M1 a M2 přijímající jazyky L1 = h(a + ε) a L2 = h(b + ε). Jejich přechodové diagramy jsou na obr. 1.24.
START
a
1
START
2
b
3
a) M1
4
b) M2
Obrázek 1.24: Automaty M1 a M2 z příkladu 1.25 Dále sestrojíme automat pro zřetězení jazyk˚ u L1 . L2 . L2 . L1 . Výsledný automat M = ({1, 2, 3, 4, 5}, {a, b}, δ, 1, {5}), kde zobrazení δ je znázorněno na obr. 1.25. 2 START
1
a
2
b
3
b
4
Obrázek 1.25: Konečný automat z příkladu 1.25
21
a
5
2 2.1
Konstrukce vyhledávacích automatů pro sousměrné vyhledávání Přesné a přibližné vyhledávání jednoho vzorku
Příklad 2.1 Sestrojme konečný automat pro přesné vyhledávání vzorku abab. Abeceda je {a, b}. Přechodový diagram nedeterministického konečného automatu je na obr. 2.1. a,b START
0
a
b
1
a
2
3
b
4
Obrázek 2.1: Nedeterministický konečný automat pro vyhledávání vzorku abab Tabulka přechodů tohoto automatu má tvar: 0 1 2 3 4
a 0, 1
b 0 2
3 4
Tabulka přechodů ekvivalentního deterministického konečného automatu má tvar: 0 01 02 013 024
a 01 01 013 01 013
Jeho přechodový diagram je na obr. 2.2.
b 0 02 0 024 0 2
Tento příklad ukazuje, že počet stavů deterministického konečného automatu je stejný jako počet stavů ekvivalentního nedeterministického konečného automatu. Toto platí pro všechny automaty pro přesné vyhledávání jednoho vzorku. Totéž platí pro automaty pro přesné vyhledávání konečného počtu vzorků.
22
b
START
a
a
0
a
b
01
a
02
b
013
024
a
b b
Obrázek 2.2: Deterministický konečný automat pro vyhledávání vzorku abab Příklad 2.2 Sestrojme konečný automat pro přibližné vyhledávání vzorku aba s Hammingovou vzdáleností k = 1. Abeceda A = {a, b}. Příklad 2.3 Sestrojme konečný automat pro přibližné vyhledávání vzorku abc s Hammingovou vzdáleností k = 2. Abeceda je A = {a, b, c, d}. Přechodový diagram nedeterministického automatu je na obr. 2.3. a,b,c,d
START
0
a
b
1 b,c,d
2
c a,b,d
a,c,d b
4
3
5
c
a,c,d
6 a,b,d
7
c
8
Obrázek 2.3: Nedeterministický konečný automat pro vyhledávání vzorku abc s Hammingovou vzdáleností k = 2 Tabulka přechodů tohoto automatu má tvar:
23
0 1 2 3 4 5 6 7 8
a 0, 1 5 6
b 0, 4 2 6
c 0, 4 5 3
d 0, 4 5 6
7 8
5 8
7 6
7 8
8
Tabulka přechodů deterministického konečného automatu má tvar: 0 01 015 0158 024 0167 0248 0347 017 045 0178 0456 0458 0467 047 0478 04
a 01 015 0158 0158 0167 015 0167 017 015 0178 015 0178 0178 017 017 017 017
b 04 024 0248 0248 0456 024 0456 045 024 0458 024 0458 0458 045 045 045 045
c 04 045 0456 0456 0347 0458 0347 0478 0458 0467 0458 0467 0467 0478 0478 0478 047
d 04 045 0458 0458 0467 045 0467 047 045 0478 045 0478 0478 047 047 047 047
Příklad 2.4 Sestrojme vyhledávací automat pro vyhledávání vzorku aba s Levenshteinovou vzdáleností k = 1. Abeceda A = {a, b}. Přechodový diagram nedeterministického automatu je na obr. 2.4. Po vyloučení ε–přechodů dostaneme konečný automat na obr. 2.5. Tabulka přechodů tohoto automatu má tvar:
24
a,b START
0
a
b
1 b
a
a,b
3 b
a,b
b
4
a
2
a
5
6
Obrázek 2.4: Nedeterministický konečný automat pro vyhledávání vzorku aba Levenshteinovou vzdáleností 1 a,b START
0
a
b
1 a,b
b
b
a,b
a b
4
a
2
5
a
3
b a
6
Obrázek 2.5: Nedeterministický konečný automat z příkladu 2.4 po vynechání ε–přechodů
0 1 2 3 4 5 6
a 0, 1 4, 5, 6 5, 3 ∅ ∅ 6 ∅
b 0, 4, 5 4, 2 5, 6 ∅ 5 ∅ ∅
Tabulka přechodů deterministického konečného automatu má tvar: 0 01 0245 01356 045 0456 0156 01456
a 01 01456 01356 01456 0156 0156 01456 01456 25
b 045 0245 0456 02456 045 045 02456 02456
Přechodový diagram tohoto automatu je na obr. 2.6. b START
a
0
b
01
a
0245
b
a
01356
a
a 01456 b
b
a
b
0156 a
a b
045
0456
b
Obrázek 2.6: Přechodový diagram deterministického konečného automatu z příkladu 2.4 Příklad 2.5 Sestrojme vyhledávací automat pro vyhledávání vzorku aba s rozšířenou Levenshteinovou vzdáleností k = 1. Abeceda je A = {a, b}. Přechodový diagram nedeterministického automatu je na obr. 2.7. Po odstranění ε– a,b START
0
a
b
1
b
a
a,b 7
a
2
3
a,b 8 b
a
b
a b
4
b
5
a
6
Obrázek 2.7: Nedeterministický konečný automat z příkladu 2.5 přechodů bude mít tento automat přechodový diagram podle obr. 2.8.
26
a,b START
a
0
b
1
b
a
a,b 7
a
2
3
a,b 8
b
a
b
a
b
4
b
a
b
5
a
6
Obrázek 2.8: Nedeterministický konečný automat po odstranění ε–přechodů Tabulka přechodů tohoto automatu má tvar: 0 1 2 3 4 5 6 7 8
a 0, 1 4, 5, 6, 8 3, 5
b 0, 4, 5, 7 2, 4 5, 6 5
6 5 6
Tabulka přechodů deterministického konečného automatu má tvar: 0 01 02457 01356 04567 0457 014568 0156 024567
a 01 014568 01356 014568 0156 0156 014568 014568 01356
b 0457 02457 04567 02457 0457 0457 024567 02457 04567
Přechodový diagram tohoto automatu je na obr. 2.9.
27
2
b START
0
a
b
01
a
b
0457
01356
b
b 014568
a b
a
02457
b
a 04567
b a
a 0156
b a
024567
Obrázek 2.9: Deterministický konečný automat z příkladu 2.5
2.2
Vyhledávání množiny vzorků
Příklad 2.6 Sestrojme vyhledávací automat, který vyhledává všechny neprázdné podřetězce vzorku abab. Přechodový diagram nedeterministického automatu M1 je na obr. 2.10. Po vyloučení ε–přechodů bude mít přechodový diagram a,b
START
a
b
a
b
b
a
b
a
b
b
Obrázek 2.10: Nedeterministický konečný automat M1 z příkladu 2.6 automatu M2 tvar podle obr. 2.11.
28
a,b START
0
a
1
b
2
b
5
a
a
a
3
6
8
b
b
b
b
4
7
9
X
Obrázek 2.11: Nedeterministický konečný automat M2 z příkladu 2.6 po vyloučení ε–přechodů Tabulka přechodů automatu M2 má tvar: 0 1 2 3 4 5 6 7 8 9 X
a 0, 1, 8
b 0, 5, X 2
3 4 6 7 9
Tabulka přechodů ekvivalentního deterministického konečného automatu M3 má tvar:
29
a 018 018 01368 018 01368 0168 018 01368
0 018 0259X 01368 024579X 05X 0168 02579X
b 05X 0259X 05X 024579X 05X 05X 02579X 05X
Přechodový diagram deterministického konečného automatu M3 je uveden na obr. 2.12. Všechny stavy kromě počátečního jsou koncové stavy. Tento a a START
a
0
b
018
0259X b
a b
0168
a
a 01368
a
b
024579X b
02579X
b b
a 05X b
Obrázek 2.12: Deterministický konečný automat M3 z příkladu 2.6 automat vyhledává tuto množinu řetězců: L(M3 ) = {abab, bab, ab, b, aba, a, ba}. Automat je homogenní automat, protože množinu stavů Q můžeme rozložit na množiny: Q(a) = {018, 01368, 0168}, Q(b) = {0259X, 024579X, 02579X, 05X}. 2 Příklad 2.7 Sestrojme konečný automat pro vyhledávání množiny vzorků P = {kajak, jak, kaj, aja, ja}. Přechodový diagram nedeterministického konečného automatu M1 je na obr. 2.13. Tabulka přechodů automatu M1 má tvar:
30
a,j,k,x START
0
k
j
k
a
j
a
1
a
6
a
9
j
C
a
F
j
2
k
7
j
A
a
D
a
3
4
k
5
8
B
E
G
Obrázek 2.13: Přechodový diagram nedeterministického konečného automatu M1 z příkladu 2.7
0 1 2 3 4 5 6 7 8 9 A B C D E F G
a 0, C 2
j 0, 6, F
k 0, 1, 9
x 0
3 4 5 7 8 A B D E G
Tabulka přechodů deterministického automatu M2 má tvar:
31
a 0C 02AC 0C 047CEG 0C 02AC 07CG 07CEG 0C 0C 0C 02AC
0 019 02AC 036BDF 047CEG 01589 06F 06DF 07CG 07ECG 0C 0189
j 06F 06F 036BDF 06F 06DF 06F 06F 06F 06DF 06DF 06DF 06F
k 019 019 019 019 01589 019 019 019 0189 0189 019 019
x 0 0 0 0 0 0 0 0 0 0 0 0
Přechodový diagram konečného automatu M2 je na obr. 2.14. x
k
k
a
k k START
0
019 a
k
036BDF a
02AC i
j
j j k a 06F
a
a
07CG
047CEG
k
01589
j
a
k k
0189
j j j
a k 0C a
j
j
06DF a
j a
k 07CEG
j a
k
Obrázek 2.14: Konečný automat M2 z příkladu 2.7 Příklad 2.8 Sestrojme vyhledávací automat pro tuto kombinovanou úlohu: Je dána množina vzorků P = {aba, aab} a vyhledávání má být provedeno přibližně s Hammingovou vzdáleností k = 1. Tento automat můžeme sestrojit tímto způsobem: Sestrojíme vyhledávací automat pro každý vzorek a pak provedeme sjednocení těchto automatů. Vyhledávací automat M1 po sjednocení bude mít 32
1
a
a,b
START
b
2
a
3
b
a
b b
A
4
a
B
C
0
5
a
a
6
b
7
a
b
b a
D
8
b
E
F
Obrázek 2.15: Vyhledávací automat M1 z příkladu 2.8 přechodový diagram na obr. 2.15. Po vyloučení ε–přechodů bude mít automat M2 přechodový diagram podle obr. 2.16. Tabulka přechodů automatu
2 a,b
0
3
a
a
a b
START
b
A
b
4 b
B
a
C
a b
6
a
7
b
b D
a
8 a
E
b
Obrázek 2.16: Vyhledávací automat M2 z příkladu 2.8 M2 má tvar:
33
F
0 2 3 4 A B C 6 7 8 D E F
a 0, 2, 6 B 4
b 0, A, D 3 C B
C 7 F
E 8
E F
Tabulka přechodů deterministického automatu M3 bude mít tvar: 0 026 0267B 03ADE 0267BCF 0246E 038ADE 0AD 0ABD 026E 03ADEF 0ABCDF 026CE
a 026 0267B 0267BCF 0246E 0267BCF 0267B 0246E 026E 026CE 0267B 0246E 026CE 0267B
b 0AD 03ADE 038ADE 0ABCDF 038ADE 03ADEF 0ABCDF 0ABD 0ABD 03ADEF 0ABCDF 0ABD 03ADEF
Přechodový diagram automatu M3 je na obr. 2.17.
34
a 0267BCF
a 0267B a 026
b
038ADE a
a
b
b 0246E
a 03ADE
a START
a
b
b
a
b 0ABCDF b
0 0267B
a b
026E a 0AD
b
a 03ADEF b
b
b a
a 0ABD
026CE
b
b
Obrázek 2.17: Deterministický vyhledávací automat M3 z příkladu 2.8
35
3
Faktorové, prefixové a sufixové automaty
3.1
Základní pojmy
Je–li text T = xyz, pak x, y, z jsou faktory textu T . Řetězec x je prefix a řetězec z je sufix textu T . Je–li x faktor (prefix, sufix) textu T , pak každý řetězec y takový, že D(x, y) ≤ k, je k–přibližný faktor (prefix, sufix) textu T . Vzdálenost D může být definována jako Hammingova, Levenshteinova, zobecněná Levenshteinova, Iliopoulosova a zobecněná Iliopoulosova. Faktorový (prefixový, sufixový) automat je konečný automat, který přijímá všechny faktory daného textu. Přibližný faktorový (prefixový, sufixový) automat je konečný automat, který přijímá přibližné faktory (prefixy, sufixy) daného textu.
3.2
Faktorové automaty
Příklad 3.1 Sestrojme faktorový automat pro text T = abbcbbd. Konstrukci automatu F ac(T ) provedeme ve čtyřech krocích a použijeme metodu založenou na ε–přechodech. 1. Vytvoříme automat M1 , který přijímá všechny předpony textu T . Jeho přechodový diagram je na obr. 3.1.
START
0
a
1
b
2
b
3
c
4
b
5
b
6
d
7
Obrázek 3.1: Konečný automat M1 , který přijímá všechny předpony textu T = abbcbbd 2. Do automatu M1 přidáme ε–přechody z počátečního stavu do všech stavů kromě posledního. Výsledkem je automat M2 , jehož přechodový diagram je na obr. 3.2.
START
0
a
1
b
2
b
3
c
4
b
5
b
6
d
7
Obrázek 3.2: Konečný automat M2 s ε–přechody, který přijímá všechny faktory textu T = abbcbbd
36
3. Z automatu M2 odstraníme ε–přechody a dostaneme automat M3 , jehož přechodový diagram je na obr. 3.3. Všimněme si, že tento automat je nedeterministický.
b
START
0
a
b
1
b
b
2
c
c
3
4
b
b
b
b
5
d
d
6
7
Obrázek 3.3: Nedeterministický konečný automat, který přijímá všechny faktory textu T = abbcbbd 4. Nedeterministický automat M3 převedeme na deterministický automat M4 . Tabulky přechodů automatů M3 a M4 mají tvar: a 1
0 1 2 3 4 5 6 7
b 2, 3, 5, 6 2 3
c 4
d 7
a 1
0 1 2 2356 3 36 4 5 6 7
4 5 6 7
b 2356 2 3 36
c 4
d 7
4 4 4
7 7
5 6 7
Přechodový diagram automatu M4 je na obr. 3.4.
d
START
c
0
a
1
b
2
b
c
3
4
c b
2356
b
b
b
5
6
d
7
d c
d
36
Obrázek 3.4: Deterministický faktorový automat, pro text T = abbcbbd
37
a
1
b
2
b
START
START
START
START
START
START
0
3
c
START
Příklad 3.2 Sestrojme faktorový automat pro stejný text T = abbcbbd jako v příkladu 3.1. V tomto případě použijeme postup založený na konečném automatu s více počátečními stavy. Vyjdeme z automatu M1 , jehož přechodový diagram je na obr. 3.1. Tento automat upravíme tak, že počáteční stavy budou všechny stavy kromě posledního. Přechodový diagram automatu M5 je na obr. 3.5.
b
4
5
b
6
d
7
Obrázek 3.5: Konečný automat M5 se sedmi počátečními stavy, který přijímá všechny faktory textu T = abbcbbd Automat M5 převedeme na deterministický konečný automat M6 s jedním počátečním stavem. Tabulka přechodů automatu M6 má tvar:
0123456 1 2 2356 3 36 4 5 6 7
a 1
b 2356 2 3 36
c 4
d 7
4 4 4
7 7
5 6 7
Při srovnání tabulky přechodů automatu M6 a tabulky přechodů automatu M4 je zřejmé, že až na označení počátečního stavu jsou stejné. Přechodový diagram automatu M6 je na obr. 3.4. Příklad 3.3 Sestrojme faktorový automat pro stejný text T = abbcbbd jako v příkladu 3.1. V tomto případě použijeme postup založený na pojmu množiny faktorů pomocí regulárního výrazu. Regulární výraz, který popisuje množinu F ac(T ) má tvar:
38
RV = a (ε + b(ε + b(ε + c(ε + b(ε + b(ε + d )))))) + b(ε + b(ε + c(ε + b(ε + b(ε + d ))))) + b(ε + c(ε + b(ε + b(ε + d )))) + c(ε + b(ε + b(ε + d ))) + b(ε + b(ε + d )) + b(ε + d ) + d Nejdříve vytvoříme automaty pro jednotlivé alternativy. Tyto automaty mají přechodové diagramy na obr. 3.6. Dále provedeme sjednocení všech
START
0
a
START
1
11
b
b
START
2
b
3
c
4
b
5
b
6
d
7
21
b
31
c
41
b
51
b
61
d
71
22
b
32
c
42
b
52
b
62
d
72
33
c
43
b
53
b
63
d
73
44
b
54
b
64
d
74
55
b
65
d
75
66
d
76
START
START
START
START
Obrázek 3.6: Konečné automaty pro jednotlivé alternativy regulárního výrazu z příkladu 3.3 těchto automatů. K tomu je třeba všechny automaty doplnit na úplné automaty. Toto doplnění provedeme tak, že vytvoříme nulový stav. Do všech automatů přidáme přechody ze všech stavů do nulového stavu pro všechny symboly, pro které přechody dosud neexistují. Nulový stav je uveden na obr. 3.7. Výsledný automat M po provedeném sjednocení všech automatů je uveden na obr. 3.8. Pro přehlednost neuvádíme v označení stavů nulový stav. Pokud v označení stavu chybí stav některého z automatů, je tímto stavem nulový stav. Konečný automat M můžeme minimalizovat. Ekvivalentní množiny stavů jsou {4, 41 , 42 , 43 }, {5, 51 , 52 , 53 }, {6, 61 , 62 , 63 }, {7, 71 , 72 , 73 , 74 , 75 , 76 }. 39
a
b
c
a
d d
0 b
c
Obrázek 3.7: Nulový stav z příkladu 3.3
c
START
X
a
1 b
b
b
2
21325465
b
3 3164
c c
c
43
4 41
42
b
b b
b
53
5 51
52
b
b b
b
63
6 61
62
d
73
d
76
d
7
d
71
d
74
d
72
d
75
Obrázek 3.8: Konečný automat M po sjednocení automatů z obr. 3.6, počáteční stav X = 011 22 33 44 55 66 Po provedení této minimalizace dostaneme automat na obr. 3.4. Příklad 3.4 Sestrojme přibližný faktorový automat pro text T = abbc pro Hammingovu vzdálenost k = 1. V tomto případě použijeme postup, který je použit v příkladu 3.1. V prvním kroku sestrojíme automat M1 , který přijímá všechny přesné a přibližné předpony textu T . Jeho přechodový diagram je na obr. 3.9. Ve druhém kroku přidáme ε přechody z počátečního stavu do stavů 1,2,3. Výsledkem je konečný automat M2 , jehož přechodový diagram je na obr. 3.10. Tento automat přijímá všechny přesné a přibližné faktory textu T = abbc. Ve třetím kroku odstraníme z automatu M2 ε–přechody a dostaneme nedeterministický automat M3 , jehož přechodový diagram je na obr. 3.11. Ve čtvrtém a posledním kroku převedeme nedeterministický automat M3 na ekvivalentní deterministický automat M4 . Tabulky přechodů automatů M3 a M4 mají tvar: 40
START 0
a
1
b
b,c
2
b
a,c
11
b
3
c
a,c
21
b
4 a,b
31
c
41
Obrázek 3.9: Konečný automat M1 , který přijímá všechny přesné a přibližné předpony textu T = abbc, Hammingova vzdálenost k = 1
START 0
a
1
b
b,c
2
b
a,c
11
b
3
c
a,c
21
b
4 a,b
31
c
41
Obrázek 3.10: Konečný automat M2 s ε–přechody, který přijímá všechny přesné a přibližné faktory textu T = abbc, Hammingova vzdálenost k = 1
b
START 0
a
1 b,c 11
b
b
2 a,c
b
21 a,c
c
b
3
c
a,c b
31 a,c
4 a,b
c
41 a,b
Obrázek 3.11: Nedeterministický konečný automat M3 , který přijímá přesné a přibližné faktory textu T = abbc, Hammingova vzdálenost k = 1
41
a 0 1 2 3 4 11 21 31 41
121 31 41 21 31 41
b c 1 1 1 231 4 41 21 31 2 21 3 31 1 4 4
a 0 121 31 41 2311 41 411 21 31 231 321 41 431 4 21 21 41 31 41 21 31 3 31 41
21 31 41
b c 1 1 1 231 4 41 21 31 231 21 41 321 41 431 1 1 2 3 41 3 31 41 1 1 3 4 4 41
121 31 41 21 31 41 31 41
31 31 41 41 4 41
31 41
41
Přechodový diagram deterministického konečného automatu M4 je na obr. 3.12.
c b
231 1 4 1
a b START 0
43 1
34
a
1
1
12 3 4
c c
1
c
c b 23 1 a
a
2141 b
b
1
a
32 1 4 1 b 1
c
3
a,b
21
b 1
23
4
31
b c
c
c
1
c
b c
41 1 2 1 3 1
41
Obrázek 3.12: Deterministický přibližný faktorový automat M4 , pro text T = abbc, Hammingova vzdálenost k = 1
42
3.3
Sufixové automaty
Příklad 3.5 Sestrojme sufixový automat pro text T = ababa. Konstrukci automatu provedeme na čtyřech krocích. 1. Vytvoříme automat M1 , který přijímá text T . Jeho přechodový diagram je na obr. 3.13.
START 0
a
1
b
2
a
3
b
4
a
5
Obrázek 3.13: Konečný automat M1 , který přijímá text T = ababa 2. Do automatu M1 přidáme ε–přechody z počátečního stavu do všech stavů kromě posledního. Výsledkem je automat M2 , jehož přechodový diagram je na obr. 3.14. Tento automat přijímá všechny přípony textu T = ababa.
START 0
a
1
b
2
a
3
b
4
a
5
Obrázek 3.14: Konečný automat M2 , který přijímá všechny přípony textu T = ababa 3. Z automatu M2 odstraníme ε–přechody. Výsledkem je nedeterministický automat M3 , jehož přechodový diagram je na obr. 3.15.
b START 0
a
1
b
2
a a
3
b b
4
a a
5
Obrázek 3.15: Konečný automat M3 bez ε–přechodů, který přijímá všechny přípony textu T = ababa 4. Posledním krokem je vytvoření deterministického konečného sufixového automatu M4 , který je ekvivalentní automatu M3 . Přechodové tabulky automatů M3 a M4 mají tvar uvedený na obr. 3.16. Přechodový diagram automatu M4 je na obr. 3.17. 43
a b 0 135 24 1 2 2 3 3 4 4 5 5 a)
a b 0 135 24 135 24 24 35 35 4 4 5 b)
Obrázek 3.16: Přechodové tabulky automatů a) M3 a b) M4 z příkladu 3.5
b START 0
a
135
b
24
a
35
b
4
a
5
Obrázek 3.17: Sufixový automat M4 , který přijímá všechny přípony textu T = ababa, Suf (ababa) = {a, ba, aba, baba, ababa}
44
4 4.1
Hranice, periody a repetice Základní pojmy
Hranice řetězce x ∈ A+ je každá neprázdná předpona řetězce x, která je současně jeho příponou. Množina všech hranic řetězce x je bord(x) = P ref (x) ∩ Suf (x). Mezi hranicemi řetězce x má zvláštní místo nejdelší hranice Border(x). Libovolný řetězec x ∈ A+ můžeme zapsat ve tvaru: x = ur v, kde v ∈ P ref (u). Délku řetězce u, p = |u|, budeme nazývat periodou řetězce x, r je exponent řetězce x a u je generátor x. Mezi periodami řetězce x má zvláštní místo nejkratší perioda Per(x). Každý řetězec x můžeme zapsat v normálním tvaru: x = ur v, kde p = |u| je nejkratší perioda (Per(x)), r je tudíž největší exponent a v ∈ Pref(u). Řetězec x, jehož nejkratší perioda má délku celého řetězce p = |x|, se nazývá primitivní řetězec. Pole hranic β[1..n] je vektor nejdelších hranic všech neprázdných předpon x[1..i] řetězce x pro i = 1, 2, . . . , n.
4.2
Hranice a periody
Příklad 4.1 Najděme všechny hranice řetězce x = abaabaab. K tomu, abychom našli všechny hranice řetězce x, sestrojíme sufixový automat pro řetězec x. Nedeterministický sufixový automat je na obr. 4.1.
b
START
0
a
1
b
a 2
a
a 3
a
b 4
b
a 5
a
a 6
a
b 7
b
8
Obrázek 4.1: Nedeterministický sufixový automat pro řetězec x = abaabaab z příkladu 4.1 Tabulky přechodů nedeterministického a deterministického sufixového automatu mají tvar:
45
0 1 2 3 4 5 6 7 8
a 1, 3, 4, 6, 7
b 2, 5, 8 2
0 13467 258 36 47 58 6 7 8
3 4 5 6 7 8
a 13467 47 36 47
b 258 258
58 6 7 8
Přechodový diagram deterministického konečného sufixového automatu je na obr. 4.2.
Obrázek 4.2: Deterministický sufixový automat pro řetězec x = abaabaab z příkladu 4.1 Analýzou tohoto automatu a zejména jeho koncových stavů zjistíme, že bord(x) = {ab, abaab}. Nejdelší hranice je Border(u) = abaab. Všimněme si, že tato hranice se v řetězci x překrývá. 2 Příklad 4.2 Najděme všechny hranice řetězce x = an . bord(x) = {a, a2 , . . . , an }. Všimněme si, že pro i ≥ (n + 1)/2 se hranice ai , ai+1 , . . . , an překrývají Border(x) = a. 2 Příklad 4.3 Najděme periody řetězce x = abaabaab. Řetězec x můžeme zapsat takto: x = (aba)2 ab. Z toho plyne, že periody jsou p1 = 3, p2 = 6, exponenty jsou r1 = 2, r2 = 1 a generátory jsou u1 = aba a u2 = abaaba. 2 Příklad 4.4 Najděme periody řetězce x = an . Řetězec x můžeme zapsat těmito způsoby: x = an x = (a2 )n/2 , když n je sudé, x = (a2 )n−1/2 a, když n je liché, .. . x = an−1 a Periody řetězce x tedy jsou: p = 1, 2, . . . , n. Nejkratší perioda p = 1. 46
2
Příklad 4.5 Najděme periody řetězce x = aaabaabab. Zjistíme, že perioda tohoto řetězce p = 9 = |u|, což znamená, že řetězec x je primitivní. 2 Příklad 4.6 Je zadán řetězec f6 = abaababaabaab (Fibonnaciho řetězec f6 ). Vytvořme pole předpon β[1 . . . 13] pro tento řetězec. Nejdříve sestrojíme pro řetězec f6 nedeterministický faktorový automat. Pak sestrojíme tu část deterministického faktorového automatu, ve které se vyskytují stavy složené z více než jednoho stavu nedeterministického automatu. Výsledek je na obr. 4.3. a
START
0
a
134689BC
b
257AD
a
368B
a
49C
b
5AD
b
a
6B
b
7
b
Obrázek 4.3: Část deterministického faktorového automatu pro řetězec f6 z příkladu 4.6, symboly A,B,C,D představují čísla 10,11,12,13 Analýzou množin stavů, které tvoří stavy deterministického automatu, směrem zprava doleva nalezneme hodnotu jednotlivých prvků pole přípon β. Celý postup je uveden v následující tabulce (písmena A,B,C,D v označení stavů znamenají pozice 10,11,12,13 v řetězci f6 ): Analyzovaný stav Hodnoty prvků pole hranic 6B β[11] = 6 5AD β[10] = 5, β[13] = 5 49C β[9] = 4, β[12] = 4 368B β[6] = 3, β[8] = 3 β[11] je už definováno 257AD β[5] = 2, β[7] = 2 β[10] a β[13] je už definováno 134689BC β[3] = 1, β[4] = 1 ostatní hodnoty jsou již definovány Výsledné pole přípon β je uvedeno v následující tabulce: Pořadí 1 2 3 4 5 6 7 8 9 10 11 12 13 Symbol a b a a b a b a a b a a b β 0 0 1 1 2 3 2 3 4 5 6 4 5 Na pozicích 1 a 2 jsou nuly, protože řetězce a a ab mají hranice délky 0.
47
4.3
Přesné repetice
Příklad 4.7 Najděme repetice v řetězci x = abcaabc. Nedeterministický faktorový automat pro x má přechodový diagram uvedený na obr. 4.4.
b
START
0
a
1
b
c 2
c
a 3
a
a 4
a
b 5
b
c 6
c
7
Obrázek 4.4: Nedeterministický faktorový automat pro x = abcaabc Přechodové tabulky nedeterministického a deterministického faktorového automatu mají tvar: a b c 0 1, 4, 5 2, 6 3, 7 1 2 2 3 3 4 4 5 5 6 6 7 7
a b c 0 145 26 37 145 5 26 26 37 37 4 4 5 5 6 6 7 7
Přechodový diagram deterministického faktorového automatu je uveden na obr. 4.5. Redukovaná tabulka repetic má tvar:
b
START
0
a
145
b
a 26
c
37
a
4
a
5
b
6
c
c Obrázek 4.5: Deterministický faktorový automat pro x = abcaabc D-subset Faktor První výstyt Repetice 145 a 1 (4, G), (5, G) 26 ab 2 (6, G) 37 abc 3 (7, G) 48
7
Z této tabulky je vidět, že všechny repetice jsou s mezerou a že základní opakující se faktor je r = abc. Všechny ostatní opakující se faktory jsou faktory r. 2 Příklad 4.8 Najděme repetice v řetězci x = abcabc. Nedeterministický faktorový automat pro x má přechodový diagram uvedený na obr. 4.6.
b
START
0
a
1
b
c c
2
a 3
a
b 4
b
c 5
c
6
Obrázek 4.6: Nedeterministický faktorový automat pro x = abcabc Přechodové tabulky nedeterministického a deterministického faktorového automatu mají tvar: a b c 0 1, 4 2, 5 3, 6 1 2 2 3 3 4 4 5 5 6 6
a b c 0 14 25 36 14 25 25 36 36 4 4 5 5 6 6
Přechodový diagram deterministického faktorového automatu je na obr. 4.7. Redukovaná tabulka repetic má tvar:
b
START
0
a
14
b
25
c
36
a
4
b
5
c
6
c Obrázek 4.7: Přechodový diagram deterministického faktorového automatu pro x = abcabc D-subset 14 25 36
Faktor a ab abc
První výskyt 1 2 3 49
Repetice (4, G) (5, G) (6, S)
Z této tabulky je vidět, že všechny repetice jsou s mezerou, kromě repetice základního faktoru r = abc. Faktor abc se opakuje jako čtverec a x = (abc)2 . 2 Příklad 4.9 Najděme repetice v řetězci x = ababa. Nedeterministický faktorový automat pro x má přechodový diagram na obr. 4.8.
b
START
a
0
1
b
a 2
a
b 3
b
a 4
a
5
Obrázek 4.8: Nedeterministický faktorový automat pro řetězec x = ababa Přechodové tabulky nedeterministického a deterministického faktorového automatu mají tvar: a b 0 1, 3, 5 2, 4 1 2 2 3 3 4 4 5 5
a b 0 135 24 135 24 24 35 35 4 4 5
Přechodový diagram deterministického faktorového automatu je na obr. 4.9.
b
START
0
a
135
b
24
a
35
b
4
a
5
Obrázek 4.9: Přechodový diagram deterministického faktorového automatu pro x = ababa Redukovaná tabulka repetic má tvar: D-subset 135 24 35
Faktor a ab aba
První výskyt 1 2 3
Repetice (3, G), (5, G) (4, S) (5, O)
Z této tabulky je vidět, že v řetězci x = ababa jsou všechny druhy repetic: a se opakuje s mezerou, 50
(ab)2 je čtverec, aba se opakuje s překrytím. Základní opakující se faktor je r = aba.
2
V dalších příkladech ukážeme typy řetězců, ve kterých je velký počet repetic. Příklad 4.10 Najděme repetice v řetězci x = aaaaaa = a6 . Nedeterministický faktorový automat pro x má přechodový diagram na obr. 4.10.
a
START
0
a
1
a
a 2
a
a 3
a
a 4
a
a 5
a
6
Obrázek 4.10: Nedeterministický faktorový automat pro řetězec x = a6 Přechodové tabulky deterministického a nedeterministického faktorového automatu mají tvar: 0 1 2 3 4 5 6
a 1, 2, 3, 4, 5, 6 2 3 4 5 6
a 0 123456 123456 23456 23456 3456 3456 456 456 56 56 6 6
Přechodový diagram deterministického faktorového automatu je na obr. 4.11.
START
0
a
123456
a
23456
a
3456
a
456
a
56
a
6
Obrázek 4.11: Přechodový diagram faktorového automatu pro x = a6 Redukovaná tabulka repetic má tvar: D-subset 123456 23456 3456 456 56
Faktor a aa aaa aaaa aaaaa
První výskyt 1 2 3 4 5 51
Repetice (2, S), (3, G), (4, G), (5, G), (6, G) (3, O), (4, S), (5, G), (6, G) (4, O), (5, O), (6, S) (5, O), (6, O) (6, O)
Z tabulky je vidět, že v řetězci x = a6 jsou všechny druhy repetic. Dokonce se zde vyskytuje „krychleÿ (aa)3 . Základní opakující se faktor je r = a5 . 2 Příklad 4.11 Najděme repetice v řetězci x = ababab = (ab)3 . Nedeterministický faktorový automat pro x má přechodový diagram na obr. 4.12.
b
START
0
a
1
b
a a
2
b 3
b
a 4
a
b 5
b
6
Obrázek 4.12: Nedeterministický faktorový automat pro řetězec x = (ab)3 Přechodové tabulky deterministického a nedeterministického faktorového automatu mají tvar: a b 0 1, 3, 5 2, 4, 6 1 2 3 4 5 6
a b 0 135 246 135 246 246 35 35 46 46 5 5 6 6
Přechodový diagram deterministického faktorového automatu je na obr. 4.13.
Obrázek 4.13: Přechodový diagram faktorového automatu pro x = (ab)3 Redukovaná tabulka repetic má tvar: D-subset 135 246 35 46
Faktor a ab aba abab
První výskyt 1 2 3 4 52
Repetice (3, G), (5, G) (4, S), (6, G) (5, O) (6, O)
Z tabulky je vidět, že v řetězci x = (ab)3 jsou všechny druhy repetic. Sám řetězec x je krychle. Základní opakující se faktor je r = abab. 2 Příklad 4.12 Najděme repetice v řetězci x = abaababa. Tento řetězec je Fibonacciho řetězec f5 . Nedeterministický faktorový automat pro x má přechodový diagram na obr. 4.14.
b
START
a
0
b
1
a 2
a
a a
3
b 4
b
a 5
a
b b
6
a 7
a
8
Obrázek 4.14: Nedeterministický faktorový automat pro řetězec x = f5 Přechodové tabulky deterministického a nedeterministického faktorového automatu mají tvar: a b 0 1, 3, 4, 6, 8 2, 5, 7 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8
a b 0 13468 257 13468 4 257 257 368 368 4 7 4 5 5 6 6 7 7 8 8
Přechodový diagram deterministického faktorového automatu je na obr. 4.15.
a
START
0
a
13468
b
257
a
368
b
a
4
b
5
a
6
b
7
a
8
b
Obrázek 4.15: Přechodový diagram faktorového automatu pro x = f5 Redukovaná tabulka repetic má tvar:
53
D-subset 13468 257 368
Faktor a ab aba
První výskyt 1 2 3
Repetice (3, G), (4, G), (6, G), (8, G) (5, G), (7, G) (6, S), (8, G)
Z tabulky je vidět, že se v řetězci f5 vyskytují repetice s mezerou a čtverec. Základní opakující se faktor je r = aba. 2 Příklad 4.13 Najděme repetice v množině řetězců X = {abaababa, ababab} = {f5 , (ab)3 } (viz příklady 4.11 a 4.12). Dále najděte nejdelší společný faktor obou řetězců. Nedeterministický faktorový automat pro X má přechodový diagram na obr. 4.16. Přechodová tabulka nedeterministického faktorového automatu
b a
START
0
1
b
a 2
a
a 3
a
b 4
b
a 5
a
b 6
b
a 7
a
8
a 1’
b
2’ b
a
3’ a
b
4’ b
a
5’ a
b
6’ b
Obrázek 4.16: Přechodový diagram nedeterministického faktorového automatu pro řetězce z množiny X = {f5 , (ab)3 } má tvar:
54
a b 0 1, 3, 4, 6, 8, 1′ , 3′ , 5′ 2, 5, 7, 2′ , 4′ , 6′ 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 1′ 2′ ′ ′ 2 3 ′ 3 4′ ′ ′ 4 5 ′ 5 6′ ′ 6 Část přechodové tabulky deterministického faktorového automatu (obsahuje jen řádky pro netriviální podmnožiny) má tvar: a b 0 134681′ 3′ 5′ 2572′ 4′ 6′ 134681′ 3′ 5′ 4 2572′ 4′ 6′ ′ ′ ′ ′ ′ 2572 4 6 3683 5 ′ ′ 3683 5 4 74′ 6′ ′ ′ ′ 74 6 85 ′ 85 6′ Odpovídající část přechodového diagramu je na obr. 4.17.
a
START
134681’3’5’
a
b
0 b
2572’4’6’
4
6’ a
a
3683’5’
b
74’6’
a
85’
Obrázek 4.17: Část přechodového diagramu deterministického faktorového automatu pro množinu X = {f5 , (ab)3 } Z automatu na obr. 4.17 je zřejmé, že nejdelší společný faktor obou řetězců je LCF (f5 , (ab)3 ) = ababa. Tato skutečnost je indikována množinou 85’. Všechny faktory řetězce LCF (f5 , (ab)3 ) jsou také společné faktory obou řetězců. 2 55
D−subset Faktor První výskyty Repetice 134681′ 3′ 5′ a 1, 1′ (3, G), (4, S), (6, G), (8, G), (3′ , G), (5′ , G) 2572′ 4′ 6′ b 2, 2′ (5, G), (7, G), (4′ , G), (6′ , G) ′ ′ ′ ′ 2572 4 6 ab 2, 2 (5, G), (7, S), (4′ , S), (6′ , S) 3683′ 5′ ba 3, 3′ (6, G), (8, S), (5′ , S) ′ ′ ′ 3683 5 aba 3, 3 (6, S), (8, O), (5′ , O) 74′ 6′ bab 7, 4′ (6, O′ ) ′ ′ ′ 74 6 abab 7, 4 (6, O′ ) 85′ baba 8, 5′ ′ 85 ababa 8, 5′
4.4
Přibližné repetice
Příklad 4.14 Najděme přesné a přibližné repetice v řetězci x = abcabd, s Hammingovou vzdáleností k = 1. Přechodový diagram nedeterministického přibližného faktorového automatu je na obr. 4.18. Přechodová tabulka tohoto automatu
b
START
0
a
1
b,c,d 1’
b
c 2
a,c,d b
2’ a,c,d
c
a 3
a,b,d c
3’ a,b,d
a
b 4
b,c,d a
4’ b,c,d
b
d 5
a,c,d b
5’ a,c,d
d
6
a,b,c d
6’ a,b,c
Obrázek 4.18: Přechodový diagram nedeterministického přibližného faktorového automatu pro X = abcabd, Hammingova vzdálenost k = 1 má tvar:
56
a b c d 0 1, 4, 2′ , 3′ , 5′ , 6′ 2, 5, 1′ , 3′ , 4′ , 6′ 3, 1′ , 2′ , 4′ , 5′ , 6′ 6, 1′ , 2′ , 3′ , 4′ , 5′ 1 2′ 2 2′ 2′ ′ ′ 2 3 3 3 3′ 3 4 4′ 4′ 4′ ′ ′ 4 5 5 5 5′ 5 6′ 6′ 6′ 6 6 1′ 2′ ′ 2 3′ 3′ 4′ ′ 4 5′ 5′ 6′ ′ 6 Při determinizaci tohoto automatu je zajímavá pro nalezení všech přesných a přibližných repetic jen ta část automatu, která obsahuje stavy tvořené množinami: - obsahujícími více stavů z hladiny 0 (přesné repetice), - obsahujícími jak stavy z hladiny 0, tak stavy z hladiny 1 (přibližné repetice). Zajímavá část tabulky přechodů deterministického automatu má tvar: a b c d 0 1, 4, 2′ , 3′ , 5′ , 6′ 2, 5, 1′ , 3′ , 4′ , 6′ 3, 1′ , 2′ , 4′ , 5′ , 6′ 6, 1′ , 2′ , 3′ , 4′ , 5′ 1, 4, 2′ , 3′ , 5′ , 6′ 2′ , 4′ , 5′ 2, 5 2′ , 3′ , 5′ 2′ , 5′ , 6′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ 2, 5, 1 , 3 , 4 , 6 3 ,4 ,6 2 ,3 ,5 ,6 3, 6 6, 3′ ′ ′ ′ ′ ′ ′ ′ ′ ′ ′ 3, 1 , 2 , 4 , 5 , 6 4 2 ,4 ,5 3 ,4 4′ , 6′ ′ ′ ′ ′ ′ ′ ′ ′ ′ 6, 1 , 2 , 3 , 4 , 5 4 2 ,5 3 6′ ′ ′ ′ ′ ′ 2, 5 3 ,6 3 ,6 3, 6 6, 3′ ′ ′ ′ 3, 6 4 4 4 4′ ′ ′ 6, 3 4
Na obr. 4.19 je uvedena část přechodového diagramu tohoto deterministického automatu. Redukovaná tabulka repetic má tvar: D-subset 2,5 3,6’ 6,3’
Faktor ab abc abd
První výskyt 2 3 6
57
Repetice (5, G, 0) (6, S, 1) (3′ , S, 1)
b
2,5,1’,3’,4’,6’
c
START
0
a
1,4,2’,3’,5’,6’
b
2,5
c d
3,6’ 6,3’
d
Obrázek 4.19: Zajímavá část deterministického přibližného faktorového automatu pro řetězec X = abcabd, Hammingova vzdálenost k = 1
58
5
Simulace nedeterministických konečných automatů – fail funkce
V této kapitole uvedeme několik příkladů KM P a AC vyhledávacích automatů, které představují simulátory nedeterministických konečných automatů pro přesné vyhledávání jednoho vzorku nebo konečné množiny vzorků. Dále uvedeme použití této metody pro přibližné vyhledávání vzorku.
5.1
KM P vyhledávací automaty
Příklad 5.1 Sestrojme KM P vyhledávací automat pro vzorek P = abab. Přechodový diagram tohoto automatu s fail funkcí f je na obr. 5.1. Přechodový diagram téhož automatu s optimalizovanou fail funkcí h je na obr. 5.2. Porovnejte tento automat s automatem z příkladu 2.1. 2 A-{a} START
a
a
b
ab
a
aba
b
abab
fail f
Obrázek 5.1: KM P vyhledávací automat, P = abab, fail funkce f
A-{a} START
a
a
b
ab
a
aba
b
abab fail h
Obrázek 5.2: KM P vyhledávací automat, P = abab, fail funkce h Příklad 5.2 Sestrojme KM P vyhledávací automat pro vzorek P = ppppp (pět p). Diagram KM P vyhledávacího automatu je na obr. 5.3. Na tomto obrázku je rozlišena fail funkce f a fail funkce h. 2
59
A-{p} START
p
p
p
p
pp
ppp
p
pppp
p
ppppp
fail f fail h
Obrázek 5.3: KM P vyhledávací automat, P = ppppp Příklad 5.3 Sestrojme KM P vyhledávací automat pro vzorek P = blablabla. Diagram tohoto automatu je na obr. 5.4. 2 A - {b}
1
l
2
a
3
b
4
l
5
a
6
b
7
l
8
a
9
ST A
RT
b
fail f fail h
Obrázek 5.4: KM P vyhledávací automat, P = blablabla
5.2
AC vyhledávací automaty
Příklad 5.4 Sestrojme AC vyhledávací automat pro vyhledávání množiny vzorků P = {abba, baba}. Diagram tohoto automatu je na obr. 5.5. Fail funkce h je uvedena jen v případě, že se liší od fail funkce f . 2 Příklad 5.5 Sestrojme AC vyhledávací automat pro vyhledávání množiny vzorků P = {k, ok, rok, brok, obrok}. Diagram tohoto automatu je na obr. 5.6. Fail funkce h je uvedena jen v případě, že se liší od fail funkce f .
60
b
a
b
abb
a
abba
a
ST A
RT
A - {a,b}
ab
b
a
b
ba
b
bab
a
baba
fail f fail h
Obrázek 5.5: AC vyhledávací automat pro množinu vzorků P = {abba, baba}
ro
o
k
rok
r r
r
A-{b,o,k,r}
br
o
bro
k
brok
b b b
o
ob
r
obr
o
obro
k
obrok
ST A
RT
o
k k
ok
fail f
k
fail h
Obrázek 5.6: AC vyhledávací P = {k, ok, rok, brok, obrok}
automat
61
pro
množinu
vzorků
Pro text T = ob rok obroky projde tento automat touto posloupností stavů: o b ⊔ r o k ε −→ o −→ ob − → b − → ε −→ ε −→ r −→ ro −→ rok − → ok − → ⊔ o b r o k k − → ε −→ ε −→ o −→ ob −→ obr −→ obro −→ obrok − → brok − → y rok − → ok − → k − → ε −→ ε Nalezené prvky množiny vzorků P jsou podtrženy. 2 Příklad 5.6 Sestrojme AC vyhledávací automat pro vyhledávání množiny vzorků P = {hers, he, his, she}. Diagram tohoto automatu je na obr. 5.7. Fail funkce h
r A-{h,s}
e h
h
he
RT
her
s
hers
i hi
ST A
r
s
his
s s
h
sh
Obrázek 5.7: AC vyhledávací P = {hers, he, his, she}
e
automat
she
pro
množinu
vzorků
je v tomto případě stejná jako fail funkce f . Pro text T = reshersche projde tento automat touto posloupností stavů: r s r e s h e ε −→ ε −→ ε −→ s −→ sh −→ she − → he −→ her −→ hers − → s − → c h e ε −→ ε −→ h −→ he Nalezené prvky množiny vzorků jsou podtrženy. 2
5.3
Přibližné vyhledávací automaty a fail funkce
Příklad 5.7 Je dán řetězec abab nad abecedou {a, b}. Sestrojme nedeterministický vyhledávací automat pro jeho přibližné vyhledávání s Hammingovou vzdáleností 1. Jeho tabulka přechodů má tvar:
62
a 0, 1 2′ 3 4′
0 1 2 3 4 1′ 2′ 3′ 4′
b 1′ 2 3′ 4 2′
3′ 4′
Přechodový diagram je na obrázku 5.8. Dále sestrojíme tabulku fail funkce: a,b
START
a
0
b
1 b
a
2 a
b
b
1’
b
3
a
a
2’
4
b
3’
4’
Obrázek 5.8: Nedeterministický automat z příkladu 5.7
4 1′ 2′ 3′ 4′
ab|ab 2
b|ε
b|b
a|a
1′
1
a|bb
a|aa
2′
2′
bb|a ab|aa ab|bb aa|ab bb|ab
0 1 2′
2′
2
2
Všimněme si, že fail funkci je třeba definovat jen pro stavy 4,1’,2’,3’,4’. To je dáno tím, že v ostatních stavech jsou možné přechody pro všechny symboly abecedy. V záhlaví této tabulky jsou uvedeny řetězce, pro které se automat do příslušného stavu může dostat z počátečního stavu. Symbolem „ | ÿ je oddělena přípona, která odpovídá stavu, do kterého fail funkce vede. Na obr. 5.11 je uveden původní vyhledávací automat bez počáteční smyčky a s doplněnou fail funkcí. Dále je u stavů 1’,2’,3’,4’ doplněn seznam řetězců, pro které se automat může dostat do příslušného stavu. 2 Abychom mohli pochopit další souvislosti, sestrojíme „přibližnýÿ faktorový automat pro řetězec abab a Hamingovu vzdálenost 1. Přechodový diagram tohoto automatu s ε–přechody je na obr. 5.9. Přibližný faktorový automat po eliminaci ε–přechodů je na obr. 5.10. Tabulka přechodů tohoto automatu 63
START
0
a
1
b
2
a
a
b
1’
3
b
b
2’
b
4
a
a
3’
b
4’
Obrázek 5.9: „Přibližnýÿ faktorový automat s ε–přechody z příkladu 5.7 má tvar: 0 1 2 3 4 1′ 2′ 3′ 4′
a 132′ 3′ 4′ 2′ 3 4′
b 241′ 2′ 3′ 4′ 2 3′ 4 2′
3′ 4′
Deterministický přibližný faktorový automat má přechodový diagram na obr. 5.12. Jeho tabulka přechodů má tvar: 0 132′ 3′ 4′ 241′ 2′ 3′ 4′ 244′ 2′ 3′ 4′ 33′ 4 3′ 4′
a 132′ 3′ 4′ 2′ 3′ 4′ 33′ 3 3′ 4′
b 241′ 2′ 3′ 4′ 244′ 2′ 3′ 4′ 3′ 4′ 44′ 4′
64
b START
a
0
1
a
b
2
a
a
b
1’
3
b
b
b b
b
2’
a
a
3’
b
a
a
4
4’ b
b
a
Obrázek 5.10: „Přibližnýÿ faktorový automat z příkladu 5.7 po odstranění ε–přechodů
START
a
0
1
b
b
2 bba
a
a
b
3
b
aaab bbab
4
a
aa
b 1’
b
2’
a aaa abb
3’
aa bb
4’
abaa abbb
bb b
b
abb aaa bba
abaa abbb aaab bbab
Obrázek 5.11: Hammingův automat s doplněnou fail funkcí z příkladu 5.7
65
START
0
a
b
132’3’4’ b
244’
a
3
b
b
b 241’2’3’4’
a
2’3’4’
4
a
a
3’
b
4’
b a
a 33’
44’ b
2 44’
2’3’4’
1 3 2’3’4’
2 4 1’2’3’4’
4’
2
4
2
4’
2’
3’
2’
4’
2’
3’
2’
4’
1
3’
1
2’
1
4
2
3’
1’
4’
1’
4’
2
2’
1’
Obrázek 5.12: Deterministický přibližný faktorový automat pro řetězec abab s Hamingovou vzdáleností rovnou 1 z příkladu 5.7
66
6
6.1
Simulace nedeterministických konečných automatů – dynamické programování a bitový paralelismus Dynamické programování
Při simulaci nedeterministického konečného automatu pomocí dynamického programování vytváříme matici D o rozměrech (m + 1) × (n + 1), kde m je délka vzorku a n je délka vstupního řetězce. V každém kroku simulace počítáme jeden sloupec matice, v němž každá jeho hodnota odpovídá hladině nejvyššího aktivního stavu v odpovídající hloubce automatu. Příklad 6.1 Mějme vzorek P = abab a text T = aababaabab. Nedeterministický automat pro přesné vyhledávání vzorku P je zkonstruován v příkladu 2.1. Tento automat budeme simulovat pro text T pomocí dynamického programování. Prvky dji matice D o rozměrech (|P | + 1) ∗ (|T | + 1) budeme počítat podle vzorce 1. dj,0 = 1, d0,i = 0, dj,i = if ti = pj then dj−1,i−1 else 1
0 < j ≤ m, 0 < i ≤ n,
(1)
0 < i ≤ n, 0 < j ≤ m. Na začátku simulace je aktivní pouze počáteční stav. Po každém kroku simulace, t.j. po výpočtu jednoho sloupce matice, jsou aktivní stavy ty, jimž odpovídají prvky s nulovými hodnotami ve vypočteném sloupci. Například pro sloupec s hodnotami 0,0,1,0,1 platí, že aktivní stavy jsou 0,1,3, což znamená, že právě byly nalezeny předpony vzorku a a aba. Jestliže je aktivním stavem stav 4, pak to signalizuje nalezení vzorku. Výsledná matice D je uvedena v tabulce 6.1. Vzorek byl nalezen na pozicích 5 (d4,5 = 0) a 10 (d4,10 = 0). D a b a b
0 1 1 1 1
a 0 0 1 1 1
a 0 0 1 1 1
b 0 1 0 1 1
a 0 0 1 0 1
b 0 1 0 1 0
a 0 0 1 0 1
a 0 0 1 1 1
b 0 1 0 1 1
a 0 0 1 0 1
b 0 1 0 1 0
Tabulka 6.1: Simulace N KA pro přesné vyhledávání vzorku P = abab v textu aababaabab 2
67
Příklad 6.2 Mějme vzorek P = adbbca a text T = adcabcaabadbbca. Zkonstruujme nedeterministický konečný automat pro přibližné vyhledávání vzorku P pro Hammingovu vzdálenost s maximálně k = 3 záměnami. Jeho přechodový diagram je na obrázku 6.1. Dále budeme simulovat tento automat nad textem T pomocí dynamického programování.
Obrázek 6.1: Konečný automat z příkladu 6.2 Pro simulaci budeme používat matici D o rozměrech (|P | + 1) × (|T | + 1). Každý prvek dj,i matice se počítá podle vzorce 2. dj,0 ← k + 1, 0<j≤m d0,i ← 0, 0≤i≤n dj,i ← if ti = pj then dj−1,i−1 else dj−1,i−1 + 1, 0 < i ≤ n, 0 < j ≤ m
(2)
Na začátku simulace je aktivní pouze počáteční stav, proto všechny vektory pro hloubky j, 0 < j ≤ m nastavíme hladinu nejvyššího aktivního stavu na k + 1. Člen dj−1,i−1 ve vzorci 2 reprezentuje přechod match, kdy vstupní symbol ti odpovídá současnému symbolu vzorku pj . V tomto případě se v následující hloubce automatu stane nejvyšším aktivním stavem stav na hladině dj−1,i−1 . V případě, že ti 6= pj , se použije přechod replace reprezentovaný členem dj−1,i−1 + 1. Zde se zvýší počet chyb a tudíž se nejvyšším aktivním stavem v následující hloubce stane stav na hladině dj−1,i−1 + 1. Výsledná matice D je pak ukázána v tabulce 6.2. V tabulce se vyskytují i hodnoty větší než k = 3. Takové hodnoty lze nahradit jednou hodnotou k + 1. Můžeme tím dosáhnout menších pamě68
D a d b b c a
0 4 4 4 4 4 4
a 0 0 5 5 5 5 4
d 0 1 0 6 6 6 6
c 0 1 2 1 7 6 7
a 0 0 2 3 2 8 6
b 0 1 1 2 3 3 9
c 0 1 2 2 3 3 4
a 0 0 2 3 3 4 3
a 0 0 1 3 4 4 4
b 0 1 1 1 3 5 5
a 0 0 2 2 2 4 5
d 0 1 0 3 3 3 5
b 0 1 2 0 3 4 4
b 0 1 2 2 0 4 5
c 0 1 2 3 3 0 5
a 0 0 2 3 4 4 0
Tabulka 6.2: Simulace NKA pro přibližné vyhledávání s k = 3 záměnami, vzorek P = adbbca a text T = adcabcaabadbbca
ťových nároků na reprezentaci čísel matice D, neboť pak potřebujeme jen ⌈log2 (k + 1)⌉ bitů na jeden prvek matice. Změňte vzorec 2 tak, aby nejvyšší hodnota byla k + 1! 2 Příklad 6.3 Mějme vzorek P = adbbca a text T = adcabcaabadbbca. Zkonstruujme nedeterministický konečný automat pro přibližné vyhledávání vzorku P pro Levenshteinovu vzdálenost s maximálně k = 3 chybami. Jeho přechodový diagram je na obrázku 6.2. Dále budeme simulovat tento automat nad textem T pomocí dynamického programování.
Obrázek 6.2: Konečný automat z příkladu 6.3 Pro simulaci budeme používat matici D o rozměrech (|P | + 1) × (|T | + 1), 69
kterou budeme konstruovat pomocí vzorce 3. dj,0 ← j, 0 ≤ j ≤ m, d0,i ← 0, 0 ≤ i ≤ n, dj,i ← min(if ti = pj then dj−1,i−1 else dj−1,i−1 + 1, if j < m then dj,i−1 + 1, dj−1,i + 1), 0 < i ≤ n, 0 < j ≤ m.
(3)
Na začátku simulace je aktivní pouze počáteční stav a všechny stavy, do kterých se lze dostat pomocí ε-přechodů (tzn. stavy z ε-uzávěru vytvořeného nad počátečním stavem). Proto všechny vektory pro hloubky j, 0 ≤ j ≤ m, nastavíme hladinu nejvyššího aktivního stavu na j. Člen dj−1,i−1 ve vzorci 3 reprezentuje přechod match, člen dj−1,i−1 + 1 reprezentuje přechod replace. Člen dj,i−1 + 1 reprezentuje přechod insert, kdy aktivní stav přechází v rámci jedné hloubky do hladiny s vyšším počtem chyb. Člen dj−1,i + 1 pak reprezentuje přechod delete, kdy aktivní stav přechází při přechodu z jedné hloubky do následující z jedné hladiny do hladiny s vyšším počtem chyb, a to vše bez čtení vstupního symbolu (tzn. index i jako ukazatel v textu se nemění). Výsledná matice je pak ukázána v tabulce 6.3. 2 D a d b b c a
0 1 2 3 4 5 6
a 0 0 1 2 3 4 5
d 0 1 0 1 2 3 4
c 0 1 1 1 2 2 3
a 0 0 1 2 2 3 2
b 0 1 1 1 2 3 4
c 0 1 2 2 2 2 3
a 0 0 1 2 3 3 2
a 0 0 1 2 3 4 3
b 0 1 1 1 2 3 4
a 0 0 1 2 2 3 3
d 0 1 0 1 2 3 4
b 0 1 1 0 1 2 3
b 0 1 2 1 0 1 2
c 0 1 2 2 1 0 1
a 0 0 1 2 2 1 0
Tabulka 6.3: Simulace NKA pro přibližné vyhledávání s k = 3 chybami, vzorek P = adbbca a text T = adcabcaabadbbca
Příklad 6.4 Mějme vzorek P = adbbca a text T = adcabcaabadbbca. Zkonstruujme nedeterministický konečný automat pro přibližné vyhledávání vzorku P pro zobecněnou Levenshteinovu vzdálenost s maximálně k = 3 chybami. Jeho přechodový diagram je na obrázku 6.3. Dále budeme simulovat tento automat nad textem T pomocí dynamického programování. Pro simulaci budeme používat matici D o rozměrech (|P | + 1) × (|T | + 1), kterou budeme konstruovat pomocí vzorce 4. 70
Obrázek 6.3: Konečný automat z příkladu 6.4
dj,0 ← j, 0 ≤ j ≤ m, d0,i ← 0, 0 ≤ i ≤ n, dj,i ← min(if ti = pj then dj−1,i−1 else dj−1,i−1 + 1, if j < m then dj,i−1 + 1, dj−1,i + 1, if i > 1 and j > 1 and ti−1 = pj and ti = pj−1 then dj−2,i−2 + 1), 0 < i ≤ n, 0 < j ≤ m.
(4)
Počáteční nastavení matice je stejné jako u Levenshteinovy vzdálenosti. Člen dj−1,i−1 ve vzorci 4 reprezentuje přechod match, člen dj−1,i−1 + 1 reprezentuje přechod replace, člen dj,i−1 + 1 reprezentuje přechod insert, člen dj−1,i + 1 reprezentuje přechod delete. Oproti vzorci 3 musíme přidat simulaci přechodu transpose. Tu reprezentuje člen dj−2,i−2 + 1). Zde aktivní stav přechází při přechodu přes dvě hloubky automatu na hladinu s vyšší počtem chyb. Při tomto přechodu zároveň musí přečíst dva po sobě jdoucí znaky vzorku v opačném pořadí. Výsledná matice je pak ukázána v tabulce 6.4. 2
6.2
Bitový paralelismus
Metoda bitového paralelismu zahrnuje několik algoritmů: Shift-Or, ShiftAnd a Shift-Add. Zde se zaměříme na algoritmus Shift-Or. Algoritmus Shift71
D a d b b c a
0 1 2 3 4 5 6
a 0 0 1 2 3 4 5
d 0 1 0 1 2 3 4
b 0 1 1 0 1 2 3
c 0 1 2 1 1 1 2
b 0 1 2 2 1 1 2
a 0 0 1 2 2 2 1
a 0 0 1 2 3 3 2
b 0 1 1 1 2 3 4
a 0 0 1 2 2 3 3
d 0 1 0 1 2 3 4
b 0 1 1 0 1 2 3
b 0 1 2 1 0 1 2
c 0 1 2 2 1 0 1
a 0 0 1 2 2 1 0
Tabulka 6.4: Simulace NKA pro přibližné vyhledávání s k = 3 chybami, vzorek P = adbbca a text T = adcabcaabadbbca And se pak od něj odlišuje pouze záměnou 0 a 1 a záměnou bitových operací or a and. Algoritmus Shift-Or používá matice Rl , 0 ≤ l ≤ k o velikosti m × (n + 1) l , 0 < j ≤ m, a maskovací matici D o velikosti m × |A|. Každý prvek rj,i 0 ≤ i ≤ n, obsahuje 0, jestliže je stav v hloubce j a úrovni l aktivní, nebo 1, jestli není aktivní. Každý prvek dj,x , 0 < j ≤ m, x ∈ Σ, obsahuje 0, když pj = x, jinak 1. Matice jsou implementovány jako tabulky bitových vektorů, jak je ukázáno níže:
Ril
=
l r1,i l r2,i .. . l rm,i
a D[x] =
d1,x d2,x .. . dm,x
, 0 ≤ i ≤ n, 0 ≤ l ≤ k, x ∈ A.
(5)
2 Příklad 6.5 Mějme vzorek P = adbbca a text T = adcabcaabadbbca. Zkonstruujme nedeterministický konečný automat pro přesné vyhledávání vzorku P . Jeho přechodový diagram je na obrázku 6.4. Dále budeme simulovat tento automat nad textem T pomocí algoritmu Shift-Or.
Obrázek 6.4: Konečný automat z příkladu 6.5 Pro simulaci budeme používat vektory Ri0 , 0 ≤ i ≤ n, které budeme konstruovat pomocí vzorce 6. 72
0 rj,0 ← 1, 0 < j ≤ m, 0 0 Ri ← shr(Ri−1 ) or D[ti ], 0 < i ≤ n.
(6)
Maskovací tabulka je ukázána v tabulce 6.5. Výsledné vektory jsou pak ukázány v tabulce 6.6. D a d b b c a
a 0 1 1 1 1 0
b 1 1 0 0 1 1
c 1 1 1 1 0 1
d 1 0 1 1 1 1
A \ {a, b, c, d} 1 1 1 1 1 1
Tabulka 6.5: Matice D pro vzorek P = adbbca 0 ) or D[t ] ve vzorci 5 simuluje přechod match — všechny Člen shr(Ri−1 i aktivní stavy se přesunou do následující hloubky a pomocí maskovacího vektoru se z nich vyberou jen ty, které přešly přes přechod označený aktuálním vstupním symbolem ti . V praxi se používá spíše posun vektoru doleva, což se využívá v případě, že je délka vektoru větší než počet bitů v počítačovém slově a je nutno daný vektor rozložit do několika počítačových slov. Zde jsme zvolili posun doprava, aby orientace přechodů odpovídala nakresleným automatům. Na začátku běhu automatu není žádný stav aktivní, proto všechny bity nastavíme na 1. Pro počáteční stav stav nepotřebujeme žádný bit. Počáteční stav je neustále aktivní kvůli smyčce pro všechny symboly abecedy. Simulace tohoto stavu je zajištěna v operaci shr(), kde se na při posunu vektoru na jeho začátek vždy vkládá nula. 2
Příklad 6.6 Mějme vzorek P = adbbca a text T = adcabcaabadbbca. Zkonstruujme nedeterministický konečný automat pro přibližné vyhledávání vzorku P pro Hammingovu vzdálenost s maximálně k = 3 záměnami. Jeho přechodový diagram je na obrázku 6.1. Dále budeme simulovat tento automat nad textem T pomocí algoritmu Shift-Or. Pro simulaci budeme používat vektory Ril , 0 ≤ i ≤ n, 0 ≤ l ≤ k, které budeme konstruovat pomocí vzorce 7.
73
R0 a d b b c a
1 1 1 1 1 1
a 0 1 1 1 1 1
d 1 0 1 1 1 1
c 1 1 1 1 1 1
a 0 1 1 1 1 1
b 1 1 1 1 1 1
c 1 1 1 1 1 1
a 0 1 1 1 1 1
a 0 1 1 1 1 1
b 1 1 1 1 1 1
a 0 1 1 1 1 1
d 1 0 1 1 1 1
b 1 1 0 1 1 1
b 1 1 1 0 1 1
c 1 1 1 1 0 1
a 0 1 1 1 1 0
Tabulka 6.6: Matice R0 pro přesné vyhledávání (pro vzorek P = adbbca a text T = adcabcaabadbbca)
l rj,0 ← 1, 0 < j ≤ m, 0 ≤ l ≤ k, 0 0 Ri ← shr(Ri−1 ) or D[ti ], 0 < i ≤ n, l ) or D[t ]) and shr(Rl−1 ), 0 < i ≤ n, 0 < l ≤ k. Ril ← (shr(Ri−1 i i−1
(7)
0 ) or D[t ] simuluje přechod match. Člen shr(Rl−1 ) simuČlen shr(Ri−1 i i−1 luje přechod replace — všechny aktivní stavy se přesunou do následující hloubku ale i úrovně (tzn. změní se jak pozice ve vzorku, tak i počet chyb). Výsledné vektory jsou pak ukázány v tabulce 6.7. 2
Příklad 6.7 Mějme vzorek P = adbbca a text T = adcabcaabadbbca. Zkonstruujme nedeterministický konečný automat pro přibližné vyhledávání vzorku P pro Levenshteinovu vzdálenost s maximálně k = 3 chybami. Jeho přechodový diagram je na obrázku 6.2. Dále budeme simulovat tento automat nad textem T pomocí algoritmu Shift-Or. Pro simulaci budeme používat vektory Ril , 0 ≤ i ≤ n, 0 ≤ l ≤ k, které budeme konstruovat pomocí vzorce 8 a 9. l rj,0 l rj,0 Ri0 Ril
← ← ← ←
0, 1, 0 ) or D[t ], shr(Ri−1 i l ) or D[t ]) (shr(Ri−1 i l−1 l−1 and shr(Ri−1 and Ril−1 ) and (Ri−1
74
0 < j ≤ l, 0 < l ≤ k, l < j ≤ m, 0 ≤ l ≤ k, 0 < i ≤ n, or V ), 0 < i ≤ n, 0 < l ≤ k.
(8)
R0 a d b b c a R1 a d b b c a R2 a d b b c a R3 a d b b c a
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
a 0 1 1 1 1 1 a 0 1 1 1 1 1 a 0 1 1 1 1 1 a 0 1 1 1 1 1
d 1 0 1 1 1 1 d 0 0 1 1 1 1 d 0 0 1 1 1 1 d 0 0 1 1 1 1
c 1 1 1 1 1 1 c 0 1 0 1 1 1 c 0 0 0 1 1 1 c 0 0 0 1 1 1
a 0 1 1 1 1 1 a 0 1 1 1 1 1 a 0 0 1 0 1 1 a 0 0 0 0 1 1
b 1 1 1 1 1 1 b 0 0 1 1 1 1 b 0 0 0 1 1 1 b 0 0 0 0 0 1
c 1 1 1 1 1 1 c 0 1 1 1 1 1 c 0 0 0 1 1 1 c 0 0 0 0 0 1
a 0 1 1 1 1 1 a 0 1 1 1 1 1 a 0 0 1 1 1 1 a 0 0 0 0 1 0
a 0 1 1 1 1 1 a 0 0 1 1 1 1 a 0 0 1 1 1 1 a 0 0 0 1 1 1
b 1 1 1 1 1 1 b 0 0 0 1 1 1 b 0 0 0 1 1 1 b 0 0 0 0 1 1
a 0 1 1 1 1 1 a 0 1 1 1 1 1 a 0 0 0 0 1 1 a 0 0 0 0 1 1
d 1 0 1 1 1 1 d 0 0 1 1 1 1 d 0 0 1 1 1 1 d 0 0 0 0 0 1
b 1 1 0 1 1 1 b 0 1 0 1 1 1 b 0 0 0 1 1 1 b 0 0 0 0 1 1
b 1 1 1 0 1 1 b 0 1 1 0 1 1 b 0 0 0 0 1 1 b 0 0 0 0 1 1
c 1 1 1 1 0 1 c 0 1 1 1 0 1 c 0 0 1 1 0 1 c 0 0 0 0 0 1
a 0 1 1 1 1 0 a 0 1 1 1 1 0 a 0 0 1 1 1 0 a 0 0 0 1 1 0
Tabulka 6.7: Matice Rl pro přibližné vyhledávání s k = 3 záměnami, vzorek P = adbbca a text T = adcabcaabadbbca
75
V =
v1 v2 .. . vm
, kde vm = 1 a vj = 0, ∀j, 1 ≤ j < m.
(9)
0 Ve vzorci 8 člen shr()Ri−1 or D[ti ] simuluje přechod match a člen l−1 l−1 shr(Ri−1 ) simuluje přechod replace. Člen Ri−1 or V simuluje přechod insert — všechny aktivní stavy se přesunou z jedné úrovně do další (tzn. zvýší se počet chyb) aniž by se změnila hloubka v automatu. Vektor V pouze zajišťuje, aby se přechod insert nesimuloval v poslední hloubce (mezi koncovými stavy), kde se tyto přechody nenacházejí. Člen shr(Ril−1 ) simuluje přechod delete — všechny aktivní stavy se bez čtení vstupního symbolu (index i se nemění) přesunou do následující hloubky a úrovně automatu. Oproti vzorci 7 se změnilo počáteční nastavení vektorů, neboť díky ε-přechodům je na začátku běhu automatu aktivní vždy první stav v každé úrovni. Výsledné vektory jsou pak ukázány v tabulce 6.8. 2
Příklad 6.8 Mějme vzorek P = adbbca a text T = adcabcaabadbbca. Zkonstruujme nedeterministický konečný automat pro přibližné vyhledávání vzorku P pro zobecněnou Levenshteinovu vzdálenost s maximálně k = 3 chybami. Jeho přechodový diagram je na obrázku 6.3. Dále budeme simulovat tento automat nad textem T pomocí algoritmu Shift-Or. Pro simulaci budeme používat vektory Ril , 0 ≤ i ≤ n, 0 ≤ l ≤ k, a Sil , 0 ≤ i ≤ n, 0 ≤ l < k, které budeme konstruovat pomocí vzorce 11, kde vektor V je definován ve vzorci 9.
Sil =
l rj,0 l rj,0 Ri0 Ril
slj,0 Sil
sl1,i sl2,i .. . slm,i
, 0 ≤ l < k, 0 ≤ i < n.
0, 1, 0 ) or D[t ], shr(Ri−1 i l ) or D[t ]) (shr(Ri−1 i l−1 l−1 and shr(Ri−1 and Ril−1 and (Si−1 l−1 and (Ri−1 or V ), ← 1, l ) or shl(D[t ]), ← shr(Ri−1 i ← ← ← ←
76
(10)
0 < j ≤ l, 0 < l ≤ k, l < j ≤ m, 0 ≤ l ≤ k, 0 < i ≤ n, or D[ti ])) 0 < i ≤ n, 0 < l ≤ k, 0 < j ≤ m, 0 ≤ l < k, 0 < i < n, 0 ≤ l < k.
(11)
R0 a d b b c a R1 a d b b c a R2 a d b b c a R3 a d b b c a
1 1 1 1 1 1 0 1 1 1 1 1 0 0 1 1 1 1 0 0 0 1 1 1
a 0 1 1 1 1 1 a 0 0 1 1 1 1 a 0 0 0 1 1 1 a 0 0 0 0 1 1
d 1 0 1 1 1 1 d 0 0 0 1 1 1 d 0 0 0 0 1 1 d 0 0 0 0 0 1
c 1 1 1 1 1 1 c 0 0 0 1 1 1 c 0 0 0 0 0 1 c 0 0 0 0 0 0
a 0 1 1 1 1 1 a 0 0 1 1 1 1 a 0 0 0 0 1 0 a 0 0 0 0 0 0
b 1 1 1 1 1 1 b 0 0 0 1 1 1 b 0 0 0 0 1 1 b 0 0 0 0 0 1
c 1 1 1 1 1 1 c 0 1 1 1 1 1 c 0 0 0 0 0 1 c 0 0 0 0 0 0
a 0 1 1 1 1 1 a 0 0 1 1 1 1 a 0 0 0 1 1 0 a 0 0 0 0 0 0
a 0 1 1 1 1 1 a 0 0 1 1 1 1 a 0 0 0 1 1 1 a 0 0 0 0 1 0
b 1 1 1 1 1 1 b 0 0 0 1 1 1 b 0 0 0 0 1 1 b 0 0 0 0 0 1
a 0 1 1 1 1 1 a 0 0 1 1 1 1 a 0 0 0 0 1 1 a 0 0 0 0 0 0
d 1 0 1 1 1 1 d 0 0 0 1 1 1 d 0 0 0 0 1 1 d 0 0 0 0 0 1
b 1 1 0 1 1 1 b 0 0 0 0 1 1 b 0 0 0 0 0 1 b 0 0 0 0 0 0
b 1 1 1 0 1 1 b 0 1 0 0 0 1 b 0 0 0 0 0 0 b 0 0 0 0 0 0
c 1 1 1 1 0 1 c 0 1 1 0 0 0 c 0 0 0 0 0 0 c 0 0 0 0 0 0
a 0 1 1 1 1 0 a 0 0 1 1 0 0 a 0 0 0 0 0 0 a 0 0 0 0 0 0
Tabulka 6.8: Matice Rl pro přibližné vyhledávání pro Levenshteinovu vzdálenost s k = 3 chybami, vzorek P = adbbca a text T = adcabcaabadbbca
77
0 Ve vzorci 11 člen shr() Ri−1 or D[ti ] simuluje přechod match, člen l−1 l−1 shr(Ri−1 ) simuluje přechod replace, člen Ri−1 or V simuluje přechod insert l−1 a člen shr(Ri ) simuluje přechod delete. Oproti vzorci 8 však musíme přidat simulaci přechodu transpose. Tento přechod však v sobě ukrývá další stav. Pro takové stavy jsme zavedli pomocné vektory Sil . Člen l ) or shl(D[t ]) při výpočtu S l zajistí, že se aktivní stavy přesushr(Ri−1 i i nou do následující hloubky automatu, kde z nich člen shl(D[ti ]) vybere jen ty, které jsou označeny vstupním symbolem ti . Jelikož je tato hrana automatu označena symbolem, který je shodný se symbolem požitým u přechodu match u následující hloubky, musíme maskovací vektor D[ti ] posunout proti l−1 směru přechodu. Člen Si−1 or D[ti ] při výpočtu Ril pak zajistí, že se zbylé aktivní stavy přesunou do další hloubky následující úrovně. Z nich se vyberou jen ty, které použily přechod označený vstupním symbolem ti . Jelikož jsou takové přechody označeny symbolem z přechodu match z předchozí hloubky, provádíme maskování vektorů ještě před jejich posunem. Celkově se tedy aktivní stavy u přechodu transpose přesunou o dvě hloubky a jednu úroveň (tzn. přečtou se dva symboly, stavy se posunou o dvě pozice ve vzorku a zvýší se počet chyb o jedničku). Výsledné vektory jsou pak ukázány v tabulce 6.9. 2
78
R0
S0
R1
S1
R2
S2
R3
a d b b c a a d b b c a a d b b c a a d b b c a a d b b c a a d b b c a a d b b c a
1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1
a 0 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1
d 1 0 1 1 1 1 0 1 1 1 1 1 0 0 0 1 1 1 0 1 1 1 1 1 0 0 0 0 1 1 0 1 1 1 1 1 0 0 0 0 0 1
b 1 1 0 1 1 1 1 1 0 1 1 1 0 0 0 0 1 1 1 0 0 1 1 1 0 0 0 0 0 1 1 0 0 1 1 1 0 0 0 0 0 0
c 1 1 1 1 1 1 1 1 1 0 1 1 0 1 0 0 0 1 1 1 1 0 1 1 0 0 0 0 0 0 1 1 1 0 1 1 0 0 0 0 0 0
b 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 0 1 1 0 1 1 1 1 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0 0
a 0 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 0 1 0 0 0 0 0 0 1 1 1 1 0 1 0 0 0 0 0 0
a 0 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 0 1 1 1 1 0 1 0 0 0 0 0 0
b 1 1 1 1 1 1 1 0 1 1 1 1 0 0 0 1 1 1 1 0 0 1 1 1 0 0 0 0 1 1 1 0 0 1 1 1 0 0 0 0 0 1
a 0 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 1 0 0 0 0 0 0
d 1 0 1 1 1 1 0 1 1 1 1 1 0 0 0 1 1 1 0 1 1 1 1 1 0 0 0 0 1 1 0 1 1 1 1 1 0 0 0 0 0 1
b 1 1 0 1 1 1 1 1 0 1 1 1 0 0 0 0 1 1 1 0 0 1 1 1 0 0 0 0 0 1 1 0 0 1 1 1 0 0 0 0 0 0
b 1 1 1 0 1 1 1 1 1 1 1 1 0 1 0 0 0 1 1 0 0 1 1 1 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0 0
c 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 0 0 0 1 1 1 0 1 1 0 0 0 0 0 0 1 1 1 0 1 1 0 0 0 0 0 0
a 0 1 1 1 1 0 1 1 1 1 1 1 0 0 1 1 0 0 1 1 1 1 0 1 0 0 0 0 0 0 1 1 1 1 0 1 0 0 0 0 0 0
Tabulka 6.9: Matice Rl a S l pro přibližné vyhledávání pro zobecněnou Levenshteinovu vzdálenost s maximálně k = 3 chybami, vzorek P = adbbca a text T = adbcbaabadbbca
79
7
Protisměrné vyhledávání v textu – vyhledávání předpon vzorku
Základním nástrojem pro vyhledávání předpon vzorku je sufixový automat sestrojený pro reverzovaný vzorek. Sufixový automat přijímá konečný jazyk Suf (P R ) tvořený všemi příponami reverzovaného vzorku P R (viz definice 1.8). To znamená, že přijímá všechny předpony vzorku P při čtení textu zprava doleva.
7.1
Sufixový automat pro reverzovaný vzorek
Příklad 7.1 Sestrojme sufixový automat pro reverzovaný vzorek babaR , který přijímá množinu Suf (babaR ) tvořenou všemi příponami řetězce abab. Suf (babaR ) = {b, ab, bab, abab}. Množina Suf (babaR ) obsahuje reverzované předpony vzorku baba. Konstrukci zahájíme konstrukcí konečného automatu M1 , který přijímá reverzovaný vzorek. Jeho přechodový diagram je na obr. 7.1. 4
b
3
a
b
2
1
a
0
START
Obrázek 7.1: Automat M1 přijímající řetězec abab Dalším krokem je přidání ε–přechodů z počátečního stavu do všech stavů kromě koncového. Tím získáme konečný automat M2 , jehož přechodový diagram je na obr. 7.2.
4
b
3
a
b
2
1
a
0
START
Obrázek 7.2: Konečný automat M2 , který přijímá všechny přípony řetězce abab K získání deterministického sufixového automatu vedou další dvě standardní operace - odstranění ε–přechodů a v případě potřeby determinizace. Sufixový automat M3 po odstranění ε–přechodů je na obr. 7.3. V případě, že se žádný symbol ve vzorku neopakuje, což znamená, že všechny symboly vzorku jsou navzájem různé, je automat M3 deterministický a celý postup končí. Jestliže se aspoň jeden symbol ve vzorku opakuje, je automat M3 nedeterministický a je třeba provést determinizaci. V našem případě je deterministický sufixový automat M4 na obr. 7.4. 2
80
b a b 4
b
3
a
b
2
1
a
0
START
Obrázek 7.3: Sufixový automat M3 , po odstranění ε–přechodů b 4
b
3
a
b
24
13
a
0
START
Obrázek 7.4: Sufixový automat M4
7.2
Přesné protisměrné vyhledávání předpon vzorku v textu
Příklad 7.2 Sufixový automat M4 z příkladu 7.1 použijeme při vyhledávání vzorku P = baba v textu T = aaaabbabab. Vzorek přiložíme na začátek textu a hledáme protisměrným vyhledáváním nejdelší předponu vzorku. Pokud je předpona rovna vzorku, je vzorek nalezen a posuv se provede o délku periody vzorku. Pokud nalezneme kratší předponu, posuneme vzorek o rozdíl délky vzorku a délky nalezené předpony. Pokud není žádná předpona nalezena, posuneme vzorek o jeho délku. Ve všech případech se začíná hledat nová nejdelší předpona. Algoritmus hledání předpon používá sufixový automat pro reverzovaný vzorek (v našem případě M4 ). Pro určení délky posunu budeme potřebovat tyto proměnné: m – délka vzorku, position – pozice symbolu v textu, ke kterému je přiložen poslední symbol vzorku, tcounter – čítač počtu přechodů, lpref ix – délka nejdelší dosud nalezené předpony. Konfigurace algoritmu je čtveřice (q, position − tcounter, tcounter, lpref ix), kde q je stav sufixového automatu. Počáteční konfigurace je (0, m, 0, 0). 1 2 3 4 5 6 7 8 9 10 Pro text T = a a a a b b a b a b provede vyhledávací algoritmus tuto posloupnost přechodů (0, 4, 0, 0) ⊢a (13, 3, 1, 0).
81
Další přechod v automatu není možný a délka předpony je 0, proto se provede posuv o 4 − 0 pozic v textu doprava: ⊢ ⊢b ⊢a ⊢b
(0, 8, 0, 0) (24, 7, 1, 1) (3, 6, 2, 1) (4, 5, 3, 3).
Další přechod není možný a délka předpony je 3, proto se provede posuv o 4 − 3 pozic doprava: ⊢ (0, 9, 0, 0) ⊢a (13, 8, 1, 0) ⊢b (24, 7, 2, 2) ⊢a (3, 6, 3, 2) ⊢b (4, 5, 4, 4). Vzorek nalezen, posuv o 2 (délka periody) doprava: ⊢ (0, 11, 0, 0). Protože position je větší než délka textu, vyhledávání končí. Z této posloupnosti přechodů je vidět, že uvedený algoritmus je neefektivní v tom, že již nalezenou předponu znovu porovnává. Modifikujme proto tento algoritmus tak, aby tato předpona nebyla znovu porovnávána. Zavedeme proto další proměnnou: ncomp – počet potřebných porovnání. Její počáteční hodnota bude délka posuvu a při každém přechodu se zmenší o jedničku. Je-li její hodnota rovna nule, je vzorek nalezen. Konfigurace algoritmu bude v tomto případě pětice (q, position−tcounter, tcounter, lpref ix, ncomp). Počáteční konfigurace je (0, m, 0, 0, m). Pro text T provede vyhledávací algoritmus tuto posloupnost přechodů: (0, 4, 0, 0, 4) ⊢a ⊢ ⊢b ⊢a ⊢b ⊢ ⊢a ⊢
(13, 3, 1, 0, 3) (0, 8, 0, 0, 4) (24, 7, 1, 1, 3) (3, 6, 2, 1, 2) (4, 5, 3, 3, 1) (0, 9, 0, 0, 1) (13, 8, 1, 0, 0) (0, 11, 0, 0, 2)
posuv o 4
posuv o 1 vzorek nalezen, posuv o 2 ukončení.
V tomto případě automat provedl 8 přechodů, zatímco v předchozím případě provedl 11 přechodů. 2
82
7.3
Sufixový automat pro přibližné protisměrné vyhledávání v textu
Základním nástrojem pro přibližné protisměrné vyhledávání předpon vzorku je přibližný sufixový automat sestrojený pro reverzovaný vzorek. V dalším textu budeme uvažovat Hammingovu vzdálenost. Hammingův sufixový automat přijímá konečný jazyk HSufk (P ) tvořený všemi příponami vzorku P a řetězci, které mají od těchto přípon Hammingovu vzdálenost menší nebo rovnu k. Příklad 7.3 Sestrojme Hammingův sufixový automat HSufk (P ) pro reverzovaný vzorek P = baba a k = 1. Konstrukci zahájíme sestrojením konečného automatu M1 , který přijímá reverzovaný vzorek s jednou chybou. Jeho přechodový diagram je na obr. 7.5. b
4 a
1
a
a
3’
b
2
b
b
4’
a
3
0
START
b
b
2’
a
1’
Obrázek 7.5: Automat M1 přijímající řetězec P = babaR = abab a řetězce se vzdáleností 1 od P Dalším krokem je přidání ε–přechodů z počátečního stavu do všech stavů na hladině 0 kromě posledního. Jedná se o stavy, které odpovídají začátkům všech přesných i přibližných předpon. Jsou to stavy 1, 2, 3. Tím získáme konečný automat M2 , jehož přechodový diagram je na obr. 7.6.
b
4 a
4’
a
3 b
b
3’
b
2
1
a
a
0
START
b
b
2’
a
1’
Obrázek 7.6: Konečný automat M2 s ε–přechody přijímající jazyk HSuf1 = abab Po odstranění ε–přechodů získáme konečný automat M3 , jehož přecho83
a b 0 132′ 4′ 241′ 3′ 1 2′ 2 2 3 3′ 3 4′ 4 4 1′ 2′ ′ ′ 2 3 ′ 3 4′ ′ 4 Tabulka 7.1: Přechodová tabulka konečného automatu M3 dový diagram je na obr. 7.7. b b
4
a
4’
a
3
a
b b
2
b
b
3’
1
a
a
0
START
b
b
2’
a
1’
a b a
Obrázek 7.7: Nedeterministický konečný automat M3 přijímající jazyk HSuf1 = abab Posledním krokem je konstrukce ekvivalentního deterministického konečného automatu M4 . Tab. 7.1 je tabulka přechodů nedeterministického konečného automatu M3 . Přechodová tabulka ekvivalentního deterministického konečného automatu je tab. 7.2. Přechodový diagram deterministického konečného automatu M4 je na obr. 7.8. 2
7.4
Přibližné protisměrné vyhledávání předpon vzorku v textu
Příklad 7.4 Sufixový automat M4 z příkladu 7.3 použijeme pro vyhledávání vzorku P = baba v textu T = aaabbbabab. Vyhledávací algoritmus pracuje podobně jako 84
a b 0 132′ 4′ 241′ 3′ 132′ 4′ 2′ 3′ 4′ 24 241′ 3′ 3 2′ 3′ 4′ 2′ 3′ 4′ 3′ 4′ 24 3 3′ 3 4′ 4 4 3′ 4′ ′ 4 Tabulka 7.2: Přechodová tabulka konečného automatu M4 0
0 b
4
a
3
a
4’
24
b
1
1 b
a
3’
a
a b
2’3’4’
a
0
START
b
1 b
132’4’
0
241’3’
b
Obrázek 7.8: Deterministický konečný automat M4 přijímající jazyk HSuf1 = abab pro přesné vyhledávání (viz příklad 7.2). Zjištění počtu chyb v nalezeném vzorku se určí podle stavu, do kterého se algoritmus dostane v okamžiku nalezení vzorku. Ve stavu 4 je nalezen vzorek bez chyb a ve stavu 4′ je vzorek nalezen s jednou chybou. Konfigurace vyhledávacího algoritmu je stejná jako pro přesné vyhledávání. Pro text 1 2 3 4 5 6 7 8 9 10 T = a a a b b b a b a b
85
provede vyhledávací algoritmus tuto posloupnost přechodů: (0, 4, 0, 0, 4) ⊢b (241′ 3′ , 3, 1, 1) ⊢a (3, 2, 2, 1) posuv o 3 ⊢ (0, 7, 0, 0) ⊢a (132′ 4′ , 6, 1, 1) ⊢b (24, 5, 2, 2) ⊢b (3′ , 4, 3, 2) ⊢b (4′ , 3, 4, 2) vzorek nalezen s jednou chybou, posuv o 2 ⊢ (0, 9, 0, 0) ⊢a (132′ 4′ , 8, 1, 1) ⊢b (24, 7, 2, 2) ⊢a (3, 6, 3, 2) ⊢b (4, 5, 4, 2) vzorek nalezen bez chyb, posuv o 2 ⊢ (0, 11, 0, 0) ukončení. 2
Poznámka: (viz příklad 7.2) Pro optimalizaci je třeba nadefinovat přibližnou periodu a přibližnou hranici.
86
8
Protisměrné vyhledávání v textu – vyhledávání opakujících se přípon vzorku
Základním modelem pro protisměrné vyhledávání s tím, že hledáme protisměrně příponu vzorku v textu, která se ve vzorku opakuje, je redukovaný sufixový automat. Redukce spočívá v tom, že ze sufixového automatu ponecháme jen ty stavy, které leží na páteři automatu a ostatní stavy a s nimi související přechody vynecháme.
8.1
Přesné protisměrné vyhledávání jednoho vzorku
Nejdříve uvedeme nejjednodušší metodu protisměrného vyhledávání. Jedná se o BMH (Boyer–Moore–Horspool) algoritmus, který používá heuristiku nazývanou „bad character shiftÿ. Výpočet posuvů se v tomto případě provádí velmi jednoduše a to tak, že posun se vypočítá pro jednotlivé symboly abecedy a je roven vzdálenosti výskytu symbolu ve vzorku od konce vzorku. Příklad 8.1 Je dán vzorek P = abcaba. Určeme tabulku posunů pro abecedu A = {a, b, c, d} pro BM H algoritmus. Dále provedeme vyhledávání v textu T = bcbaabcabab. Nejdříve sestrojíme nedeterministický faktorový automat pro reverzovaný vzorek P R . Jeho přechodový diagram je na obr. 8.1. Pro vý-
a 6
b a
5
c b
a c
4
3
b a
2
b
1
a
0
START
Obrázek 8.1: Nedeterministický faktorový automat pro vzorek P R = abacab počet posuvů stačí sestrojit první řádek tabulky přechodů deterministického konečného automatu: 0
a 136
b 25
c 4
Z této tabulky vybereme pro každý symbol stav s nejmenší vzdáleností od konce vzorku větší než 1 a odečteme jedničku. Tím dostaneme velikost posuvu pro daný symbol. Výsledkem je tabulka posuvů: symbol posuv
a 2
b 1 87
c 3
Pro symboly abecedy, které se ve vzorku nevyskytují je posuv roven délce vzorku. V našem případě je posuv pro symbol d roven 6. Celý tento postup můžeme zapsat ve formě programu takto: (1) f or symbol := symb[1] to symb[|A|] do posuv [symbol] := m; (2) f or j := 1 to m − 1 do posuv [P [j]] := m − j; Proveďme výpočet posuvů pro zadaný vzorek P = abcaba. počáteční cykl(2) nastavení (1) j = 1 j = 2 j = 3 j = 4 j = 5 6 5
2 6 4
1 6
3
6
a b c d
Kroužky označují vypočtenou hodnotu posuvů pro jednotlivé symboly. Nyní provedeme vyhledávání vzorku P = abcaba v textu T = bcbaabcabab. bcbaabcabab abcaba
neshoda posuv[b]=1
bcbaabcabab abcaba
neshoda posuv[c]=3
bcbaabcabab abcaba
shoda posuv[a]=2
V tomto okamžiku se má provést posuv až za konec textu a proto vyhledávání končí. Příklad 8.2 Je dán vzorek P = babba. Sestrojme redukovaný sufixový automat pro reverzovaný vzorek P R = (babba)R = abbab. Nedeterministický sufixový automat pro vzorek abbab je na obr. 8.2. Jeho deterministický ekvivalent je na b a b b 5
b
4
a
3
b
2
b
1
a
0
START
Obrázek 8.2: Nedeterministický sufixový automat pro vzorek P R = abbab obr. 8.3. Deterministický sufixový automat pro vzorek abbab ukazuje tyto skutečnosti: 88
5
b
4
a
3
b
a
25
b
b
14
a
0
START
b 235
Obrázek 8.3: Deterministický sufixový automat pro vzorek P R = abbab a) sufix a se opakuje na pozicích 1 a 4, b) sufix ab se opakuje na pozicích 2 a 5, c) faktor b se opakuje na pozicích 2,3 a 5. Z hlediska naší úlohy nás zajímá pouze opakování těch faktorů, které jsou předponami reverzovaného vzorku, t.j. příponami původního vzorku. V našem případě se jedná o faktory (přípony) a a ab. Proto vynecháme stav 235 a získáme potřebný redukovaný sufixový automat (RSA). Jeho přechodový diagram je na obr. 8.4. K jednotlivým stavům RSA jsou doplněny délky 5 3
b
4 3
a
3
b
25
3
3
b
14 5
a
0
START
1
Obrázek 8.4: Redukovaný sufixový automat pro vzorek P R = abbab posuvů. Tyto posuvy se provedou v okamžiku, kdy protisměrné vyhledávání skončí v příslušném stavu. Postup při výpočtu jednotlivých posuvů je shrnut v tab. 8.1. Porovnejte vypočtené posuvy s postupem při protisměrném vyhledávání předpon vzorku! 2 Příklad 8.3 Je dán vzorek P = ababa. Sestrojme reverzovaný sufixový automat a vypočtěte délky posuvů. Přechodové diagramy příslušných automatů jsou na obr. 8.5. Z výsledného automatu je zřejmé, že ve vzorku jsou předponou i příponou řetězce a a aba. Podle toho jsou určeny i posuvy. 2 Příklad 8.4 Je dán vzorek P = aabaa. Sestrojme RSA a vypočtěme délky posuvů. Přechodové diagramy jsou na obr. 8.6. Tento vzorek má opět dvě přípony a a aa, které jsou předponami. Podle nejdelší přípony se určí délka posuvu ve stavech 25,3,4,5. Posuv ve stavu 0 je 2, protože poslední symbol vzorku se opakuje jako předposlední. Ve stavu 1245 je posuv 1, protože nalezený 89
Stav 0
Posuv 1
1
5
2
3
3,4,5
3
Způsob výpočtu První srovnání bylo neúspěšné, v textu je jiný symbol než a. Posuneme o jednu pozici doprava, protože předcházející symbol ve vzorku je jiný než a. Byla nalezena přípona vzorku a a před ní není symbol b. Posuv se provede o celou délku vzorku (5) protože řetězec xa, kde x 6= b se ve vzorku neopakuje. Byla nalezena přípona vzorku ba, která je jeho předponou a nikde jinde se ve vzorku neopakuje. Posuv se provede o rozdíl délky vzorku a délku přípony (5-2=3). Nejdelší nalezená přípona, která je předponou má délku 2. Posuv se provede o rozdíl délky vzorku a nejdelší nalezené přípony (5-2=3).
Tabulka 8.1: Výpočet posuvů při protisměrném vyhledávání opakujících se přípon řetězec a se ve vzorku opakuje s jiným levým kontextem ve vzdálenosti 1. 2 Příklad 8.5 Je dán vzorek P = bbaba. Sestrojme RSA a vypočtěme délky posuvů. Přechodové diagramy jsou na obr. 8.7 V tomto případě žádná přípona vzorku není jeho předponou. Dvě přípony a a ba jsou faktory vzorku. Přípona a se ve vzorku opakuje, ale se stejným levým kontextem. Proto může ve stavu 13 být posuv o 5. Přípona ba se opakuje s jiným levým kontextem a proto je ve stavu 24 posuv o 2 (4-2=2). Žádná další přípona se neopakuje a proto posuv ve stavech 3,4,5 je o délku vzorku. 2 Příklad 8.6 Je dán vzorek P = babaa. Sestrojme RSA a vypočtěme délky posuvů. Přechodové diagramy jsou na obr. 8.8. V tomto případě se přípona a ve vzorku třikrát opakuje. Opakování tohoto faktoru je na pozici 2 a 4 s jiným levým kontextem než a na pozici 1. Proto je posuv ve stavu 124 k jeho nejbližšímu opakování, t.j. 1. Posuv ve stavu 0 je roven dvěma, protože a se opakuje na předposledním místě. Ve stavech 2,3,4,5 je posuv roven délce vzorku. 2 Příklad 8.7 Je dán vzorek P = aaaaa. Sestrojme RSA a vypočtěme délky posuvů. Přechodové diagramy jsou na obr. 8.9. Je vidět, že všechny přípony jsou současně předpony a proto jsou posuvy od 5 do 1. 2
90
a b a b 5
5
a
4
a
4
2
b
3
b
35
2
a
b
2
a
b
24
2
4
1
135
a
a
4
0
0
START
START
1
Obrázek 8.5: Nedeterministický a deterministický redukovaný sufixový automat pro vzorek P R = ababa
a a b a 5
5 3
a
a
4
4 3
a
a
3
3
b
b
2
25
3
3
a
a
1
1245 1
a
a
0
0
START
START
2
Obrázek 8.6: Nedeterministický a deterministický redukovaný sufixový automat pro vzorek P R = aabaa
91
b b a b 5
5
b
4
b
4
5
b
3
b
3
5
a
b
2
a
b
24
5
2
1
13
a
a
5
0
0
START
START
1
Obrázek 8.7: Nedeterministický a deterministický redukovaný sufixový automat pro vzorek P R = bbaba
b a b a 5
5 5
b
b
4
4 5
a
a
3
3
b
2
b
2
5
5
a
a
1
124 1
a
a
0
0
START
START
2
Obrázek 8.8: Nedeterministický a deterministický redukovaný sufixový automat pro vzorek P R = aabab
92
a a a a 5
5 1
a
a
4
45 1
a
a
3
345
a
a
2
2345
2
3
a
a
1
12345 4
a
a
0
0
START
START
5
Obrázek 8.9: Nedeterministický a deterministický redukovaný sufixový automat pro vzorek P R = aaaaa
93
8.2
Protisměrné vyhledávání konečné množiny vzorků
Příklad 8.8 Je dána množina vzorků S = {bbaba, babaa}. Abeceda A = {a, b}. Sestrojme RSA pro tuto množinu a vypočtěme posuvy. Přechodové diagramy jsou na obr. 8.10. Přechodová tabulka deterministického RSA je v tab. 8.2. b b a b 51
b
41
b
31
a
21 b
a
1
0
START
a 52
b
42
b
32
a
22
a
b a
b
51
b
1
4152
b
1
3142
a
21324152
3
2
b 12 2 3 1 4 2 a
52 5
b
42 5
a
32
b
5
a
0
START
1
22
5
5
Obrázek 8.10: Nedeterministický a deterministický redukovaný sufixový automat pro množinu vzorků S R = {bbabaR , babaaR } V této tabulce jsou uvedeny jen přechody RSA. Vynechané přechody jsou označeny ?. V tab. 8.3 je shrnut postup výpočtu jednotlivých posuvů. 2
94
a b 0 122 31 42 21 32 41 51 52 122 31 42 22 21 32 41 52 21 32 41 52 31 42 ? 31 42 ? 41 52 41 52 ? 51 22 ? 32 32 42 ? 42 ? 52 Tabulka 8.2: Přechodová tabulka deterministického RSA
Stav 0
Posuv 1
122 31 42
?
21 32 41 52
2
31 42
3
41 52 51 22 32 41
1 1 5
52
5
Postup výpočtu Symbol a se na předposledním místě ve vzorku bbaba neopakuje, ale opakuje se na předposlední pozici vzorku babaa Posuv není definován, protože vždy je možný přechod do dalšího stavu Přípona ba se opakuje s jiným levým kontextem v témže vzorku (bbaba) o 2 pozice vlevo (41 − 21 = 2). Přípona aba se neopakuje s jiným levým kontextem než b nikde, ani není předponou. Kratší předpona má délku 2. Přípona baba je předponou vzorku babaa (5-4=1) Nejdelší kratší předpona má délku 4. (5-4=1) Žádná z přípon aa, baa, abaa se neopakuje, ani není předponou Žádná přípona vzorku babaa není předponou žádného vzorku
Tabulka 8.3: Výpočet posuvů při protisměrném vyhledávání opakujících se přípon
95
9
Indexové metody
Informační systémy zpracovávají kolekce dokument˚ u. Na základě dotazu uživatele vybírají dokumenty, které nejlépe vyhovují požadavk˚ um zadavatele. Aby se dosáhla rychlá odezva informačního systému jsou dokumenty předzpracovány. Pro předzpracování dokument˚ u se využívá indexace. Výsledkem indexace je index, který se používá pro vyhodnocování dotaz˚ u. Z hlediska úplnosti dělíme indexy na indexy úplné a neúplné(slovní indexy). Úplný index umožňuje vyhledávat všechny podřetězce daného textu. Používá se hlavně pro jednotlivé dokumenty, popř. jejich malou sadu. Je vhodný pro nestrukturované texty, binární data, DNA sekvence. Není vhodný pro rychle se měnící dokumenty, či jejich sady. Pro vytváření úplných index˚ u se používají tyto modely: • faktorový automat, • suffixový automat, • suffixový strom, • kompaktní suffixový strom, • uspořádané pole přípon (Suffix Array ). Pro vytváření neúplných index˚ u se používají tyto modely: • uspořádané pole slov (Suffix Array ), • supra index, • indexový strom (index tree), • slovní indexy, booleovský a vektorový model, • signatury. Neúplné indexy se obvykle vytvářejí pro množinu dokument˚ u. Tyto dokumenty jsou napsány v přirozeném jazyce, skládají se ze slov. Neúplné indexy umožňují zpracovávat velké množství, rychle se měnících sad dokument˚ u. Dotaz do vyhledávacího systému s neúplným indexem je předzpracován a poté předložen k vyhodnocení. Během předzpracování dotazu m˚ uže být použit lematizátor a thesaurus. Indexace m˚ uže být řízená a neřízená. Při řízené indexaci je známa množina term˚ u, podle kterých se indexuje. Indexace pak přiřazuje každému dokumentu množinu term˚ u (slov), které jej charakterizují. Při neřízené indexaci není množina term˚ u dopředu známá a se zvětšujícím počtem dokument˚ u m˚ uže r˚ ust. Při obou zp˚ usobech indexace existuje množina slov, která nemají pro vyhledávání význam. Tento seznam se označuje pojmem stop list a tvoří jej nevýznamná slova jako jsou členy, předložky, spojky, částice, pomocná a zp˚ usobová slovesa a podobně. 96
Z hlediska vytváření indexu lze indexaci rozdělit na ruční a automatickou. Při ruční indexaci vytváří seznam term˚ u specialista. Nevýhodou tohoto systému je jeho subjektivita a problémy spojené s dynamickým nár˚ ustem množství zpracovávaných dat. Dalším významným faktorem ovlivňujícím výslednou kvalitu dokumentografického informačního systému je výběr term˚ u pro indexaci. Pro indexaci nejsou vhodné termy, které se v dokumentech vyskytují velmi zřídka, protože neúměrně zvyšují velikost výsledného indexu. A naopak, ani příliš často se opakující termy nejsou vhodné, neboť mají slabou selektivní schopnost. Termy jako základ pro vyhledávání používají booleovské a vektorové informační systémy. Jejich realizace úzce souvisí s definicí dotaz˚ u a bude podrobněji popsána v kapitole věnované dotazovacím jazyk˚ um. Speciálním případem indexace je indexace pomocí signatur, která předzpracovává text i vzorek. Jde o nepřesnou metodu, neboť určuje pro daný dokument pouze zda m˚ uže či nem˚ uže dané termy obsahovat. Signatury se proto používají jako prostředek pro rychlé omezení množiny dokument˚ u, které mohou daný vzorek obsahovat.
9.1
Faktorové automaty
Řetězec P = p1 p2 . . . pm je podřetězcem řetězce T = t1 t2 . . . tn , právě tehdy když existuje nezáporné číslo i takové, že p1 = ti + 1, p2 = ti + 2, . . . pm = ti + m. Řetězec P nazýváme faktorem řetězce T . Číslo i označuje pozici faktoru P v textu T . Faktorový automat textu T je minimální deterministický automat, který přijímá množinu všech faktor˚ u daného textu. Příklad 9.1 Zkonstruujte faktorový automat pro text T = acbaccac. V první fázi sestrojíme automat přijímající celý text T . Tento automat rozšíříme o ε přechody a všechny stavy označíme za koncové. Tento automat je na obrázku 9.1. Odstraněním ε přechod˚ u vznikne nedeterministický automat - 9.2.
Obrázek 9.1: Nedeterministický faktorový automat pro text T = acbaccac Tento automat má tabulku přechod˚ u:
97
Obrázek 9.2: Nedeterministický faktorový automat bez ε přechod˚ u pro text T = acbaccac
0 1 2 3 4 5 6 7 8
a 1,4,7 4 7 -
b 3 3 -
c 2,5,6,8 2 5 6 8 -
Tento automat je nedeterministický, protože například ze stavu 0 existuje více přechod˚ u pro symbol a(do stav˚ u 1,4,7). Tento nedeterminismus odstraníme vytvořením nového stavu - označme jej [1,4,7]. Přechody pro tento stav vzniknou sloučením řádk˚ u pro stavy 1,4,7. Postupně vznikne nová tabulka přechod˚ u: 0 [1,4,7] [2,5,6,8] [2,5,8] 3 4 5 6 7 8
a [1,4,7] 7 4 7 -
b 3 3 3 -
c [2,5,6,8] [2,5,8] 6 6 5 6 8 -
Tento automat je minimální, protože neobsahuje žádné ekvivalentní stavy. Jeho přechodový diagram je znázorněn na obrázku 9.3. Příklad 9.2 Pomocí faktorového automatu z předchozího příkladu určete, zda řetězce P1 = acbacc,P2 = abacb a P3 = ac jsou faktory textu T . V případě, že ano, určete všechny pozice, na kterých se nacházejí. 98
Obrázek 9.3: Faktorový automat pro text T = acbaccac. Příklad 9.3 Navrhněte automat, který přijímá řetězec P = abba a všechny řetězce, které se od něj liší maximálně jednou záměnou, tj. kHam = 1. Pomocí pr˚ uniku automat˚ u nalezněte všechny výskyty těchto řetězc˚ u v textu z příkladu 9.1.
9.2
Suffixový automat
Suffixový automat textu T je minimální deterministický automat příjímající všechny přípony textu T . Konstrukce automatu je obdobná postupu pro faktorový automat,ale edeterministický automat s ε přechody bude mít koncové pouze první a poslední stav.
9.3
Suffixový strom
Příklad 9.4 Pro text T = acbaccac sestrojte suffixový strom. Strom je na obrázku 9.4.
Obrázek 9.4: Suffixový strom pro text T = acbaccac.
9.4
Kompaktní suffixový strom
Kompaktní suffixový strom (Patricia tree) lze vytvořit ze suffixového stromu vypuštěním všech stav˚ u, které mají pouze jeden výstupní přechod. Přechody 99
mezi stavy jsou ohodnoceny řetězci symbol˚ u místo jednotlivých symbol˚ u. Tyto řetězce jsou podřetězci textu T a mohou být kódovány pozicí začátku a konce v textu T . Příklad 9.5 Pro text T = acbaccac sestrojte kompaktní suffixový strom. Strom je na obrázku 9.5.
Obrázek 9.5: Kompaktní suffixový strom pro text T = acbaccac.
9.5
Pole přípon – Suffix Array
Pro vyhledávání v textu, kdy je počet vyhledávání veliký, text je statický nebo jsou kladeny vysoké nároky na rychlost vyhledávání jsou s výhodou používány metody, které předzpracovávají text. Tyto metody vytváří index umožňující zrychlený přístup k hledaným částem textu. Jako příklad indexační struktury, která není založena na automatech uvedeme pole přípon - suffix array. Suffix array je pole všech přípon seřazených v uspořádání umožňujícím efektivní vyhledávání, tj. abecední uspořádání. Protože všechny přípony textu jsou jednoznačně identifikovatelné pomocí jejich počátku v textu, jsou pro identifikaci použity odkazy do textu. Text je nutné uchovávat ve fázi konstrukce suffixového pole i ve fázi vyhledávání. Příklad 9.6 Vytvořme suffix array pro text T=acagac#. Text je doplňen speciálním znakem označujícím konec textu, tento znak není součástí vstupní abecedy, nevyskytuje se v textu. V abecedním uspořádání je za všemi symboly vstupní abecedy. Pro text délky n je suffix array pole délky n+1, kde každá položka odpovídá nějaké příponě textu. První položka odpovídá příponě, která je v abecedním uspořádání první, druhá položka odkazuje na příponu, která je druhá, atd. Inicializace pole se provede ve vzestupném pořadí indexy 0 - n. 100
První položka tak odpovídá nejdelší příponě, tedy SA[0] = acagac#, SA[1] = cagac#, SA[2] = agac#, SA[3] = gac#, atd, poslední položka odpovídá nejkratšímu suffixu SA[6] = #. (tato položka z˚ ustane i po uspořádání na posledním místě, nemá vliv na vyhledávání a někdy se neuvažuje. Pak má suffix array délku n.) Nyní musíme přeorganizovat pořadí suffix˚ u tak, aby splňovali požadavek abecedního uspořádání. 0 4 2 a a a c c g a # a g c a # c #
1 c a g a c
5 c #
3 g a c
6 #
#
#
Obrázek 9.6: Suffixové pole pro text T = acagac# Výsledek uspořádání je na obrázku : Konstrukční fáze odpovídá uspořádání položek pole délky n+1, tedy O(n*log2 n)1 při použití metody třídění merge-sort. Tato metoda zvýší nároky na uložení pomocného pole pro vytváření suffix array z (n + 4*n) - p˚ uvodní text + index, každý index na 42 bajty - na celkovou velikost 9*n - ještě jedno pole index˚ u. Zjištění zda vzorek délky m je obsažen v textu T s použitím suffix array je úloha řešitelná v čase O(m*log n) pomocí binárního p˚ ulení. Tuto metodu je možné zrychlit s vylepšením algoritmu na hodnotu O(m+log n). Pro vylepšení algoritmu se využívá informace o délce shodné předpony levé a pravé hranice prohledávané části pole. Tyto informace lze získat během kostrukce suffixového pole. Suffix array je struktura oblíbená mezi programátory, neboť umožňuje výrazné urychlení proti metodám bez předzpracování textu a cena - čas nutný k naprogramování - je velice nízká. Celá konstrukce je možná pomocí volání standartní C funkce qsort implementující quick-sort. qsort(SuffArr, arraylegth, sizeof(SuffArr[0]), sortfunction); SuffArr je pole, v němž jsou inicializovány odkazy, jeho délka je arraylength a funkce porovnávající dva řetězce od pozice SuffArr[a] a SuffArr[b] je sortfunction. Obdobně vyhledávání daného vzorku je možné pomocí funkce bsearch. 1 konstrukci suffix array lze zrychlit na čas O(n) na O(n) prostoru, ale pouze při použití složitějších struktur jako jsou suffix trees 2 Magické číslo 4 je dáno obvyklou velikostí typu ukazatel. Nejdelší indexovatelný soubor m˚ uže obsahovat 232 symbol˚ u.
101
velikost pole 14 6 3 3
dolní hranice 0 0 3 1
index v suff. poli 7 3 5 4
odkaz do textu 7 1 10 6
srovnávaný vzorek aaac aaac aaac aaac
srovnávaný text aag . . . aaab . . . aaa# aaag . . .
Tabulka 9.1: Vyhledávání vzorku P = aaac v textu T = aaaabaaaagaaa# pomocí suffixového pole. Příklad 9.7 Vytvořte suffix array pro text T = aaaabaaaagaaa#. Zjistěte zda vzorek P = aaac je obsažen v textu T, použijte algoritmus binárního p˚ ulení pro suffix array. Inicializace: SuffArray = 0 1 2 3 4 5 6 7 8 9 10 11 12 13 Obrázek 9.7 ukazuje suffixové pole po uspořádání. Každá položka reprezentuje zobrazený řetězec. Šipky reprezentují jednotlivé kroky při vyhledávání vzorku P = aaac binárním p˚ ulením.
Obrázek 9.7: Suffixové pole pro text T = aaaabaaaagaaa# a vyhledávání vzorku P = aaac Během vyhledávání si potřebujeme pamatovat velikost a dolní hranici části pole, v kterém hledáme vzorek. Příklad 9.8 Pro text T = acbaccac sestrojte suffixové pole. Výsledek je na obrázku 9.8.
102
Obrázek 9.8: Suffixové pole pro text T = acbaccac.
9.6 9.6.1
Slovní indexy Uspořádané pole slov
Příklad 9.9 Mějme dokument obsahující následující text: Na základě dotazu uživatele vybírají dokumenty, které nejlépe vyhovují požadavk˚ um zadávajícího uživatele. Vytvořte pro tento text uspořádané pole slov. Nejprve určíme množinu slov vhodných k indexaci. Tato množina bude : {dotaz, uživatel, dokument, požadavek}. Jednotlivé pozice vybraných slov jsou v následujícím textu označeny indexy: Na základě 12 dotazu 19 uživatele vybírají 38 dokumenty, které nejlépe vyhovují 72 požadavk˚ um zadávajícího 96 uživatele. Výsledné uspořádané pole slov je na obrázku 9.9. 38
12
72
19
96
Obrázek 9.9: Uspořádané pole slov.
9.6.2
Indexový strom
Příklad 9.10 Pro text z příkladu 9.9 vytvořte indexový strom. Výsledný indexový strom je na obrázku 9.10. 9.6.3
Booleovské informační systémy
Booleovské informační systémy vznikly jako první systémy ného knihovnictví. Umožňují zpracovávat dotazy obsahující and, or a not. Problematické je měření relevance odpovědi, oleovský model vhodný pro zpracování dotaz˚ u, na které je mnoho dokument˚ u. 103
automatizovalogické spojky proto není bovybráno příliš
u d
uivatel: 19, 96
p poadavek: 72
o k
t dotaz: 12
dokument: 38
Obrázek 9.10: Indexový strom. Každý dokument je v booleovském informačním systému reprezentován množinou term˚ u, které jej nejlépe charakterizují. Protože jsou v dotazech uvedeny jednotlivé termy, je vhodné, aby byl index reprezentován pořadí. Pak jsou k jednotlivým term˚ um přiřazeny množiny dokument˚ u, v kterých je příslušný term obsažen. Tento index se označuje jako invertovaný indexový soubor. Příklad 9.11 Mějme čtyři články s názvy R˚ ust cen ropy na světových trzích, Palivová soustava diesselových motor˚ u, Výroční cena řidička roku a Ceny povinného ručení. Označme tyto dokumenty po řadě D1 , D2 , D3 a D4 . Indexátor nám vybral pro dokument D1 tyto charakterizující termy: {benzín,nafta,cena}, pro D2 termy {automobil,nafta}, pro D3 termy {řidič,cena} a pro D4 termy {automobil,cena}. Sestrojte invertovaný soubor pro tuto množinu dokument˚ u. Invertovaný soubor má tuto podobu: Term automobil benzín cena nafta řidič
Množina dokument˚ u D2 ,D4 D1 D1 ,D3 ,D4 D1 ,D2 D3
Jiná jeho realizace m˚ uže být pomocí matice bit˚ u o velikosti m × k, kde m je počet term˚ u a k je počet dokument˚ u. Každý prvek této matice určuje, zda term je pro dokument charakterizující (hodnota 1) či není (hodnota 0). Výsledná matice má tvar:
0 1 1 1 0
1 0 0 1 0
0 0 1 0 1
104
1 0 1 0 0
Na zp˚ usobu implementace závisí systém vyhodnocení dotaz˚ u obsahujících logické operátory. První zp˚ usob, kdy je invertovaný soubor implementován jako zřetězený seznam, realizuje operaci and pr˚ unikem množin odpovídajících operand˚ um, operace or je realizována sjednocením a operace not doplňkem do množiny všech dokument˚ u. Tyto operace urychlí setřídění dokument˚ u a reprezentace množin jako setříděných seznam˚ u. Implementace založená na bitových vektorech příslušejících ke každému termu realizuje logické operace and, or a not pomocí odpovídajících bitových operací nad vektory operand˚ u. Příklad 9.12 V booleovském informačním systému z předchozího příkladu sestavte dotaz na to, jak se projeví typ pohonné směsi na cenu vozu. Využijte pouze termy z IS. Výpočet proveďte pro realizaci zřetězeným seznamem i bitovými vektory. Dotaz by mohl mit podobu: (benzin or nafta) and cena and automobil Vyhodnocením dotazu dostaneme množinu dokument˚ u: ({D1 } ∪ {D1 , D2 }) ∩ {D1 , D3 , D4 } ∩ {D2 , D4 } = ∅ resp. ((1 0 0 0) or (1 1 0 0)) and (1 0 1 1) and (0 1 0 1) = (0 0 0 0) Výsledkem dotazu je prázdná množina dokument˚ u. To m˚ uže být zp˚ usobeno více faktory: • špatně položený dotaz • neexistence relevantního dokumentu v databázi • nevhodný informační systém Předpokládejme, že v databázi existuje dokument odpovídající našemu požadavku a přetvořme dotaz. Nový dotaz m˚ uže mít podobu: benzin or nafta or cena or automobil Vyhodnocením tohoto dotazu dostaneme množinu dokument˚ u: {D1 } ∪ {D1 , D2 } ∪ {D1 , D3 , D4 } ∪ {D2 , D4 } = {D1 , D2 , D3 , D4 } Nastal druhý extrémní případ, kdy množina dokument˚ u je příliš velká. Standardní booleovský model informačního systému neposkytuje uspořádání v množině výsledk˚ u dotazu, všechny dokumenty se zdají být stejně významné. Toto se dá částečně kompenzovat zavedením uspořádání do výsledku dotazu. Příklad 9.13 Mějme dotaz v booleovské logice Q = (t1 or t2 ) and t3 . Výraz převedeme do disjunktivně normální formy (DKNF): Q = (t1 and t2 and t3 ) or (not t1 and t2 and t3 ) or(t1 and not t2 and t3 ). Každý z uzávorkovaných výraz˚ u definuje množinu jemu odpovídajících term˚ u. Tyto množiny jsou disjunktní a jejich sjednocení odpovídá množině 105
Operátor t1 (m,n) t2 t1 sentence t2 t1 paragraph t2
Význam term t2 se vyskytuje v dokumentu nejdále m slov za t1 , nebo se term t1 vyskytuje nejdále n slov za termem t2 termy t1 a t2 se vyskytují ve stejné větě termy t1 a t2 se vyskytují ve stejném odstavci
Tabulka 9.2: Operátory vyjadřující požadavky na vzájemnou polohu term˚ u v dokumentu. relevantních dokument˚ u. Každou tuto množinu m˚ užeme ohodnotit počtem pozitivních term˚ u v příslušné elementární konjunkci. Pro náš krátký dotaz dostaneme ohodnocení 3,2,2, které nám umožní uspořádat dokumenty do dvou tříd podle relevance. Příklad 9.14 Vytvořte ohodnocení dokument˚ u pro dotaz: Q = (t1 or t2 or t3 ) and (t4 or t5 ) and t6 9.6.4
Rozšíření dotaz˚ u v booleovském DIS
Dotazem v booleovském IS nazveme logický výraz termy a operátory and, or a not, např.: Q1 = automobil and (benzín or nafta). Tento systém bývá rozšířen o možnost zadávání víceslovných term˚ u, např.: Q2 = ’nový automobil’ and (benzín or nafta). Dalším rozšířením poskytujícím lepší odezvu (recall - množství dokument˚ u vyhodnocených jako relevantních) je použití zástupných znak˚ u (wildcards) ’∗’ a ’?’, např.: Q3 = nov? automobil∗. Symbol ∗ nahrazuje libovolný řetězec i nulové délky, symbol ? nahrazuje právě jeden znak. Některé dotazovací jazyky (rozšíření SQL v systému ORACLE) používají místo symbolu ∗ symbol %. Dotazu Q3 odpovídá množina term˚ u obsahujících termy nový, nová, nové, automobil, automobily, automobilový atd. Dotazy obsahující zástupné znaky se převádějí na dotazy bez nich tak, ze každý term se zástupným znakem je nahrazen disjunkcí vyhovujících term˚ u. Pro vyjádření vzájemné polohy dvou term˚ u v dokumentu dovolují některé vyhledávací jazyky použití operátor˚ u vyjadřujících proximitní omezení. Jejich přehled shrnuje tabulka 9.2. Další snahou o zlepšení vyhodnocovacích schopností DIS je zavedení vnitřní struktury v indexu - tezauru. Pro práci s tezaurem se používají operátory uvedené v tabulce 9.3.Mimoto se tezaurus používá pro automatické rozšíření dotazu. 106
Operátor BT(t) NT(t) PT(t) SYN(t) RT(t) TT(t)
Význam broader term, širší term k termu t narrowed terms, užší termy k termu t preferred term, doporučovaný term k termu t synonyms, synonyma k termínu t related terms, příbuzné termy k termu t top term, nejširší termín
Tabulka 9.3: Operátory pro práci s tezaurem v systému Oracle TextRetrieval 9.6.5
Vektorové informační systémy
Vektorové informační systémy reprezentují každý dokument pomocí vektoru, kde každá složka definuje míru d˚ uležitosti odpovídajícího termu pro identifikaci dokumentu. Dokument Di , i ∈ {1, 2, . . . , m}, je charakterizován vektorem − → Di = [wi,1 , wi,2 , . . . , wi,n ], kde wi,j ∈ h0, 1i je váha termu tj , j ∈ {1, 2, . . . , n}, v dokumentu Di . Indexový soubor je reprezentován maticí
D=
w1,1 w2,1 .. .
w1,2 w2,2 .. .
... ... .. .
w1,n w2,n .. .
wm,1 wm,2 . . . wm,n
Dotaz ve vektorovém modelu je vektor − → Q = [q1 , q2 , . . . , qn ], kde qi ∈ h0, 1i. Pro určení míry relevance dokumentu vzhledem k dotazu se zavádí koeficient podobnosti (angl. similarity) n X − → − → qk ∗ wi,k Sim( Q , Di ) = k=1
Tento vzorec představuje skalární součin obou vektor˚ u, − → − → − → − → − → − → Sim( Q , Di ) = Q · Di = | Q | · |Di | · ϕ, kde ϕ je úhel sevřený oběma vektory. Je-li ϕ = π2 , vektory jsou na sebe kolmé(nemají jediný společný term), výsledek nulový. Velikost koeficientu podobnosti je nepříznivě ovlivněna velikostmi vektor˚ u, zvláště dlouhé dokumenty mající mnoho r˚ uzných slov a tím mnoho nenulových pozic pro jednotlivé termy jsou zvýhodněny před kratšími dokumenty. Tento problém 107
lze řešit normalizací vektor˚ u, nebo úpravou předpisu pro výpočet koeficientu podobnosti. Normalizovaný vektor se vypočítá podle vzorce: − → − → Di Di − → q = Di, = − → Pn 2 |D i | k=1 wi,k Velikost normalizovaného vektoru je jedna. Další možností je vytvoření nového předpisu pro koeficient podobnosti. Jedním z nich je kosínová míra, která vyjadřuje velikost úhlu mezi srovnávanými vektory: Pn − → − → Q · Di − → − → k=1 qk ∗ wi,k qP Simcos ( Q , Di ) = − → − → = qPn n 2 · 2 | Q | · |Di | w k=1 k=1 q i,k
k
Je lehko ověřitelné, že pro normalizované vektory je − → − → − → − → Sim( Q , Di ) = Simcos ( Q , Di ). Příklad 9.15 Mějme sadu citát˚ u od Jana Wericha: 1. B˚ uh stvořil člověka, ale nedal si to patentovat, a tak to teď po něm m˚ uže dělat kdejakej blbec. 2. Na světě je zavedeno, že spousta hloupých si hraje na chytré. Z chytrých, kterých je na světě nedostatek, jen ti nejchytřejší si hrají na hloupé. . . 3. Humor je boj s lidskou hloupostí. V tomto boji nem˚ užeme nikdy vyhrát. Ale nikdy v něm nesmíme ustat. Ovšem pozor na zmýlenou. Ten koho považujeme za blbce, považuje za blbce nás. Jde o to se nevyvraždit. 4. Smích není nikdy pro nic a za nic, snad jen u šílených lidí. Normální člověk musí mít d˚ uvod, směje se něčemu. 5. Kdo víno má a nepije, kdo hrozny má a nejí je, kdo ženu má a nelíbá, kdo zábavě se vyhýbá, na toho vemte bič a h˚ ul, to není člověk, to je v˚ ul. 6. Když už člověk jednou je, tak má koukat, aby byl, a když kouká aby byl a je, tak má být to co je, a ne to co není, jak tomu v mnoha případech je. 7. Jakmile se z mládí začne dělat zásluha, je to špatné. Protože každej blbec - starej - byl taky jednou mladej blbec. 108
8. Ale přemýšlet, a to dá práci, umí jenom část lidstva. Ona část, ona tenoučká vrstva, která válčí s lidskou hloupostí. 9. Kde blb, tam nebezpečno. Vyberte množinu term˚ u pro indexaci. Předpokládejte, že se sada citát˚ u nebude rozšiřovat. Určete množinu term˚ u nevýznamných pro indexaci - stop words. Kvalitní informační systém při zpracování dokument˚ u používá lematizátor. Lematizátor je jednotka, která ke slovu z přirozeného jazyka přiřadí odpovídající term ze slovníku informačního systému. Odpovídajícím termem je obvykle základní tvar, např. popošel −→ jít. Každý term by měl mít selektivní schopnost, měl by být charakteristický pro nemalou a zároveň nevelkou množinu dokument˚ u. V našem případě mohou být pro indexaci vybrána slova: {B˚ uh, člověk, blbec, chytrý, humor, boj, normální, víno, věk, práce}. Termy je nutné chápat ve smyslu významu, který reprezentují. Pak mohou nahrazovat množinu slov, např. term člověk nahrazuje slova člověk, lidský, lidstvo. Do stop listu lze vložit slova ale, si, to, a, tak teď, po, něm, kdejakej, m˚ uže, na, je, že a mnohá další. Příklad 9.16 Ručně zaindexujte citáty z předchozího příkladu. Touto indexací m˚ uže vzniknout například tento index D1 D2 D3 D4 B˚ uh(stvořitel, stvořit) 1 0 0 0 člověk(lidský, lidstvo) 0, 8 0, 2 0, 4 0, 8 blbec(hloupý, šílený, v˚ ul) 0, 7 0, 9 0, 6 0, 7 chytrý 0 0, 9 0 0 humor(smích, zábava) 0 0 0, 8 1 boj(vyhrát, prohrát) 0 0 0, 9 0 normální 0 0 0 0, 7 víno 0 0 0 0 věk(mládí, stáří) 0 0 0 0 práce 0, 1 0 0 0
D5 D6 D7 0 0 0 0, 5 0, 6 0 0, 5 0 0, 9 0 0 0 0, 5 0 0 0 0 0 0 0 0 0, 5 0 0 0 0 0, 9 0 0 0
D8 D9 0 0 0, 9 0 0, 5 0, 6 0 0 0 0 0, 5 0 0 0 0 0 0 0 0, 5 0
Příklad 9.17 Vytvořte dotaz, který bude požadovat citáty o lidské hlouposti. Dotaz by mohl vypadat následovně: lidská hloupost. Pomocí lematizátoru a slovníku jsou oba termy nahrazeny na člověk a blbec. Neuvažujme postavení obou term˚ u v dotazu a přiřaďme jim oběma stejnou váhu, jedna. 109
Dokumenty vrácené IS jako vyhovující, B nevrácené IS, B
vyhovující dotazu A A∩B A∩B
nevyhovující dotazu A A∩B A∩B
Tabulka 9.4: Rozdělení množiny dokument˚ u na základě dotazu Vznikne nám vektor dotazu Q = (0, 1, 1, 0, 0, 0, 0, 0, 0, 0). Míra relevance dokumentu D1 vzhledem k dotazu Q je Sim(Q, D1 ) = 0, 8 ⋆ 1 + 0, 7 ⋆ 1 = 1, 5. Obdobně pro další dokumenty postupně obdržíme hodnoty 1,1; 1; 1,5; 1; 0,6; 0,9; 1,4; 0,6. Příklad 9.18 Vypočítejte koeficienty podobnosti Simcos () pro dotaz z předchozího příkladu. Na základě těchto koeficient˚ u seřaďte citáty podle relevance v˚ uči dotazu. Příklad 9.19 Najděte nejpodobnější citáty k citátu, který nejlépe vyhovoval dotazu z předchozích příklad˚ u. Jako měřítko podobnosti použijte koeficient podobnosti Sim() a Simcos (). Výsledky porovnejte. Přesnost a úplnost Přesnost a úplnost jsou dvě veličiny, které byly zavedeny, aby bylo možné měřit kvalitu odpovědi poskytnuté informačním systémem na položený dotaz. Každý dotaz dělí množinu dokument˚ u na dokumenty, které dotazu vyhovují – A (splňují jeho podmínky, jsou relevantní) a množinu dokument˚ u, které dotazu nevyhovují – A, tedy doplněk množiny A do množiny všech dokument˚ u. Relevanci dokumentu vzhledem k dotazu posuzuje odborník, či zadavatel. Podobně informační systém vyhodnocením dotazu vytvoří množinu dokument˚ u, které vrátí jako odpověď – B. Celou situaci shrnuje tabulka 9.4. Na základě tohoto rozdělení lze definovat měřítka efektivity informačního systému. Přesnost (angl. precision) odpovědi je P =
|A ∩ B| , |B|
úplnost (angl. recall) odpovědi je definována jako R=
|A ∩ B| , |A|
Mezi úplností a přesností je nepřímá úměra, tzn. Pokud zvyšujeme přesnost informačního systému dochází k r˚ ustu počtu relevantních dokument˚ u,
110
hranice 1,25 1,05 0,95 0,85
relevantní dokumenty D2 , D3 , D8 D2 , D3 , D8 D2 , D3 , D8 D2 , D3 , D8
dokumenty vrácené IS D1 , D4 , D8 D1 , D2 , D4 , D8 D1 , D2 , D3 , D4 , D5 , D8 D1 , D2 , D3 , D4 , D5 , D7 , D8
přesnost
úplnost
0,33 0,50 0,50 0,43
0,33 0,66 1 1
Tabulka 9.5: Přesnost a úplnost IS pro dotaz lidská hloupost v závislosti na hranici relevance které IS označí za nevyhovující. Pokud požadujeme vyšší úplnost roste pravděpodobnost, že do množiny vrácených dokument˚ u přijdou i dokumenty, které nejsou relevantní. Příklad 9.20 Mějme dotaz z příkladu 11. Předpokládejme, že odborník na dotaz lidská hloupost vybral dokumenty D2 , D3 a D8 . Informační systém ohodnotil jednotlivé dokumenty koeficiety podobnosti: (1,5; 1,1; 1; 1,5; 1; 0,6; 0,9; 1,4; 0,6. ). Určením hranice rozdělí systém dokumenty na dotazu relevantní a dokumenty dotazu nerelevantní. Změnou této hranice měníme přesnost a úplnost informačního systému vzhledem k dotazu lidská hloupost. Příklad 9.21 Vytvořte obdobnou tabulku k tabulce 9.5 pro koeficient podobnosti z příkladu 12. Tabulka 9.5 ukazuje změnu přesnosti a úplnosti IS na dotaz lidská hloupost.
9.7
Signatury
Signaturové informační systémy umožňují pro danou množinu term˚ u velmi rychlé zmenšení počtu dokument˚ u, které tyto dokumenty obsahují. Toto zmenšení je nepřesné, do množiny výsledných dokument˚ u se dostanou i dokumenty, které dotazované termy neobsahují. Proto je nutné použít na redukovanou sadu dokument˚ u přesné vyhledávání. Signatura Sx textu x je k-bitový řetězec. Vyhledávání množiny term˚ u je realizováno vytvořením jejich signatury Sv a porovnáním se signaturami dokumnet˚ u SD1 , SD2 , . . . , SDm . Aby dokument splňoval všechny požadavky množiny vzorku, musí platit: SD and Sv ≡ Sv Pokud dokument tuto podmínku nesplňuje, je jasné, že dané vzorky neobsahuje. Pokud ji dokument splňuje je ještě nutné ověřit, zda dokument dané vzorky opravdu obsahuje. V praxi se používá jednodušší podmínka: Sv and not SD ≡ 0 111
9.7.1
Přiřazení signatury k jednomu termu
Pro přiřazení signatury k jednomu termu se používají dvě metody: 1. Každému termu odpovídá jeden bit v signatuře. 2. Siganatura termu je vytvořena nějakou hashovací funkcí. Příklad 9.22 Pro každý term z množiny jmen JM = {Josef, Jan, Božena, Alois, Karel} vytvořte jeho signaturu. Použijte hashovací funkci, která každému termu přiřadí jeden bit. Určete signaturu množiny vzork˚ u V = {Jan, Josef}. Výsledná signatura musí obsahovat alespoň pět bit˚ u. Jedna z možných hashovacích funkcí vytváří signatury: term(jméno) Josef Jan Božena Alois Karel
signatura (binární zápis) 10000 01000 00100 00010 00001
Signatura pro množinu vzork˚ u obsahujících jména V = {Jan,Josef} se vytvoří pomocí binárního or pro jednotlivé bity. Výsledná signatura bude SV = 11000. Příklad 9.23 : Pro termy z množiny příjmení P R = {Čapek, Neruda, Němcová, Poláček, Jungman, Jirásek} vytvořte pomocí nějaké hashovací funkce signatury délky pět bit˚ u. Příklad výsledných signatur je uveden v následující tabulce: term(jméno) Čapek Neruda Němcová Poláček Jungman Jirásek
signatura (binární zápis) 10001 01010 00100 00010 01001 00001
Ze signatur jednotlivých term˚ u (nebo jejich skupin) m˚ užeme vytvořit signaturu dokumentu řetězeným kódováním nebo vrstveným kódováním. Příklad 9.24 Vytvořte řetězené signatury autor˚ u A = {Božena Němcová, Karel Čapek, Josef Čapek, Josef Jungman, Karel Poláček}. Využijte signatur vytvořených v příkladu 9.22 a 9.23. Výsledné signatury jsou: 112
Autor Božena Němcová Karel Čapek Josef Čapek Josef Jungman Karel Poláček
Signatura 0010000100 0000110001 1000010001 1000001001 0000100010
Příklad 9.25 Vytvořte vrstvené signatury autor˚ u A = {Božena Němcová, Karel Čapek, Josef Čapek, Josef Jungman, Karel Poláček}. Využijte signatur vytvořených v příkladu 9.22 a 9.23. Výsledné signatury jsou: Autor Božena Němcová Karel Čapek Josef Čapek Josef Jungman Karel Poláček
Signatura 00100 10001 10001 11001 00011
Z výsledné signatury je vidět, že dokumenty, které mají v části věnované autor˚ um Josefa Čapka se neliší od dokument˚ u od Karla Čapka (ani od dokument˚ u obou bratr˚ u). To je daň za úsporu místa při použití vrstvené signatury.
9.8
Indexace a Web
Hlavním posláním informačních systém˚ u je shromažďování informací. Takto shromážděné informace jsou poskytovány uživateli informačního systému. Aby mohl uživatel definovat své požadavky je vytvořena sada pravidel, která definují dotazovací jazyk. Pro účely této podkapitoly budeme označovat soubor všech dosažitelných dokument˚ u pomocí WWW(world wide web) jako webovské stránky, web. Web představuje obrovskou skladovací plochu pro množství informací. Tyto informace se liší formátem (text, HTML, PDF, obraz, multimedia), jazykem, zp˚ usobem vygenerování. Bohužel tato r˚ uznorodost je vykoupena nízkou mírou organizace ukládaných dat. Počet dokument˚ u na webu se velmi rychle zvyšuje, obsahy jednotlivých stránek se rychle mění. Aby bylo možné účelně vyhledávat informace na webu vznikly speciální seznamy odkaz˚ u, umožňující stromové procházení podle oboru a specializace vyhledávané informace. Tyto seznamy si vynucují ruční zpracování, které je subjektivní, pomalé a drahé. Jako druhá možnost vznikají automatické vyhledávací systémy, které se snaží tyto hierarchické seznamy nahradit. Na internet3 vstu3
internet je pojem širší než web, kromě webu obsahuje speciální přenosové služby (posílání pošty, telefonní hovory, videokonference apod.)
113
Stahovače stránek
Ukládací server
URL server
Sklad odkazů
Dekodér URL Indexátor
Skladiště stránek
Barely
Odkazy
Slovník
DOC index
Třídič
PageRank
Vyhledávač
Obrázek 9.11: Anatomie vyhledávače google. puje množství komerčních subjekt˚ u4 , jejichž zájmem je vysoké umístění v žebříčku odpovědí na dotaz, které jim zaručuje životaschopnost. Vyhledávače na webu se snaží o podání reálné informace5 , proto je pochopitelné, že se pokouší detaily své implementace skrýt. Za účelem osvětlení základních princip˚ u využívaných při konstrukci webových vyhledávač˚ u bude nastíněna struktura akademického vyhledávače google z roku 2000. Tento projekt vznikl na univerzite ve Stanfordu, v USA. P˚ uvodní adresa tohoto vyhledávače (http://google.stanford.edu/) je v současné době přesměrována na komerční produkt www.google.com. Trocha historie Technologie vyhledávač˚ u na webu se rozvinula s nár˚ ustem počtu stránek a dokument˚ u přístupných pomocí webu. V roce 1994 jeden z prvních vyhledávač˚ u na webu, World Wide Web Worm, zveřejňuje, že má index čítající 100 000 webových stránek a dokument˚ u. V listopadu 1997 mají přední vyhledávače zaindexováno od 2 (WebCrawler) do 100 milión˚ u dokument˚ u(Search Engine Watch). V prosinci 2002 uvádí google, že má zaindexováno přes 3 miliardy dokument˚ u. V březnu a dubnu roku 1994 World Wide Web Worm zpracovával okolo 1500 dotaz˚ u denně. V roce 1997 uvádí Altavista, že zpracovává okolo 20 000 000 dotaz˚ u denně. Takové množství heterogenních dokument˚ u a nutnost zpracování všech 4
V roce 1993 bylo 1,5% server˚ u na .com doméně, do roku 1997 vzrost podíl server˚ u na této doméně na 60%. 5 Jejich komerční část bývá na hlavní stránce. Uživatel, potenciální zákazník, ji navštíví pouze v případě, že bude s výsledkem vyhledávání spokojen.
114
dotaz˚ u (řádově tisíce za sekundu) v reálném čase si vynucuje speciální strukturu vyhledávače. Kolekce dokument˚ u přístupných pomocí webu není zpracovávána standartními metodami. Množství dokument˚ u si vynucuje použití automatických indexátor˚ u, které musí být navrženy s ohledem na strukturu webových dokument˚ u. Vyhledávač Google využívá dvě základní vlastnosti, které mu pomáhají dosáhnout vysoké přesnosti odpovědí. První využívá propojení mezi stránkami (dokumenty webu) a pro každou stránku určuje ohodnocení (angl. PageRank). Druhou vlastností je využití odkaz˚ u k zlepšení výsledk˚ u vyhledávání. Ohodnocení stránky - PageRank Orientovaný graf odkaz˚ u mezi stránkami (hyperlinks) poskytuje množství informace o významu stránky. Tato vlastnost webových stránek byla staršími vyhledávači opomíjena. Idea vzniku tohoto ohodnocení je následující - ohodnocení stránky je závislé na počtu stránek, které na tuto stránku odkazují. Lze předpokládat, že uživatelé webu si d˚ uležité odkazy vloží do svých stránek. Tím zvýší ohodnocení příslušné stránky a posunou ji ve výsledkové listině v odpovědi na relevantní dotaz. Tento přístup řeší problém s odstraňováním neplatných stránek, neboť se předpokládá, že administrátoři stránek obsah svých stránek kontrolují a neplatné odkazy odstraňují. Ohodnocení stránky A - PR(A) se vypočítá podle vzorce: P R(A) = (1 − d) + d(P R(T1 )/C(T1 ) + . . . + P R(Tn )/C(Tn )), kde d je faktor útlumu(obvykle 0,85), T1 . . . Tn jsou stránky obsahující odkaz na stránku A, C(Ti ) je počet odkaz˚ u na stránce Ti . Ze vzorce je patrné, že příspěvek odkazující stránky zvyšuje její hodnota (stránky odkazované z www.google.com jsou významné) a příspěvek stránky je rozdělen mezi všechny stránky, na které odkazuje. Ohodnocení stránky A je pravděpodobnost, že náhodný ”brousič” (uživatel brouzdající na webu) navštíví stránku A. Faktor útlumu d představuje pravděpodobnost, že je ”brousič” unaven a začne s novým procházením. Text odkazu Text odkazu (anchor text) je velmi charakterizujícím prvkem stránky, na kterou odkazuje. Velmi mnoho vyhledávač˚ u spojuje odkaz na stránku s textem odrážejícím její obsah. Tento popis bývá mnohdy přesnější než popis získaný rozborem stránky. Text odkazu umožňuje zaindexovat i dokumenty, které nemohou být indexovány pro jejich netextovou povahu. V roce 2000 měl vyhledávač Google staženo 24 milión˚ u stránek, na nich našel a zaindexoval 259 milión˚ u text˚ u odkaz˚ u, to je více než 10 odkaz˚ u na stránku.
115
Vedle ohodnocení stránek a text˚ u odkaz˚ u využívá Google i jiných vlastností. Jednou z nich je velikost a tloušťka písma. Slova na stránce, která jsou větším písmem mají vyšší váhu pro popis stránky. Anatomie vyhledávače Google Většina kódu vyhledávače Google je napsána v jazyce C nebo C++ z d˚ uvodu požadavku efektivity a m˚ uže běžet v operačním systému Solaris nebo Linux. Následující schéma znázorňuje strukturu vyhledávače Google. Dokumenty (webové stránky), které chce Google zpracovávat musí nejprve stáhnout. To zajišťují distribuované roboty(pro naši potřebu stahovače), které navštěvují jednotlivé adresy a stahují jejich obsah. Tento obsah předají serveru, který zajistí jednoznačnou identifikaci každého dokumentu(docID) a jeho komprimaci a uložení do skladu dokument˚ u. Každý dokument je následně zpracován indexátorem. Ten dokument rozbalí a analyzuje. Poté je každý dokument převeden na množinu výskyt˚ u slov zvaných hity(angl. hits). Každý hit zaznamenává slovo, jeho pozici v dokumentu a jeho ”váhu” - aproximaci velikosti fontu a umístění slova. Tyto hity ukládá idexátor do sady barel˚ u, čímž vytváří částečně uspořádaný dopředný index. Dále indexátor během analýzy stránky vyhledává všechny odkazy a ukládá o nich informace (odkud a kam vede odkaz, jeho text) do souboru odkaz˚ u. Dekodér URL čte soubor odkaz˚ u a převádí relativní URL na absolutní. Text odkazu vkládá do dopředného seznamu spojeného s identifikátorem dokumentu (docID), na který daný odkaz ukazuje. Dekodér URL dále vytváří databázi propojení, která slouží jako základ pro výpočtu ohodnocení stránky – PageRank. Třídič bere barely uspořádané podle docID a vytvoří invertovaný index, který je uspořádán podle identifikátor˚ u term˚ u. Třídič vytvoří seznam slov spojený s ukazateli do invertovaného indexu. Takto vytvořený slovník je podstoupen vlastnímu vyhledávači. URL server a stahovače jsou napsány v jazyce Python. V roce 2000 používal Google 4 stahovače, které byly schopny stáhnout maximálně 100 stránek za sekundu, což představovalo 600 kB/s. Tento počet snižovalo zpoždění zp˚ usobené pomalou odezvou DNS. Proto měl každý stahovač vyrovnávací paměť DNS. Během procházení webu navštívili stahovače celkem 76,5 miliónu adres, z nichž použil Google 24 milión˚ u stránek pro indexaci. Na těchto adresách nalezl 1,7 miliónu e-mailových adres a 1,6 miliónu adres bylo neplatných (chyba HTTP 404 - File not found). Indexátor zpracovával dokumenty uskladněné v skladišti stánek. Toto skladiště obsadilo 53,5 GB paměti a obsahovalo 147,8 GB rozbalených dat. Pro kompresi dokument˚ u byla použita metoda zlib(varianta algoritmu LZ77), která dosahuje komprimačního poměru 1/3. Na stejných datech by algoritmus bzip (používá aritmetické kódování) dosáhl poměru 1/4, ale rychlost komprese a dekomprese rozhodla pro zlib. Indexátor pro každý výskyt každého termu v každém dokumentu vytvoří záznam, označovaný hit. Struktura hit˚ u bude popsána později. Indexátor 116
ukládá hity do barel˚ u (bylo použito 64 barel˚ u). Umístění hit˚ u v barelech je na základě termu, který reprezentuje, uvnitř barelu jsou hity řazeny podle identifikátoru dokument˚ u (docId), v kterém se dané slovo vyskytuje. Během zpracování stránek indexátor zpracuje odkazy z dané stránky a pro každý odkaz vytvoří záznam do skladu odkaz˚ u. Tento sklad obsadil 6,6 GB paměti. Odkazy jsou základním prvkem nutným pro výpočet ohodnocení stránky PageRank. Každý hit se váže na jeden výskyt nějakého termu v nějakém dokumentu. Jeho délka byla 2B. Hity se dělili na dva typy, standardní a speciální. Speciální hity popisovaly výskyty term˚ u v titulu dokumentu, v textu odkazu, v URL a meta tagu. Odkazy na stránky se většinou nevyskytují v podobě adresy, ale jsou reprezentovány jménem. Převod relativního URL do absolutního provádí dekodér URL. Pro odkazy bylo potřeba 3,9 GB. Dekóder URL vstupuje i do DOC indexu, kde jsou uloženy statistiky týkající se dokumentu, status dokumentu, jeho pozice ve skladišti dokument˚ u, kontrolní součet. Velikost tohoto indexu byla 9,7 GB. Indexátor vytváří slovník. Požadavkem na slovník byla jeho malá velikost(měl 293MB), aby se vešel do operační paměti. Základním úkolem slovníku je k danému termu najít odpovídající identifikátor, tzv. wordId. Použitý slovník obsahoval 14 milión˚ u term˚ u, velmi řídká slova do něj nebyla zařazena. Jazyk vyhledávače Google Každý informační systém poskytuje uživateli informace. Uživatel zadává své dotazy, které informační systém zpracovává. Tyto dotazy mají určitou formu, jsou napsány v nějakém jazyce. Webové vyhledávače mají dotazovací jazyk přizp˚ usobený formě a obsahu dat, které zpracovávají. Standardní vyhledávání předpokládá, že uživatel zadává jednotlivé termy, které chce vyhledat. Předpokládá se propojení odpovídající logické spojce and. Např. Dotaz:Auto Moto. Odpovědí budou všechny dokumenty obsahující slovo auto a slovo moto. Není potřeba vkládat logickou spojku AND. Pokud chceme najít dokumenty obsahující alespoň jedno slovo, auto nebo moto, pak ve vyhledávacím okně zapíšeme: auto OR moto. Dokumenty obsahující obě slova budou vyhodnoceny jako lepší a v žebříčku pořadí odpovědí budou vráceny na vyšším místě. Vyhledání všech dokument˚ u obsahující auto a neobsahující moto zajistí dotaz auto -moto. Při zpracovávání dotazu jsou slova uvedená na stop listu (seznam slov nevýznamných pro vyhledávání) z dotazu vyřazena. Mezi těmito slovy jsou i jednoznakové řetězce. Další zjednodušení dotazu je provedeno změnou velikosti písma na malou. Termy ”Petr”, ”petr” i ”pEtR” jsou z hlediska vyhledávání shodné. Velikost písma m˚ uže mít vliv na pořadí dokument˚ u v odpovědi. Protože slovník nem˚ uže obsahovat všechna slova ve všech tvarech, je 117
použit mechanismus, který k danému slovu najde jeho základní tvar. Toto zajišťuje lematizátor. Na základě shlukové analýzy lze zjistit, která slova si jsou významově blízká (výskyt jednoho slova v textu s vysokou pravděpodobností určuje, že i druhé slovo bude v textu obsaženo, m˚ uže jít o synonyma, slova ve vztahu širší a užší term). Pak není potřeba vést obě slova v indexu, ale stačí si zapamatovat převod slova na term, který mu odpovídá v indexu. Je snahou udržovat slovník s maximální selektivní schopností (každý term má zmenšovat množinu odpovídajících dokument˚ u) a přitom je potřeba mít tento slovník, co nejmenší. Je odpozorováno, že uživatel prochází jen několik málo desítek odpovědí a v případě velkého množství dokument˚ u v odpovědi začne sv˚ uj dotaz upřesňovat. Vyhledávač předpokládá tento postup, proto termy nacházející se na začátku dotazu jsou brány s vyšším ohodnocením. Vyhledávač Google při hledání odpovídajícího termu ve slovníku provádí kontrolu správnosti pravopisu. Ve vyhledávání lze definovat, aby se dané slovo či slovní spojení vyhledávalo přesně uzavřením do uvozovek. Protože Google dokáže indexovat i soubory r˚ uzných typ˚ u je možnost specifikace typu přidána do jazyka vyhledávání. Odpověď na dotaz santa filetype:jpg budou dokumenty mající odkaz na obrázek se santou. A naopak v dotazu lze specifikovat, že dokumenty určitého typu nemají být do odpovědi zařazeny přidáním znaku - před slovo filetype. Přímo v dotazu lze zadat specifickou stránku, v které se má vyhledévat ( k dotazu přidej site:jménostránky). Stránky odkazující na stránku ČVUT vyhledáte pomocí: link:www.cvut.cz. Toto a mnoho dalšího (výběr jazyka, hledání podobných stránek, hledání v archívu. . .) lze jednoduše vložit do dotazu pomocí formuláře pod odkazem na pokročilé vyhledávání.
118
10
Statistické metody komprese dat
10.1
Základní pojmy
Statistické metody komprese dat jsou založeny na myšlence kódů s proměnnou délkou. Symbolům s větší pravděpodobností výskytu jsou přiřazeny kratší kódy a symbolům s menší pravděpodobností výskytu jsou přiděleny delší kódy. Kódy navržené pro kompresi dat musí splňovat dvě základní podmínky: 1. kód musí být možno jednoznačně dekódovat, 2. kód musí mít minimální průměrnou délku. Příklad 10.1 Předpokládejme abecedu A = {a1 , a2 , a3 , a4 }. Pokud se symboly vyskytují se stejnou pravděpodobností p(ai ) = 0, 25, pak entropie H1 (A) = −
X
p(ai ) log p(ai ) = −4(0, 25 log 0, 25) = 2 bity.
To znamená, že je možné použít kód CB se dvěma bity pro každý symbol: CB (a1 ) = 00, CB (a2 ) = 01, CB (a3 ) = 10, CB (a4 ) = 11. Tento kód se nazývá blokový a v případě stejných pravděpodobností výskytu jednotlivých symbolů je redundance nulová a statistickými metodami žádné komprese nelze dosáhnout. Jiná situace nastává, když je pravděpodobnost výskytu jednotlivých symbolů různá. Předpokládejme, že p(a1 ) = 0, 49; p(a2 ) = 0, 25; p(a3 ) = 0, 25 a p(a4 ) = 0, 01. V tomto případě je entropie: H2 (A) = −(0, 49 log 0, 49 + 2 · 0, 25 log 0, 25 + 0, 01 log 0, 01)=1, ˙ 57. Použijeme-li 2-bitový kód CB , pak redundance bude RB = H1 (A) − H2 (A) = 2 − 1, 57 = 0, 43. Zde se nabízí možnost použít kódu s proměnnou délkou. Dva kódy C1 a C2 jsou uvedeny v tabulce 10.1. Průměrná délka obou kódů C1 a C2 je stejná a činí: H3 = 1 · 0, 49 + 2 · 0, 25 + 3 · 0, 25 + 3 · 0, 01 = 1, 57, což je velmi blízko entropii H2 a redundance: RC1 = RC2 = H3 − H2 = 0, 02. Této redundance lze dosáhnout pro řetězce delší než 100 symbolů, kde počet výskytů jednotlivých symbolů odpovídá jejich pravděpodobnostem. Vzhledem k redundanci a entropii se oba kódy C1 a C2 chovají stejně. Kód C1 není prefixový. Pro kód C2 , který je prefixový může být jeho dekodérem konečný automat na obr. 10.1. 2 119
Symbol Pravděpodobnost C1 C2 a1 0, 49 1 1 a2 0, 25 01 01 a3 0, 25 010 000 a4 0, 01 001 001 Tabulka 10.1: Kódy C1 a C2 s proměnnou délkou z příkladu 10.1
1
0
a1 1
0
a2 1 a4
0 a3
Obrázek 10.1: Dekodér prefixového kódu C2 z příkladu 10.1
10.2
Shannon–Fanův kód
Příklad 10.2 Shannon-Fanovo kódování. Sestrojme Shannon-Fanův kód pro symboly s pravděpodobností podle tabulky 10.2. Průměrná délka tohoto kódu je: Symbol Pravděpodobnost Kód Krok a1 0, 25 11 2 a2 0, 20 01 1 a3 0, 15 011 4 a4 0, 15 010 3 a5 0, 10 001 a6 0, 10 0001 5 a7 0, 05 0000 6 Tabulka 10.2: Konstrukce Shannon-Fanova kódu z příkladu 10.2
H(C) = 0, 25·2+0, 20·2+0, 15·3·2+0, 10·3+0, 10·4+0, 05·4 = 2, 7
120
bitů . symbol
Entropie abecedy je H(A)=2, ˙ 67
bitů . symbol
Je vidět, že entropie abecedy a entropie kódu není stejná. Redundance je přibližně 0,02 bitů/symbol. Důvod je v tom, že nebylo možno rozdělit příslušné množiny symbolů na poloviny s přesně stejnou pravděpodobností. Sestrojte dekodér pro vytvořený kód! 2 Příklad 10.3 Sestrojme Shannon-Fanův kód pro symboly s pravděpodobností podle tabulky 10.3. Průměrná délka tohoto kódu je: Symbol Pravděpodobnost Kód Krok a1 0, 25 11 2 a2 0, 25 10 1 a3 0, 125 011 4 a4 0, 125 010 3 a5 0, 125 001 5 a6 0, 125 000 Tabulka 10.3: Konstrukce Shannon-Fanova kódu z příkladu 10.3
H(C) = 2 · 0, 25 · 2 + 4 · 0, 125 · 3 = 2, 5
bitů . symbol
Entropie abecedy je H(A) = −(2 · 0, 25 log 0, 25 + 4 · 0, 125 log 0, 125) = 2, 5
bitů . symbol
Zde vidíme, že entropie kódu a entropie abecedy je stejná. Důvod spočívá v tom, že při každém dělení množiny symbolů bylo možné rozdělení na poloviny se stejnou pravděpodobností. Sestrojte dekodér pro vytvořený kód! 2
10.3
Huffmanův kód
Příklad 10.4 Sestrojme Huffmanův kód pro abecedu A = {a1 , a2 , a3 , a4 , a5 } s pravděpodobnostmi p(A) = {0, 4; 0, 2; 0, 2; 0, 1; 0, 1}. Huffmanův strom HT1 je na obrázku 10.2. Pro stejnou abecedu můžeme sestrojit ještě jiný Huffmanův kód. Jeho konstrukce je uvedena na obr. 10.3 (Huffmanův strom HT2 ). Ke dvěma dosud vytvořeným kódům lze vytvořit ještě třetí. Jeho Huffmanův 121
1,0
1 0,6
1 0,4
1 0,2
0
0
0
0
1
0,4
0,2
0,2
0,1
0,1
a1
a2
a3
a4
a5
Obrázek 10.2: Huffmanův strom HT1 z příkladu 10.4 Symbol Pravděpodobnost H1 H2 H3 a1 0, 4 0 0 00 a2 0, 2 10 100 10 a3 0, 2 110 101 11 a4 0, 1 1110 110 010 a5 0, 1 1111 111 011 Tabulka 10.4: Huffmanovy kódy H1 , H2 , H3 z příkladu 10.4 strom HT3 je na obr. 10.4. Všechny tři vytvořené kódy H1 , H2 , H3 jsou uvedeny v tabulce 10.4. Z uvedeného příkladu je zřejmé, že pro danou abecedu a dané pravděpodobnosti výskytu jednotlivých symbolů je možné sestrojit více Huffmanových kódů. Proveďme jejich analýzu. 1. Průměrná délka všech kódů je stejná: AL(H1 ) = 0, 4 · 1 + 0, 2 · 2 + 0, 2 · 3 + 0, 1 · 4 + 0, 1 · 4 = 2, 2 , AL(H2 ) = 0, 4 · 1 + 0, 2 · 3 + 0, 2 · 3 + 0, 1 · 3 + 0, 1 · 3 = 2, 2 , AL(H3 ) = 0, 4 · 2 + 0, 2 · 2 + 0, 2 · 2 + 0, 1 · 3 + 0, 1 · 3 = 2, 2 . Tato skutečnost znamená, že pro kompresi dat jsou všechny tři kódy stejně vhodné. 2. Kód H1 má největší rozdíl délek mezi nejkratším a nejdelším kódovým slovem. 3. Kód H3 má nejmenší rozdíl délek mezi nejkratším a nejdelším kódovým slovem.
122
1,0 1 0,6 0
1 0,2
0,4 0
0
0
1
1
0,4
0,2
0,2
0,1
0,1
a1
a2
a3
a4
a5
Obrázek 10.3: Huffmanův strom HT2 z příkladu 10.4 Kód H3 je vhodný v případě, že vytváříme vstup pro přenosový kanál s konstantní rychlostí. Vytvoření kódu H3 vyžaduje doplnění algoritmu konstrukce Huffmanova stromu takto: Pokud je více dvojic uzlů, které je možno kombinovat, vyber dvojici s nejnižším a nejvyšším uzlem. 2
123
1,0 0 0,6 1
1 0,2 0
0
0,4 0
1
1
0,4
0,1
0,1
0,2
0,2
a1
a4
a5
a2
a3
Obrázek 10.4: Huffmanův strom HT3 z příkladu 10.4
124
Příklad 10.5 Sestrojme Shannon-Fanův kód pro stejnou abecedu jako v příkladu 10.4. Vzhledem k rozložení pravděpodobností je možné sestrojit tři různé kódy. Tyto kódy a jejich postup sestrojení je uveden v tab. 10.5, 10.6 a 10.7. Symbol Pravděpodobnost Kód Krok a1 0, 4 1 1 a2 0, 2 01 2 a3 0, 2 001 3 a4 0, 1 0001 4 a5 0, 1 0000 Tabulka 10.5: Shannon-Fanův kód SF1 z příkladu 10.5 Symbol Pravděpodobnost Kód Krok a1 0, 4 1 1 a2 0, 2 011 3 a3 0, 2 010 2 a4 0, 1 001 4 a5 0, 1 000 Tabulka 10.6: Shannon-Fanův kód SF2 z příkladu 10.5 Symbol Pravděpodobnost Kód Krok a1 0, 4 11 2 a2 0, 2 10 1 a3 0, 2 01 3 a4 0, 1 001 4 a5 0, 1 000 Tabulka 10.7: Shannon-Fanův kód SF3 z příkladu 10.5 Porovnáme-li kódy H1 , H2 a H3 z příkladu 10.4 a kódy SF1 , SF2 a SF3 zjistíme, že jejich charakteristiky jsou stejné. 2 Domácí úkol: Nalezněte příklad(y), kdy Huffmanovy a Shannon-Fanovy kódy mají různé charakteristiky. Příklad 10.6 Sestrojme Huffmanův kód pro text T = abracadabra. Abeceda 5 , A = {a, b, c, d, r} má tyto pravděpodobnosti výskytu: p(a) = 11 2 1 p(b) = p(r) = 11 , p(c) = p(d) = 11 . Huffmanův kód je na obr. 10.5.
125
11 11
1 6 11
1 4 11
1
0 0
0
0
2 11
1
5 11
2 11
1 11
1 11
2 11
a
b
c
d
r
Obrázek 10.5: Huffmanův strom z příkladu 10.6 Jednotlivé symboly zakódujeme podle tabulky 10.8. Zakódovaný text má Symbol a b c d r Kód 0 10 1100 1101 111 Tabulka 10.8: Huffmanův kód z příkladu 10.6 tvar: h(T ) = 0 10 111 0 1100 0 1101 0 10 111 0 a má délku 23 bitů.
2
Příklad 10.7 Zakódujme text T = abracadabra pomocí adaptivního Huffmanova kódování. Počáteční kódy jednotlivých symbolů jsou uvedeny v tab. 10.9. Postupnou konstrukci Huffmanova stromu znázorňuje obr. 10.6 až obr. 10.12. Symbol a b c d r Kód 00000 00001 00010 00011 10001 Tabulka 10.9: Počáteční kódy symbolů z příkladu 10.7 Výsledný Huffmanův kód je uveden v tab. 10.10. Text je zakódovaný takto: 00000 0|00001 00|10001 0 100|00010 0 1100|00011 0 110 110 0 a b r a c a d a b r a Je vidět, že při prvním výskytu symbolu je jeho kód dlouhý, ale při dalších výskytech se zkracuje. Všimněte si, že kódy symbolů b a r jsou stejné. Proč? 126
Symbol a b c d r Kód 0 111 101 1001 110 1000 Tabulka 10.10: Huffmanův kód
2 0
1
a
0
0
b
1
00000
0 00001 0
1
1
0
1 a
1
1
0
a 1 b
3
4
0 r 00 10001
0
1
0
a
0
1
1 0 0
a
2
1
2
2 0
a
1 1
0
r
1
1 0
b 1
1
1 1
b 1 r
Obrázek 10.6: Postupná konstrukce Huffmanova stromu-1.část
127
5 0 c 100 00010
1 3
2 0
a
1
1
2 0
b
1 1
1 0
1
0
r 1 c
6 0 a 0
1 3
3 0
a
1
1
2 0
b
1 1
1 0 0
1
r 1 c
Obrázek 10.7: Postupná konstrukce Huffmanova stromu-2.část
128
2 0 d
1
3
1100 00011
4
a
0
1
2
2 1
0 1 1
0 0
1
0 1
1
1
c
b
r
1 d
Obrázek 10.8: Postupná konstrukce Huffmanova stromu-3.část
8 0 a
1
4
0
4
a
0
1
2 1
0 1 0 0
2
1
0
1
1
1
1
c
b
r
1 d
Obrázek 10.9: Postupná konstrukce Huffmanova stromu-4.část
129
9 0 b
1
4
110
5
a
0
1
2
3 1
0 1 1
0 0
1
0 1
1
2
c
r
b
1 d
Obrázek 10.10: Postupná konstrukce Huffmanova stromu-5.část
10 0 r
1
4
110
6
a
0
1
2 1
0 1 0 0
4
1
0
1
1
2
2
c
r
b
1 d
Obrázek 10.11: Postupná konstrukce Huffmanova stromu-6.část
130
11 0 a
1
5
0
6
a
0
1
2 1
0 1 0 0
4
1
0
1
1
2
2
c
r
b
1 d
Obrázek 10.12: Postupná konstrukce Huffmanova stromu-7.část
131
Příklad 10.8 Sestrojme Huffmanův kód pro abecedu A = {a1 , a2 , a3 , a4 , a5 }, kde všechny symboly mají stejnou pravděpodobnost p(ai ) = 0, 2, i = 1, 2, . . . , 5. Huffmanův strom je na obr. 10.13. Huffmanův kód uvádí tab. 10.11. Průměrná
1,0 0
1 0,6 0
0,4 0
1
0,4 0
1
1
0,2
0,2
0,2
0,2
0,2
a1
a2
a3
a4
a5
Obrázek 10.13: Huffmanův strom Symbol Pravděpodobnost Kód a1 0, 2 00 a2 0, 2 01 a3 0, 2 100 a4 0, 2 101 a5 0, 2 11 Tabulka 10.11: Huffmanův kód délka kódu je AL = 0, 2(2 + 2 + 3 + 3 + 2) = 2, 4
bitů . symbol
Je vidět, že i v tomto případě lze dosáhnout komprese pro případ, že počet symbolů abecedy je jiný než mocnina dvou.
10.4
Aritmetické kódování
Příklad 10.9 Je dána abeceda A = {a1 , a2 , a3 }, s pravděpodobnostmi p(a1 ) = 0, 4; p(a2 ) = 0, 5; p(a3 ) = 0, 1. Zakódujme pomocí aritmetického kódování řetězec T = 132
0,0
0,4
0,6
0,7
0,6
0,7
0,75
0,85
0,825
0,8125
0,8125
a1
0,4
a2
0,9 a3 1,0
0,9 a2
0,85 a2
0,825 a2
0,825 a3
Obrázek 10.14: Aritmetické kódování řetězce a2 a2 a2 a3 a2 a2 a2 a3 . Postup kódování je znázorněn na obr. 10.14. Řetězec T může být zakódován libovolným číslem z intervalu < 0, 8125; 0, 825), například 0,820. Příklad 10.10 Zde je třeba vložit příklad na implementaci s použitím shiftu.
133
11
Slovníkové komprese dat
11.1
LZ77
Metoda LZ77 je nazývána metodou posuvného okna. Posuvné okno je použito pro zakódování textu. Je rozděleno na dvě části, zakódovanou část a nezakódovanou část. Dohromady tvoří celkovou velikost okna. Předpony z nezakódované části jsou kódovány pomocí podřetězc˚ u začínajících v zakódované části okna. Do výstupního proudu je v každém kroku uložena trojice (i, j, a). Předpokládejme, že jsme nalezli nejdelší řetězec ( označme jej s ) začínající v zakódované části a shodující se s předponou řetězce z nezakódované části posuvného okna ( označme jej p ). Pak i je vzdálenost prvního znaku řetězce s od hranice mezi zakódovanou a nezakódovanou částí okna, j je délka řetězce s a a je první znak za předponou p. Po uložení trojice (i, j, a) je celé okno posunuto o j + 1 znak˚ u doprava. Příklad 11.1 Metodou LZ77 zakódujte text T = aabaacaaaaaababababbab. Použijte okno velikosti 10 znak˚ u, velikost nezakódované části volte čtyři znaky. Zhodnoťte dosaženou kompresi. Kódování začíná s posuvným oknem položeným na text tak, že hranice mezi zakódovanou a nezakódovanou částí leží na začátku textu. V zakódované části se nenachází jediný znak, slovník pro vyhledávání je tedy prázdný. Tuto situaci ukazuje následující obrázek. - - - znak doprava.
-
-
a
a
b
a Trojice je (0,0,a), posun okna o jeden
Jelikož nejdelší předpona z nezakódované části začínající v zakódované části má délku 0, je do výstupního proudu vložena trojice (0, 0,a), kde a je první znak kódovaného řetězce. Celé okno je posunuto o jeden znak doprava. Kódování pokračuje v následujících krocích: -
-
-
-
-
-
-
-
a
a
a
a
b
a
a
a
b a
c
b
a a
a a
a
a (1,1,b)
c
a (3,2,c) a
a (3,2,a)
Nejdelší předpona v nezakódované části okna na předcházejícím obrázku byla aa. Tato předpona se nachází v zakódované části okna na dvou pozicích a to pozici 3 a pozici 6. Proto jsou dvě možnosti zakódování následující trojice : (3,2,a) a (6,2,a). Na jednoznačnost dekódování nemá výběr jedné
134
trojice vliv, nicméně volíme trojici (3,2,a), neboť obsahuje nižší čísla a dá se předpokládat, že budou kódována kratšími kódy. a
a
c
a
a
a
a
a
a
b (1,3,b)
Připomeňme, že nalezený řetězec nemusí končit v zakódované části okna. Na základě úmluvy z předcházejícího odstavce použijeme trojici (1,3,b) z možných trojic (1,3,b),(2,3,b) a (3,3,b). a
a
a
a
a
b
a
b
a
b (2,3,b)
Zde nastává situace, kdy je celá nezakódovaná část okna ve slovníku v zakódované části, ale protože se do výstupního proudu musí dát jeden symbol (ten by byl právě za oknem), je do výstupního proudu dána trojice (2,3,b). a
b
a
b
a
b
a
b
b
a (2,2,b)
b
a
b
a
b
b
a
b
-
- (3,2,b)
Závěr kódování. Nezakódovaná část okna není zcela zaplňena a poslední znak musí být uveden jako následující znak za nalezeným podřetězcem. Metoda LZ77 nepotřebuje ukončovací znak, protože binární kód každé trojice je delší než jeden byte. Výsledný kód je tedy: (0, 0, a) (1, 1, b) (3, 2, c) (3, 2, a) (1, 3, b) (2, 3, b) (2, 2, b) (3, 1, b) První číslo v uspořádané trojici adresuje nezakódovanou část okna, interval přípustných hodnot je tedy < 0, 6 >. Při použití binárního kódu bude potřeba pro uložení této adresy třech bit˚ u. Druhé číslo určuje délku nalezeného podřetězce. Maximální délka je rovna délce nezakódované části okna zmenšené o jedničku (znak do výstupu), v našem případě tři znaky. Nejkratší délka je pro případ, kdy již první znak v nezakódované části okna není obsažen ve slovníku, pak je délka rovna nule. Tedy interval < 0, 3 >, binární kód délky dva. Pro kódování znak˚ u použijeme standardní ASCII kód, tedy 8 bit˚ u. Celková délka kódu bude 7 ∗ (3 + 2 + 8) = 91 bit˚ u. Byl-li p˚ uvodní text v ASCII kódování, byla jeho délka 22 ∗ 8 = 176 bit˚ u. Kompresní poměr je . 91/176 = 0, 52. 135
Příklad 11.2 Proveďte dekódování textu z předchozího příkladu. Postup je obdobný jako u kódování. Dekodér bude používat stejné okno, na základě index˚ u bude doplňovat znaky do výstupního proudu. Potom přesune okno tak, aby hranice mezi zakódovanou a nezakódovanou částí byla za posledním znakem. Vše je znázorněno na následujících obrázcích. - - - - - - - - - Trojice je (0,0,a), do výstupu vlož symbol a. - - - - - - a - - - (1,1,b) Posuň okno o jeden znak ( o j+1, zde 0+1). -
-
-
-
-
-
-
-
a
a
a
a
b
a
a
c
a
a
a
- (3,2,a) Vlož aa a přidej a.
a
a
c
a
a
a
a
a
a
b (1,3,b)
a
a
a
a
a
b
a
b
a
b (2,3,b)
a
b
a
b
a
b
a
b
b
- (2,2,b)
b
a
b
a
b
b
a
b
-
- (3,1,b)
11.2
a
a
b
b
a
-
a
- (1,1,b) Vlož a a přidej b. c
- (3,2,c) Vlož aa a přidej c.
LZ78
Příklad 11.3 Metodou LZ78 zakódujte text T = aabaacaaaaaababababbab. Zhodnoťte dosaženou kompresi. Metoda LZ78 produkuje v každém kroku jednu dvojici (i, a), kde i je index fráze ve slovníku a a je symbol nacházející se bezprostředně za ukládanou frází. Slovník je reprezentován jako strom s očíslovanými uzly, každý uzel reprezentuje frázi na cestě z kořene do tohoto uzlu. Po vložení jedné uspořádané dvojice do výstupního proudu je slovník rozšířen o novou frázi, která vznikne rozšířením ukládané fráze o právě ukládaný symbol. Tato fráze bude označena nejnižším novým číslem a začleněna do kódovacího stromu. Kódování začíná se stromem obsahujícím jediný uzel, uzel nula. Nejdelší předpona nalezená v tomto stromu je ε, do výstupu jde dvojice (0,a) a strom 136
je rozšířen o uzel 1 a hranu ohodnocenou symbolem a. Uzel 1 tedy reprezentuje frázi a. Hranice mezi zakódovanou a neazakódovanou částí vstupního řetězce je posunuta: a|abaacaaaaaababababbab Protože nejdelší předpona nezakódované části řetězce nalezená v kódovacím stromu je a, tj. uzel 1, do výstupu se předá (1,b). Strom je rozšířen o novou frázi 2 = 1b = ab. Hranice je posunuta za třetí symbol: aab|aacaaaaaababababbab 0 a
c
1
4
b 8
a
b 2
3
a
b
a
7
9
5 b 6
Obrázek 11.1: Stromová reprezentace slovníku metody LZ78. Algoritmus komprese postupně vytvoří strom na obrázku 11.1. Hranice mezi zakódovanou a nezakódovanou částí budou: a|ab|aa|c|aaa|aaab|aba|b|abb|ab Každý podřetězec uzavřený sousedícími hranicemi je kódovací fráze, její pořadí odpovídá číslu uzlu, jež ji reprezentuje. Výjimku tvoří poslední podřetězec, který zde nevytváří novou frázi a je kódován dvojicí (1,b), protože algoritmus dekódování vyžaduje vložení symbolu. Výsledný kód je:
137
Kód (0,a) (1,b) (1,a) (0,c) (3,a) (5,b) (2,a) (0,b) (2,b) (1,b)
velikost slovníku 0 1 2 3 4 5 6 7 8 9
počet bit˚ u pro index fráze 0 1 2 2 3 3 3 3 4 4
Pro výpočet kompresního poměru předpokládejme, že p˚ uvodní text používal 8 bit˚ u na jeden symbol, d0lka p˚ uvodního textu byla 22 ∗ 8 = 176 bit˚ u. Jednotlivé symboly budeme kódovat také 8 bity. Indexy frází budeme kódovat binárním kódem jehož délka bude závislá na velikosti slovníku, tj. při kódování první dvojice, je slovník prázdný, není potřeba kódovat index fráze, po vložení první fráze je potřeba jeden bit (0 . . . nová fráze, 1 . . . fráze a). Celková délka kódu bude 10∗8+1+2∗2+4∗3+2∗4 = 105 bit˚ u. Kompresní . poměr je 105/176 = 0, 60. Příklad 11.4 Dekódujte výstup z předchozího příkladu. Pro reprezentaci slovníku je při dekódování výhodnější tabulka. Její inicializace je: Index fráze 0
fráze ε
První dvojice je (0, a), do výstupu je přidán řetězec odpovídající indexu fráze 0, tedy ε a symbol a. Tabulka frází je rozšířena o frázi vzniklou zřetězením fráze 0 a symbolu a, tedy a. Výsledná tabulka včetně dokódování bude Index fráze 0 1 2 3 4 5 6 7 8 9 −
fráze ε 0a . . . a 1b . . . ab 1a . . . aa 0c . . . c 3a . . . aaa 5b . . . aaab 2a . . . aba 0b . . . b 2b . . . abb − 138
do výstupu a ab aa c aaa aaab aba b abb ab
11.3
LZW
Metoda LZW vymyšlená Welchem vychází z metody LZ78. Jejím výstupem jsou pouze indexy, slovník je inicializován všemi symboly vstupní abecedy, poslední symbol posledně vložené fráze je počátečním symbolem vkládané fráze. Příklad 11.5 Metodou LZW zakódujte text T = aabaacaaaaaababababbab. Zhodnoťte dosaženou kompresi. Metoda LZW předpokládá slovník inicializovaný všemi symboly abecedy. Pro jednoduchost předpokládejme, že vstupní abeceda obsahuje pouze symboly a, b, c6 . Slovník bude obsahovat fráze a, b a c, indexované čísly 1, 2 a 3. Celý slovník je zobrazen na obrázku 11.2.
0 a 1
4
3
2 b
a
c
b
b 5
14
a
a 6
8
c
a
a
b
7
9
11
13
a
a
10
12
Obrázek 11.2: Stromová reprezentace slovníku metody LZW. Následující tabulka shrnuje jednotlivé kroky kódování. Symbolem | je označena nová hranice mezi zakódovanou a nezakódovanou částí textu, fráze ukládaná do slovníku je zvýrazněna tučně. 6
Obecně nevíme jaké symboly budou v textu obsaženy, proto se slovník inicializuje všemi možnými symboly. Jinou možností by bylo zjišťování pravdy, které by si vyžádalo jeden pr˚ uchod zakódovávaným textem a předání inicializovaného stromu dekodéru.
139
Text a|abaacaaaaaababababbab aa|baacaaaaaababababbab aab|aacaaaaaababababbab aabaa|caaaaaababababbab aabaac|aaaaaababababbab aabaacaa|aaaababababbab aabaacaaaaa|ababababbab aabaacaaaaaab|abababbab aabaacaaaaaababa|babbab aabaacaaaaaabababa|bbab aabaacaaaaaabababab|bab aabaacaaaaaababababbab|
index do výstupu 1 1 2 4 3 4 9 5 11 6 2 13
index nové fráze 4 5 6 7 8 9 10 11 12 13 14 −
Výsledná posloupnost index˚ u je 1,1,2,4,3,4,9,5,11,6,2,13. Pro kódování jednotlivých index˚ u použijeme binární kód, jehož délka bude ⌈log2 (sl)⌉, kde sl je velikost slovníku, tj. první a druhý index fráze budou zakódovány dvěma bity (inicializovaný slovník obsahuje 3 fráze). Délka výsledného kódu bude 2 ∗ 2 + 4 ∗ 3 + 6 ∗ 4 = 40 bit˚ u. Pokud byl p˚ uvodní text v ASCII kódu, je . kompresní poměr 40/176 = 0, 23. Příklad 11.6 Dekódujte posloupnost z předchozího příkladu. Uvažujte stejný počáteční slovník. Počáteční slovník obsahuje tři fráze: Index fráze 1 2 3
fráze a b c
Připomeňme, že každá nová fráze má první symbol shodný s posledním symbolem předchozí fráze. Pro dekódování si je nutné uchovávat dva odkazy do textu, místo kam p˚ ujde další symbol (vždy za poslední symbol) a poslední symbol v poslední uložené frázi. První index je číslo jedna, odpovídající fráze je a. Druhý index je jedna, odpovídající fráze je a, celý výstup je aa. Nová fráze je aa, číslo 4. Tento a další kroky shrnuje následující tabulka, nová fráze je zvýrazněna pruhem nad dekódovaným textem, poslední dekódovaná fráze je zvýrazněna tučným písmem.
140
Index fráze ze vstupu 1 2 4 3 4
výstup aa aab aabaa aabaac aabaacaa
nová fráze 4 . . . aa 5 . . . ab 6 . . . ba 7 . . . aac 8 . . . ca
V tomto okamžiku je na vstupu index 9, tato fráze ještě nebyla vložena do slovníku. Tento případ nastává pro fráze typu axa, kde x je libovolný řetězec a fráze ax je již ve slovníku. Tato fráze je rozšířením posledně dekódované fráze. V našem případě jde o frázi 4 . . . aa, první a poslední symbol nové fráze se musí shodovat, fráze 9 bude aaa. Stejný problém bude dekodér řešit s frází 11. Index fráze ze vstupu 9 5 11 6 2 13
výstup aabaacaaaaa aabaacaaaaaaab aabaacaaaaaababa aabaacaaaaaabababa aabaacaaaaaabababab aabaacaaaaaababababbab
141
nová fráze 9 . . . aaa 10 . . . aaaa 11 . . . aba 12 . . . abab 13 . . . bab 14 . . . bb
12
Kontextové metody komprese dat
12.1
Základní pojmy
Metody, které jsou uvedeny v této kapitole, jsou založeny na tom, že se vytváří model dat ve formě konečného automatu. Statistické charakteristiky mohou být pro každý stav automatu jiné a proto může být komprese lepší než v modelech, které neuvažují levý kontext. Dále budeme předpokládat, že pro kódování je použito aritmetické kódování, které zaručuje zakódování symbolu s přesností blízkou entropii. Proto budeme v dalších úvahách rozdíl mezi entropií symbolu a jeho kódu zanedbávat. Příklad 12.1 Uvažme, jak se bude lišit komprese textu při použití konečného automatu s jedním stavem (bez uvažování levého kontextu) a automatu se dvěma stavy (s uvažováním levého kontextu o délce jeden symbol). Předpokládejme, že byl přečten text T = aaabbcaaabbc. Pravděpodobnosti výskytu jednotlivých symbolů jsou: p(a) = 21 , p(b) = 13 , p(c) = 61 . Na obr. 12.1a) je jednostavový model tohoto textu. V tomto případě je
a(1/2)
b(1/6) a(1/3)
START
b(1/3) q1
START
a(1/3)
q1
q2
b(1/6) c(1/6)
c(1/6)
a)
b)
Obrázek 12.1: Konečné automaty jako modely pro kompresi textu entropie (počet bitů na symbol) tohoto modelu dána: . H = − 12 log 21 − 31 log 13 − 61 log 61 = 1, 43 bitů/symbol. Použijeme–li dvoustavový model z obr. 12.1b), pak se situace změní. Entropie tohoto modelu se určí pro každý stav zvlášť a výsledná entropie se získá váženým součtem entropií jednotlivých stavů: H = p(q1 )H(q1 ) + p(q2 )H(q2 ). Pravděpodobnost, že automat bude ve stavu q je p(q1 ) =
X
δ(r,a)=q
142
p(a).
V našem případě p(q1 ) = p(b)
přechod q1 → q1
+p(c)
přechod q1 → q1
+p(a)
přechod q2 → q1
+p(b)
přechod q2 → q1
=
1 6
+
1 6
b
c
a b
+
+
1 6
=
2 3 a
p(q2 ) = p(a) =
1 6
přechod q1 → q2
1 3.
Entropie stavů q1 a q2 je dána rozložením pravděpodobnosti jednotlivých přechodů: b H(q1 ) = − 16 log 16 přechod q1 → q1 c
− 61 log 16
přechod q1 → q1
− 31 log 13
přechod q1 → q2
H(q2 ) = − 61 log 16
přechod q2 → q1
− 61 log 16
přechod q2 → q1
a
. = 1, 3899, a b
. = 0, 8616. Celková entropie modelu je: 2 3
· 1, 3899 +
1 3
· 0, 8616 = 1, 21 bitů/symbol.
Je vidět, že tato entropie je menší než v případě jednostavového modelu. Příklad 12.2 Předpokládejme, že model textu ve formě konečného automatu je zadán. Přechodový diagram tohoto automatu je na obr. 12.2. a|1 START
q0
a|1 b|0
q1
a|1 c|0
q2
d|0
Obrázek 12.2: Konečný automat, který je modelem dat Budeme–li předpokládat, že pravděpodobnost výskytu každého symbolu v každém stavu je stejná, pak na zakódování každého symbolu stačí jeden bit. Proto může komprese probíhat jako formální překlad popsaný konečným 143
překladovým automatem na obr. 12.2. Komprese textu T = abacadbcda má tento výsledek: C(T ) = 1010100001.
12.2
Dynamické Markovovo kódování
Příklad 12.3 Uveďme adaptivní metodu konstrukce konečného automatu nabízenou DMC (Dynamic Markov Coding). Tato metoda je založena na operaci zvané klonování stavů. Její princip je znázorněn na obr. 12.3. D
A 0
A
0
C
0
0
D 0
C 1
1
1
B
E
B
a)
1
C’
1
E
b)
Obrázek 12.3: Klonování stavů Jestliže do stavu C na obr. 12.3a) míří přechody pro různé symboly z různých stavů (v našem případě přechod pro symbol 0 ze stavu A a pro symbol 1 ze stavu B), pak vytvoříme nový stav C ′ a jednotlivé přechody přesměrujeme podle obr. 12.3b). Pravděpodobnosti přechodů ze stavů C a C ′ upravíme ve stejném poměru podle pravděpodobností přechodů ze stavu A do stavu C a ze stavu B do stavu C. Ve speciálním případě, když jsou tyto pravděpodobnosti stejné, rozdělíme pravděpodobnosti přechodů ze stavu C na poloviny a předělíme je přechodům ze stavů C a C ′ . Celý proces začíná od nějakého počátečního automatu. Těch je navrženo několik typů. Nejjednodušší z nich je jednostavový automat se smyčkami pro všechny symboly abecedy. Nyní ukažme, jak se takový počáteční automat může adaptovat postupným přidáváním stavů. Na obr. 12.4a) je uveden počáteční jednostavový model. Na obr. 12.4b) je tento počáteční automat překreslen do schematu, který je východiskem pro klonování. Výsledkem klonování je vznik stavu q1 , do kterého se provede přechod při čtení jedničky (obr. 12.4c)). Stav q? , do kterého směřuje přechod z nového stavu při čtení jedničky odpovídá právě klonovanému stavu q0 . Můžeme si proto vybrat, zda tento stav bude původní stav q0 nebo nově vzniklý stav q1 . V tomto případě bude q? = q1 . (Poznámka: je třeba určit pravidlo pro takový výběr.) Když přejdeme od schematu zpět k reálnému automatu, dostaneme automat na obr. 12.4d). Druhý krok je naznačen na obr. 12.5. Východiskem je automat na obr. 12.4d). Na obr. 12.5a) je schema pro klonování, jehož výsledek je na obr. 12.5b). 144
0
q0
q0 0 START
q0
0 q0
1 1
q0
a) q0
0
q0
1
q0 b) 0
q0
0
1
0 START 1 q0
1
q1
1
1
q0
q1
0 q?
c)
d)
Obrázek 12.4: První krok při klonování stavů Zde je opět klonovaný stav stavem cílovým pro přechod ze stavu q2 při čtení symbolu 0. Tentokrát bude q? = q2 . Na obr. 12.5c) je výsledný konečný automat. Třetí krok je naznačen na obr. 12.6. Pro klonování je vybrán stav q1 . V tomto případě q? = q3 a výsledný automat je na obr. 12.6c). Čtvrtý krok klonování stavů ukazuje obr. 12.7. Tentokrát se klonuje stav q1 . Pátým klonovaným stavem je stav q2 . Postup je na obr. 12.8.
12.3
Metoda PPM
Příklad 12.4 Uveďme adaptivní metodu konstrukce konečného automatu pro metodu komprese dat zvanou PPM (Prediction with Partial String Matching). Tento automat má tvar stromu a pro každý podřetězec, který se v textu vyskytl, obsahuje jeden uzel. U tohoto uzlu je čítač, který udává, kolikrát se poslední symbol a vyskytl s levým kontextem x. Hloubka stromu je n + 1, kde n je délka nejdelšího kontextu. Začíná se od stromu tvořeného pouze kořenem. Je zadán text T = assanissimassa. Tvar jednotlivých stromů je po každém kroku uveden na obr. 12.9 – 12.11.
145
0
0
q1
q0
q1
0
q0
q?
0
0
q0 1 0
1
q0
0
q0
q1
1
q2
a)
q1
b) 0 1 1
q0
0 1
q1
q2
0 c)
Obrázek 12.5: Druhý krok při klonování stavů
1
1
q2
q0
q2
q1
0
q0
0 0 q1
1
1
1
q1
1
q1
q1
q3
a)
1
q?
b) 0
0 START
q0
1
q1
1
q2
0 0
1
q3
1
c)
Obrázek 12.6: Třetí krok klonování stavů 146
q0
q0
q0 1
1
0
q1
0
q0 0
q1 1 1
1
q2
q2
q3
1
1
q4 b)
a) 0 START
q0
1
0
q1
q2
0 0
1 1
0
q3
1
q4
c)
Obrázek 12.7: Čtvrtý krok klonování stavů
147
q3
0
0
q2
q2
q2
0
q2
q2
0 0 q2
0
1
1
q0
0
q0
q4
1
q5
a)
q4
b) 0
START
q0
1
0
0
q1
0
q5
1
1
1
1 0
1
q3
q4
c)
Obrázek 12.8: Pátý krok klonování stavů
148
q2
a,1
a,1
s,1
s,1
a,2
s,2
a,2
s,1
s,1
s,1
s,1 1.’a’
a,2
2.’s’
n,1
s,2
a,1
a,1
s,1 3.’s’
s,2
4.’a’
a,2
i,1
n,1 s,1
a,1
s,1
n,1
s,1
s,1
n,1
a,1
i,1
s,1
5.’n’
n,1
i,1
6.’i’
Obrázek 12.9: Čtrnáct stromů pro metodu PPM
149
s,1
s,2
a,1
s,1
n,1
a,1
a,2
i,1 n,1
i,1 n,1
a,2
s,3
n,1 s,1 s,1 s,1
a,1 s,1
n,1 s,1 s,1 s,1
i,1 a,1
s,2
i,1 s,1
n,1 a,1
i,1 s,1 s,1 s,1 s,1 n,1
a,1
s,1
8.’s’
7.’s’
s,4
a,2
i,2
n,1
n,1 s,1
s,1
i,1 a,1 i,1 s,2
i,1 s,1
s,1
s,1 n,1
a,2
a,1
i,1
m,1 n,1
i,2
i,2
m,1 n,1
i,1 a,1 i,1
i,1 s,1
s,1 n,1 m,1 a,1
s,1
s,2 i,1
10.’m’
a,2
s,4
n,1 s,1 m,1 s,1 a,1 i,1 a,1 i,1 s,2 s,1 n,1 m,1 a,1 i,1
i,1 s,1 a,1 s,1
s,5
n,1 s,1 m,1 s,1
9.’i’
a,2
s,5
i,2
m,1 n,1
s,5
n,1 s,2 m,1 s,1 a,1 i,1 a,1 i,1 s,2 i,1 s,1 a,1 s,1 s,1 s,1 n,1 m,1 a,1 i,1 12.’s’
11.’a’
Obrázek 12.10: Čtrnáct stromů pro metodu PPM - pokračování
150
a,3
i,2
m,1 n,1
a,4
s,6
i,2
m,1 n,1
s,6
n,1 s,2 m,1 s,1 a,1 i,1 a,1 i,1 s,3
n,1 s,2 m,1 s,1 a,1 i,1 a,2 i,1
i,1 s,2 a,1 s,1 s,1 s,1 n,1 m,1 a,1 i,1
i,1 s,2 a,1 s,1 s,1 s,1 n,1 m,1 a,2 i,1
13.’s’
14.’a’
Obrázek 12.11: Čtrnáct stromů pro metodu PPM - pokračování
151
s,3
13
Kontrola textu
152
Reference [JPR]
Melichar, B.: Jazyky a překlady. Vydavatelství ČVUT, Praha 1999.
[SDFA01]
Melichar, B., Skryja, J.: On the Size Deterministic Finite Automata. In: Bruce W. Watson, Derick Wood (eds.) Proceedings of Conference on Implementations and Applications of Automata, Pretoria 2001.
[SK00]
Skryja, J.: Semihomogenons Finite Automata. Master’s Thesis, CTU of Prague, Faculty of Electrical Engineering, Department of Computer Science and Engineering, Prague 2000.
[JPR01]
Melichar, B. a kol.: Jazyky a překlady - cvičení. Nepublikovaný text.
153
