1.8. Поиск
Задача поиска – одна из наиболее часто встречающихся в программировании.
Она также дает прекрасные возможности показать применение рассмотренных структур данных. Есть несколько основных вариаций на тему поиска, и здесь при%
думано множество алгоритмов. Основное предположение, которое мы делаем в дальнейшем изложении, состоит в том, что набор данных, в котором ищется за%
данное значение, фиксирован. Будем предполагать, что этот набор
N
элементов представлен массивом, скажем a: ARRAY N OF Item
Обычно элементы являются записями, одно из полей которых играет роль ключа. Тогда задача состоит в нахождении элемента, у которого поле ключа равно заданному значению x
, которое еще называют аргументом поиска. Найденный индекс i
, удовлетворяющий условию a[i].key = x
, позволит обратиться к другим полям найденного элемента. Поскольку нам здесь интересна только задача поис%
ка, но не данные, ради которых производится поиск, мы будем предполагать, что тип
Item состоит только из ключа, то есть сам является ключом.
Поиск
Фундаментальные структуры данных
50
1.8.1. Линейный поиск
Если нет никакой дополнительной информации о данных, то очевидное реше%
ние – последовательно проходить по массиву, шаг за шагом увеличивая величину той части массива, где искомое значение заведомо отсутствует. Это решение изве%
стно как линейный поиск. Поиск прекращается при одном из двух условий:
1. Элемент найден, то есть a
i
= x
2. Просмотрен весь массив, но элемент не найден.
Приходим к следующему алгоритму:
i := 0;
(* ADruS18_ *)
WHILE (i < N) & (a[i] # x) DO INC(i) END
Отметим, что порядок операндов в булевском выражении важен.
До и после каждого шага цикла выполняется следующее условие:
(0
≤ i < N) & (A
A
A
A
Ak: 0
≤ k < i : a k
≠ x)
Такое условие называется инвариантом. В данном случае инвариант означает,
что для всех значений k
, меньших, чем i
, среди a
k искомого значения x
нет. Заме%
тим, что до и после каждого шага цикла значения i
– разные. Сохранение инвари%
анта при изменении i
имеет место в данном случае благодаря истинности охраны цикла (условия между ключевыми словами
WHILE
и
DO
).
Из выполнения инварианта и из того факта, что поиск прекращается, только если станет ложной охрана цикла, получается условие, выполняющееся после окончания данного фрагмента программы (так называемое постусловие для дан%
ного фрагмента):
((i = N) OR (a i
= x )) & (A
A
A
A
Ak: 0
≤ k < i : a k
≠ x)
Это условие не только является искомым результатом, но еще и подразумева%
ет, что если найден элемент, равный x
, то это первый такой элемент. При этом i = N
означает, что искомого значения не найдено.
Окончание цикла гарантировано, так как величина i
на каждом шаге увели%
чивается и поэтому обязательно достигнет границы
N
после конечного числа ша%
гов; на самом деле после
N
шагов, если искомого значения в массиве нет.
На каждом шаге нужно вычислять булевское выражение и увеличивать ин%
декс. Можно ли упростить эту задачу и тем самым ускорить поиск? Единственная возможность – упростить булевское выражение, состоящее, как видим, из двух членов. Поэтому построить более простое решение удастся, только если найти ус%
ловие с единственным членом, из которого будут следовать оба. Это возможно лишь при гарантии, что искомое значение всегда будет найдено, а это можно обес%
печить, помещая дополнительный элемент со значением x
в конец массива. Будем называть такой вспомогательный элемент барьером (sentinel), так как он препят%
ствует выходу поиска за границу массива. Теперь массив a
объявляется так:
a: ARRAY N+1 OF INTEGER,
51
и алгоритм линейного поиска с барьером выражается следующим образом:
a[N] := x; i := 0;
(* ADruS18_ *)
WHILE a[i] # x DO INC(i) END
В итоге получается условие, выведенное из того же инварианта, что и ранее:
(a i
= x) & (Ak: 0
≤ k < i : a k
≠ x)
Очевидно, из i = N
следует, что искомое значение не встретилось (не считая значения%барьера).
1.8.2. Поиск делением пополамПонятно, что ускорить поиск невозможно, если нет дополнительной информации о данных, в которых он выполняется. Хорошо известно, что поиск может быть го%
раздо более эффективным, если данные упорядочены. Достаточно представить себе телефонный справочник, в котором номера даны не по алфавиту: такой спра%
вочник совершенно бесполезен. Поэтому обсудим теперь алгоритм, который ис%
пользует информацию о том, что массив a
упорядочен, то есть что выполняется условие
A
A
A
A
Ak: 1
≤ k < N : a k–1
≤ a k
Ключевая идея – в том, чтобы выбрать наугад элемент, скажем a
m
, и сравнить его с искомым значением x
. Если он равен x
, то поиск прекращается; если он мень%
ше x
, то можно заключить, что все элементы с индексами, равными или меньшими m
, можно игнорировать в дальнейшем поиске; а если он больше x
, то можно игно%
рировать все значения индекса, большие или равные m
. Это приводит к следую%
щему алгоритму, который носит название
поиск делением пополам (binary search);
в нем используются две индексные переменные
L
и
R
, отмечающие в массиве a
левый и правый концы отрезка, в котором искомое значение все еще может быть найдено:
L := 0; R := N–1;
(* ADruS18_ *)
m :=
L R;
WHILE (L <= R) & (a[m] # x) DO
IF a[m] < x THEN
L := m+1
ELSE
R := m–1
END;
m :=
L R
END
Подчеркнем фундаментальное структурное подобие этого алгоритма и алго%
ритма линейного поиска в предыдущем разделе: роль i
теперь играет тройка
L, m,
R
. Чтобы не потерять это подобие и тем самым надежней гарантировать коррект%
ность цикла, мы воздержались от соблазна мелкой оптимизации программы с целью устранения дублирования инструкции присваивания переменной m
Поиск
Фундаментальные структуры данных
52
Следующее условие является инвариантом цикла, то есть выполняется до и после каждого шага:
(A
A
A
A
Ak: 0
≤ k < L : a k
< x) & (A
A
A
A
Ak: R < k < N : a k
> x)
откуда выводим для цикла такое постусловие:
((L > R) OR (a m
= x)) & (A
A
A
A
Ak: 0
≤ k < L : a k
< x ) & (A
A
A
A
Ak: R < k < N : a k
> x)
Из него следует, что
((L > R) & (A
A
A
A
Ak: 0
≤ k < N : a k
≠ x)) OR (a m
= x)
Выбор m
, очевидно, произволен в том смысле, что правильность алгоритма от него не зависит. Но от него зависит эффективность алгоритма. Ясно, что на каждом шаге нужно исключать из дальнейшего поиска как можно больше эле%
ментов независимо от результата сравнения. Оптимальное решение – выбрать средний элемент, так как здесь в любом случае из поиска исключается половина отрезка. Получается, что максимальное число шагов равно log
2
N
, округленное до ближайшего целого. Поэтому данный алгоритм представляет собой ради%
кальное улучшение по сравнению с линейным поиском, где среднее число срав%
нений равно
N/2
Как уже упоминалось, можно заняться устранением дублирования инструк%
ции присваивания m
. Однако такая оптимизация на уровне кода является преждевременной в том смысле, что сначала лучше попытаться оптимизировать алгоритм на уровне логики задачи. Здесь это действительно возможно: ввиду сходства алгоритма с алгоритмом линейного поиска естественно искать решение с более простым условием окончания, то есть без второго операнда конъюнкции в охране цикла. Для этого нужно отказаться от наивного желания закончить поиск сразу после нахождения искомого значения. На первый взгляд это неразумно, но при ближайшем рассмотрении оказывается, что выигрыш в эффективности на каждом шаге больше, чем потери из%за небольшого числа дополнительных срав%
нений. Напомним, что число шагов не превышает log N
Более быстрое решение основано на следующем инварианте:
(A
A
A
A
Ak: 0
≤ k < L : a k
< x) & (A
A
A
A
Ak: R
≤ k < N : a k
≥ x)
а поиск продолжается, пока два отрезка не будут покрывать весь массив:
L := 0; R := N;
(* ADruS18_ *)
WHILE L < R DO
m := (L+R) DIV 2;
IF a[m] < x THEN L := m+1 ELSE R := m END
END
Можно сказать, что теперь ищется не элемент a[m] = x
, а граница, отделяющая все элементы, меньшие x
, от всех прочих.
Условие окончания –
L
≥
R
. Есть ли гарантия его достижения? Чтобы убедить%
ся в этом, нужно показать, что в любых обстоятельствах разность
R–L
умень%
шается на каждом шаге. Условие
L < R
справедливо в начале каждого шага. Тогда
53
среднее арифметическое удовлетворяет условию
L
≤ m < R
. Поэтому разность действительно уменьшается благодаря либо присваиванию значения m+1
пере%
менной
L
(что увеличивает
L
), либо значению m
переменной
R
(что уменьшает
R
),
и цикл прекращается при
L = R
Однако выполнение инварианта вместе с условием
L = R
еще не гарантирует успеха поиска. Разумеется, если
R = N
, то искомого значения в массиве нет. В про%
тивном случае нужно учесть, что элемент a[R]
еще не сравнивался. Поэтому нужна дополнительная проверка равенства a[R] = x
. В
отличие от первого решения, дан%
ный алгоритм – как и линейный поиск – находит искомое значение в позиции с наименьшим индексом.
1.8.3. Поиск в таблицеПоиск в массиве иногда называют
поиском в таблице, особенно если ключи сами являются составными объектами, такими как массивы чисел или литер. После%
дний случай встречается часто; массивы литер называют
цепочками литер(string), или
словами. Определим тип
String так:
String = ARRAY M OF CHAR
и пусть отношение порядка для цепочек определено так, что для цепочек x
и y
:
(x = y)
≡ (A
A
A
A
Aj: 0
≤ j < M : x j
= y j
)
(x < y)
≡ EEEEEi: 0 ≤ i < N : ((A
A
A
A
Aj: 0
≤ j < i : x j
= y j
) & (x i
< y i
))
Очевидно, равенство цепочек эквивалентно равенству всех литер. В сущности,
достаточно искать пару неравных литер. Отсутствие такой пары означает равен%
ство цепочек. Будем предполагать, что длина слов достаточно мала, скажем мень%
ше 30, и будем использовать линейный поиск.
В большинстве приложений нужно считать, что цепочки литер имеют переменную длину. Это достигается тем, что с каждой цепочкой литер ассоции%
руется ее длина. Учитывая данное выше определение типа, эта длина не должна превышать максимального значения
M
. Такая схема оставляет достаточно гибкос%
ти для многих задач, избегая при этом сложностей динамического распределения памяти. Чаще всего используются два представления длины цепочек литер:
1. Длина задается неявно тем, что к концу цепочки литер приписывается так называемая
концевая литера, которая в других целях не используется.
Обычно для этой цели используют литеру
0X
,
не имеющую графического образа. (Для дальнейшего важно, что это
самая младшая литера во всем множестве литер.)
2. Длина хранится непосредственно в первом элементе массива, то есть цепоч%
ка литер s имеет вид s = s
0
, s
1
, s
2
, ... , s
N–1
где s
1
... s
N–1
суть фактические литеры цепочки, а s
0
= CHR(N)
. Преимуще%
ство этого способа – в том, что длина доступна непосредственно, а недоста%
Поиск
Фундаментальные структуры данных
54
ток – что максимальная длина ограничена размером множества литер, то есть в случае множества ASCII значением 256.
В дальнейшем мы придерживаемся первой схемы. Сравнение цепочек литер принимает вид i := 0;
WHILE (x[i] # 0X) & (x[i] = y[i]) DO i := i+1 END
Здесь концевая литера играет роль барьера, а инвариант цикла имеет вид
A
A
A
A
Aj: 0
≤ j < i : x j
= y j
≠ 0X,
и в результате выполняется следующее условие:
((x i
= 0X) OR (x i
≠ y i
)) & (Aj: 0
≤ j < i : x j
= y j
≠ 0X).
Отсюда следует совпадение цепочек x
и y
, если x
i
= y
i
; при этом x < y
, если x
i
< y i
Теперь мы готовы вернуться к поиску в таблицах. Здесь требуется «поиск в поиске», то есть поиск среди элементов таблицы, причем для каждого элемента таблицы нужна последовательность сравнений между компонентами массивов.
Например, пусть таблица
T
и аргумент поиска x
определены так:
T: ARRAY N OF String;
x: String
Предполагая, что
N
может быть большим и что таблица упорядочена по алфа%
виту, будем использовать поиск делением пополам. Используя построенные выше алгоритмы для поиска делением пополам и для сравнения строк, получаем следующий программный фрагмент:
i := –1;
(* ADruS183 *)
L := 0; R := N;
WHILE L < R DO
m := (L+R) DIV 2;
i := 0;
WHILE (x[i] # 0X) & (T[m,i] = x[i]) DO i := i+1 END;
IF T[m,i] < x[i] THEN L := m+1 ELSE R := m END
END;
IF R < N THEN
i := 0;
WHILE (x[i] # 0X) & (T[R,i] = x[i]) DO i := i+1 END
END
(* (R < N) & (T[R,i] = x[i]) *)
1.9. Поиск образца в тексте
(string search)
Часто встречается особый вид поиска – поиск образца в тексте. Он определяется следующим образом. Пусть даны массив s
из
N
элементов и массив p
из
M
элемен%
тов, где
0 < M < N
:
55
s: ARRAY N OF Item p: ARRAY M OF Item
Требуется найти первое вхождение p
в s
. Обычно элементы этих массивов
(
Item
) являются литерами; тогда s
можно считать текстом, а p
– образцом
(pattern) или словом, и тогда нужно найти первое вхождение слова в тексте. Это основная операция в любой системе обработки текстов, и для нее важно иметь эффективный алгоритм.
Особенность этой задачи – наличие двух массивов данных и необходимость их одновременного просмотра, причем координация движения индексов%бегунков,
с помощью которых осуществляются просмотры, определяется данными. Коррект%
ная реализация подобных «сплетенных» циклов упрощается, если выражать их, используя так называемый
цикл Дейкстры – многоветочный вариант цикла
WHILE
. Поскольку эта фундаментальная и мощная управляющая структура пред%
ставлена не во
всех языках программирования, ее описанию посвящено приложе%
ние C.
Мы последовательно рассмотрим три алгоритма: простой поиск, построенный самым наивным образом; алгоритм Кнута, Морриса и Пратта (КМП%алгоритм),
представляющий собой оптимизацию простого поиска; и, наконец, самый эффек%
тивный из трех алгоритм Бойера и Мура (БМ%алгоритм), основанный на пере%
смотре базовой идеи простого алгоритма.
1.9.1. Простой поиск образца в текстеПрежде чем думать об эффективности, опишем простейший алгоритм поиска.
Назовем его
простым поиском образца в тексте. Удобно иметь в виду рис. 1.9, на котором схематически показан образец p
длины
M
, сопоставляемый с текстом s
длины
N
в позиции i
. При этом индекс j
нумерует элементы образца, и элементу образца p[j]
сопоставляется элемент текста s[i+j]
Рис. 1.9. Образец длины
M, сопоставляемый с текстом s в позиции i
Предикат
R(i)
, описывающий полное совпадение образца с литерами текста в позиции i
, формулируется так:
R(i) = A
A
A
A
Ak: 0
≤ j < M : p j
= s i+j
Поиск образца в тексте (string search)
Фундаментальные структуры данных
56
Допустимые значения i
, в которых может реализоваться совпадение, – от
0
до
N–M
включительно. Вычисление условия
R
естественным образом сводится к пов%
торным сравнениям отдельных пар литер. Если применить теорему де Моргана к
R
, то окажется, что эти повторные сравнения должны представлять собой поиск на неравенство среди пар соответствующих литер текста и образца:
R(i) = (A
A
A
A
Aj: 0
≤ j < M : p j
= s i+j
) = (E
E
E
E
Ej: 0
≤ j < M : p j
≠ s i+j
)
Поэтому предикат
R(i)
легко реализуется в виде процедуры%функции, постро%
енной по схеме линейного поиска:
PROCEDURE R (i: INTEGER): BOOLEAN;
VAR j: INTEGER;
BEGIN
(* 0 <= i < N *)
j := 0;
WHILE (j < M) & (p[j] = s[i+j]) DO INC(j) END;
RETURN (j < M)
END R
Пусть искомым результатом будет значение индекса i
, указывающее на первое
вхождение образца в тексте s
. Тогда должно удовлетворяться условие
R(i)
. Но так как требуется найти именно первое вхождение образца, то условие
R(k)
должно быть ложным для всех k < i
. Обозначим это новое условие как
Q(i)
:
Q(i) = A
A
A
A
Ak: 0
≤ k < i : R(k)
Такая формулировка задачи сразу наводит на мысль построить программу по образцу линейного поиска (раздел 1.8.1):
i := 0;
(* ADruS191_ *)
WHILE (i <= N–M) & R(i) DO INC(i) END
Инвариантом этого цикла является предикат
Q(i)
, который выполняется как до инструкции
INC(i)
, так и – благодаря второму операнду охраны – после нее.
Достоинство этого алгоритма – легкость понимания логики благодаря чет%
кой развязке двух циклов поиска за счет упрятывания одного из них внутрь про%
цедуры%функции
R
. Однако это же свойство может обернуться и недостатком:
во%первых, дополнительный вызов процедуры на каждом шаге потенциально длинного цикла может оказаться слишком дорогостоящим для такой базовой операции, как поиск образца. Во%вторых, более совершенные алгоритмы, рас%
сматриваемые ниже, используют информацию, получаемую во внутреннем цик%
ле, для увеличения i
во внешнем цикле на величину, большую единицы, так что два цикла уже нельзя рассматривать как вполне независимые. Можно избавить%
ся от процедуры вычисления
R
, введя дополнительную логическую переменную для ее результата и вложив цикл из процедуры в тело основного цикла по i
. Од%
нако логика взаимодействия двух вложенных циклов через логическую пере%
менную теряет исходную прозрачность, что чревато ошибками при эволюции программы.
57
В подобных случаях удобно использовать так называемый цикл Дейкстры –
цикл
WHILE
с несколькими ветвями, каждая из которых имеет свою охрану (см.
приложение C). В данном случае две ветви будут соответствовать шагам по i
и j
соответственно. Вспомним рис. 1.9 и введем предикат
P(i, j)
, означающий совпаде%
ние первых j
литер образца с литерами текста, начиная с позиции i
:
P(i, j) = A
A
A
A
Ak: 0
≤ k < j : s i+k
= p k
Тогда
R(i) = P(i, M)
Рисунок 1.9 показывает, что текущее состояние процесса поиска характеризу%
ется значениями пары переменных i и j
. При этом инвариант (условие, которому удовлетворяет состояние поиска и к которому процесс должен возвращаться пос%
ле каждого шага при новых i или j
) можно выбрать так: в позициях до i
совпадений образца нет, а в позиции i
имеется частичное совпадение первых j
литер образца,
что формально записывается следующим образом:
Q(i) & P(i, j)
Очевидно, j = M
означает, что имеет место искомое вхождение образца в текст в позиции i
, а i > N – M
означает, что вхождений нет вообще.
Очевидно, для поиска достаточно пытаться увеличивать j
на 1, чтобы расши%
рить совпадающий сегмент, а если это невозможно, то продвинуть образец в но%
вую позицию, увеличив i
на
1
, и сбросить j
в нуль, чтобы начать с начала проверку совпадения образца в новой позиции:
i := 0; j := 0;
WHILE
v # DO
INC( j )
ELSIF
DO
INC( i ); j := 0
END;
Остается сосредоточиться на каждом из двух шагов по отдельности и аккурат%
но выписать условия, при которых каждый шаг имеет смысл, то есть сохраняет инвариант. Для первой ветки это условие (
i
≤
N–M) & (j < M) & (s i+j
= p j
)
,
гаранти%
рующее
P(i, j)
после увеличения j
. Для второй ветки последний операнд конъюн%
кции должен содержать неравенство вместо равенства, что влечет
R(i)
и гаранти%
рует
Q(i)
после увеличения i
. Учитывая, что охраны веток вычисляются в порядке их перечисления в тексте, можно опустить последний операнд конъюнкции во второй охране и получить окончательную программу:
i := 0; j := 0;
(* ADruS191_ *)
WHILE (i <= N–M) & (j < M) & (s[i+j] = p[j]) DO
INC( j )
ELSIF (i <= N–M) & (j < M) DO
INC( i ); j := 0
END;
Поcле цикла гарантировано условие, равное конъюнкции отрицаний всех ох%
ран, то есть (
i
>
N–M) OR (j >= M)
, причем из структуры шагов цикла дополнитель%
Поиск образца в тексте (string search)
Фундаментальные структуры данных
58
но следует, что два операнда не могут быть истинны одновременно, а j
не может превысить
M
. Тогда i
>
N–M
означает, что вхождений образца нет, а j = M
– что справедливо
Q(i) & P(i, M)
, то есть найдено искомое полное вхождение в позиции i
Анализ простого поиска в тексте. Этот алгоритм довольно эффективен,
если предполагать, что неравенство литер обнаруживается лишь после небольшо%
го
числа сравнений литер, то есть при небольших j
. Такое вполне вероятно, если мощность типа элементов велика. Для поиска в тексте с мощностью множества литер, равной 128, разумно предположить, что неравенство имеет место уже после проверки одной или двух литер. Тем не менее поведение в худшем случае вызыва%
ет тревогу. Например, рассмотрим текст, состоящий из
N–1
букв
A
, за которыми следует единственная буква
B
, и пусть образец состоит из
M–1
литер
A
, за которы%
ми следует одна
B
. Тогда нужно порядка
N*M
сравнений, чтобы обнаружить совпа%
дение в конце текста. К счастью, как мы увидим в дальнейшем, существуют мето%
ды, которые в этом худшем случае ведут себя гораздо лучше.
1.9.2. Алгоритм Кнута, Морриса и ПраттаОколо 1970 г. Кнут, Моррис и Пратт придумали алгоритм, который требует толь%
ко порядка
N
сравнений литер, причем даже в худшем случае [1.8]. Алгоритм ос%
нован на том наблюдении, что, всегда сдвигая образец по тексту только на едини%
цу, мы не используем полезную информацию, полученную в предыдущих сравнениях. Ведь после частичного совпадения начала образца с соответствую%
щими литерами в тексте мы фактически знаем пройденную часть текста и могли бы использовать заранее подготовленную информацию (полученную из анализа образца) для более быстрого продвижения по тексту. Следующий пример, в кото%
ром ищется слово Hooligan, иллюстрирует идею алгоритма. Подчеркнуты лите%
ры, которые уже сравнивались. Каждый раз, когда сравниваемые литеры оказыва%
ются не равны, образец сдвигается на весь уже пройденный путь, так как полное совпадение с образцом заведомо невозможно для слова Hooligan при меньшем сдвиге:
Hoola–Hoola girls like Hooligans.
Hooligan
Hooligan
Hooligan
Hooligan
Hooligan
Hooligan
Hooligan
Здесь, в отличие от простого алгоритма, точка сравнения (позиция очередного элемента в тексте, сравниваемого с некоторым элементом образца) никогда не сдвигается назад. Именно эту точку сравнения (а не позицию первого элемента образца) будем теперь хранить в переменной i
; переменная j
, как и раньше, будет указывать на соответствующий элемент образца (см. рис. 1.10).
59
Центральным пунктом алгоритма является сравнение элементов s[i]
и p[j]
, при равенстве i и
j одновременно сдвигаются вправо на единицу, а в случае неравен%
ства должен быть сдвинут образец, что выражается присваиванием j
некоторого меньшего значения
D
. Граничный случай j = 0
показывает, что нужно предусмо%
треть возможность сдвига образца целиком за текущую позицию сравнения (что%
бы элемент p[0]
оказался выравнен с s[i+1]
). Для такого случая удобно положить
D = –1
. Главный цикл алгоритма приобретает следующий вид:
i := 0; j := 0;
WHILE (i < N) & (j < M) & ((j < 0) OR (s[i] = p[j])) DO
INC( i ); INC( j )
ELSIF (i < N) & (j < M) DO (* ((j >= 0) & (s[i] # p[j]) *)
j := D
END;
Эта формулировка не совсем полна, так как еще не определено значение сдви%
га
D
. Мы к этому вернемся чуть ниже, а пока отметим, что инвариант здесь берется как в предыдущей версии алгоритма; в новых обозначениях это
Q(i–j) & P(i–j, j)
Постусловие цикла, вычисленное как конъюнкция отрицаний охран, – это вы%
ражение
(j >= M) OR (i >= N)
, но реально могут реализоваться только равенства.
Если алгоритм останавливается при j = M
, то имеет место совпадение с образцом в позиции i–M
(член
P(i–j, j)
инварианта влечет
P(i–M, M) = R(i)
). В противном слу%
чае остановка происходит с i = N
, и так как здесь j < M
, то первый член инварианта,
Q(i–j)
, влечет отсутствие совпадений с образцом во всем тексте.
Нужно убедиться, что инвариант в алгоритме всегда сохраняется. Очевидно,
инвариант выполнен в начале цикла при значениях i = j = 0
. Не нарушается он и в первой ветке цикла, то есть после выполнения двух операторов, увеличивающих i
и j
на 1. В самом деле,
Q(i–j)
не нарушается, так как разность i–j не меняется.
Не нарушается и
P(i–j, j)
при увеличении j благодаря равенству в охране ветки (ср.
определение
P
). Что касается второй ветки, то мы просто потребуем, чтобы значе%
ние
D
всегда было таким, чтобы замена j
на
D
сохраняла инвариант.
Присваивание j := D при условии
D < j означает сдвиг образца вправо на j–D
позиций. Хотелось бы сделать этот сдвиг как можно больше, то есть сделать
D
как можно меньше. Это иллюстрируется на рис. 1.11.
Рис. 1.10. В обозначениях алгоритма КМП
позиция в тексте первой литеры образца равна i–j
(а не i, как в простом алгоритме)
Поиск образца в тексте (string search)
Фундаментальные структуры данных
60
Если мы хотим, чтобы инвариант
P(i–j, j) & Q(i–j)
выполнялся после присваива%
ния j := D
, то до присваивания должно выполняться условие
P(i–D, D) & Q(i–D)
Это предусловие и будет ключом к поиску подходящего выражения для
D наряду с условием
P(i–j, j) & Q(i–j)
, которое предполагается уже выполненным перед при%
сваиванием (к этой точке программы относятся все дальнейшие рассуждения).
Решающее наблюдение состоит в том, что истинность
P(i–j, j)
означает p
0
... p j–1
= s i–j
... s i–1
(ведь мы только что просмотрели первые j
литер образца и установили их совпа%
дение с соответствующими литерами текста). Поэтому условие
P(i–D, D)
при
D
< j
,
то есть p
0
... p
D–1
= s i–D
... s i–1
превращается в уравнение для
D
:
p
0
... p
D–1
= p j–D
... p j–1
Что касается
Q(i–D)
, то это условие следует из
Q(i–j)
, если
R(i–k)
для k = D+1 ... j
. При этом истинность
R(i–k)
для j = k гарантируется неравенством s[i] # p[j]
. Хотя условия
R(i–k)
≡
P(i–k, M) для k = D+1 ... j–1
нельзя полностью вычислить, используя только уже прочитанный фрагмент текста, но зато можно вычислить достаточные условия
P(i–k,k)
. Раскрывая их с учетом уже найденных равенств между элементами s
и p
, получаем следующее условие:
p
0
... p k–1
≠
p j–k
... p j–1
для всех k = D+1 ... j–1
То есть
D
должно быть максимальным решением вышеприведенного уравнения.
Рисунок 1.12 показывает, как работает этот механизм сдвигов.
Если решения для
D
нет, то совпадение с образцом невозможно ни в какой по%
зиции ниже i+1
. Тогда полагаем
D := –1
. Такая ситуация показана в верхнем при%
мере на рис. 1.13.
Последний пример на рис. 1.12 подсказывает, что алгоритм можно еще чуть%
чуть улучшить: если бы литера p
j была равна
A
вместо
F
, то мы знали бы, что соот%
ветствующая литера в тексте никак не может быть равна
A
, и сразу в следующей итерации цикла пришлось бы выполнить сдвиг образца с
D = –1
(ср. нижнюю часть рис. 1.13). Поэтому при поиске
D
можно сразу наложить дополнительное ограничение p
D
≠
p j
. Это позволяет в полной мере использовать информацию из неравенства в охране данной ветки цикла.
Рис. 1.11. Присваивание j := D сдвигает образец на j–D позиций
61
Рис. 1.12. Частичные совпадения образца и вычисление
D
Рис. 1.13. Сдвиг образца за позицию последней литеры
Поиск образца в тексте (string search)
Фундаментальные структуры данных
62
Важный итог состоит в том, что значение
D
определяется только образцом и значением j
, но не зависит от текста. Обозначим
D
для заданного j
как d
j
. Таблицу d
можно построить до начала собственно поиска, что можно назвать предкомпи%
ляцией образца. Очевидно, такие накладные расходы оправдаются, только если текст значительно длиннее образца (
M << N
). Если нужно найти несколько вхож%
дений одного и того же образца, то таблицу d
можно использовать повторно.
Величина d
j
< j является длиной максимальной последовательности, удовлет%
воряющей условию p
0
... p d[j]–1
= p j–d[j]
... p j–1
с дополнительным ограничением p
d[j]
≠
p j
. Проход построенного цикла по самому образцу p
вместо s
последовательно находит максимальные последовательности,
что позволяет вычислить d
j
:
PROCEDURE Search (VAR p, s: ARRAY OF CHAR; M, N: INTEGER; VAR r: INTEGER);
(* ADruS192_ *)
(* p M s N; M <= Mmax*)
(* p , r # s, r = –1*)
VAR i, j, k: INTEGER;
d: ARRAY Mmax OF INTEGER;
BEGIN
(* d p*)
d[0] := –1;
IF p[0] # p[1] THEN d[1] := 0 ELSE d[1] := –1 END;
j := 1; k := 0;
WHILE (j < M–1) & (k >= 0) & (p[j] # p[k]) DO
k := d[k]
ELSIF j < M–1 DO (* (k < 0) OR (p[j] = p[k]) *)
INC( j ); INC( k );
IF p[j] # p[k] THEN d[j] := k ELSE d[j] := d[k] END; ASSERT( d[j] = D(j) );
END;
(* *)
i := 0; j := 0;
WHILE (j < M) & (i < N) & (j >= 0) & (s[i] # p[j]) DO
j := d[j];
ELSIF (j < M) & (i < N) DO
INC(i); INC(j);
END;
IF j = M THEN r := i–M ELSE r := –1 END
END Search
Анализ КМПалгоритма. Точный анализ эффективности КМП%алгоритма,
как и сам алгоритм, весьма непрост. В работе [1.8] его изобретатели доказали, что число сравнений литер имеет порядок
M+N
, что гораздо лучше, чем
M*N
в простом поиске. Они также указали на то приятное обстоятельство, что указатель i
всегда движется по тексту только вперед, тогда как в простом поиске просмотр текста всегда начинается с первой литеры образца после обнаружения неравенства ли%
тер, и поэтому уже просмотренные литеры могут просматриваться снова. Это мо%
жет привести к трудностям, если текст считывается из внешней памяти, так как
63
в таких случаях обратный ход по тексту может дорого обойтись. Даже если вход%
ные данные буферизуются, образец может оказаться таким, что потребуется воз%
врат за пределы буфера.
1.9.3. Алгоритм Бойера и Мура
Хитроумная схема КМП%алгоритма дает выигрыш, только если несовпадение об%
наруживается после частичного совпадения некоторого фрагмента. Только в та%
ком случае происходит сдвиг образца более чем на одну позицию. Увы, это скорее исключение, чем правило: совпадения встречаются реже, чем несовпадения. По%
этому выигрыш от использования КМП%стратегии оказывается не слишком су%
щественным в большинстве случаев обычного поиска в текстах. Метод, который мы теперь обсудим, улучшает поведение не только в наихудшем случае, но и в среднем. Он был изобретен около 1975 г. Бойером и Муром [1.9], и мы будем называть его БМ алгоритмом. Мы представим его упрощенную версию.
БМ%алгоритм основан на несколько неожиданной идее – начать сравнение ли%
тер не с начала, а с конца образца. Как и в КМП%алгоритме, до начала собственно поиска для образца предкомпилируется таблица d
. Для каждой литеры x
из всего множества литер обозначим как d
x расстояние от конца образца до ее самого пра%
вого вхождения. Теперь предположим, что обнаружено несовпадение между тек%
стом и образцом. Тогда образец можно сразу сдвигать вправо на d
p[M–1]
позиций,
и весьма вероятно, что эта величина окажется больше, чем 1. Если p
M–1
вообще не встречается в образце, сдвиг еще больше и равен длине всего образца. Следующий пример иллюстрирует такую процедуру:
Hoola–Hoola girls like Hooligans.
Hooligan
Hooligan
Hooligan
Hooligan
Hooligan
Так как литеры теперь сравниваются справа налево, то будет удобнее исполь%
зовать следующие слегка модифицированные версии предикатов
P
,
R
и
Q
:
P(i, j) = A
A
A
A
Ak: j
≤ k < M : s i–M+k
= p k
R(i)
= P(i, 0)
Q(i)
= A
A
A
A
Ak: M
≤ k < i : R(k)
В этих терминах инвариант цикла будет иметь прежний вид:
Q(i) & P(i, j)
. Мы еще введем переменную k = i–M+j.
Теперь можно дать следующую формулировку
БМ%алгоритма:
i := M; j := M; k := i;
WHILE (j > 0) & (i <= N) & (s[k–1] = p[j–1]) DO
DEC(k); DEC(j)
ELSIF (j > 0) & (i <= N) DO
i := i + d[ORD(s[i–1])]; j := M; k := i;
END
Поиск образца в тексте (string search)
Фундаментальные структуры данных
64
Индексы удовлетворяют ограничениям
0
≤
j
≤
M, M
≤
i, 0 < k
≤
i
. Остановка алгоритма с j = 0
влечет
P(i, 0) = R(i)
, то есть совпадение в позиции k = i–M
. Для остановки c j > 0
нужно, чтобы i > N
; тогда
Q(i)
влечет
Q(N)
и, следовательно, от%
сутствие совпадений. Разумеется, нам еще нужно убедиться, что
Q(i)
и
P(i, j)
действительно являются инвариантами двух циклов. Они очевидным образом удовлетворены в начале цикла, поскольку
Q(M)
и
P(x, M)
всегда истинны.
Сначала рассмотрим первую ветку. Одновременное уменьшение k
и j
никак не влияет на
Q(i)
, и, следовательно, поскольку уже установлено, что s
k–1
= p j–1
, а
P(i, j)
выполняется до операции уменьшения j
, то
P(i, j)
выполняется и после нее.
Во второй ветке достаточно показать, что присваивание i := i + d s[i–1]
не нару%
шает инвариант
Q(i)
, так как после остальных присваиваний
P(i, j) выполняется автоматически.
Q(i) выполняется после изменения i, если до него выполняется
Q(i+d s[i–1]
)
. Поскольку мы знаем, что выполняется
Q(i)
, достаточно установить, что
R(i+h)
для h = 1 .. d s[i–1]
–1
. Вспомним, что величина d
x определена как расстояние от конца до крайнего правого вхождения x
в образце. Формально это выражается в виде:
A
A
A
A
Ak: M–d x
≤ k < M–1 : p k
≠ x
Для x = s i–1
получаем
A
A
A
A
Ak: M–d s[i–1]
k < M–1 : s i–1
≠ p k
= A
A
A
A
Ah: 1
≤ h ≤ d s[i–1]
–1 : s i–1
≠ p
M–1–h
⇒ A
A
A
A
Ah: 1
≤ h ≤ d s[i–1]
–1 : R(i+h)
В следующей программе рассмотренная упрощенная стратегия Бойера–Мура оформлена подобно предыдущей программе, реализующей КМП%алгоритм:
PROCEDURE Search (VAR s, p: ARRAY OF CHAR; M, N: INTEGER; VAR r: INTEGER);
(* ADruS193_ *)
(* p M s N*)
(* p , r # s, r = –1*)
VAR i, j, k: INTEGER;
d: ARRAY 128 OF INTEGER;
BEGIN
FOR i := 0 TO 127 DO d[i] := M END;
FOR j := 0 TO M–2 DO d[ORD(p[j])] := M–j–1 END;
i := M; j := M; k := i;
WHILE (j > 0) & (i <= N) & (s[k–1] = p[j–1]) DO
DEC(k); DEC(j)
ELSIF (j > 0) & (i <= N) DO
i := i + d[ORD(s[i–1])]; j := M; k := i;
END;
IF j <= 0 THEN r := k ELSE r := –1 END
END Search
Анализ алгоритма Бойера и Мура. В оригинальной публикации этого алго%
ритма [1.9] детально изучена и его производительность. Замечательно то, что он всегда требует существенно меньше, чем
N
, сравнений, за исключением специ%
65
ально построенных примеров. В самом удачном случае, когда последняя литера образца всегда падает на неравную ей литеру текста, число сравнений равно
N/M
Авторы предложили несколько возможных путей дальнейшего улучшения алгоритма. Один состоит в том, чтобы скомбинировать описанную стратегию, ко%
торая обеспечивает большие шаги сдвига для случаев несовпадения, со стратеги%
ей Кнута, Морриса и Пратта, которая допускает большие сдвиги после (частично%
го) совпадения. Такой метод потребует предварительного вычисления двух таблиц – по одной для БМ%алгоритма и для КМП%алгоритма. И тогда можно брать больший из сдвигов, полученных двумя способами, так как оба гарантиру%
ют, что меньшие сдвиги не могут дать совпадения. Мы воздержимся от обсужде%
ния деталей, так как дополнительная сложность вычисления таблиц и самого по%
иска, по%видимому, не приводит к существенному выигрышу в эффективности.
Зато при этом увеличиваются накладные расходы, так что непонятно, является ли столь изощренное усовершенствование улучшением или ухудшением.
Замечание переводчика. Три алгоритма поиска образца в тексте – простой,
КМП и БМ – иллюстрируют одну закономерность, которую важно понимать любому проектировщику. В простом алгоритме инстинктивно реализуется дебютная идея, что проверку совпадения литер образца с литерами текста надо производить в том же направлении, в котором продвигается по тексту образец.
КМП%алгоритм, унаследовав эту идею, не осознавая этого факта, оптимизирует ее добавлением изощренной «заплатки» – механизма продвижения образца на более чем одну позицию с учетом уже просмотренных литер. Зато построение
БМ%алгоритма начинается с критического пересмотра самой дебютной идеи простого алгоритма: ведь сравнение литер образца в порядке движения образца по тексту обусловлено, в сущности, лишь инерцией мышления. При этом и уско%
ряющая «заплатка» здесь оказывается несравненно проще (ср. вычисление вспомогательных таблиц d в двух программах), и итоговый алгоритм суще%
ственно быстрее, и его математический анализ сильно облегчается. Это общая закономерность: первый импульс к конкретной деятельности, который про%
граммист ощущает, заметив какой%нибудь «очевидный» способ решения (когда,
что называется, «руки чешутся» начать писать код), способен помешать увидеть путь к наилучшему решению. Поэтому нужны специальные усилия, требующие дисциплины, для «пристального разглядывания» проблемы, чтобы выявить не%
явные, инстинктивные предположения – еще до первых попыток составить кон%
кретное решение, когда внимание уже будет поглощено не исходной задачей,
а красотой и
эффективностью предполагаемого решения, ярко демонстрирую%
щего остроумие и изобретательность программиста, а также его познания в ме%
тодах оптимизации.
Упражнения1.1. Обозначим мощности стандартных типов
INTEGER
,
REAL
и
CHAR
как c
int
, c
real и
c char
. Каковы мощности следующих типов данных, определенных в этой главе в качестве примеров:
Complex
,
Date
,
Person
,
Row
,
Card
,
Name
?
Упражнения
Фундаментальные структуры данных
66 1.2. Какие последовательности машинных инструкций (на вашем компьютере)
соответствуют следующим операциям:
a) чтение и запись для элементов упакованных записей и массивов;
b) операции для множеств, включая проверку принадлежности числа мно%
жеству?
1.3. Каковы могут быть аргументы в пользу определения некоторых наборов дан%
ных в виде последовательностей, а не массивов?
1.4. Пусть дано ежедневное железнодорожное расписание для поездов на нескольких линиях. Найдите такое представление этих данных в виде масси%
вов, записей или последовательностей, которое было бы удобно для опреде%
ления времени прибытия и отправления для заданных станции и направле%
ния поезда.
1.5. Пусть даны текст
T
, представленный последовательностью, а также списки небольшого числа слов в виде двух массивов
A
и
B
. Предположим, что слова являются короткими массивами литер небольшой фиксированной макси%
мальной длины. Напишите программу, преобразующую текст
T
в текст
S
за%
меной каждого вхождения слова
A
i соответствующим словом
B
i
1.6. Сравните следующие три варианта поиска делением пополам с тем, который был дан в основном тексте. Какие из трех программ правильны? Определите соответствующие инварианты. Какие варианты более эффективны? Предпо%
лагается, что определены константа
N > 0
и следующие переменные:
VAR i, j, k, x: INTEGER;
a: ARRAY N OF INTEGER;
Программа A:
i := 0; j := N–1;
REPEAT
k := (i+j) DIV 2;
IF a[k] < x THEN i := k ELSE j := k END
UNTIL (a[k] = x) OR (i > j)
Программа B:
i := 0; j := N–1;
REPEAT
k := (i+j) DIV 2;
IF x < a[k] THEN j := k–1 END;
IF a[k] < x THEN i := k+1 END
UNTIL i > j
Программа C:
i := 0; j := N–1;
REPEAT
k := (i+j) DIV 2;
IF x < a[k] THEN j := k ELSE i := k+1 END
UNTIL i > j
67
Подсказка. Все программы должны заканчиваться с a
k
= x
, если такой эле%
мент присутствует, или a
k
≠ x
, если элемента со значением x нет.
1.7. Некая компания проводит опрос, чтобы определить, насколько популярна ее продукция – записи эстрадных песен, а самые популярные песни должны быть объявлены в хит%параде. Опрашиваемую выборку покупателей нужно разделить на четыре группы в соответствии с полом и возрастом (скажем, не старше 20 и старше 20). Каждого покупателя просят назвать пять любимых пе%
сен. Песни нумеруются числами от
1
до
N
(пусть
N = 30
). Результаты опроса нужно подходящим образом закодировать в виде последовательности литер.
Подсказка: Используйте процедуры
Read и
ReadInt для чтения данных опроса.
TYPE hit = INTEGER;
reponse = RECORD name, firstname: Name;
male: BOOLEAN;
age: INTEGER;
choice: ARRAY 5 OF hit
END;
VAR poll: Files.File
Этот файл содержит входные данные для программы, вычисляющей следую%
щие результаты:
1. Список A песен в порядке популярности. Каждая запись списка состоит из номера песни и количества ее упоминаний в опросе. Ни разу не названные песни в список не включаются.
2. Четыре разных списка с фамилиями и именами всех респондентов, которые поставили на первое место один из трех самых популярных хитов в своей группе.
Перед каждым из пяти списков должен идти подходящий заголовок.
Литература
[1.1] Dahl O%.J., Dijkstra E. W., Hoare C. A. R. Structured Programming. F. Genuys,
Ed., New York, Academic Press, 1972 (имеется перевод: Дал У., Дейкстра Э.,
Хоор К. Структурное программирование. – М.: Мир, 1975).
[1.2] Hoare C. A. R., in Structured Programming [1.1]. Р. 83–174 (имеется перевод:
Хоор К. О структурной организации данных. В кн. [1.1]. С. 98–197.)
[1.3] Jensen K. and Wirth N. PASCAL – User Manual and Report. Springer%Verlag,
1974 (имеется перевод: Йенсен К., Вирт Н. Паскаль. Руководство для пользователя и описание языка. – М.: Финансы и статистика, 1988).
[1.4] Wirth N. Program development by stepwise refinement. Comm. ACM, 14, No. 4
(1971), 221–27.
[1.5] Wirth N. Programming in Modula%2. Springer%Verlag, 1982 (имеется перевод:
Вирт Н. Программирование на языке Модула%2. – М.: Мир, 1987).
Литература
Фундаментальные структуры данных
68
[1.6] Wirth N. On the composition of well%structured programs. Computing Surveys,
6, No. 4, (1974) 247–259.
[1.7] Hoare C. A. R. The Monitor: An operating systems structuring concept. Comm.
ACM, 17, 10 (Oct. 1974), 549–557.
[1.8] Knuth D. E., Morris J. H. and Pratt V. R. Fast pattern matching in strings. SIAM
J. Comput., 6, 2, (June 1977), 323–349.
[1.9] Boyer R. S. and Moore J. S. A fast string searching algorithm. Comm. ACM, 20,
10 (Oct. 1977), 762–772.
Скачать 2.67 Mb.