пластическая акробатика

АНДРЕЙ «ORC» СЕРЕГИН

Спецвыпуск: Хакер, номер #071, стр. 071-034-2

Метод фон Неймана – самый сложный в реализации, хотя и самый оптимальный. В своем повседневном программировании ты, конечно, сам волен выбирать, каким из описанных алгоритмов воспользоваться.

[поиск.]

Конечно, ты не переплюнешь таких монстров поиска, как Яндекс или Гугл (хотя, кто знает). Но то, что ты прочтешь далее, позволит тебе написать, к примеру, собственный поисковый движок по сайту. А не пользоваться готовыми компонентами и скриптами — несерьезно ведь.

За время развития программирования возможности поиска шагнули далеко вперед, но принципы и алгоритмы остаются теми же, что и 10 лет назад. Самый простой – метод брутфорса, то есть последовательного перебора. Берем первую букву в искомой строке, ищем ее в оригинале. Если находим – смотрим следующую букву. И так далее. Такой алгоритм проще пареной репы, запрограммировать его тоже очень просто (S – строка, P – искомая подстрока, а сама функция возвращает индекс, с которого в строке S начинается подстрока P):

function BFSearch (S, P : String) : Integer;

var

A, B : Integer;

begin

Result := 0;

if Length(P) > Length(S) then Exit;

for A := 1 to Length(S) — Length(P) + 1 do

for B := 1 to Length(P) do

if P[B] <> S[A+B-1] then Break

else if B = Length(P) then

begin

Result := A;

Exit;

end;

end;

А вот на алгоритме поиска по методу Бойера-Мура-Хорспула (Boyer-Moor-Horspool Pattern Search, чаще всего просто BMH) стоит остановиться поподробнее. Действие алгоритма начинается с построения «таблицы смещений» для искомой подстроки — каждому символу в подстроке приравнивается число, которое представляет собой смещение символа алфавита относительно последнего символа в подстроке. Следующим шагом совмещаем начало строки и подстроки и смотрим, совпал ли последний символ в подстроке с символом из строки, полученном при таком наложении. Если это условие не выполняется — смещаем подстроку на количество символов из таблицы смещений, а если выполняется – сравниваем предпоследние символы. И так далее. Самая простая реализация такого алгоритма может выглядеть так:

function BMHSearch(StartPos: Integer; S, P: string): Integer;

type

BMHTable = array[0..255] of Integer;

var

Pos, lp, i: Integer;

BMHT: BMHTable;

begin

for i := 0 to 255 do

BMHT[i] := Length(P);

for i := Length(P) downto 1 do

if BMHT[Byte(P[i])] = Length(P) then

BMHT[Byte(P[i])] := Length(P) — i;

lp := Length(P);

Pos := StartPos + lp — 1;

while Pos <= Length(S) do

if P[lp] <> S[Pos] then

Pos := Pos + BMHT[Byte(S[Pos])]

else if lp = 1 then

begin

Result := Pos;

Exit;

end

else

for i := lp — 1 downto 1 do

if P[i] <> S[Pos — lp + i] then

begin

Inc(Pos);

Break;

end

else if i = 1 then

begin

Result := Pos — lp + 1;

Exit;

end;

Result := 0;

End;

Но, пожалуй, самый известный и популярный алгоритм – это поиск методом Кнута-Морриса-Пратта, который представляет собой эволюцию алгоритма Морриса-Пратта (который, в свою очередь, есть усложненный метод брутфорса). Идея алгоритма заключается в том, что мы предварительно обрабатываем искомую подстроку – создаем для нее префикс-функцию, то есть ищем в начале и в конце подстроки наибольшую последовательность повторяющихся символов. Например, для строки 12345qwerty12345 префикс-функция должна возвратить 12345. Вот реализация такой функции: