Boyer-Moore string search

Boyer-Moore string search is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Task

This algorithm is designed for pattern searching on certain types of devices which are backtracking-unfriendly such as Tape drives and Hard disks.

Its works by first caching a segment of data from storage and match it against the pattern from the highest position backward to the lowest, if the matching fails, cache next segment of data, and move the start point forward to skip the portion of data which will definitely fail to match, until we successfully match the pattern or the pointer exceeds the data length.

Follow this link for more information about this algorithm.

To properly test this algorithm, it would be good to search for a string which contains repeated subsequences, such as alfalfa and the text being searched should not only include a match but that match should be preceded by words which partially match, such as behalf.

Emacs Lisp

<lang lisp>

Compile the pattern to a right most position map

(defun bm_compile_pattern (pattern)

 (let* ((R 256) (patLen (length pattern)) (rightMap (make-vector R -1)))
   (let ((j -1))
     (while (progn (setq j (1+ j)) (< j patLen))

(aset rightMap (elt pattern j) j) ) )

   rightMap
   )
 )

(print (bm_compile_pattern "abcdb"))

(defun bm_substring_search (pattern text)

 "Boyer-Moore string search"
 (let ((startPos 0)

(skip 0) (result nil) (rightMap nil) (result nil))

   (setq rightMap (bm_compile_pattern pattern))

   ;; Continue this loop when no result and not exceed the text length
   (while (and (not result) (<= (+ startPos skip (length pattern)) (length text)))
     (setq startPos (+ startPos skip))

     (let ((idx (length pattern)) (skip1 nil))

(while (and (not skip1) (>= (setq idx (1- idx)) 0))  ;; skip when the character at position idx is different (when (/= (elt pattern idx) (elt text (+ startPos idx)))  ;; looking up the right most position in pattern (let ((right (aref rightMap (elt text (+ startPos idx))))) (if (>= right 0) (progn (setq skip1 (- idx right)) (when (<= skip1 0) (setq skip1 1))) (progn (setq skip1 (1+ idx))) ) ) ) ) (if (or (not skip1) (<= skip1 0)) (progn (setq result startPos)) (progn (setq skip skip1)) ) )

     )
   result
   )
 )

</lang>

Python

Slightly modified from en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string-search_algorithm#Python_implementation. <lang python>""" This version uses ASCII for case-sensitive matching. For Unicode you may want to match in UTF-8 bytes instead of creating a 0x10FFFF-sized table. """

from typing import List

ALPHABET_SIZE = 256

def alphabet_index(c: str) -> int:

   """Return the index of the given ASCII character. """
   val = ord(c)
   assert 0 <= val < ALPHABET_SIZE
   return val

def match_length(S: str, idx1: int, idx2: int) -> int:

   """Return the length of the match of the substrings of S beginning at idx1 and idx2."""
   if idx1 == idx2:
       return len(S) - idx1
   match_count = 0
   while idx1 < len(S) and idx2 < len(S) and S[idx1] == S[idx2]:
       match_count += 1
       idx1 += 1
       idx2 += 1
   return match_count

def fundamental_preprocess(S: str) -> List[int]:

   """Return Z, the Fundamental Preprocessing of S.

   Z[i] is the length of the substring beginning at i which is also a prefix of S.
   This pre-processing is done in O(n) time, where n is the length of S.
   """
   if len(S) == 0:  # Handles case of empty string
       return []
   if len(S) == 1:  # Handles case of single-character string
       return [1]
   z = [0 for x in S]
   z[0] = len(S)
   z[1] = match_length(S, 0, 1)
   for i in range(2, 1 + z[1]):  # Optimization from exercise 1-5
       z[i] = z[1] - i + 1
   # Defines lower and upper limits of z-box
   l = 0
   r = 0
   for i in range(2 + z[1], len(S)):
       if i <= r:  # i falls within existing z-box
           k = i - l
           b = z[k]
           a = r - i + 1
           if b < a:  # b ends within existing z-box
               z[i] = b
           else:  # b ends at or after the end of the z-box, we need to do an explicit match to the right of the z-box
               z[i] = a + match_length(S, a, r + 1)
               l = i
               r = i + z[i] - 1
       else:  # i does not reside within existing z-box
           z[i] = match_length(S, 0, i)
           if z[i] > 0:
               l = i
               r = i + z[i] - 1
   return z

def bad_character_table(S: str) -> List[List[int]]:

   """
   Generates R for S, which is an array indexed by the position of some character c in the
   ASCII table. At that index in R is an array of length |S|+1, specifying for each
   index i in S (plus the index after S) the next location of character c encountered when
   traversing S from right to left starting at i. This is used for a constant-time lookup
   for the bad character rule in the Boyer-Moore string search algorithm, although it has
   a much larger size than non-constant-time solutions.
   """
   if len(S) == 0:
       return [[] for a in range(ALPHABET_SIZE)]
   R = [[-1] for a in range(ALPHABET_SIZE)]
   alpha = [-1 for a in range(ALPHABET_SIZE)]
   for i, c in enumerate(S):
       alpha[alphabet_index(c)] = i
       for j, a in enumerate(alpha):
           R[j].append(a)
   return R

def good_suffix_table(S: str) -> List[int]:

   """
   Generates L for S, an array used in the implementation of the strong good suffix rule.
   L[i] = k, the largest position in S such that S[i:] (the suffix of S starting at i) matches
   a suffix of S[:k] (a substring in S ending at k). Used in Boyer-Moore, L gives an amount to
   shift P relative to T such that no instances of P in T are skipped and a suffix of P[:L[i]]
   matches the substring of T matched by a suffix of P in the previous match attempt.
   Specifically, if the mismatch took place at position i-1 in P, the shift magnitude is given
   by the equation len(P) - L[i]. In the case that L[i] = -1, the full shift table is used.
   Since only proper suffixes matter, L[0] = -1.
   """
   L = [-1 for c in S]
   N = fundamental_preprocess(S[::-1])  # S[::-1] reverses S
   N.reverse()
   for j in range(0, len(S) - 1):
       i = len(S) - N[j]
       if i != len(S):
           L[i] = j
   return L

def full_shift_table(S: str) -> List[int]:

   """
   Generates F for S, an array used in a special case of the good suffix rule in the Boyer-Moore
   string search algorithm. F[i] is the length of the longest suffix of S[i:] that is also a
   prefix of S. In the cases it is used, the shift magnitude of the pattern P relative to the
   text T is len(P) - F[i] for a mismatch occurring at i-1.
   """
   F = [0 for c in S]
   Z = fundamental_preprocess(S)
   longest = 0
   for i, zv in enumerate(reversed(Z)):
       longest = max(zv, longest) if zv == i + 1 else longest
       F[-i - 1] = longest
   return F

def string_search(P, T) -> List[int]:

   """
   Implementation of the Boyer-Moore string search algorithm. This finds all occurrences of P
   in T, and incorporates numerous ways of pre-processing the pattern to determine the optimal
   amount to shift the string and skip comparisons. In practice it runs in O(m) (and even
   sublinear) time, where m is the length of T. This implementation performs a case-sensitive
   search on ASCII characters. P must be ASCII as well.
   """
   if len(P) == 0 or len(T) == 0 or len(T) < len(P):
       return []

   matches = []

   # Preprocessing
   R = bad_character_table(P)
   L = good_suffix_table(P)
   F = full_shift_table(P)

   k = len(P) - 1      # Represents alignment of end of P relative to T
   previous_k = -1     # Represents alignment in previous phase (Galil's rule)
   while k < len(T):
       i = len(P) - 1  # Character to compare in P
       h = k           # Character to compare in T
       while i >= 0 and h > previous_k and P[i] == T[h]:  # Matches starting from end of P
           i -= 1
           h -= 1
       if i == -1 or h == previous_k:  # Match has been found (Galil's rule)
           matches.append(k - len(P) + 1)
           k += len(P) - F[1] if len(P) > 1 else 1
       else:  # No match, shift by max of bad character and good suffix rules
           char_shift = i - R[alphabet_index(T[h])][i]
           if i + 1 == len(P):  # Mismatch happened on first attempt
               suffix_shift = 1
           elif L[i + 1] == -1:  # Matched suffix does not appear anywhere in P
               suffix_shift = len(P) - F[i + 1]
           else:               # Matched suffix appears in P
               suffix_shift = len(P) - 1 - L[i + 1]
           shift = max(char_shift, suffix_shift)
           previous_k = k if shift >= i + 1 else previous_k  # Galil's rule
           k += shift
   return matches

TEXT1 = 'InhisbookseriesTheArtofComputerProgrammingpublishedbyAddisonWesleyDKnuthusesanimaginarycomputertheMIXanditsassociatedmachinecodeandassemblylanguagestoillustratetheconceptsandalgorithmsastheyarepresented' TEXT2 = "Nearby farms grew a half acre of alfalfa on the dairy's behalf, with bales of all that alfalfa exchanged for milk." PAT1, PAT2, PAT3 = 'put', 'and', 'alfalfa'

print("Found", PAT1, "at:", string_search(PAT1, TEXT1)) print("Found", PAT2, "at:", string_search(PAT2, TEXT1)) print("Found", PAT3, "at:", string_search(PAT3, TEXT2))

</lang>

Output:

Found put at: [26, 90]
Found and at: [101, 128, 171]
Found alfalfa at: [33, 87]

Wren

