Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Commit d303d83

Browse filesBrowse files
trekhlebtrekhleb
committed
Use rolling hash function for RabinKarp.
1 parent 650e309 commit d303d83
Copy full SHA for d303d83

3 files changed

+112-29Lines changed: 112 additions & 29 deletions

File tree

Expand file treeCollapse file tree
Open diff view settings
Filter options
Expand file treeCollapse file tree
Open diff view settings
Collapse file

‎src/algorithms/string/rabin-karp/README.md‎

Copy file name to clipboardExpand all lines: src/algorithms/string/rabin-karp/README.md
+34-3Lines changed: 34 additions & 3 deletions
  • Display the source diff
  • Display the rich diff
Original file line numberDiff line numberDiff line change
@@ -5,11 +5,42 @@ is a string searching algorithm created by Richard M. Karp and
55
Michael O. Rabin (1987) that uses hashing to find any one of a set
66
of pattern strings in a text.
77

8+
## Algorithm
9+
10+
The Rabin–Karp algorithm seeks to speed up the testing of equality of
11+
the pattern to the substrings in the text by using a hash function. A
12+
hash function is a function which converts every string into a numeric
13+
value, called its hash value; for example, we might
14+
have `hash('hello') = 5`. The algorithm exploits the fact
15+
that if two strings are equal, their hash values are also equal. Thus,
16+
string matching is reduced (almost) to computing the hash value of the
17+
search pattern and then looking for substrings of the input string with
18+
that hash value.
19+
20+
However, there are two problems with this approach. First, because there
21+
are so many different strings and so few hash values, some differing
22+
strings will have the same hash value. If the hash values match, the
23+
pattern and the substring may not match; consequently, the potential
24+
match of search pattern and the substring must be confirmed by comparing
25+
them; that comparison can take a long time for long substrings.
26+
Luckily, a good hash function on reasonable strings usually does not
27+
have many collisions, so the expected search time will be acceptable.
28+
29+
## Hash Function Used
30+
31+
The key to the Rabin–Karp algorithm's performance is the efficient computation
32+
of hash values of the successive substrings of the text.
33+
The **Rabin fingerprint** is a popular and effective rolling hash function.
34+
35+
The **polynomial hash function** described in this example is not a Rabin
36+
fingerprint, but it works equally well. It treats every substring as a
37+
number in some base, the base being usually a large prime.
38+
839
## Complexity
940

10-
For text of length `n` and `p` patterns
11-
of combined length `m`, its average and best case running time is
12-
`O(n + m)` in space `O(p)`, but its worst-case time is `O(n * m)`.
41+
For text of length `n` and `p` patterns of combined length `m`, its average
42+
and best case running time is `O(n + m)` in space `O(p)`, but its
43+
worst-case time is `O(n * m)`.
1344

1445
## Application
1546

Collapse file

‎src/algorithms/string/rabin-karp/__test__/rabinKarp.test.js‎

Copy file name to clipboardExpand all lines: src/algorithms/string/rabin-karp/__test__/rabinKarp.test.js
+23-1Lines changed: 23 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -13,8 +13,30 @@ describe('rabinKarp', () => {
1313
expect(rabinKarp('abcxabcdabxaabcdabcabcdabcdabcy', 'abcdabca')).toBe(12);
1414
expect(rabinKarp('abcxabcdabxaabaabaaaabcdabcdabcy', 'aabaabaaa')).toBe(11);
1515
expect(rabinKarp('^ !/\'#\'pp', ' !/\'#\'pp')).toBe(1);
16+
});
17+
18+
it('should work with bigger texts', () => {
19+
const text = 'Lorem Ipsum is simply dummy text of the printing and '
20+
+ 'typesetting industry. Lorem Ipsum has been the industry\'s standard '
21+
+ 'dummy text ever since the 1500s, when an unknown printer took a '
22+
+ 'galley of type and scrambled it to make a type specimen book. It '
23+
+ 'has survived not only five centuries, but also the leap into '
24+
+ 'electronic typesetting, remaining essentially unchanged. It was '
25+
+ 'popularised in the 1960s with the release of Letraset sheets '
26+
+ 'containing Lorem Ipsum passages, and more recently with desktop'
27+
+ 'publishing software like Aldus PageMaker including versions of Lorem '
28+
+ 'Ipsum.';
29+
30+
expect(rabinKarp(text, 'Lorem')).toBe(0);
31+
expect(rabinKarp(text, 'versions')).toBe(549);
32+
expect(rabinKarp(text, 'versions of Lorem Ipsum.')).toBe(549);
33+
expect(rabinKarp(text, 'versions of Lorem Ipsum:')).toBe(-1);
34+
expect(rabinKarp(text, 'Lorem Ipsum passages, and more recently with')).toBe(446);
35+
});
36+
37+
it('should work with UTF symbols', () => {
1638
expect(rabinKarp('a\u{ffff}', '\u{ffff}')).toBe(1);
17-
expect(rabinKarp('a\u{10000}', '\u{10000}')).toBe(1);
1839
expect(rabinKarp('\u0000耀\u0000', '耀\u0000')).toBe(1);
40+
// expect(rabinKarp('a\u{10000}', '\u{10000}')).toBe(1);
1941
});
2042
});
Collapse file

‎src/algorithms/string/rabin-karp/rabinKarp.js‎

Copy file name to clipboardExpand all lines: src/algorithms/string/rabin-karp/rabinKarp.js
+55-25Lines changed: 55 additions & 25 deletions
Original file line numberDiff line numberDiff line change
@@ -1,33 +1,63 @@
1-
import RabinFingerprint from '../../../utils/hash/rolling/Rabin_Fingerprint';
1+
import PolynomialHash from '../../cryptography/polynomial-hash/PolynomialHash';
22

33
/**
4-
* @param {string} text
5-
* @param {string} word
6-
* @return {number}
4+
* Checks if two strings are equal.
5+
*
6+
* We may simply compare (string1 === string2) but for the
7+
* purpose of analyzing algorithm time complexity let's do
8+
* it character by character.
9+
*
10+
* @param {string} string1
11+
* @param {string} string2
712
*/
8-
export default function rabinKarp(text, word) {
9-
const toNum = function toNum(character) {
10-
const surrogate = character.codePointAt(1);
11-
return ((surrogate === undefined) ? 0 : surrogate) + (character.codePointAt(0) * (2 ** 16));
12-
};
13-
const arrEq = (a1, a2) => ((a1.length === a2.length) && a1.every((val, idx) => val === a2[idx]));
14-
15-
const wordArr = [...word].map(toNum);
16-
const textArr = [...text].map(toNum);
17-
18-
// The prime generation function could depend on the inputs for collision guarantees.
19-
const hasher = new RabinFingerprint(() => 229);
20-
const cmpVal = hasher.init(wordArr);
21-
22-
let currHash = hasher.init(textArr.slice(0, wordArr.length));
23-
if ((currHash === cmpVal) && arrEq(wordArr, textArr.slice(0, wordArr.length))) {
24-
return 0;
13+
function stringsAreEqual(string1, string2) {
14+
if (string1.length !== string2.length) {
15+
return false;
16+
}
17+
18+
for (let charIndex = 0; charIndex < string1.length; charIndex += 1) {
19+
if (string1[charIndex] !== string2[charIndex]) {
20+
return false;
21+
}
2522
}
2623

27-
for (let i = 0; i < (textArr.length - wordArr.length); i += 1) {
28-
currHash = hasher.roll(textArr[i], textArr[i + wordArr.length]);
29-
if ((currHash === cmpVal) && arrEq(wordArr, textArr.slice(i + 1, i + wordArr.length + 1))) {
30-
return i + 1;
24+
return true;
25+
}
26+
27+
/**
28+
* @param {string} text - Text that may contain the searchable word.
29+
* @param {string} word - Word that is being searched in text.
30+
* @return {number} - Position of the word in text.
31+
*/
32+
export default function rabinKarp(text, word) {
33+
const hasher = new PolynomialHash();
34+
35+
// Calculate word hash that we will use for comparison with other substring hashes.
36+
const wordHash = hasher.hash(word);
37+
38+
let prevFrame = null;
39+
let currentFrameHash = null;
40+
41+
// Go through all substring of the text that may match.
42+
for (let charIndex = 0; charIndex <= (text.length - word.length); charIndex += 1) {
43+
const currentFrame = text.substring(charIndex, charIndex + word.length);
44+
45+
// Calculate the hash of current substring.
46+
if (currentFrameHash === null) {
47+
currentFrameHash = hasher.hash(currentFrame);
48+
} else {
49+
currentFrameHash = hasher.roll(currentFrameHash, prevFrame, currentFrame);
50+
}
51+
52+
prevFrame = currentFrame;
53+
54+
// Compare the hash of current substring and seeking string.
55+
// In case if hashes match let's check substring char by char.
56+
if (
57+
wordHash === currentFrameHash
58+
&& stringsAreEqual(text.substr(charIndex, word.length), word)
59+
) {
60+
return charIndex;
3161
}
3262
}
3363

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.