Поиск

1.5. Поиск в строке. Алгоритм Кнута, Морриса и Пратта

Приблизительно в 1970 г. Д. Кнут, Дж. Моррис и В. Пратт изобрели алгоритм (КМП-алгоритм), фактически требующий только N сравнений даже в самом плохом случае. Новый алгоритм основывается на том соображении, что, начиная каждый раз сравнение образа с самого начала, мы можем уничтожать ценную информацию. После частичного совпадения начальной части образа с соответствующими символами строки мы фактически знаем пройденную часть строки и можем "вычислить" некоторые сведения (на основе самого образа), с помощью которых потом быстро продвинемся по тексту. Приведенный пример поиска слова Hooligan показывает принцип работы такого алгоритма. Символы, подвергшиеся сравнению, здесь подчеркнуты. Обратите внимание: при каждом несовпадении двух символов образ сдвигается на все пройденное расстояние, поскольку меньшие сдвиги не могут привести к полному совпадению.
Hoola-Hoola girls like Hooligans.
Hooligan

Hooli

Hooligan

КМП - алгоритм записывается так :
i=0; j=0;
while ((j< М) && (i < N)) {
while ((i ≥ 0) && (s[i] != p[j])) j = D;
i++; j++;
};

Однако такая запись умышленно не совсем точная, поскоку в ней есть сдвиг на неопределенную величину D. Вскоре мы к ней вернемся, а теперь сначала отметим, что условия Q(i -j) и P(i –j,j) сохраняются как глобальные инварианты, и к ним можно добавить отношения 0 ≤i < N и 0 ≤ j < М. Это предполагает, что мы должны отказаться от соглашения, что i всегда отмечает в тексте текущее положение первого символа образа. Точнее, выравненное положение образа теперь i -j.

Если алгоритм заканчивает работу по причине j = М, то из составляющей
P(i - j,j) следует справедливость P(i - М, М), т.е. согласно Р(i,j)=A_k: 0≤k<j: s_i+k=p_k. совпадение начинается с позиции i - М. Если же работа окончена из-за i = N, то, поскольку, j < М, из инварианта Q(i) следует, что совпадения вообще нет.

Теперь мы должны показать, что алгоритм никогда не делает инвариант ложным. Видно, что вначале i =j = 0, и он истинен. Сначала исследуем эффект от двух операторов, увеличивающих i и j на единицу. Они, очевидно, не сдвигают образ вправо и не делают ложным Q(i - j), поскольку разность остается неиз¬менной. Но, может быть, они делают ложным Р(i - j, j) — вторую составляющую инварианта? Обращаем внимание, что в этой точке истинно отрицание выражения в заголовке внутреннего цикла, т. е. либо j < 0, либо s_i = р_j. Последнее увеличивает частичное совпадение и устанавливает P(i - j, j + 1), а первое также постулирует истинность P(i - j, j + 1). Следовательно, увеличение на единицу i и j не может также сделать ложным тот или другой инвариант. Но в алгоритме остается еще только присваивание j = D. Мы просто постулируем, что значение D всегда таково, что замена j на D оставляет инвариант справедливым.

Для того чтобы найти соответствующее выражение для D, мы должны вначале понять смысл этого присваивания. При условии что D < j, присваивание соответствует сдвигу образа вправо на j - D позиций. Естественно, мы хотим, чтобы сдвиг был настолько больше, насколько это возможно, т. е. D должно быть как можно мень¬ше.

Если инвариант P(i – j, j) & Q(i - j) после присваивания j значения D истинен, то перед ним должно быть истинно P(i - D,D) & Q(i - D). Это предусловие и будет поэтому нашим ориентиром при поиске подходящего выражения для D. Основное соображение: благодаря P(i - j, j ) мы знаем, что
S_i-j...S_i-1 =P₀...p_i-1
(мы только что просматривали первые j символов образа и убедились в их совпадении с текстом). Поэтому условие P( i - D, D) c D≤j, т.е.
p₀…p_D-1=s_i-D…s_i-1
превращается в
p₀…p_D-1=p_i-D…p_j-1 (1)
и предикат ~P(i -k,M) для k=1, ...,j - D (чтобы убедиться в инвариантности Q(i - D)) превращается в
р₀...р_k-1!=p_j-k…p_j-1 для всех k=1,…,J - D. (2)

Важный вывод: очевидно, что значение D определяется одним лишь образом и не зависит от строки текста. Условия 1 и 2 говорят, что для определения D мы должны для каждого j найти наименьшее D, т. е. самую длинную последовательность символов образа, непосредственно предшествующих позиции j, которая совпадает полностью с началом образа. Для каждого j такое D мы будем обозначать через d_j. Так как эти значения зависят только от образа, то перед началом фактического поиска можно вычислить вспомогательную таблицу d; эти вычисления сводятся к некоторой предтрансляции образа. Соответствующие усилия будут оправданными, если размер текста значительно превышает размер образа (М<<N). Если нужно искать многие вхождения одного и того же образа, то можно пользоваться одними и теми же d.