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], ; okno zawiera wzorzec?
       to pisz i ; jeśli tak, to wypisujemy pozycję
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 <ctime>

using namespace std;

int main()
{
  string s, p;
  int i;
 
  srand(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 " ";
  End If
Next
Print: Print
End

Python (dodatek)

# Algorytm WWN
# Data:   6.03.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------

import random

s = "" # łańcuch
p = "" # wzorzec

# generujemy łańcuch

for i in range(60):
    s += chr(random.randrange(65,68))

# generujemy wzorzec

for i in range(3):
    p += chr(random.randrange(65,68))

# wypisujemy wzorzec

print(p)

# wypisujemy łańcuch

print(s)

# szukamy wzorca w łańcuchu

for i in range(58):
    if p == s[i:i+3]:
        print("^", end="")
    else:
        print(" ", end="")
print()
print()

Wynik:

ACC
CAACCAABCBCAAAABAACCABBBAACCCCACBCACBBABAAABCCABAABCBAABCACC
  ^              ^       ^                               ^

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 – w efekcie 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: ; pozycje okna
     wykonuj kroki K06…K08
K06:  j ← 0 ; pozycja w oknie i we wzorcu
K07:  Dopóki s[i+j] = p[j], ; szukamy pierwszego różnego
      wykonuj j ← j + 1     ; znaku okna i wzorca
K08:  Jeśli j = m, ; sprawdzamy, czy cały wzorzec
      to pisz i    ; 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 <ctime>

using namespace std;

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

  srand(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 " ";
  End If
Next

Print: Print
End

Python (dodatek)

# Algorytm WWN z wartownikami
# Data:   6.03.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------

import random

# generujemy łańcuch

s = ""
for i in range(60):
    s += chr(random.randrange(65,68))

# generujemy wzorzec

p = ""
for i in range(3):
    p += chr(random.randrange(65,68))

# wypisujemy wzorzec

print(p)

# wypisujemy łańcuch

print(s)

# dodajemy wartowników

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

# szukamy wzorca w łańcuchu

for i in range(58):
    j = 0
    while s[i+j:i+j+1] == p[j:j+1]:
        j += 1
    if j == 3:
        print("^", end="")
    else:
        print(" ", end="")
print()
print()

Jako ćwiczenie dodaj do programu usuwanie wartowników przed zakończeniem pracy.

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