Algorytm sardinasa-pattersona



Pobieranie 65.56 Kb.
Data28.04.2016
Rozmiar65.56 Kb.
TEORIA KODÓW

Lekcja 2 Testowanie kodów
ALGORYTM SARDINASA-PATTERSONA
Przedstawiony niżej algorytm, znany jako algorytm Sardinasa-Pattersona, pochodzi z roku 1953 i do dziś uważany jest za najlepszy (i najbardziej znany) algorytm testowania kodów. Nie korzysta on z żadnych zaawansowanych technik, bazując jedynie na włas­nościach kodów, wynikających wprost z definicji.

Pokażemy później, że w przypadku, gdy testowany zbiór X jest regularny, oblicze­nie algorytmu Sardinasa-Pattersona jest zawsze skończone i zakończone odpowiedzią rozstrzygającą: „TAK - X jest kodem” lub „NIE - X nie jest kodem”. Innymi słowy, problem „czy dany zbiór X jest kodem” jest efektywnie rozstrzygalny dla zbiorów regularnych.


Definicja 2.1: Niech X,YA*. Iloraz lewostronny zbioru X przez zbiór Y, oznaczany symbolem X/Y, to zbiór wszystkich ilorazów lewostronnych słów zbioru X przez słowa zbioru Y:

X/Y = {vA* | (uY) uvX}


Konstrukcja 2.2: Niech XA+ będzie zbiorem do zbadania. Budujemy (potencjalnie nieskończony) ciąg zbiorów Un(X):

U1(X) = X/X{}

Un+1(X) = Un(X)/X  X/Un(X)

Zauważmy, że elementy każdego ze zbiorów Un(X) są pewnymi suffiksami badanego zbioru X. Dalej mówiąc o zbiorach Un(X) rozumieć będziemy ciąg zbiorów, zdefinio­wany powyższym wzorem rekurencyjnym. Będziemy pisać Un zamiast Un(X), gdy zbiór X będzie wyraźnie ustalony.


Twierdzenie 2.3: Zbiór XA+ jest kodem  (n1) Un(X).

Dowód będzie podany za chwilę. Jest on dość trudny i jego znajomość nie jest obowiąz­kowa. Trudno jednak wyobrazić sobie wykład z teorii kodów bez niego.
Przykład 2.4: Zbadamy, czy zbiór X={b, abb, abbba, bbba, baabb} jest kodem.

Budujemy ciąg zbiorów Un(X):

U1(X) = {bba, aabb, ba} U1/X={ba, a} X/U1={abb}

U2(X) = {ba, a, abb} U2/X={a, } X/U2={abb, bb, bbba, , ba}

U3(X) = {a, , abb, bb, bbba, ba} NIE - zbiór X nie jest kodem, bo U3(X).

Budowanie następnych ilorazów nie jest potrzebne po otrzymaniu pierwszego Un zawie­rającego , w tym przypadku U3 (nawet nie całego, można przerwać już po stwier­dzeniu, że U2/X).

Przykład niejednoznacznego rozkładu uzyskamy, rekonstruując drogę dojścia do . W naszym przykładzie U2/X={a, } otrzymaliśmy przez kolejne dzielenia:

abbba/abb=baU1, baabb/ba=abbU2, abb/abb=U3.

Mamy więc (abbba)=(abb)ba i (baabb)=ba(abb), stąd (abbba)(abb)=(abb)ba(abb)= (abb)(baabb) [nawiasami () otoczyliśmy elementy zbioru X]. Ciąg dzieleń prowadzący do  dał nam dwa różne rozkłady słowa w=abbbaabbX* względem elementów X, mianowicie w=(abbba)(abb)=(abb)(baabb). Można zauważyć, że tak będzie zawsze, bo w pierwszym i ostatnim ilorazie dzielna i dzielnik zawsze należą do X, a w ilorazach pośrednich dzielna lub dzielnik należy do X. To jest oczywiście bardzo bardzo pobieżny szkic pełnego dowodu Tw. 2.1, a raczej tylko rzut oka na jego ideę.
Przykład 2.5: Zbadamy, czy X={a, ab, ba} jest kodem. Budujemy ciąg Un:

U1={b} U2={a} U3={, b} U4=X U5= U3

Odpowiedź: NIE - zbiór X nie jest kodem, bo U3(X).
Przykład 2.6: Zbadamy, czy X={aa, ba, bb, baa, bba} jest kodem. Budujemy ciąg Un:

U1={a} U2=U1 (n1) Un={a}

