राबिन-कार्प एलगोरिदम

इस ट्यूटोरियल में, आप सीखेंगे कि रबिन-कार्प एल्गोरोथम क्या है। इसके अलावा, आप C, C ++, जावा और पायथन में रबिन-कार्प एल्गोरिदम के काम करने के उदाहरण पाएंगे।

राबिन-कार्प एल्गोरिथ्म एक एल्गोरिथ्म है जिसका उपयोग टेक्स्ट में हैश फ़ंक्शन का उपयोग करके खोज / मिलान करने के लिए किया जाता है। नाइव स्ट्रिंग मिलान एल्गोरिदम के विपरीत, यह प्रारंभिक चरण में प्रत्येक चरित्र के माध्यम से यात्रा नहीं करता है, बल्कि यह उन पात्रों को फ़िल्टर करता है जो मेल नहीं खाते हैं और फिर तुलना करते हैं।

एक हैश फ़ंक्शन एक बड़े इनपुट मान को छोटे आउटपुट मान पर मैप करने के लिए एक उपकरण है। इस आउटपुट वैल्यू को हैश वैल्यू कहा जाता है।

रबिन-कार्प एल्गोरिदम कैसे काम करता है?

आवश्यक स्ट्रिंग की उपस्थिति की संभावना के लिए पात्रों का एक क्रम लिया जाता है और जाँच की जाती है। यदि संभावना मिलती है, तो चरित्र मिलान किया जाता है।

आइए हम निम्नलिखित चरणों के साथ एल्गोरिथ्म को समझते हैं:

  1. पाठ होने दें: पाठ
    और उपरोक्त पाठ में खोजा जाने वाला स्ट्रिंग: पैटर्न
  2. आइए हम numerical value(v)/weightउन पात्रों के लिए असाइन करें जिन्हें हम समस्या में उपयोग कर रहे हैं। यहाँ, हमने पहले दस अक्षर केवल (यानी A से J) लिए हैं। पाठ वजन
  3. मी पैटर्न की लंबाई हो और n पाठ की लंबाई हो। यहां, m = 10 and n = 3.
    इनपुट सेट में वर्णों की संख्या d होने दें। यहाँ, हमने इनपुट सेट (A, B, C,…, J) लिया है। तो, d = 10। आप d के लिए कोई भी उपयुक्त मूल्य मान सकते हैं।
  4. आइए हम पैटर्न के हैश मान की गणना करते हैं। पाठ का मूल्य मान
पैटर्न के लिए हैश मान (p) = Σ (v * dm-1) mod 13 = ((3 * 10 2 ) + (4 * 10 1 ) + (4 * 10 0 )) mod 13 = 344 mod 13 = 6

ऊपर की गणना में, एक प्राइम संख्या (यहां, 13) इस तरह से चुनें कि हम एकल-सटीक अंकगणित के साथ सभी गणना कर सकें।

मापांक की गणना करने का कारण नीचे दिया गया है।

  1. आकार m की पाठ-विंडो के लिए हैश मान की गणना करें।
पहली विंडो एबीसी के लिए, हैश वैल्यू फॉर टेक्स्ट (t) = v (v * dn-1) mod 13 = ((1 * 10 2 ) + (2 * 10 1 ) + (3 * 10 0 )) mod 13 = 123 मॉड 13 = 6
  1. पाठ के हैश मान के साथ पैटर्न के हैश मान की तुलना करें। यदि वे मेल खाते हैं, तो चरित्र-मिलान किया जाता है।
    उपरोक्त उदाहरणों में, पहली विंडो का हैश मान p (यानी t) के साथ मेल खाता है, इसलिए ABC और CDD के बीच मिलान वाले वर्ण के लिए जाएं। चूंकि वे ऐसा मेल नहीं खाते हैं, अगली विंडो के लिए जाएं।
  2. हम पहले पद को घटाकर और नीचे दिखाए गए अनुसार अगले पद को जोड़कर अगली विंडो के हैश मान की गणना करते हैं।
t = ((1 * 10 2 ) + ((2 * 10 1 ) + (3 * 10 0 )) * 10 + (3 * 10 0 )) mod 13 = 233 mod 13 = 12

इस प्रक्रिया को अनुकूलित करने के लिए, हम निम्न तरीके से पिछले हैश मान का उपयोग करते हैं।

