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

END

Поиск в таблице

BEGIN

BEGIN

m:=(L+R) DIV 2; { выбрираем любой элемент между элементами с номерами L и R }

IF a[ m ]=x THEN found:=TRUE ELSE

IF a[ m ]<x THEN L:=m+1 ELSE R:=m-1;

END;

IFfound THEN writeln(‘искомый элемент ‘,a [ m ]);

Инвариант цикла, т. е. условие, выполняющееся перед каждым шагом, таков:

(L ≤ R) & (A k: 1 ≤ k < L: a_k < х) & (A k: R < k ≤ N: a_k > х) (1.41)

из чего выводится результат

found OR ((L > R) & (A k: 1 ≤ k < L: a_k < х) & (A k: R < k ≤ N: a_k > х))

откуда следует

(a_m = x) OR (A k: 1 ≤ k ≤ N: a_k ≠ х).

Выбор m совершенно произволен в том смысле, что корректность алгоритма от него не зависит. Однако на его эффективность выбор влияет. Ясно, что наша задача — исключить на каждом шагу из дальнейшего поиска, каким бы ни был результат сравнения, как можно больше элементов. Оптимальным решением будет выбор среднего элемента, так как при этом в любом случае будет исключаться половина массива. В результате максимальное число сравнений равно log₂(N), округленному до ближайшего целого. Таким образом, приведенный алгоритм существенно выиг­рывает по сравнению с линейным поиском, ведь там ожидаемое число сравнений - N/2.

Эффективность можно несколько улучшить, поме­няв местами заголовки условных операторов. Про­верку на равенство можно выполнять во вторую оче­редь, так как она встречается лишь единожды и при­водит к окончанию работы. Но более существенно следующее соображение: нельзя ли, как и при линей­ном поиске, отыскать такое решение, которое опять бы упростило условие окончания. И мы действитель­но находим такой быстрый алгоритм, как только от­казываемся от наивного желания кончить поиск при фиксации совпадения. На первый взгляд это кажется странным, однако при внимательном рассмотрении обнаруживается, что выигрыш в эффективности на каждом шаге превосходит потери от сравнения с не­сколькими дополнительными элементами. Напомним, что число шагов в худшем случае – log₂(N). Быстрый алгоритм основан на следующем инварианте:

(A k: 1 ≤ k < L: a_k < х) & (A k: R < k ≤ N: a_k ≥ х) (1.42)

причем поиск продолжается до тех пор, пока обе сек­ции не «накроют» массив целиком.

L:=1; R:=N+1;

WHILE L<R DO

j:= (L+R) DIV 2;

IF a [ j ] < x THEN L:=j+1 ELSE R:=j;

END;

IF a [ R ] = x THEN writeln(‘искомый элемент ‘,a [ R ]);

Условие окончания – L ≥ R, но достижимо ли оно? Для доказательства этого нам необходимо пока­зать, что пр и всех обстоятельствах разность R - L на каждом шаге убывает. В начале каждого шага L < R. Для среднего арифметического m справедливо условие L ≤ m < R. Следовательно, разность дей­ствительно убывает, ведь либо L увеличивается при присваивании ему значения m + 1, либо R уменьша­ется при присваивании значения m. При L = R по­вторение цикла заканчивается. Однако наш инвари­ант и условие L = R еще не свидетельствуют о совпа­дении. Конечно, при R = N+1 никаких совпадений нет. В других же случаях мы должны учитывать, что эле­мент а [ R ] в сравнениях никогда не участвует. Следо­вательно, необходима дополнительная проверка на равенство а [ R ] = х. В отличие от первого нашего ре­шения (1.40) приведенный алгоритм, как и в случае линейного поиска, находит совпадающий элемент с наименьшим индексом.

Поиск в массиве иногда называют поиском, в таб­лице, особенно если ключ сам является составным объектом, таким, как массив чисел или символов. Ча­сто встречается именно последний случай, когда мас­сивы символов называют строками или словами. Строковый тип определяется так: String =ARRAY[0.. М - 1] OF CHAR (1.44)