Odpowiedź: TAK - zbiór X jest kodem, bo (n1) Un(X).
Zauważmy, że w Przykładach 2.5 i 2.6 rodziny zbiorów {Un | n1} były skończone. Jest tak również w Przykładzie 2.4 (ćwiczenie - pociągnij dalej i sprawdź). Jest to ogólna własność dla skończonych X-ów:
Stwierdzenie 2.7: Jeśli X jest skończony, to algorytm Sardinasa-Pattersona jest efek­tywną procedurą rozstrzygającą, czy X jest kodem.

Dowód: Zbiory Un zawierają suffiksy zbioru X. Jeśli X jest skończony, to i zbiór wszystkich jego suffiksów jest skończony, więc zbiór wszystkich możliwych Un jest skończony.
Stwierdzenie 2.7 prawdzie jest dla dowolnych, również nieskończonych, zbiorów regu­larnych. Pokażemy to w części nieobowiązkowej; tu zadowolimy się jedynie sformuło­waniem tego faktu:
Twierdzenie 2.8: Jeśli X jest regularny, to algorytm Sardinasa-Pattersona jest efek­tywną procedurą rozstrzygającą, czy X jest kodem.
Ćwiczenie 2.9: Zbadaj, które z poniższych zbiorów są kodami:

(1) {aa, ab, aab, abb, bb}

(2) {aaa, aaba, aabb, ab, baa, baba, babb, bba, bbb}


  1. {aa, aab}

  2. {a, aba, abab, banb}

  3. {aa, ab, aab, bba}

  4. {b, ab, baa, abaa, aaaa}

  5. {ab, ba}{aa, bb}*

  6. {aa, aba, abb, b} – kod

  7. {abn | nN} – kod

  8. {a, aab, bab, bb} – kod

  9. {a, aaab, aba} – nie kod

  10. {aa, aaa}

DODATEK NIEOBOWIĄZKOWY - DOWODY TWIERDZEŃ 2.3 I 2.8
Dowód Tw. 2.3 oparty będzie na następującym lemacie:
Lemat 2.10: Niech XA+.

(n1) (k:1kn) [Un  (uUk) (i,j0) i+j+k=n  uXiXj]



Dowód: Indukcja, dla każdego ustalonego n1, zstępująca względem k.

Krok początkowy: Niech k=n. Jeśli Un, to dla u=, i=j=0 mamy i+j+k=0+0+n=n i uXiXj={}{}={}. Odwrotnie, jeśli i+j+k=n, to i=j=0, więc jeśli uXiXj= u{}{}, to u=, czyli Un.

Założenie indukcyjne: Równoważność lematu zachodzi dla k+1n:

Un  (uUk+1) (i,j0) i+j+k+1=n  uXiXj



Krok indukcyjny: Z założenia indukcyjnego wywnioskujemy, że równoważność lematu zachodzi dla kn. Najpierw pokażemy implikację , potem .

Krok indukcyjny :

Jeśli Un, to (z zał. ind.) (vUk+1) (i,j0) i+j+k+1=n  vXiXj. Istnieją zatem słowa xXi i yXj takie, że vx=y. Ponieważ vUk+1, zachodzi przynajmniej jeden z dwu przypadków:

(1) vUk/X, a wtedy (zX) zvUk

lub (2) vX/Uk, a wtedy (uUk) uvX

Jeśli (1), to (zv)x=z(vx). Ale (zv)x(zv)Xi i z(vx)=zyXXj=Xj+1, więc dla u=zvUk mamy uxuXiXj+1, czyli (uUk) uXiXj+1. Równość i+(j+1)+k=n wynika wprost z założenia indukcyjnego.

Jeśli (2), to (uv)x=u(vx). Ale (uv)xXXi i u(vx)=uyuXj, zatem dla uUk mamy uvx= uyuXjXi+1, więc (uUk) uXjXi+1. Równość j+(i+1)+k=n wynika z zał. ind.



Krok indukcyjny :

Teraz przyjmujemy, że (uUk) (i,j0) i+j+k=n  uXiXj. Zatem ux1...xi=y1...yj dla pewnych xr,ysX. Jeśli j=0 to i=0 i k=n, jest to więc, sprawdzony wcześniej, krok początkowy. Przyjmijmy j1; możliwe są dwa przypadki:

(1) u=y1v dla pewnego vA*; Wtedy vUk/XUk+1 i ponadto vx1...xi=y2...yj.

Zatem vXiXj-1 i (z zał. ind.) Un.

