Naiwne wyszukiwanie wzorca w tekście


Tematy pokrewne   Podrozdziały
Łańcuchy znakowe
Podstawowe pojęcia dotyczące przetwarzania tekstów
Podstawowe operacje na łańcuchach znakowych
Naiwne wyszukiwanie wzorca w tekście
Wyszukiwanie maksymalnego prefikso-sufiksu
Szybkie wyszukiwanie wzorca algorytmem Morrisa-Pratta
Szybkie wyszukiwanie wzorca algorytmem Knutha-Morrisa-Pratta
Szybkie wyszukiwanie wzorca uproszczonym algorytmem Boyera-Moore'a
Szybkie wyszukiwanie wzorca pełnym algorytmem Boyera-Moore'a
Wyszukiwanie wzorca algorytmem Karpa-Rabina
Zliczanie słów w łańcuchu
Dzielenie łańcucha na słowa
Wyszukiwanie najdłuższego słowa w łańcuchu
Wyszukiwanie najdłuższego wspólnego podłańcucha
Wyszukiwanie najdłuższego wspólnego podciągu
Wyszukiwanie najkrótszego wspólnego nadłańcucha
Wyszukiwanie słów podwójnych
Wyszukiwanie palindromów
MasterMind – komputer kontra człowiek
MasterMind – człowiek kontra komputer
Szyfr Cezara
Szyfrowanie z pseudolosowym odstępem
Szyfry przestawieniowe
Szyfr Enigmy
Szyfrowanie RSA
Dodawanie dużych liczb
Mnożenie dużych liczb
Potęgowanie dużych liczb
Duże liczby Fibonacciego
Haszowanie
Wbudowane generatory liczb pseudolosowych
Generowanie liczb pseudolosowych
Podstawowe operacje na tablicach
Wyszukiwanie liniowe
  Rozwiązanie 1
Rozwiązanie 2

 

Problem

W łańcuchu znakowym s znaleźć wszystkie wystąpienia wzorca p.

 

 

Rozwiązanie nr 1

Problem Wyszukiwania Wzorca WW (ang. pattern matching) to jeden z podstawowych problemów tekstowych, który intensywnie badali wybitni informatycy. Rozwiązaniem jest wskazanie w ciągu s wszystkich pozycji i takich, że zachodzi równość:

 

s[i : i + |p|] = p

 

Oznacza to, iż wzorzec p jest fragmentem łańcucha s występującym na pozycji i-tej.

 

Algorytm N – naiwny – ustawia okno o długości wzorca p na pierwszej pozycji w łańcuchu s. Następnie sprawdza, czy zawartość tego okna jest równa wzorcowi p. Jeśli tak, pozycja okna jest zwracana jako wynik, po czym okno przesuwa się o jedną pozycję w prawo i cała procedura powtarza się. Algorytm kończymy, gdy okno wyjdzie poza koniec łańcucha. Klasa pesymistycznej złożoności obliczeniowej algorytmu N jest równa O(n × m), gdzie n oznacza liczbę znaków tekstu, a m liczbę znaków wzorca. Jednakże w typowych warunkach algorytm pracuje w czasie O(n), ponieważ zwykle wystarczy porównanie kilku początkowych znaków okna z wzorcem, aby stwierdzić, iż są one niezgodne.

 

Algorytm naiwny wyszukiwania wzorca w łańcuchu tekstowym

Wejście
s  –  łańcuch znakowy
p  –  łańcuch wzorca
Wyjście:

Wszystkie pozycje wzorca p w łańcuchu s.

Elementy pomocnicze:
i  –  pozycja okna, i N
n  – długość łańcucha s, n N
m  – długość wzorca p, m N
Lista kroków:
K01: n ← |s| ; obliczamy długość łańcucha s
K02: m ← |p| ; obliczamy długość wzorca p
K03: Dla i = 0,1,... n - m wykonuj K04  
K04:     Jeśli p = s[i : i + m], to pisz i ; okno zawiera wzorzec?
K05: Zakończ  

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Program generuje 80 znakowy łańcuch zbudowany z pseudolosowych kombinacji liter A, B i C. Następnie losuje 3 literowy wzorzec z tych samych liter i algorytmem naiwnym wyszukuje wszystkie wystąpienia wzorca w łańcuchu. Pozycję wzorca zaznacza znakiem ^.

 

Lazarus
// Algorytm WWN
// Data:   29.05.2008
// (C)2012 mgr Jerzy Wałaszek
//-----------------------------

program prg;

var
  s,p : ansistring;
  i : integer;

begin
  randomize;

  // generujemy łańcuch

  s := '';
  for i := 1 to 80 do s := s + chr(65 + random(3));

  // generujemy wzorzec

  p := '';
  for i := 1 to 3 do p := p + chr(65 + random(3));

  // wypisujemy wzorzec

  writeln(p); 

  // wypisujemy łańcuch

  write(s);

  // szukamy wzorca w łańcuchu

  for i := 1 to 78 do
    if p = copy(s,i,3) then write('^') else write(' ');

  writeln;
  writeln;
end.
Code::Blocks
// Algorytm WWN
// Data:   29.05.2008
// (C)2012 mgr Jerzy Wałaszek
//-----------------------------

#include <iostream>
#include <string>
#include <cstdlib>
#include <time.h>

using namespace std;

int main()
{
  string s,p;
  int i;
  
  srand((unsigned)time(NULL));

  // generujemy łańcuch

  s = "";
  for(i = 0; i < 80; i++) s += char(65 + (rand() % 3));

  // generujemy wzorzec

  p = "";
  for(i = 0; i < 3; i++) p += char(65 + (rand() % 3));

  // wypisujemy wzorzec

  cout << p << endl; 

  // wypisujemy łańcuch

  cout << s;

  // szukamy wzorca w łańcuchu

  for(i = 0; i < 78; i++)
    cout << (p == s.substr(i,3) ? "^" : " ");

  cout << endl << endl;
  return 0;
}
Free Basic
' Algorytm WWN
' Data:   29.05.2008
' (C)2012 mgr Jerzy Wałaszek
'-----------------------------

Dim As String s,p
Dim As Integer i

Randomize

' generujemy łańcuch

s = ""
For i = 1 To 80: s += Chr(65 + Cint(Rnd * 2)): Next

' generujemy wzorzec

p = ""
For i = 1 To 3: p += Chr(65 + Cint(Rnd * 2)): Next

' wypisujemy wzorzec

Print p

' wypisujemy łańcuch

Print s;

' szukamy wzorca w łańcuchu

For i = 1 To 78
  If p = Mid(s,i,3) Then Print "^";: Else Print " ";
Next
Print: Print
End
Wynik
CBC
AACBBAACCACBCCBABBBBABACAABAAACABCABBCBAAAAAAACCAAACBBAACABCBCCABCBCCBCBCAABACAC
          ^                                                ^     ^  ^ ^

 

Wyszukiwanie wzorca algorytmem N
(C)2012 mgr Jerzy Wałaszek


...

 

Rozwiązanie nr 2

Algorytm N możemy nieco usprawnić wykorzystując ideę wartowników. Na końcu łańcucha oraz wzorca umieszczamy dwa różne znaki. Zapobiegną one wyjściu poza obszar łańcucha przy testowaniu znaków w oknie i we wzorcu. Dzięki nim odpadnie sprawdzanie zakresu indeksów w oknie – algorytm wykona mniej operacji.

 

Algorytm naiwny wyszukiwania wzorca z wartownikami

Wejście
s  –  łańcuch znakowy
p  –  łańcuch wzorca
Wyjście:

Wszystkie pozycje wzorca p w łańcuchu s.

Elementy pomocnicze:
i  –  pozycja okna w łańcuchu s, i N
j  – pozycja wewnątrz okna, j N
n  – długość łańcucha s, n N
m  – długość wzorca p, m N
Lista kroków:
K01: n ← |s| ; obliczamy długość łańcucha s
K02: m ← |p| ; obliczamy długość wzorca p
K03: ss + 'X' ; na końcu łańcucha umieszczamy wartownika
K04: pp + 'Y' ; na końcu wzorca umieszczamy innego wartownika
K05: Dla i = 0,1,...,n - m wykonuj K06...K08 ; pozycje okna
K06:     j ← 0 ; pozycja w oknie i we wzorcu
K07:     Dopóki s[i + j] = p[j], wykonuj jj + 1 ; szukamy pierwszego różnego znaku okna i wzorca
K08:     Jeśli j = m, to pisz i ; sprawdzamy, czy cały wzorzec wystąpił w oknie
K09: Usuń ostatni znak z s ; pozbywamy się wartownika z łańcucha
K10: Usuń ostatni znak z p ; pozbywamy się wartownika ze wzorca
K11: Zakończ  

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Program generuje 80 znakowy łańcuch zbudowany z pseudolosowych kombinacji liter A, B i C. Następnie losuje 3 literowy wzorzec z tych samych liter i algorytmem naiwnym wyszukuje wszystkie wystąpienia wzorca w łańcuchu. Pozycję wzorca zaznacza znakiem ^.

 

Lazarus
// Algorytm WWN z wartownikami
// Data:   30.05.2008
// (C)2012 mgr Jerzy Wałaszek
//-----------------------------

program prg;

var
  s,p : ansistring;
  i,j : integer;

begin
  randomize;

  // generujemy łańcuch

  s := '';
  for i := 1 to 80 do s := s + chr(65 + random(3));

  // generujemy wzorzec

  p := '';
  for i := 1 to 3 do p := p + chr(65 + random(3));

  // wypisujemy wzorzec

  writeln(p);

  // wypisujemy łańcuch

  write(s);

  // dodajemy wartowników

  s := s + 'X'; p := p + 'Y';

  // szukamy wzorca w łańcuchu

  for i := 1 to 78 do
  begin
    j := 0;
    while s[i + j] = p[j + 1] do inc(j);
    if j = 3 then write('^') else write(' ');
  end;

  writeln;
  writeln;
end.
Code::Blocks
// Algorytm WWN z wartownikami
// Data:   30.05.2008
// (C)2012 mgr Jerzy Wałaszek
//-----------------------------

#include <iostream>
#include <cstdlib>
#include <time.h>

using namespace std;

int main()
{
  string s,p;
  int i,j;

  srand((unsigned)time(NULL));

  // generujemy łańcuch

  s = "";
  for(i = 0; i < 80; i++) s += char(65 + (rand() % 3));

  // generujemy wzorzec

  p = "";
  for(i = 0; i < 3; i++) p += char(65 + (rand() % 3));

  // wypisujemy wzorzec

  cout << p << endl; 

  // wypisujemy łańcuch

  cout << s;

  // dodajemy wartowników

  s += "X"; p += "Y";

  // szukamy wzorca w łańcuchu

  for(i = 0; i < 78; i++)
  {
    for(j = 0; s[i + j] == p[j]; j++) ;
    cout << (j == 3 ? "^" : " ");
  }

  cout << endl << endl;
  return 0;
}
Free Basic
' Algorytm WWN z wartownikami
' Data:   30.05.2008
' (C)2012 mgr Jerzy Wałaszek
'-----------------------------

Dim As String s,p
Dim As Integer i,j

Randomize

' generujemy łańcuch

s = ""
For i = 1 To 80: s += Chr(65 + Cint(Rnd * 2)): Next

' generujemy wzorzec

p = ""
For i = 1 To 3: p += Chr(65 + Cint(Rnd * 2)): Next

' wypisujemy wzorzec

Print p

' wypisujemy łańcuch

Print s;

' dodajemy wartowników

s += "X": p += "Y"

' szukamy wzorca w łańcuchu

For i = 1 To 78
  j = 0
  While Mid(s,i + j,1) = Mid(p,j + 1,1): j += 1: Wend
  If j = 3 Then Print "^";: Else Print " ";
Next

Print: Print
End

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.