Pattern Matching Algorithm in Data Structure

Pattern Matching Algorithm in Data Structure – Pattern Matching का मतलब ये पता करना होता है कि क्या Input किया गया Substring किसी अन्‍य String में उपलब्ध है या नहीं। ये पता करने के लिए हमें किसी Array के हर Characters को Sub String के हर Character से Match करवाना होता है। किसी Pattern को Match करने के लिए विभिन्न प्रकार के Algorithms का प्रयोग किया जाता है। हम यहां पर सबसे ज्यादा प्रयोग में आने वाले व सबसे सरल Algorithm का प्रयोग किसी String में Pattern को Match करने के लिए कर रहे हैं। इस Algorithm को Brute Force Algorithm कहा जाता है। ये Algorithm निम्नानुसार है-

[code]
Algorithm 
Here ARRAY[N] and PATTERN[M] is a String of Size N and M. 
I, J and K are the Variables For Looping. 
STRLEN1 is the Length of ARRAY[N] and STRLEN2 is the Length of PATTERN[M]. 
This Algorithm Finds the Position of PATTERN[M] in ARRAY[N].

START
SET POS = 0
REPEATE FOR I = POS TO STRLEN1 – STRLEN2 STEP I = I + 1
SET J = 0
SET K = I
REPEATE STEP 7 and 8 WHILE ARRAY[K] == PATTERN[J] .AND. J<STRLEN2
K = K + 1
  J = J + 1
      [ End of Inner Loop ]
    IF J == PATTERN then BREAK
      [ End of Outer Loop ]
PRINT “String is at the Position” I
[/code]

इस Algorithm का प्रयोग करके हम निम्नानुसार एक Program बना सकते हैं। ये Program दो String User से लेता है और दूसरी String को पहली String में खोजता है। यदि पहली Sting में दूसरी String मिल जाती है तो ये Algorithm पहली String के उस Index Number को Return करता है जहां पर String का Pattern Match करता है। Program निम्नानुसार है-

[code]
#include <stdio.h>
#include <string.h>
#define SIZE 20

main()
{
char string[SIZE], substring[10],pos = 0;
int i, j, k, stringLength, subStringLength;

clrscr();

printf("Enter String : ");
gets(string);
fflush(stdin);

printf("Enter Sub String which you want to Find in String : ");
gets(substring);
fflush(stdin);

stringLength = strlen(string);
subStringLength = strlen(substring);

for(i=(int)pos; i<=stringLength-subStringLength; i++)
{
      j = 0;
      k = i;
      while((string[k] == substring[j]) && (j<subStringLength))
      {
            k++;
            j++;
      }
      if(j==substring)
            break;
}
printf("Sub String Found at Index Number %d", i);
getch();
}

Output 
Enter String : Indian Lata Mageskar 
Enter Sub String which you want to Find in String : Mageskar
Sub String Found at Index Number 13
[/code]

यहां हमने कुछ उदाहरण देखे जो कि किसी String से सम्बंधित Operations करने के सम्बंध में हैं। हम और भी कई प्रकार के String Operations कर सकते हैं। इसी प्रकार के Operations विभिन्न Word Processor Softwares में अपनाए जाते हैं और String को विभिन्न तरीकों से Process किया जाता है। हालांकि कुछ और भी Algorithms हैं जो String Processing के लिए काफी उपयोगी होते हैं लेकिन किसी Pattern Matching के लिए Brute Force Algorithm को काफी Use किया जाता है।

इस Algorithm की Complexity में Data की Size String व Sub String की जोड के बराबर होती है। यानी यदि किसी String में 20 Characters हों और Find किए जाने वाले Pattern में 6 Character हों, तो कुल Input Data Items की संख्‍या इन दोनों के जोड के बराबर होती है। यानी यदि String के Data Items की संख्‍या s हो व Find किए जा रहे String के Data Items की संख्‍या r हो तो कुल Input Data Items की संख्‍या निम्नानसार n होगी :

n = s + r

किसी Worst Case Complexity में इस Algorithm की Complexity C(n) = r(s – r + 1) होती है। यदि n का मान Fixed हो जैसा कि हमारे Case में s = n – r है, तो Complexity निम्नानुसार होगी-

C(n) = r( n – 2*r + 1)

C(n) का अधिकतम मान तब होता है जब r = (n+1)/4 होता है। यदि इस Equation में r का मान Place किया जाए तो Function निम्नानुसार होगा-

C(n) = (n + 1 )² / 8 = O(n²)