(2) y1=uv dla pewnego vA*; Wtedy vX/UkUk+1 i ponadto x1...xi=vy2...yj.

Zatem XivXj-1 i (z zał. ind.) Un.

To kończy dowód Lematu 2.10. 
Warto zauważyć, że natura zbioru U1 nie odgrywała żadnej roli w dowodzie Lematu 2.10. Innymi słowy, lemat ten pozostaje prawdziwy, gdy U1 zastąpimy dowolnym zbiorem Y (oczywiście, zachowując definicję zbiorów Un dla n1 jak w Konstrukcji 2.2). Trzeba tu jednak podkreślić, że w dowodzie Tw. 2.3 (niżej) definicja U1=X/X{} jest już istotna.
Teraz jesteśmy już gotowi do udowodnienia Twierdzenia 2.3:
Twierdzenie 2.3: Zbiór XA+ jest kodem (n1) Un(X).

Dowód: Wygodniej będzie pokazać równoważność zaprzeczeń (dowód nie wprost).

() Jeśli X nie jest kodem, to istnieją xi,yjX takie, że x1...xp=y1...yp i x1y1. Niech |y1||x1|, czyli x1=y1u dla pewnego uA+. Ale wtedy uU1 oraz uXp-1Xq-1. Z Lematu 2.9 mamy Up+q-1.

() Jeśli Un, to weźmy k=1 w Lemacie 2.9. Istnieje uU1 oraz i,j0 takie, że uXiXj. Ale uU1 pociąga, że xu=y dla pewnych x,yX, ponadto xy, bo u.
Z tego, że xuXixXj wynika, że yXixXj, więc X nie jest kodem.
Pokażemy teraz, że Tw. 2.3 dostarcza efektywny algorytm testujący, czy dowolny zbiór regularny jest kodem.
Twierdzenie 2.11: Jeśli XA+ jest regularny, to zbiór {Un | n1} jest skończony.

Uwaga: Dla X-ów skończonych teza jest oczywista - zob. Stwierdzenie 2.7.

Dowód: Określmy relację XA*A* następująco:

uXv  X/u=X/v  (u==v  uv)

Zauważmy, że X jest relacją równoważności [ćwiczenie], oraz jeśli X jest regularny, to liczba klas abstrakcji relacji X jest skończona [ćwiczenie] i X jest wtedy skończoną sumą klas (niekoniecznie wszystkich) relacji X [ćwiczenie]. Można pokazać następujący

Fakt: Jeśli LA* jest skończoną sumą klas relacji X,
to (YA*) L/Y też jest skończoną sumą klas relacji X.

Udowodnij jako ćwiczenie; skorzystaj z faktu, że (L/Y)/w=L/Yw.

Teraz pokażemy indukcyjnie, że dla każdego n1 zbiór Un jest sumą pewnych klas abstrakcji relacji X. Jeśli n=1, to U1=X/X-{}, a X/X jest sumą klas (z powyższgo Faktu), zatem X/X-{} jest też sumą klas (po usunięciu klasy []). Jeśli Un jest sumą klas to, znów korzystając z Faktu, wnioskujemy, że X/Un i Un/X też są sumami klas X. Zatem ich suma Un+1=X/UnUn/X też jest sumą klas relacji X. Ale liczba klas relacji X jest skończona (bo X regularny), więc liczba różnych sum tych klas jest też skończona, zatem liczba różnych zbiorów Un jest skończona. 


Właśnie udowodniliśmy Tw. 2.8:
Twierdzenie 2.8:

Problem „Czy dany zbiór regularny XA+ jest kodem?” jest rozstrzygalny.



Dowód: Wystarczy sprawdzić (wobec Tw. 2.3), czy Un(X) dla wszystkich Un(X). Można to zrobić efektywnie, bo zbiory Un są regularne (bo X regularny) i jest ich skoń­czenie wiele (Tw. 2.11). 
Uwaga 2.12: Jeśli XA+ jest prefiksowy (więc jest kodem), to U1=X/X{}=. Zatem dla regularnych zbiorów prefiksowych algorytm staje już po pierwszym kroku. Nie jest to prawdą dla zbiorów suffiksowych; dzieje się tak dlatego, że ciąg Un został zde­finiowany pod kątem testowania od lewej do prawej. Oczywiście, dla regularnych zbiorów suffiksowych algorytm też staje, tyle że nie od razu.


Kody – Lekcja 2


©absta.pl 2016
wyślij wiadomość

    Strona główna