Strona główna

Z 90 min adanie5 5


Pobieranie 41.5 Kb.
Data18.06.2016
Rozmiar41.5 Kb.

Algorytmy w VB autor: Janusz Białowąs

Z
90 min
adanie5_5


Wyszukiwanie wzorca w tekście za pomocą algorytmu Boyera-Moore’a

OPIS ZADANIA

Zadanie to polega na utworzeniu aplikacji wyszukującej podany wzorzec w tekście. Program będzie wykorzystywał znany algorytm Boyera-Moore’a, pozwalający efektywnie sprawdzić, czy podany wzorzec występuje w tekście.
Celem zadania jest: zapoznanie się z nowym algorytmem służącym do wyszukiwania.
EFEKT KOŃCOWY

Efektem końcowym zadania jest aplikacja przedstawiona na ilustracji poniżej. Wykorzystuje ona znany algorytm do wyszukiwania wzorca w podanym tekście.



- Zadanie nie wymaga plików ćwiczeniowych.

REALIZACJA ZADANIA



Wykonując to zadanie, dowiesz się, jak wyszukać podaną frazę w tekście. Aplikacja będzie odczytywać tekst
z dysku i wyszukiwać w nim wszystkie przypadki wystąpień podanego wzorca. Do wyszukiwania zastosujesz algorytm Boyera-Moore’a. Podczas wykonywania zadania skoncentruj się na algorytmie oraz jego praktycznej implementacji w VB.NET
Uwaga: W kolejnych krokach scenariusza nowo dodany kod oznaczony został czcionką pogrubioną. Niepogrubione linie kodu mają służyć wyłącznie do oznaczenia miejsca, w którym należy wpisać nowy kod.
Krok 1: Tworzenie projektu formularza

  1. Utwórz nowy projekt aplikacji Windows o nazwie BoyerMoore w folderze wskazanym przez nauczyciela.

  2. Ustaw następujące właściwości formularza:



      Właściwość

      Wartość

      Text

      Algorytm Boyera-Moore’a



  3. Na formularzu umieść kontrolki widoczne na rysunku: 2 etykiety Label, przycisk Button oraz pole tekstowe TextBox.



      Typ kontrolki

      Nazwa kontrolki

      Właściwość Text kontrolki

      Label

      Label1

      Podaj szukaną frazę

      Label

      lblTekst



      Button

      btnSprawdz

      Sprawdź

      TextBox

      txtWzorzec





Krok 2: Utworzenie procedury tworzącej tablicę przesunięć dla wzorca

  1. Przejdź do edytora kodu i zadeklaruj zmienne globalne w programie.

Public Class Form1

Inherits System.Windows.Forms.Form

Dim tablicaP(52) As Integer

Dim wzorzec As String

Dim tekst As String

  1. Utwórz funkcję indeks, zwracającą numer litery w alfabecie.

Function indeks(ByVal znak As Char) As Integer

End Sub

  1. Sprawdź, czy znak to spacja; jeżeli tak, funkcja zwraca wartość zero.

Function indeks(ByVal znak As Char) As Integer

If znak = " " Then

Return 0

  1. Oblicz numer znaku w alfabecie, pamiętając o rozróżnieniu małych i dużych liter i zwróć go jak wartość funkcji.

If znak = " " Then

Return 0

Else

If znak.IsLower(znak) Then

Return Asc(znak) - Asc("a") + 1

Else

Return Asc(znak) - Asc("A") + 27

End If

End If

  1. Utwórz procedurę przesuniecie z jednym parametrem typu String.

Sub przesuniecie(ByVal wzorzec As String)

End Sub

  1. Zadeklaruj zmienne pomocnicze w procedurze.

Sub przesuniecie(ByVal wzorzec As String)

Dim i As Integer

  1. Wypełnij tablicę przesunięć wartością długości wzorca.

ReDim tablicaP(wzorzec.Length)

tablicaP(0) = 0

For i = 0 To 52

tablicaP(i) = wzorzec.Length - 1

Next

  1. Wypełnij pola tablicy, dla których występują znaki we wzorcu odpowiednią wartością przesunięcia.

For i = 0 To 52

tablicaP(i) = wzorzec.Length - 1

Next

For i = 0 To wzorzec.Length - 1

tablicaP(indeks(wzorzec.Chars(i))) = wzorzec.Length - i - 1

Next

Krok 3: Tworzenie procedur wyszukujących wzorzec w tekście z wykorzystaniem tablicy przesunięć

  1. Kliknij dwukrotnie na pasek aplikacji by przejść do edytora kodu i procedury zdarzenia Load formularza.

Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load

End Sub

  1. Odczytaj z pliku tekst, który będzie wyszukiwany. Operacje odczytu umieść w bloku kodu chronionego
    i obsłuż wyjątki mogące wystąpić podczas odczytu danych z pliku.

Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load

Dim NrPliku As String

NrPliku = FreeFile()

Try

FileOpen(NrPliku, "..\tekst.txt", OpenMode.Input)

tekst = LineInput(NrPliku)

lblTekst.Text = tekst

Catch ex As Exception

MessageBox.Show("Bład podczas odczytu z pliku", "Błąd", MessageBoxButtons.OK, MessageBoxIcon.Error)

Finally

FileClose(NrPliku)

End Try

  1. Kliknij dwukrotnie przycisk Sprawdź, aby przejść do edytora kodu i procedury obsługi zdarzenia kliknięcia tej kontrolki.

Private Sub btnSprawdz_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles btnSprawdz.Click

End Sub

  1. Zadeklaruj zmienne lokalne i odczytaj wartość wzorca z pola tekstowego.

Private Sub btnSprawdz_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles btnSprawdz.Click

Dim i, j, x As Integer

wzorzec = txtWzorzec.Text

  1. Odczytaj długość wzorca

Dim i, j, x As Integer

wzorzec = txtWzorzec.Text

i = wzorzec.Length

j = wzorzec.Length

  1. Wpisz blok kodu wyszukujący wzorca w tekście. Zwróć uwagę na zastosowanie tablicy przesunięć oraz funkcji indeks.

i = wzorzec.Length

j = wzorzec.Length

Do While j > 0

j -= 1

i -= 1

Do While tekst.Chars(i) <> wzorzec.Chars(j)

x = tablicaP(indeks(tekst.Chars(i)))

If wzorzec.Length - j > x Then

i = i + wzorzec.Length - j

Else

i = i + x

End If

If i >= tekst.Length Then

MessageBox.Show("Brak wzorca w tekście ", "Wynik", MessageBoxButtons.OK, MessageBoxIcon.Information)

Exit Sub

End If

j = wzorzec.Length - 1

Loop

Loop

MessageBox.Show("Wzorzec występuje na pozycji " & i, "Wynik", MessageBoxButtons.OK, MessageBoxIcon.Information)

Krok 4: Testowanie aplikacji

  1. Utwórz plik tekstowy zawierający tekst, w którym będzie wyszukiwany wzorzec. Nazwij plik tekst.txt
    i zapisz go w folderze rozwiązania.

  2. Uruchom aplikację i sprawdź działanie programu dla różnych wzorców.

  3. Jeśli poznałeś algorytm K-M-P, zastanów się na efektywnością obydwu poznanych sposobów wyszukiwania wzorca.


Algorytmika i programowanie


©snauka.pl 2016
wyślij wiadomość