Boyer-Moore

Alex_Boyer-Moore

# big text for timed tests
big_text = "The RSVP Hello message exchange was introduced in [RFC3209].  The
   usage of RSVP Hello has been extended in [RFC3473] to support RSVP
   Graceful Restart (GR) procedures.
   More specifically, [RFC3473] specifies the use of the RSVP Hello
   messages for GR procedures for Generalized MPLS (GMPLS).  GMPLS
   introduces the notion of control plane and data plane separation.  In
   other words, in GMPLS networks, the control plane information is
   carried over a control network whose end-points are IP capable and
   that may be physically or logically disjoint from the data bearer
   links it controls.  One of the consequences of separation of data
   bearer links from control channels is that RSVP Hello messages are
   not terminated on data bearer links' interfaces even if (some of)
   those are numbered.  Instead, RSVP Hello messages are terminated at
   the control channel (IP-capable) end-points.  The latter MAY be
   identified by the value assigned to the node hosting these control
   channels, i.e., Node-ID.  Consequently, the use of RSVP Hello
   messages for GR applications introduces a need for clarifying the
   behavior and usage of Node-ID based Hello sessions.
   Even in the case of packet switching capable interfaces, when link
   failure detection is performed by some means other than RSVP Hello
   messages (e.g., [BFD]), the use of Node-ID based Hello sessions is
   also optimal for detection of signaling adjacency failures for
   GMPLS-RSVP-TE and RSVP-TE when there is more than one link between a
   pair of nodes.  Similarly, when all TE links between neighbor nodes
   are unnumbered, it is implied that the nodes will exchange Node-ID
   based Hello messages for detection of signaling adjacency failures.
   This document also clarifies the use of Node-ID based Hello message
   exchanges when all or a sub-set of TE links are unnumbered.
2.  Terminology
   Node-ID: TE Router ID as advertised in the Router Address TLV for
   OSPF [OSPF-TE] and Traffic Engineering Router ID TLV for ISIS
   [ISIS-TE].  For IPv6, the Node-ID refers to the Router_IPv6_Address
   for OSPFv3 [OSPFv3-TE] and the IPv6 TE Router_ID for IS-IS
   [IS-ISv6-TE].
   Node-ID based Hello Session: A Hello session in which local and
   remote Node-IDs are used in the source and destination fields of the
   Hello packet, respectively.
   Interface bounded Hello Session: A Hello session in which local and
   remote addresses of the interface in question are used in the source
   and destination fields of the Hello packet, respectively.
Ali, et al.                 Standards Track                     [Page 2]

RFC 4558                Node-ID Based RSVP Hello               June 2006
2.1.  Conventions Used in This Document
3.  Node-ID Based RSVP Hello Messages
   A Node-ID based Hello session is established through the exchange of
   RSVP Hello messages such that local and remote Node-IDs are
   respectively used in the source and destination fields of Hello
   packets.  Here, for IPv4, Node-ID refers to the TE router-id as
   defined in the Router Address TLV for OSPF [OSPF-TE] and the Traffic
   Engineering router ID TLV for ISIS [ISIS-TE].  For IPv6, the Node-ID
   refers to the Router_IPv6_Address for OSPFv3 [OSPFv3-TE] and the IPv6
   TE Router_ID for IS-IS [IS-ISv6-TE].  This section formalizes a
   procedure for establishing Node-ID based Hello sessions.
   If a node wishes to establish a Node-ID based RSVP Hello session with
   its neighbor, it sends a Hello message with its Node-ID in the source
   IP address field of the Hello packet.  Furthermore, the node also
   puts the neighbor's Node-ID in the destination address field of the
   IP packet.
   When a node receives a Hello packet where the destination IP address
   is its local Node-ID as advertised in the IGP-TE topology, the node
   MUST use its Node-ID in replying to the Hello message.  In other
   words, nodes MUST ensure that the Node-IDs used in RSVP Hello
   messages are those derived/contained in the IGP-TE topology.
   Furthermore, a node can only run one Node-ID based RSVP Hello session
   per IGP instance (i.e., per Node-ID pair) with its neighbor.
   Even in the case of packet switching capable interfaces, when link
   failure detection is performed by some means other than exchanging
   RSVP Hello messages, use of Node-ID based Hello sessions is also
   optimal in detecting signaling adjacency failures for GMPLS-RSVP-TE
   and RSVP-TE when there is more than one link between a pair of nodes.
   Similarly, if all interfaces between a pair of nodes are unnumbered,
   the optimal way to use RSVP to detect signaling adjacency failure is
   to run Node-ID based Hello sessions.  Furthermore, in the case of an
   optical network with single or multiple numbered or unnumbered
   control channels, use of Node-ID based Hello messages for detecting
   signaling adjacency failure is also optimal.  Therefore, when link
   failure detection is performed by some means other than exchanging
   RSVP Hello messages, or if all interfaces between a pair of nodes are
   unnumbered, or in a GMPLS network with data and control plane
   separation, a node MUST run Node-ID based Hello sessions for
   detection of signaling adjacency failure for RSVP-TE.  Nonetheless,"




# First iteration Boyer-Moore, with no "bad character/good suffix rule".

def boyer_moore_search str, sub

  str_length = str.length
  sub_length = sub.length

  for i in (sub_length - 1 ... str_length)
    # if str at index i matches the last element in sub
    if str[i] == sub[-1]
      # set j, our sub indexer to 0
      j = 0
      # set count, our match counter to 1
      count = 1
      until j == sub_length
        count += 1 if str[i - j] == sub[(sub_length - 1) - j]
        return i - (sub_length - 1) if count == sub_length
        j += 1
      end
    end
  end
  return "not found"
end

# tests
puts " "
puts "Boyer Moore No Bad Character Test:"
puts " "

# match
test_str     = "Hello how do you do? Good? OK great."
test_pattern = "great"
should_be    = 30
result       = boyer_moore_search test_str, test_pattern

puts "Pattern at index #{result} "
raise "This is wrong" unless result == should_be

# no match
test_str2     = "Hello how do you do? Good? OK great."
test_pattern2 = "potato"
should_be2    = "not found"
result2       = boyer_moore_search test_str2, test_pattern2

puts "Pattern at index #{result2} "

raise "This is wrong" unless result == should_be


#Second iteration with Bad Match Table.

class BM_Search

  def initialize str, pattern
    @str = str
    @pattern = pattern
    @pattern_length = pattern.length
    @str_length = str.length
    @distances = Hash.new
    @index = 0

    bad_match_table
  end

  def bad_match_table
    for i in (0...@pattern_length - 1)
      @distances[@pattern[i]] = @pattern_length - i - 1
    end
    @distances
  end

  def boyer_moore_search

    until @index >= @str_length
      # if @str at index i matches the last element in pattern
      if @str[@index] == @pattern[-1]
        # set j, our pattern indexer to 0
        j = 0
        # set count, our match counter to 1
        count = 1
        until j == @pattern_length
          count += 1 if @str[@index - j] == @pattern[(@pattern_length - 1) - j]
          return @index - (@pattern_length - 1) if count == @pattern_length
          j += 1
        end
      # if the char of the string we are looking at in not a match but IS in the pattern,
      # find the value in @distances with the key of that char and add it to @index
      elsif @distances[@str[@index]] != nil
        @index += @distances[@str[@index]]
      # if the char of the string we are looking at is not a match AND is NOT in the pattern
      # add the pattern length to the index
      else
        @index += @pattern_length
      end
    end
    return "not found"
  end

end

# tests
puts " "
puts '*' * 40
puts "Boyer Moore With Bad Character Test:"
puts " "
# match

test_str     = "Hello how do you do? Good? OK great."
test_pattern = "great"
should_be    = 30
test         = BM_Search.new test_str, test_pattern
result3      = test.boyer_moore_search

puts "Pattern at index #{result3} "
raise "This is wrong" unless result3 == should_be

# no match

test_str2     = "let them eat cake"
test_pattern2 = "potato"
should_be2    = "not found"
test2         = BM_Search.new test_str2, test_pattern2
result4       = test2.boyer_moore_search

puts "Pattern at index #{result4} "

raise "This is wrong" unless result4 == should_be2



# Timed Tests

# No Table
puts " "
puts "*" * 40
puts "Timed tests:"
puts " "
puts "With no table:"
time_test_pattern = "RSVP-TE"

beginning_time = Time.now
boyer_moore_search big_text, time_test_pattern
end_time       = Time.now
puts "Pattern at index #{boyer_moore_search big_text, time_test_pattern} "
puts "Time elapsed #{(end_time - beginning_time)*1000} milliseconds"

# With Table

puts " "
puts "With Table"
beginning_time2  = Time.now

time_test        =  BM_Search.new big_text, time_test_pattern
time_test_result = time_test.boyer_moore_search

end_time2        = Time.now
puts "Pattern at index #{time_test_result} "

puts "Time elapsed #{(end_time2 - beginning_time2)*1000} milliseconds"
puts " "