algorytm.org

Algorytm GS' (Galila Seiferasa)

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Algorytm GS' (Galila Seiferasa)
Ocena użytkowników:***** / 1
SłabyŚwietny 
Wpisany przez Tomasz Lubiński, 26 lipca 2005 19:08

Podstawowym problemem dotyczącym tekstów jest problem wyszukiwania wzorca. Polega on na znalezieniu wszystkich wystąpień tekstu wzorzec, w tekście tekst. Przyjmujemy ponadto, że: |wzorzec|=m, |tekst|=n oraz n>=m.

Algorytm Galila-Seiferasa umożliwia rozwiązanie tego problemu w czasie liniowym i jednocześnie w pamięcie O(1). Przez pewien czas uważano nawet, że taki algorytm w ogóle nie jest możliwy. Poniżej zostanie opisana jego słabsza wersja.
Na potrzeby tego algorytmu wprowadziwy najpierw pojęcie wzorca łatwego. O wzorcu x powiemy, że jest łatwy, gdy żadne słowo niepuste postaci vvv nie jest jego prefiksem. Na przykład x=bcbcbcdef nie jest ławty, gdyż dla v=bc można zapisać, go jako x=vvvdef, natomiast x=abbababba jest wzorcem łatwym.
W przypadku, gdy mamy do czynienia ze wzorcem ławtym można skonstruować algorytm podobny do algorytmu KMP, w którym tablicę P zastępuje się przez pewne przybliżone oszacowania: P[j]<2j/3, przesunięcie(j)≥j/3

Gotowy algorytm ma postać:
while i<=n-m+1 do
begin
  j:=0;
  while ((j<m)and(wzorzec[j+1]=tekst[i+j])) do j:=j+1;
  if j=m then writeln((IntToStr(i)));
  i:=i+max(1,ceil(j/3));
end;

Algorytm GS' dla wzorców, ktore nie są łatwe, może (choć nie musi) dać odpowiedź niepoprawną. Dla następującego przykładu: wzorzec=aaaaaaab i tekst=aaaaaaaab zostanie wypisanych zero wystąpień wzorca, podczas gdy występuje on w tekscie począwszy od pozycji 2.
Przykładem zbioru łatwych wzorców jest zbiór słów Fibonacciego, który tworzy się podobnie jak ciąg liczb Fibonacciego, z tą jednak różnicą, że zamiast klasycznej sumy liczb stosuje się konkatenację lańcuchów: fibk+2=fibk+1fibk dla k>0. Na przykład dla fib1=a, fib2=b otrzymamy kolejno: fib3=ba, fib4=bab, fib5=babba, fib6=babbbabab.

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Tomasz LubińskiC/C++
.cpp
.cpp
***** / 1
Tomasz LubińskiDelphi/Pascal
.pas
.pas
***** / 1
Tomasz LubińskiJava
.java
.java
***** / 1
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 11 czerwca 2011 14:21
Komentarze
photo
-1 # Nerus 2010-11-20 13:18
Witam, chciałbym się dowiedzieć jaka jest różnica między algorytmem naiwnym a przedstawionym, dodatkowo chciałbym zaznaczyć że w kodzie C++ "chyba" występuje błąd tekst[i+j-1] "-1"
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz