Алгоритмы поиска в тексте

самое последнее вхождение образца 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 будут найдены все вхождения слов «бросать» и «бросить» (а также «забросать», «забросить», «бросаться» и т.п., так как не указаны предваряющий и завершающий пробелы).

В заключение рассмотрим вопрос о том, всегда ли следует применять алгоритм Бойера-Мура, и какой вариант этого алгоритма лучше выбрать. Превосходство алгоритма Бойера-Мура перед методом грубой силы наиболее ощутимо проявляется с увеличением длины образца. Хотя алгоритм Бойера-Мура производит меньше сравнений, чем примитивный алгоритм при длине образца более двух символов, большая сложность этого алгоритма и необходимость заранее вычислять таблицу смещений может свести на нет его преимущества, если поиск проводится в коротком тексте, и длина образца невелика.

Преимущество в быстродействии более сложного варианта алгоритма Бойера-Мура перед более простым вариантом сказывается, только если длина образца велика, и в тексте часто встречаются отдельные последовательности символов, содержащиеся в образце. Главное же достоинство более сложного варианта алгоритма заключается в возможности реализации регистронезависимого поиска и поиска по шаблону.

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: