Zaawansowane algorytmy i struktury danych/Wykład 3

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Zaawansowane algorytmy tekstowe III



W module tym zajmiemy się wykrywaniem regularności w tekstach: szukaniem symetrii.

Słowo jest symetryczne, gdy , gdzie jest operacją odwracania słowa. Algorytmicznie symetrie w słowach są bardzo interesujące.


Wykrywanie symetrii w tekstach

Słowo nazwiemy palindromem, gdy jest symetryczne oraz . Palindromy parzyste to palindromy o parzystej długości. Oznaczmy zbiór wszystkich palindromów przez , a przez oznaczmy odpowiednio zbiory palindromów parzystych i nieparzystych.

Przykładami palindromów są słowa:

kajak, atypotopyta, zagwiżdżiwgaz


Problem najdłuższego prefikso-palindromu polega na rozkładzie danego słowa takim, że oraz jest najdłuższy o tej własności. Istnieje prosty algorytm oparty na tablicy prefikso-sufiksów .


Algorytm Prefikso-Palindrom


  1. oblicz tablicę P dla słowa-kompozycji (słowo długości ),
  2. jeśli to jest to długość najdłuższego prefikso-palindromu
  3. w przeciwnym przypadku nie ma prefikso-palindromu.

Podobnie możemy zdefiniować problem najkrótszego prefisko-palindromu. Algorytm powyższy można łatwo zmodyfikować, aby znajdował najkrótszy prefikso-palindrom.

Chociaż powyższy algorytm działa w czasie liniowym, możliwy jest szybszy algorytm, który znajduje najkrótszy prefikso-palindrom w czasie , gdzie jest długością najkrótszego prefikso-palindromu, założywszy że tekst posiada prefikso-palindrom.

Skoncentrujemy się na razie na palindromach parzystych. Definiujemy dla każdej pozycji promień palindromu parzystego o środku w jako:

Załóżmy, dla uproszczenia, że tekst zaczyna się od specjalnego symbolu (marker początku), który występuje tylko na początku.

Opiszemy algorytm, który oblicza tablice promieni palindromów dla kolejnych pozycji od strony lewej do prawej. Załóżmy, że policzyliśmy już wartości:

Okazuje się, że korzystając z symetrii możemy obliczyć pewne nowe elementy tablicy , nie wykonując żadnych porównań symboli. Wynika to z następującego faktu.


Własność promieni palindromów

Uzasadnimy krótko tę własność rozważając dwa przypadki:


Przypadek (a): .

Wówczas palindrom o środku w jest całowicie zawarty w dłuższym palindromie o środku w . Pozycja jest symetryczna do ze względu na . Zatem z symetrii o środku wynika, że najdłuższy palindrom o środku ma taki sam promień jak ten o środku . Zatem w tym przypadku .

Przypadek (b): .

Sytuacja jest pokazna na rysunku, który przedstawia maksymalne palindromy o środkach , i . Ponieważ (z definicji maksymalności palindromu o środku w ), zatem .

ZASD 3 3.jpg
Rysunek 3: Przypadek (b) dowodu własności promieni palindromów parzystych.

Poniżej przedstawiamy algorytm Promienie-Palindromów. W jednej głównej iteracji pętli while algorytm oblicza dla kolejnych , dla których . Jeśli ostatnim takim jest , wtedy zaczynamy całą główną iterację od nowego równego .

Pozostawiamy jako ćwiczenie modyfikację algorytmu, aby liczył promienie palindromów nieparzystych.

W pierwszym momencie, gdy algorytm wykryje prefikso-palindrom (promień palindromu sięga do początku tekstu), możemy algorytm zatrzymać i podać długość najkrótszego prefikso-palindromu. W sumie pokazaliśmy następujący fakt:

(a) Tablicę promieni palindromów (parzystych i nieparzystych) można policzyć w czasie liniowym.

(b) Długość najkrótszego prefikso-palindromu (zakładając że taki istnieje) można policzyć w czasie proporcjonalnym do jego długości.


Algorytm Promienie-Palindromów


; ;
;

while do
   while do ;
   ;
   ;
   while do
      ; ;
   ;;

Kompozycje słów symetrycznych

Rozważmy teraz interesujący (chociaż tylko czysto teoretyczny ) problem sprawdzania, czy słowo jest nietrywialną kompozycją słów symetrycznych. Przez oznaczmy odpowiednio zbiór konkatenacji dowolnej liczby słów należących do .

Elementy nazywamy palstarami a elementy nazywamy palstarami parzystymi.

Niech , będzie (ze względów technicznych załóżmy, że słowo puste też jest palstarem (parzystm i nieparzystym jednocześnie)) odpowiednio pierwszą pozycją w słowie taką, że , , wartością funkcji zaś jest zero, gdy nie ma takiego .


Algorytm Parzyste-Palstary


;
while do    ;
   if then return false;
   ;
return true;


Mówiąc nieformalnie, algorytm Parzyste-Palstary obcina słowo o najkrótszy prefikso-palindrom, aż tekst będzie pusty (sukces) albo aż się zatnie (nie ma rozkładu na parzyste palindromy). Algorytm Parzyste-Palstary ma złożoność liniową, ponieważ policzenie zajmuje czas proporcjonalny do wartości , zakładając, że . Nietrywialna natomiast jest poprawność algorytmu. Zdefiniujmy

oraz lub


Własność parzystych palstarów:

Poprawność algorytmu wynika natychmiast z powyższej własności. Pozostawiamy dowód tej własności jako ćwiczenie.

Możemy podobnie zdefiniować funkcję dla dowolnych palstarów i dowolnych palindromów. Własność parzystych palstarów nie zachodzi dla dowolnych palstarów, ale zachodzi własność bardziej skomplikowana.

Własność dowolnych palstarów:


Pozostawimay dowód tej własności jako ćwiczenie. Algorytm testowania dowolnych palstarów jest interesujący, ponieważ przebiega on zupełnie inaczej niż dla parzystych palstarów.

Pierwszym krokiem algorytmu jest stablicowanie funkcji . Obliczamy tablicę w czasie liniowym dla wszystkich łącznie.

Pozostawiamy jako ćwiczenie policzenie tej tablicy w czasie . Obliczenie takie opiera się na wykorzystaniu tablicy promieni palindromów.

Załóżmy teraz, że mamy tablicę FIRST. Funkcja działa teraz w czasie stałym (gotowe wartości z tablicy). Poniższy algorytm dla każdej pozycji sprawdza, czy . Odpowiedź jest zapisana w tablicy logicznej . Zakładamy, że początkowo tablica ma wartości \mathit{ false}, włącznie z elementami wykraczającymi poza zakres tablicy (dla uproszczenia zapisu).


Algorytm Testowanie-Palstarów


true;
for down to do    ;
   if then false
   else or or



Interesującym problemem jest rozkład słowa w postaci , gdzie jest ustalone. Istnieją algorytmy liniowe dla oparte na następującej własności zawężającej zbiór rozkładów do zweryfikowania:

jeśli to , dla pewnych gdzie jest najdłuższym palindromem będącym prefiksem lub jest najdłuższym palindromem będącym sufiksem .