Class: RollingHash

Inherits:
Object
  • Object
show all
Defined in:
lib/rolling_hash.rb

Overview

Rolling hash as used in Rabin-Karp.

hasher = RollingHash.new hasher.hash(“abc”) #=> 6432038 hasher.next_hash(“d”) #=> 6498345

||

hasher.hash(“bcd”) #=> 6498345

Instance Method Summary collapse

Constructor Details

#initialize(hash = {}) ⇒ RollingHash 



17
18
19
20
21
22
23
 
# File 'lib/rolling_hash.rb', line 17

def initialize(hash = {})
  hash = { :base => 257, # prime
           :mod  => 1000000007
         }.merge!(hash)
  @base = hash[:base]
  @mod  = hash[:mod]
end

Instance Method Details

#hash(input) ⇒ Object

Given a string “abc…xyz” with length len, return the hash using @base as

“a”.ord * @base**(len - 1) + “b”.ord * @base**(len - 2) + … + “y”.ord * @base**(1) + “z”.ord * @base**0 (== “z”.ord)



38
39
40
41
42
43
44
45
46
47
48
49
50
51
 
# File 'lib/rolling_hash.rb', line 38

def hash(input)
  hash = 0
  characters = input.split("")
  input_length = characters.length
  
  characters.each_with_index do |character, index|
    hash += character.ord * modulo_exp(input_length - 1 - index) % @mod
    hash = hash % @mod
  end
  @prev_hash = hash
  @prev_input = input
  @highest_power = input_length - 1
  hash
end

#modulo_exp(power) ⇒ Object

Compute @base**power working modulo @mod



26
27
28
 
# File 'lib/rolling_hash.rb', line 26

def modulo_exp(power)
  self.class.modulo_exp(@base, power, @mod)
end

#next_hash(character) ⇒ Object

Returns the hash of (@prev_input + character) by using @prev_hash, so that the sum turns from

“a”.ord * @base**(len - 1) + “b”.ord * @base**(len - 2) + … + “y”.ord * @base**(1) + “z”.ord * @base**0 (== “z”.ord)

into

“b”.ord * @base**(len - 1) + … + “y”.ord * @base**(2) + “z”.ord * @base**1 + character.ord * @base**0



69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
 
# File 'lib/rolling_hash.rb', line 69

def next_hash(character)
  # the leading value of the computed sum
  char_to_subtract = @prev_input.chars.first
  hash = @prev_hash
  
  # subtract the leading value
  hash = hash - char_to_subtract.ord * @base**@highest_power
  
  # shift everything over to the left by 1, and add the
  # new character as the lowest value
  hash = (hash * @base) + character.ord
  hash = hash % @mod
  
  # trim off the first character
  @prev_input.slice!(0)
  @prev_input << character
  @prev_hash = hash
  
  hash
end