Horspool's Algorithm

Today, another algorithm. Admittedly this one is not likely to be of much use to many programmers as an actual implementation. Horspool's algorithm, the subject of today's post, is nothing more than a pretty efficient way to search a string for a pattern. Obviously unless your project is to write a new programming language API then you already have such facilities ready at hand. In fact I'd be willing to bet that whatever API you're using has an algorithm similar to this to do the job.

The point here is that the purpose of these exercises are not to reinvent the wheel. They are to understand how things work, under the hood so to speak. I, for one, like that. I feel that it is the sign of a good programmer to have that sort of curiosity, to not just know how to do things but how things work. For my own selfish reasons, I find that I never really understand something until I write about it. So, acknowledging that this post might not have a huge audience, at least I'll get something out of it.

Anyway, about Horspool's algorithm. Obviously the simplest way to do a string pattern search is just to start at the beginning of both string and pattern and do a character by character comparison. Then, if a mismatch is found in any character, shift the pattern one position forward in the string and do the comparison again. Really, this is probably efficient enough for most purposes, should a programmer actually need to implement such an algorithm for some reason. For large searches through many large strings something better might be worth it, though.

Obviously (hopefully) I'm not going to be so foolish as to post such a trivial algorithm as the simple version described above, so there is an optimization, Horspool's that is. (One day I'll have an algorithm named after me.) Firstly, Horspool's starts by aligning the string and pattern as described above. Then it does it's comparison starting at the end of the pattern instead of the start. Now, the key insight is that if a mismatch is found the pattern can be shifted more than a single character. For instance if the final character, the first checked, does not match and also is not contained anywhere in the pattern then the pattern can be shifted the whole length of the pattern forward in the string. If, on the other hand, there is a mismatch but the character does exist elsewhere in the pattern then the pattern can be shifted forward the distance necessary to align that character in the pattern with the string character just checked. Furthermore this is true of any character mismatch anywhere in the string. The exact same shifting rule applies.

The algorithm will continue in this way until either all characters are found to match or the start position of the pattern within the string is such that the end of the pattern would be beyond the end of the string. in that case a "no match" indicator is returned (-1 in my version).

Note that an algorithm like this would not be worth it in code that just does low frequency single character comparisons. The simple algorithm is plenty good enough for that. In fact the computation of the shift table might erase any potential efficiency gain. For large comparisons, though, say a grep on a set of large files this algorithm could make a substantial difference. Note that the shift table is calculated only once and so can be amortized across multiple searches. Of course, as I mentioned before, in the real world we already have grep at our disposal but I'm sure whatever greppers one uses have a similar implementation to this (or maybe even more efficient versions, which exist, although those are quite a bit more complex and might be considered not worth it even for api vendors. Evidence of this is that Horpool published his algorithm after the more efficient, but similar, version. Apparently he saw a need for a simplification).

Anyway, here is my Ruby implementation. I tried to include a good many comments to make the logic easy to follow. Hopefully I succeeded. Enjoy.

class Horspool
 def findIn(str, pattern)
  @shiftTable=Hash.new(nil) #will contain shift amounts for all valid chars
  @pattern=pattern
  calcShift #buld the shift table
  i=0 #pos in str
  j=pattern.size-1 #pos in pattern
  shift=pattern.size #initialize shift to maximum posible
  while i+pattern.size-1<str.size #Pattern doesn't extend past end of str
   #Use shift table lookup to shift the precomputed amount minus dist from 
   #end of pattern (which is (pattern.size-1)-j), if that's less then
   #previously computed shift make it the current shift
   newShift=@shiftTable[str[i+j,1]]-((pattern.size-1)-j)
   (newShift<shift)?shift=newShift:nil
   if str[i+j]==pattern[j] #str/pattern char match
    j-=1 #moving backward through pattern
    if j<0 #Made it all the way through pattern, must match
     return i
    end
   else
    i+=shift #Start comparing at new post in str
    j=pattern.size-1 #reset j to end of pattern
    shift=pattern.size
   end
  end
  return -1 #No match
 end

private
 
 def calcShift
  #Precompute to shift whole pattern length for chars not in pattern
  for i in 'a'..'z' 
   @shiftTable[i]=@pattern.size
  end
  #Shift distance from end of pattern-1 for chars in pattern
  for i in 0... @pattern.size-1
   @shiftTable[@pattern[i,1]]=(@pattern.size-i)-1
  end
 end
end

if __FILE__ == $0
 print Horspool.new.findIn("ericzetterbaum","zett")
end