1.4. Прямой поиск строки

Часто приходится сталкиваться со специфическим поиском, так называемым поиском строки. Его мож­но определить следующим образом. Пусть задан мас­сив s из N элементов и массив р из М элементов, при­чем 0 < М ≤ N. Описаны они так:

s: ARRAY[ 1 .. N ] OF item

p: ARRAY[ 1 .. М ] OF item

Поиск строки обнаруживает первое вхождение р в s. Обычно item—это символы, т. е. s можно считать некоторым текстом, а р - образом или словом, и мы хотим найти первое вхождение этого слова в указан­ном тексте. Это действие типично для любых систем обработки текстов, отсюда и очевидная заинтересо­ванность в поиске эффективного алгоритма для этой задачи. Однако, прежде чем обращать внимание на эффективность, давайте сначала разберем некий «пря­молинейный» алгоритм поиска. Мы его будем назы­вать прямым поиском строки.

Еще до определения алгоритма нужно более точ­но сформулировать, что же мы от него желаем полу­чить. Будем считать результатом индекс i, указываю­щий на первое с начала строки совпадение с образом. С этой целью введем предикат P( i, j ):

P( i, j ) = A k: 1 ≤ k < j: s_i+k=p_k (1.47)

Наш результирующий индекс, очевидно, должен удов­летворять предикату Р( i, М ). Но этого недоста­точно. Поскольку поиск должен обнаружить первое вхождение образа P(k, M) должно быть ложным для всех k < i. Обозначим это условие через Q(i):

Q( i ) = A k: 1 ≤ k < i: ~ P(k,M) (1.48)

Поставленная задача сразу же наводит на мысль оформить поиск как повторяющееся сравнение, и мы предлагаем такой вариант:

i:=0;

REPEAT (* Q(i)*)

i:=i+1;

found:= P(i,M)

UNTIL found OR (i=N-M);

Вычисление Р, естественно, вновь сводится к повто­ряющимся сравнениям отдельных символов. Если применить к Р теорему Моргана, то получается, что итерации должны «искать» несовпадение между об­разом и строкой символов.

P( i, j )=( A k: 1 ≤ k < j: s_i+k=p_k )=( ~E k: 1 ≤ k < j: s_i+k≠p_k )

В результате этого уточнения мы приходим к повто­рению внутри повторения. Предикаты Р и Q включаются в соответствующие места программы как примечания. Они представляют собой инварианты циклов упомянутых итеративных процессов.

i:=0;

REPEAT (* Q(i)*)

i:=i+1; j:=0;

WHILE ( j < M ) AND ( s[ i+j ]=p[ j+1 ] ) DO j:=j+1 (* P( i,j+1) *)

(* Q( i ) & P( i, j ) & (( j=M ) OR ( s[ i+j ] ≠ p[ j ] )) *)

UNTIL ( j=M ) OR ( i=N-M );

В действительности выражение j = M в условии окончания соответствует условию found, так как из него следует P(i, М). Выражение i=N-М имплицирует Q(N—M) и тем самым свидетельствует, что нигде в строке совпадения нет. Если итерации продолжаются при j < М, то они должны продолжаться и при s_i+k=p_k. В соот­ветствии с (1.47) отсюда следует ~P(i, j), затем из-за (1.48) следует Q(i +1), что и подтверждает справедливость Q(i) после очередного увеличения i.

Анализ прямого поиски в строке. Этот алгоритм работает достаточно эффективно, если мы допускаем, что несовпадение пары символов происходит по край­ней мере после всего лишь нескольких сравнений во внутреннем цикле. При большой мощности типа item это достаточно частый случай. Можно предполагать, что для текстов, составленных из 128 символов, не­совпадение будет обнаруживаться после одной или двух проверок. Тем не менее в худшем случае про­изводительность будет внушать опасение. Возьмем, например, строку, состоящую из N-1 символов А и единственного В, а образ содержит М-1 симво­лов А и опять В. Чтобы обнаружить совпадение в конце строки, требуется произвести порядка N*M сравнений. К счастью, как мы скоро увидим, есть прием, который существенно улучшает обработ­ку этого неблагоприятного варианта.