Sequential Search and Brute Force String Matching

Kategori: Algorithm Design and Analysis , 12 Haziran 2020 , JanFranco


Brute force algoritmalarını görmeye devam ediyoruz, bu kez sequential search ve string matching algoritmalarına bakacağız:


Algorithm SequentialSearch(A[0..n], K)

A[n] <- K
i <- 0
while A[i] != K do
    i <- i + 1
if i < n return i
else return -1
Sequential search algoritmasında, aradığımız değer bulunana kadar i indisini birer birer artırırız. Dizide aradığımız elemanı bulduğumuzda while döngüsü sona erer. Eğer i < n ise elemanı bulduk demektir, i indisinin değerini return ederiz. Eğer i < n değilse eleman bulunamamıştır ve -1 return edilir. Veya farklı bir değer.

Bu algoritmanın zaman etkinliği O(n)'dir. Algoritmanın Worst Case'i elemanın dizide olmamasıdır. Eleman dizide olmadığından bütün diziyi tararız (n). Best Case ise aranan elemanın dizinin 0. indisinde olmasıdır. Bu durumda ilk elemanı kontrol ederiz ve while döngüsü sona erer (1).

Brute force string matching algoritmasında ya bir kelimede harf dizisi veya harf ararız ya da bir text'te bir kelime ararız. Sahte kodu görelim:


Algorithm BruteForceStringMatch(T[0..n-1], P[0..m-1])

for i <- 0 to n - m do
    j <- 0
    while j < m and P[j] = T[i + j] do
	j <- j + 1
    if j = m return i
return -1
Eğer kelimenin uzunlu 20 ise, aradığımız harf dizisi de 5 harfli ise, kelimede sona kadar gitmemize gerek yoktur, 20 - 5 kadar gitmeliyiz. 16. indise geldiğimizde zaten 5 harf kalmayacaktır bu nedenle 5 harflik bir dizi arattığımızdan bulunma ihtimali yoktur. İlk for döngüsünün 0'dan n-m'e kadar çalışmasının mantığı budur.

İçteki while döngüsünde, i. indisten başlayarak birer birer aranılan dizi uzunluğu kadar gideriz. Eğer bir harf uyuşmazsa while döngüsünü sona erdiririz. Eğer kelime, harf dizisi bulunulursa j = m olacağından dolayı, bunun kontrolünü yaparız. Eğer aradığımız bulursak, başlangıç indisini return ederiz. Bir örnek üzerinden görelim:


N O B O D Y _ N O T I C E D _ H I M
N O T
  N O T
    N O T
      N O T
	N O T
	  N O T
	    N O T
	      N O T
Bu algoritmanın Worst Case'i aranılan dizinin hem string'de olmaması hem de aranılan dizinin son harfi hariç tüm harflerinin string ile uyuşmasıdır. Bunu bir örnekle görelim:

11111111111111111111

Bu dizide 1110 dizisini aratırsak hem tüm diziyi gezeceğiz, hem de her indiste 3 kez 1110 karşılaştırması yapacağız. Sadece 0 karakterini arasaydık bu daha iyi bir durum olurdu. Best Case ise ilk indiste aranılan karakterin veya dizinin bulunmasıdır.


Yorumlar

Henüz bir yorum bulunmuyor.