I've worked here from the Java code in the Wikipedia article though, as this version only finds the index of the first occurrence of the substring, I've added a routine to find all non-overlapping occurrences by repeatedly calling the BoyerMoore.indexOf method. Indices are zero-based.

The same examples have been used as in the Python entry above. <lang ecmascript>class BoyerMoore {

   /**
    * Returns the index within this string of the first occurrence of the
    * specified substring. If it is not a substring, return -1.
    *
    * There is no Galil because it only generates one match.
    *
    * @param haystack The string to be scanned
    * @param needle The target string to search
    * @return The start index of the substring
    */
   static indexOf(haystack, needle) {
       haystack = haystack.bytes.toList
       needle = needle.bytes.toList
       var nc = needle.count
       if (nc == 0) return 0
       var charTable = makeCharTable_(needle)
       var offsetTable = makeOffsetTable_(needle)
       var i = nc - 1
       while (i < haystack.count) {
           var j = nc - 1
           while (needle[j] == haystack[i]) {
               if (j == 0) return i
               i = i - 1
               j = j - 1
           }
           i = i + offsetTable[nc - 1 - j].max(charTable[haystack[i]])
       }
       return -1
   }

   /**
    * Makes the jump table based on the mismatched character information.
    */
   static makeCharTable_(needle) {
       var ALPHABET_SIZE = 256 // use bytes rather than codepoints
       var nc = needle.count
       var table = List.filled(ALPHABET_SIZE, nc)
       for (i in 0...nc) table[needle[i]] = nc - 1 - i
       return table
   }

   /**
    * Makes the jump table based on the scan offset which mismatch occurs.
    * (bad character rule).
    */
   static makeOffsetTable_(needle) {
       var nc = needle.count
       var table = List.filled(nc, 0)
       var lastPrefixPosition = nc
       for (i in nc...0) {
           if (isPrefix_(needle, i)) lastPrefixPosition = i
           table[nc-1] = lastPrefixPosition - i - nc
       }
       for (i in 0...nc-1) {
           var slen = suffixLength_(needle, i)
           table[slen] = nc - 1 - i + slen
       }
       return table
   }

   /**
    * Is needle[p..-1] a prefix of needle?
    */
   static isPrefix_(needle, p) {
       var i = p
       var j = 0
       var nc = needle.count
       while (i < nc) {
           if (needle[i] != needle[j]) return false
           i = i + 1
           j = j + 1
       }
       return true
   }

   /**
    * Returns the maximum length of the substring ends at p and is a suffix.
    * (good suffix rule)
    */
  static suffixLength_(needle, p) {
       var len = 0
       var nc = needle.count
       var i = p
       var j = nc - 1
       while (i >= 0 && needle[i] == needle[j]) {
           len = len + 1
           i = i - 1
           j = j - 1
       }
       return len
   }

}

/*

* Uses the BoyerMoore class to find the indices of ALL non-overlapping matches of the specified substring
* and return a list of them. Returns an empty list if it not a substring.
*/

var indicesOf = Fn.new { |haystack, needle|

   var indices = []
   var hc = haystack.bytes.count
   var bc = needle.bytes.count
   var start = 0
   while (true) {
       var haystack2 = haystack[start..-1]
       var index = BoyerMoore.indexOf(haystack2, needle)
       if (index == -1) return indices
       indices.add(start + index)
       start = start + index + bc
       if (start >= hc) return indices
   }

}

var text1 = "InhisbookseriesTheArtofComputerProgrammingpublishedbyAddisonWesleyDKnuthusesanimaginarycomputertheMIXanditsassociatedmachinecodeandassemblylanguagestoillustratetheconceptsandalgorithmsastheyarepresented" var text2 = "Nearby farms grew a half acre of alfalfa on the dairy's behalf, with bales of all that alfalfa exchanged for milk." var pat1 = "put" var pat2 = "and" var pat3 = "alfalfa" System.print("text1 = %(text1)") System.print("text2 = %(text2)") System.print() System.print("Found '%(pat1)' in 'text1' at indices %(indicesOf.call(text1, pat1))") System.print("Found '%(pat2)' in 'text1' at indices %(indicesOf.call(text1, pat2))") System.print("Found '%(pat3)' in 'text2' at indices %(indicesOf.call(text2, pat3))")</lang>

Output:

text1 = InhisbookseriesTheArtofComputerProgrammingpublishedbyAddisonWesleyDKnuthusesanimaginarycomputertheMIXanditsassociatedmachinecodeandassemblylanguagestoillustratetheconceptsandalgorithmsastheyarepresented
text2 = Nearby farms grew a half acre of alfalfa on the dairy's behalf, with bales of all that alfalfa exchanged for milk.

Found 'put' in 'text1' at indices [26, 90]
Found 'and' in 'text1' at indices [101, 128, 171]
Found 'alfalfa' in 'text2' at indices [33, 87]