t = ((* * (t - v (हटाया जाने वाला वर्ण) * h) + v (वर्ण जोड़ा जाना है)) mod 13 = ((10 * (6 - 1 * 9) + 3) mod 13 = 12 कहाँ , h = d m-1 = 10 3-1 = 100।
  1. बीसीसी के लिए, टी = 12 ( ≠ 6)। इसलिए, अगली विंडो के लिए जाएं।
    कुछ खोजों के बाद, हमें पाठ में विंडो सीडीए के लिए मैच मिलेगा। अलग-अलग विंडो का हैश वैल्यू

कलन विधि

 n = t.length m = p.length h = dm-1 mod qp = 0 t0 = 0 के लिए i = 1 से लेकर mp = (dp + p (i)) mod q t0 = (dt0 + t (i) mod) q के लिए s = 0 से n - m यदि p = ts यदि p (1 … m) = t (s + 1 … s + m) प्रिंट "पैटर्न" पोजीशन पर पाया जाता है "s s <nm ts + 1 = (d (#) ts - t (s + 1) h) + t (s + m + 1)) mod q

पायथन, जावा और सी / सी ++ उदाहरण

पायथन जावा सी सी ++ 
 # Rabin-Karp algorithm in python d = 10 def search(pattern, text, q): m = len(pattern) n = len(text) p = 0 t = 0 h = 1 i = 0 j = 0 for i in range(m-1): h = (h*d) % q # Calculate hash value for pattern and text for i in range(m): p = (d*p + ord(pattern(i))) % q t = (d*t + ord(text(i))) % q # Find the match for i in range(n-m+1): if p == t: for j in range(m): if text(i+j) != pattern(j): break j += 1 if j == m: print("Pattern is found at position: " + str(i+1)) if i < n-m: t = (d*(t-ord(text(i))*h) + ord(text(i+m))) % q if t < 0: t = t+q text = "ABCCDDAEFG" pattern = "CDD" q = 13 search(pattern, text, q)
 // Rabin-Karp algorithm in Java public class RabinKarp ( public final static int d = 10; static void search(String pattern, String txt, int q) ( int m = pattern.length(); int n = txt.length(); int i, j; int p = 0; int t = 0; int h = 1; for (i = 0; i < m - 1; i++) h = (h * d) % q; // Calculate hash value for pattern and text for (i = 0; i < m; i++) ( p = (d * p + pattern.charAt(i)) % q; t = (d * t + txt.charAt(i)) % q; ) // Find the match for (i = 0; i <= n - m; i++) ( if (p == t) ( for (j = 0; j < m; j++) ( if (txt.charAt(i + j) != pattern.charAt(j)) break; ) if (j == m) System.out.println("Pattern is found at position: " + (i + 1)); ) if (i < n - m) ( t = (d * (t - txt.charAt(i) * h) + txt.charAt(i + m)) % q; if (t < 0) t = (t + q); ) ) ) public static void main(String() args) ( String txt = "ABCCDDAEFG"; String pattern = "CDD"; int q = 13; search(pattern, txt, q); ) )
 // Rabin-Karp algorithm in C #include #include #define d 10 void rabinKarp(char pattern(), char text(), int q) ( int m = strlen(pattern); int n = strlen(text); int i, j; int p = 0; int t = 0; int h = 1; for (i = 0; i < m - 1; i++) h = (h * d) % q; // Calculate hash value for pattern and text for (i = 0; i < m; i++) ( p = (d * p + pattern(i)) % q; t = (d * t + text(i)) % q; ) // Find the match for (i = 0; i <= n - m; i++) ( if (p == t) ( for (j = 0; j < m; j++) ( if (text(i + j) != pattern(j)) break; ) if (j == m) printf("Pattern is found at position: %d ", i + 1); ) if (i < n - m) ( t = (d * (t - text(i) * h) + text(i + m)) % q; if (t < 0) t = (t + q); ) ) ) int main() ( char text() = "ABCCDDAEFG"; char pattern() = "CDD"; int q = 13; rabinKarp(pattern, text, q); )
 // Rabin-Karp algorithm in C++ #include #include using namespace std; #define d 10 void rabinKarp(char pattern(), char text(), int q) ( int m = strlen(pattern); int n = strlen(text); int i, j; int p = 0; int t = 0; int h = 1; for (i = 0; i < m - 1; i++) h = (h * d) % q; // Calculate hash value for pattern and text for (i = 0; i < m; i++) ( p = (d * p + pattern(i)) % q; t = (d * t + text(i)) % q; ) // Find the match for (i = 0; i <= n - m; i++) ( if (p == t) ( for (j = 0; j < m; j++) ( if (text(i + j) != pattern(j)) break; ) if (j == m) cout << "Pattern is found at position: " << i + 1 << endl; ) if (i < n - m) ( t = (d * (t - text(i) * h) + text(i + m)) % q; if (t < 0) t = (t + q); ) ) ) int main() ( char text() = "ABCCDDAEFG"; char pattern() = "CDD"; int q = 13; rabinKarp(pattern, text, q); )

राबिन-कार्प एल्गोरिथ्म की सीमाएं

स्प्रिचुअल हिट

जब पैटर्न का हैश मान पाठ की विंडो के हैश मान के साथ मेल खाता है लेकिन विंडो वास्तविक पैटर्न नहीं है तो इसे एक स्थानिक हिट कहा जाता है।

स्प्रिचुअल हिट एल्गोरिथ्म के समय की जटिलता को बढ़ाता है। स्थानिक हिट को कम करने के लिए, हम मापांक का उपयोग करते हैं। यह स्पुरियस हिट को बहुत कम करता है।

राबिन-कार्प एल्गोरिथम जटिलता

राबिन-कार्प एल्गोरिथ्म का औसत मामला और सबसे अच्छा मामला जटिलता है O(m + n)और सबसे खराब स्थिति जटिलता ओ (एमएन) है।

सबसे खराब स्थिति तब होती है जब सभी खिड़कियों के लिए एक हिट हिट संख्या होती है।

राबिन-कार्प एलगोरिदम एप्लीकेशन

  • पैटर्न मिलान के लिए
  • एक बड़े पाठ में स्ट्रिंग खोजने के लिए

दिलचस्प लेख...