соответственно определяется и отношение порядка для строк:

(х = у) = (A j: 0 ≤ j < M: x_j = y_j)

(х < у) = E i: 0 ≤ i < N: ((A j: 0 ≤ j < i: x_j = y_j ) & (x_i < y_i ))

Для того чтобы установить факт совпадения, мы должны, очевидно, убедиться, что все символы срав­ниваемых строк соответственно равны один другому. Поэтому сравнение составных операндов сводится к поиску их несовпадающих частей, т. е. к поиску «на неравенство». Если неравных частей не существует, то можно говорить о равенстве. Предположим, что размер слов достаточно мал, скажем, меньше 30. В этом случае мы будем использовать линейный по­иск и поступать таким образом.

Для большинства практических приложений жела­тельно исходить из того, что строки имеют перемен­ный размер. Это предполагает, что размер указыва­ется в каждой отдельной строке. Если исходить из ранее описанного типа, то размер не должен превос­ходить максимального размера M. Такая схема до­статочно гибка и подходит для многих случаев, в тоже время она позволяет избежать сложностей дина­мического распределения памяти. Чаще всего исполь­зуются два таких представления размера строк:

ü Размер неявно указывается путем добавления концевого символа, больше этот символ нигде не упо­требляется. Обычно для этой цели используется «не­печатаемый» символ со значением 0С. (Для дальней­шего важно, что это минимальный символ из всего множества символов.)

ü Размер явно хранится в качестве первого эле­мента массива, т.е. строка s имеет следующий вид: s= s₀, s₁, s₂,..., s_n-i. здесь s_i,..., s_n-i — фактиче­ские символы строки, a s₀ = CHR(N). Такой прием имеет то преимущество, что размер явно доступен, недостаток же в том, что этот размер ограничен раз­мером множества символов.

В последующем алгоритме поиска мы отдаем пред­почтение первой схеме. В этом случае сравнение строк выполняется так:

i:=0;

WHILE (x[ i ] = y[ i ]) & (x[ i ] <> 0C) DO i:=i+1; (1.45)

Концевой символ работает теперь как барьер, а ин­вариант цикла таков:

A j: 0 ≤ j < i: x_j = y_j ≠ 0C

Результирующее же условие выглядит следующим образом:

((x_i ≠ y_i ) OR (x_j = 0C)) & (A j: 0 ≤ j < i: x_i = y_j ≠ 0C)

При условии x_i = y_i считается, что х и у совпадают, если же х; <: у), то х < у.

Теперь мы готовы вернуться к задаче поиска в таб­лице. Он требует «вложенных» поисков, а именно: по­иска по строчкам таблицы, а для каждой строчки по­следовательных сравнений—между компонентами, Например, пусть таблица Т и аргумент поиска х опре­деляются таким образом:

Т: ARRAY [0... N-1] OF String;

x: String;

Допустим, N достаточно велико, а таблица упорядо­чена в алфавитном порядке. Воспользуемся поиском делением пополам. Используя соответствующие алго­ритмы (1.43) и сравнения строк (1.45), о которых шла речь выше, получаем такой фрагмент про­граммы:

L:=0; R:=N; (1.46)

WHILE L<R DO BEGIN

m:= (L+R) DIV 2; i:=0;

WHILE (T[m,i] = x[i]) AND (x[i] ≠ 0С) DO i: =i+1;

IF T[m,i] < x[i] THEN L:=m+1 ELSE R:=m

END;

IF R<N THEN BEGIN

i:=0;

WHILE (T[R,i] = x[i]) AND (x[i] ≠ 0С) DO i:=i+l

(* (R<N) & (T[R,i] = x[i]) фиксирует совпадение *)

Часто приходится сталкиваться со специфическим поиском, так называемым поиском строки. Его мож­но определить следующим образом. Пусть задан мас­сив 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 сравнений. К счастью, как мы скоро увидим, есть прием, который существенно улучшает обработ­ку этого неблагоприятного варианта.

Дата добавления: 2014-01-13