Friday, October 23, 2009

Boyer-Moore-Horspool algorithm

If you ever need to search a string very fast then you should use Boyer-Moore-Horspool algorithm, it's so fast that you can search 80Mb text files in under 300 miliseconds!
Example of implementation in Delphi
function search(pat: string; text: string): integer;
var
  i, j, k, m, n: integer;
  skip: array [0..MAXCHAR] of integer;
  found: boolean;
begin
  found := FALSE;
  search := 0;
  m := length(pat);
  if m=0 then
  begin
    search := 1;
    found := TRUE;
  end;
  for k:=0 to MAXCHAR do
    skip[k] := m;   {*** Preprocessing ***}
  for k:=1 to m-1 do
    skip[ord(pat[k])] := m-k;
  k := m;
  n := length(text);            {*** Search ***}
  while not found and (k <= n) do
  begin
    i := k; j := m;
    while (j >= 1) do
    begin
      if text[i] <> pat[j] then
        j := -1
      else
      begin
        j := j-1;
        i := i-1;
      end;
      if j = 0 then
      begin
        search := i+1;
        found := TRUE;
      end;
      k := k + skip[ord(text[k])];
    end;
  end;
end;
This snippet is taken from www.delphidabbler.com, it can be viewed fallowing this link.
In a few days I will post a trie implementation which is way faster than Boyer-Moore.

1 comment:

Blogroll(General programming and Delphi feeds)