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.
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
Autor | Język programowania | Komentarz | Otwórz | Pobierz | Ocena |
Tomasz Lubiński | C/C++ | .cpp | .cpp | ***** / 1 | |
Tomasz Lubiński | Delphi/Pascal | .pas | .pas | ***** / 1 | |
Tomasz Lubiński | Java | .java | .java | ***** / 1 |
Poprawiony: 11 czerwca 2011 14:21