Class: MemDB::Index::SequenceMatch::SequenceIndex

Inherits:
Object
  • Object
show all
Defined in:
lib/mem_db/index/sequence_match.rb

Overview

en.wikipedia.org/wiki/Boyer-Moore_string_search_algorithm

Instance Method Summary collapse

Constructor Details

#initialize(pattern) ⇒ SequenceIndex

Returns a new instance of SequenceIndex.



27
28
29
30
31
32
33
34
 
# File 'lib/mem_db/index/sequence_match.rb', line 27

def initialize(pattern)
  @pattern = pattern
  @pattern_length = pattern.length
  @bad_char_skip = {}
  @good_suffix_skip = Array.new(@pattern_length, 0)

  init_tables
end

Instance Method Details

#index(seq) ⇒ Object 



36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
 
# File 'lib/mem_db/index/sequence_match.rb', line 36

def index(seq)
  i = @pattern_length - 1

  while i < seq.length
    j = @pattern_length - 1

    while j >= 0 && seq[i] == @pattern[j]
      i -= 1
      j -= 1
    end

    return i + 1 if j.negative?

    bad_skip = @bad_char_skip[seq[i]] || @pattern_length
    good_skip = @good_suffix_skip[j]
    i += good_skip > bad_skip ? good_skip : bad_skip
  end

  -1
end

#init_tables ⇒ Object

rubocop:disable Metrics/AbcSize



57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
 
# File 'lib/mem_db/index/sequence_match.rb', line 57

def init_tables # rubocop:disable Metrics/AbcSize
  last = @pattern_length - 1

  i = 0
  while i < last
    @bad_char_skip[@pattern[i]] = last - i
    i += 1
  end

  last_prefix = last

  i = last
  while i >= 0
    last_prefix = i + 1 if pattern_suffix?(i + 1)

    @good_suffix_skip[i] = last_prefix + last - i
    i -= 1
  end

  i = 0
  while i < last
    len_suffix = longest_pattern_suffix(i)

    if @pattern[i - len_suffix] != @pattern[last - len_suffix]
      @good_suffix_skip[last - len_suffix] = len_suffix + last - i
    end

    i += 1
  end
end

#longest_pattern_suffix(pos) ⇒ Object 



98
99
100
101
102
103
104
105
106
107
108
 
# File 'lib/mem_db/index/sequence_match.rb', line 98

def longest_pattern_suffix(pos)
  i = 0

  while i < @pattern.length && i < pos
    break if @pattern[@pattern.length - 1 - i] != @pattern[pos - i]

    i += 1
  end

  i
end

#pattern_suffix?(pos) ⇒ Boolean

Returns:

  • (Boolean) 


88
89
90
91
92
93
94
95
96
 
# File 'lib/mem_db/index/sequence_match.rb', line 88

def pattern_suffix?(pos)
  i = 0
  while i + pos < @pattern.length
    return false if @pattern[i] != @pattern[i + pos]

    i += 1
  end
  true
end