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.

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

do podrozdziału do 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.

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: 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 jego pracy.

do podrozdziału do 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:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Rozwiązanie nr 2

Algorytm naiwny wyszukiwania wzorca z wartownikami

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy