Далее приводятся функции и определения, реализующие алгоритм для 256-символьного набора.
| type TIntVect = array [0..255] of Integer; TBMTable = array [0..0] of TIntVect; PBMTable = ^TBMTable;function FindRightmost( const S, P : String; n : Integer) : Integer; var i, j, lp : Integer; begin Result := 0; lp := Length(P); if lp > n then Exit; for i := n - lp + 1 downto 1 do for j := 1 to lp do if P[j] <> S[i+j-1] then Break else if j = lp then begin Result := i; Exit; end; end;procedure MakeBMTable( var BMT : PBMTable; const P : String); var i, j, lp, MaxShift, CurShift, SufPos : Integer; Suffix : String; begin lp := Length(P); GetMem(BMT, SizeOf(TIntVect)*lp); for i := 0 to 255 do BMT^[lp-1][i] := lp; for i := lp downto 1 do if BMT^[lp-1][Byte(P[i])] = lp then BMT^[lp-1][Byte(P[i])] := lp - i; MaxShift := lp; for i := lp - 1 downto 1 do begin SetLength(Suffix, lp - i); Move(P[i+1], Suffix[1], lp - i); if Pos(Suffix, P) = 1 then MaxShift := i; for j := 0 to 255 do begin CurShift := MaxShift; SetLength(Suffix, lp - i + 1); Suffix[1] := Char(j); Move(P[i + 1], Suffix[2], lp - i ); SufPos := FindRightmost(P, Suffix, lp - 1); if SufPos <> 0 then CurShift := i - SufPos; BMT^[i-1][j] := CurShift; end; BMT^[i-1][Byte(P[i])] := 0; end; end;function BMSearch( StartPos, lp : Integer; const S : String; BMT : PBMTable) : Integer; var Pos, i : Integer; begin Pos := StartPos + lp -1; while Pos < Length(S) do for i := lp downto 1 do if BMT^[i-1][Byte(S[Pos-lp+i])] <> 0 then begin Pos := Pos + BMT^[i-1][Byte(S[Pos-lp+i])]; Break; end else if i = 1 then begin Result := Pos - lp + 1; Exit; end; Result := 0; end; |
Служебная функция FindRightmost возвращает самое последнее вхождение образца P среди n первых символов строки S. Формат вызова функции BMSearch отличается от предыдущего. В параметре lp передается длина строки образца, сама же строка не нужна, так как таблица смещений однозначно описывает образец. Следует также учесть, что функция MakeBMTable динамически выделяет память для таблицы смещений, и после окончания использования функции BMSearch эту память необходимо освободить при помощи функции FreeMem. Следующий фрагмент кода иллюстрирует поиск всех вхождений образца P в строке S.
| MakeBMTable(BMT, P); PatPos := BMSearch(1, Length(P), S, BMT); while PatPos <> 0 do begin ... PatPos := BMSearch(PatPos + 1, Length(P), S, BMT); end; FreeMem(BMT); |
Дополнительным преимуществом данного варианта алгоритма является возможность организовать «регистронезависимый» поиск, т. е. поиск слова вне зависимости от регистра букв. Для этого достаточно в таблице смещений сопоставить одинаковые строки одним и тем же буквам разного регистра. Можно даже ввести поиск по шаблону, содержащему подстановочные символы. Ниже приводятся функции формирования таблицы смещений для шаблонов, в которых символ «?» соответствует любому символу используемого набора.
| function WCBeginsWith( const P, S : String) : Boolean; var i, lp : Integer; begin Result := False; lp := Length(P); if lp > Length(S) then Exit; for i := 1 to lp do if (P[i]<>S[i]) and (P[i]<>'?') and (S[i]<>'?') then Exit; Result := True; end;function WCFindRightmost( const S, P : String; l : Integer) : Integer; var i, j, lp : Integer; begin Result := 0; lp := Length(P); if lp > l then Exit; for i := l - lp + 1 downto 1 do for j := 1 to lp do if (P[j]<>S[i+j-1]) and (P[j]<>'?') and (S[i+j-1]<>'?') then Break else if j = lp then begin Result := i; Exit; end; end;procedure WCMakeBMTable( var BMT : PBMTable; const P : String); var i, j, lp, MaxShift, CurShift, SufPos : Integer; Suffix : String; begin lp := Length(P); GetMem(BMT, SizeOf(TIntVect)*lp); if P[lp] = '?' then for i := 0 to 255 do BMT^[lp-1][i] := 0 else begin for i := 0 to 255 do BMT^[lp-1][i] := lp; for i := lp downto 1 do if BMT^[lp-1][Byte(P[i])] = lp then BMT^[lp-1][Byte(P[i])] := lp - i; end; MaxShift := lp; for i := lp - 1 downto 1 do begin SetLength(Suffix, lp - i); Move(P[i+1], Suffix[1], lp - i); if WCBeginsWith(Suffix, P) then MaxShift := i; if P[i] = '?' then for j := 0 to 255 do BMT^[i-1][j] := 0 else for j := 0 to 255 do begin CurShift := MaxShift; SetLength(Suffix, lp - i + 1); Suffix[1] := Char(j); Move(P[i + 1], Suffix[2], lp - i ); SufPos := WCFindRightmost(P, Suffix, lp - 1); if SufPos <> 0 then CurShift := i - SufPos; BMT^[i-1][j] := CurShift; end; BMT^[i-1][Byte(P[i])] := 0; end; end; |
Например, если в качестве шаблона функции WCMakeBMTable передать строку «брос?ть», и передать полученную таблицу функции BMSearch, в тексте S будут найдены все вхождения слов «бросать» и «бросить» (а также «забросать», «забросить», «бросаться» и т.п., так как не указаны предваряющий и завершающий пробелы).
В заключение рассмотрим вопрос о том, всегда ли следует применять алгоритм Бойера-Мура, и какой вариант этого алгоритма лучше выбрать. Превосходство алгоритма Бойера-Мура перед методом грубой силы наиболее ощутимо проявляется с увеличением длины образца. Хотя алгоритм Бойера-Мура производит меньше сравнений, чем примитивный алгоритм при длине образца более двух символов, большая сложность этого алгоритма и необходимость заранее вычислять таблицу смещений может свести на нет его преимущества, если поиск проводится в коротком тексте, и длина образца невелика.
Преимущество в быстродействии более сложного варианта алгоритма Бойера-Мура перед более простым вариантом сказывается, только если длина образца велика, и в тексте часто встречаются отдельные последовательности символов, содержащиеся в образце. Главное же достоинство более сложного варианта алгоритма заключается в возможности реализации регистронезависимого поиска и поиска по шаблону.