Content deleted Content added
m →Rabin-Karp and multiple pattern search: fixed wiki testing by previous person |
m →Use of hashing for shifting substring search: Changing hashing link (hash table) to hash function |
||
Line 5:
== Use of hashing for shifting substring search ==
Rabin-Karp algorithm takes a very different approach. Rather than pursuing more sophisticated skipping, it seeks to speed up the testing of equality of the pattern to the substrings in the text by using [[hash function|hashing]]. Hashing a string means computing a numerical value from the value of its characters using some standard hash function (a very primitive one could involve adding the [[ASCII]] values of all of its characters together). Rabin-Karp exploits the fact that if 2 strings are equal, their hash values are also equal. Note that the converse of this statement is not valid, although good hash functions seek to reduce the number of such hash collisions. Rabin-Karp computes hash value of the pattern, and then goes through the text computing hash values of all of its substrings and checking whether or not the pattern's hash is equal to the substring hash, and advancing by 1 character every time. If the two numbers are indeed discovered to be equal, then the algorithm has to verify that the two string really are equal, rather than this being a fluke of the hashing scheme. It does so using regular string comparison. It is this verification that in the worst case can drag down algorithm performance down to the level of the naive string search. This general approach is sometimes referred to as the use of a virtual hash table.
== Hash function used ==
| |||