String Matching Algorithms

Do data science also uses technique of String Matching?
  • Digital Forensics
  • Spelling Checker
  • Spam Filters
  • Intrusion Detection System
Naive String Algorithm

The Rabin-Karp Algorithm

Rabin and Karp devised a string-matching algorithm that works well in reality and generalises to other methods for similar issues like two-dimensional pattern matching. The Rabin-Karp algorithm uses Θ(m) preprocessing time, and its worst-case running time is Θ((n — m +1)m). However, it has a better average-case running time based on specific assumptions.

In the Rabin-Karp algorithm. Each character is a decimal digit, and we compute values modulo from a prime number say 13. (a) A text string. A window of length 5 is shown. The numerical value of this number is computed modulo 13, yielding the value 7. (b) (b) For each conceivable position of a length-5 window, the same text string with values computed modulo 13.
Using the pattern P = 31415, we check for windows with a modulo 13 value of 7, because 31415 = 7. (mod 13). Two such windows are found. Starting at the first text position 7 is actually the appearance of the pattern, and starting at the second text position 13 is a false match. Computing the value for a window in constant time, given the value for the previous window. The first window has value 31415. Dropping the high-order digit 3, shifting left (multiplying by 10), and then adding in the low order digit 2 gives us the new value 14152. However, because both computations are modulo 13, the value computed for the first window is 7, and the value computed for the next window is 8.

The following procedure of Rabin-Karp-Matcher works as follows:

Rabin-Karp Algorithm

Limitations of Rabin-Karp Algorithm

Spurious Hit

It is a condition when the hash value of the window of the text matches, the hash value of the pattern but the window is not the actual pattern.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
AADI JAIN

AADI JAIN

Hey, take a cup of coffee, sit back, relax and ameliorate your knowledge reading my blogs. https://linktr.ee/aadijain7