Часть 3. Поиск подстроки в строке. Более эффективный вариант
Рассмотренный упрощенный алгоритм вполне пригоден с практической точки
зрения (и часто применяется). Нельзя не заметить, что результаты
сравнений используются недостаточно эффективно. Действительно, на
втором шаге, когда у нас совпали три символа, мы, зная, что
последовательность “bad” встречается в образце только один раз, могли
бы сразу сместить образец на всю его длину, а не на один символ.
Теперь мы рассмотрим другой, немного более сложный вариант алгоритма Бойера-Мура, позволяющий учесть результаты предыдущих сравнений в случаечастичного совпадения образца и подстроки. Прежде всего изменим принцип построения таблицы смещений. В этом варианте алгоритма таблица – двумерная, каждому символу образца соответствует один столбец таблицы, а каждой букве алфавита – одна строка. В ячейках таблицы содержатся значения смещений, на которые нужно сдвинуть образец, если при проверке данного символа образца обнаружено несовпадение и вместо искомого символа получен символ алфавита, соответствующий некоторой строке в таблице. Например, таблица последовательности “abdab” для нашего пятибуквенного алфавита будет выглядеть следующим образом:
Заполнение таблицы начинается с последнего столбца. Самый правый столбец таблицы фактически соответствует массиву, который используется в упрощенном варианте алгоритма. Следующие столбцы содержат значения сдвига для образца при условии, что предыдущие (при движении справа налево) символы совпали. Проводя поиск при помощи этой таблицы, мы последовательно просматриваем значения ячеек, лежащих на пересечении столбца, соответствующего символу образца и строки, соответствующей символу текста. Просмотр начинается с последнего столбца. Если в каждом столбце выбранная ячейка содержит 0, значит, подстрока найдена. Если значение ячейки отличается от нуля, мы сдвигаем образец на соответствующее значение.
Определенные сложности могут возникнуть при работе с кодировкой Unicode. Очевидно, что таблица, число строк которой равно числу символов двухбайтовой кодировки, будет слишком громоздкой. К счастью, в такой таблице нет необходимости, ведь в случае двухбайтовой кодировки любой образец содержит лишь небольшую часть символов алфавита. Для всех символов, не содержащихся в образце, значения смещения в каждом столбце таблицы будут одинаковыми. Эта особенность позволяет разработать сокращенные варианты таблицы для Unicode. Конечно, Unicode-строку можно рассматривать как последовательность байтов, где каждый Unicode-символ представлен двумя байтами. Однако этот подход менее эффективен и не позволяет воспользоваться теми дополнительными возможностями алгоритма, о которых будет сказано ниже.
Далее приводятся функции и определения, реализующие алгоритм для 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 будут найдены все вхождения слов «бросать» и «бросить» (а также «забросать», «забросить», «бросаться» и т.п., так как не указаны предваряющий и завершающий пробелы).
В заключение рассмотрим вопрос о том, всегда ли следует применять алгоритм Бойера-Мура, и какой вариант этого алгоритма лучше выбрать. Превосходство алгоритма Бойера-Мура перед методом грубой силы наиболее ощутимо проявляется с увеличением длины образца. Хотя алгоритм Бойера-Мура производит меньше сравнений, чем примитивный алгоритм при длине образца более двух символов, большая сложность этого алгоритма и необходимость заранее вычислять таблицу смещений может свести на нет его преимущества, если поиск проводится в коротком тексте, и длина образца невелика.
Преимущество в быстродействии более сложного варианта алгоритма Бойера-Мура перед более простым вариантом сказывается, только если длина образца велика, и в тексте часто встречаются отдельные последовательности символов, содержащиеся в образце. Главное же достоинство более сложного варианта алгоритма заключается в возможности реализации регистронезависимого поиска и поиска по шаблону.
