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

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

Поиск в массиве иногда называют поиском в таблице, особенно если ключ является составным объектом, таким как массив чисел или символов.

Массивы символов называют строками или словами.

Строковый тип определяется следующим образом:

Siring = ARRAY[0..M-1] OF CHAR;

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

(x=y)=(Aj:0≤j<M:xj=y,),

(x<y) = Ei:0≤i<N:((Aj:0≤j<i:х_j = y_j)&(х_i<y_i)).

Чтобы установить факт совпадения, нужно убедиться, что все символы сравниваемых строк соответ­ственно равны один другому.

Поэтому сравнение составных опе­рандов сводится к поиску их несовпадающих частей, т. е. к поис­ку "на неравенство".

Если неравных частей не существует, то можно говорить о равенстве.

Например: размер слов до­статочно мал, меньше 30. В этом случае будет исполь­зоваться линейный поиск.

Для практических приложений желательно исхо­дить из того, что строки имеют переменный размер,т.е размер указывается в каждой отдельной строке.

Размер не должен превос­ходить максимального размера М. Такая схема достаточно гибка, и подходит для многих случаев и она позволяет из­бежать сложностей динамического распределения памяти.

Чаще всего используются два таких представления размера строк:

1. Размер неявно указывается путем добавления концевого сим­вола, и больше этот символ нигде не употребляется. Для этой цели используется "непечатаемый" символ со зна­чением #0 - это минимальный символ из всего множества символов.

2. Размер явно хранится в качестве первого элемента массива, т. е. строка s имеет следующий вид: s = s₀, s₁, s₂, …, s_n-1, где

s₁, s₂, …, s_n-1 - фактические символы строки,

s₀ = CHR(N).

Преимуществоэтого приема в том, что размер досту­пен, недостаток - в том, что этот размер ограничен разме­ром множества символов (256).

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

s: ARRAY[0..N-1] OF item; p: ARRAY[0..M-1] OF itemПоиск строки обнаруживает первое вхождение pes. Обычно i tern — это символы, т. е. s можно считать некоторым текстом, ар — обра­зом или словом, и мы хотим найти первое вхождение этого слова в указанном тексте. Это действие типично для любых систем об­работки текстов, отсюда и очевидная заинтересованность в поис­ке эффективного алгоритма для этой задачи. Однако прежде, чем обращать внимание на эффективность, давайте сначала разберем некий "прямолинейный" алгоритм поиска. Мы его будем назы­вать прямым поиском строки.

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

P(iJ) = Ak: 0 <A</:si+t-p*. (147)

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

Q(i) = Ak:0<k<i: ~P(k, M). (1.48)

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

i := -1;

REPEAT i := i+1 (« Q(i) .)

found : = P(i.M)

UNTIL found OR (i = N-M);

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

P(i,j)-<,Ak:0<k<j:sj+k-P*)~(-®i-0<k<j:Si+k*Pk)-

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

- L+1; j := 0; (-' 0(i) •) (1.49)

WHILE (] < M) and (S[i+j] = p[]]) DO (• P(i,j*1) •) j := 1+1;

(• Q(i) and P(i,j) and ((j = M) OR (s[i+j] <> p[j])) •) UNTIL (] = M) OR (i = N-M).

действительности член;' = Mb условии окончания соответству-т условию found, так как из него следует P(i, М). Член i = N - М мплицирует Q(N- M) и тем самым свидетельствует, что нигде в троке совпадения нет. Если итерации продолжаются при j < М, о они должны продолжаться и при S; >_; ^ pj. В соответствии (1.4 7 ) отсюда следует - P(i,j), затем из-за (1.48) следует Q(j + 1), что и подтверждает справедливость Q(i) после очередного увели-ения;'.

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

Чтобы обнаружить совпадение в конце строки, требуется про­извести порядка N * М сравнений. К счастью, как мы скоро уви­дим, есть прием, который существенно улучшает обработку этого неблагоприятного варианта.