Algorytmy i Struktury Danych - Naiwne wyszukiwanie wzorca

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.

Zmienne 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 krok K04
K04:	Jeśli p = s [ i : i + m ], to pisz i	okno zawiera wzorzec?
K05:	Zakończ

Przykładowe programy

Uwaga:

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 60 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 ^.

Pascal

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

program prg;

var
  s, p : ansistring;
  i : integer;

begin
  randomize;

  // generujemy łańcuch

  s := '';
  for i := 1 to 60 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

  writeln ( s );

  // szukamy wzorca w łańcuchu

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

  writeln;
  writeln;
end.

C++

// Algorytm WWN
// Data:   29.05.2008
// (C)2020 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 < 60; 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 << endl;

  // szukamy wzorca w łańcuchu

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

  cout << endl << endl;
  return 0;
}

Basic

' Algorytm WWN
' Data:   29.05.2008
' (C)2020 mgr Jerzy Wałaszek
'-----------------------------

Dim As String s, p
Dim As Integer i

Randomize

' generujemy łańcuch

s = ""
For i = 1 To 60: 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 58
  If p = Mid ( s, i, 3 ) Then Print "^";: Else Print " ";
Next
Print: Print
End

Wynik:

ABB
ABCBBAAABBCAABCBBABBBCCBAABCBBCCABCBACBBAACAABCCCABACCCACAAA
^ ^

Na początek: podrozdziału strony

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.

Zmienne 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:	s ← s + 'X'	na końcu łańcucha umieszczamy wartownika
K04:	p ← p + 'Y'	na końcu wzorca umieszczamy innego wartownika
K05:	Dla i = 0, 1, ..., n - m: wykonuj kroki K06...K08	pozycje okna
K06:	j ← 0	pozycja w oknie i we wzorcu
K07:	Dopóki s [ i + j ] = p [ j ], wykonuj j ← j + 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

Przykładowe programy

Uwaga:

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.

Pascal

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

program prg;

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

begin
  randomize;

  // generujemy łańcuch

  s := '';
  for i := 1 to 60 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

  writeln ( s );

  // dodajemy wartowników

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

  // szukamy wzorca w łańcuchu

  for i := 1 to 58 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.

C++

// Algorytm WWN z wartownikami
// Data:   30.05.2008
// (C)2020 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 < 60; 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 << endl;

  // dodajemy wartowników

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

  // szukamy wzorca w łańcuchu

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

  cout << endl << endl;
  return 0;
}

Basic

' Algorytm WWN z wartownikami
' Data:   30.05.2008
' (C)2020 mgr Jerzy Wałaszek
'-----------------------------

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

Randomize

' generujemy łańcuch

s = ""
For i = 1 To 60: 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 58
  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

Na początek: podrozdziału strony

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.

Naiwne wyszukiwanie wzorca w tekście

Problem

Rozwiązanie nr 1

Algorytm naiwny wyszukiwania wzorca w łańcuchu tekstowym

Wejście:

Wyjście:

Zmienne pomocnicze:

Lista kroków:

Przykładowe programy

Rozwiązanie nr 2

Algorytm naiwny wyszukiwania wzorca z wartownikami

Wejście:

Wyjście:

Zmienne pomocnicze:

Lista kroków:

Przykładowe programy