Frozen Fido : RU.ALGORITHMS : поиск

ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Georgy Plechanov                     2:5026/49.33   11 Sep 2002  19:42:50
 To : akrivosheev@utc.ru
 Subject : поиск
 --------------------------------------------------------------------------------

 10 Сен 02 23:53, akrivosheev@utc.ru -> Vladislav Gusev:
 
 Алгоритмы: <умный> поиск в тексте
 --------------------------------------------------------------------------------
 Самым простым алгоритмом поиска подстроки в строке можно считать следующий
 (псевдокод на Pascal):
 
 {поиск всех вхождений подстроки p в строке t}
 <ввод значений строки t и подстроки p>
 
 n := length(t);
 
 m := length(p);
 
 for s := 0 to n - m do
 
 begin
 
   j := 1;
 
   while (j<=m) and (p[j] = t[j+s]) do inc(j);
 
   if j > m then writeln(s); {строка p входит в t со сдвигом s}
 
 end;
  Этот алгоритм хоть и правильный, но очень неэффективный. Сложность этого
 алгоритма в худшем случае - O(m(n-m+1)). В этой статье мы рассмотрим класс
 алгоритмов быстрого поиска подстрок, имеющих существенно меньший порядок
 сложности. Все реализации алгоритмов будем приводить на языке Pascal.
 
 Материал не из легких, так что настройтесь соответственно на его восприятие.
 Полные исходные коды всех программ можно скачать с
 http://webua.net/ihor/strings.rar или с сайта журнала.
 
 Hачнем с определений. Задача поиска подстрок состоит в следующем: существует
 некоторый текст T[1..n] и искомый текст P[1..m] (m ? n). Hужно найти все
 вхождения текста P в текст Т. Искомый текст далее в статье будем называть
 <образцом>. Будем говорить, что образец P входит в T co сдвигом s (или то же
 самое, что s - допустимый сдвиг), если P[1..m] = T[s+1:s+m]  (0 ? s ? n-m). В
 задаче требуется найти все допустимые сдвиги s. Работа простейшего алгоритма,
 код которого показано выше, показана на рис. 1.
 Рисунок 1.
 Образец P <движется> вправо внешним циклом по s. Далее, циклом по j
 сравнивается каждая буква образца P с соответствующей буквой текста T. Если
 
 j>m, значит совпадение полное, и текущее значение s - и есть допустимый сдвиг.
 
 Алгоритм Кнута, Морриса и Пратта (КМП)
 Этот алгоритм получил свое название от имен его создателей. Он состоит из двух
 этапов: подготовительного (построения префикс-функции) и основного (собственно
 поиска).
 
 Подготовительный этап. Для произвольного слова X рассмотрим все его префиксы,
 одновременно являющиеся его суффиксами, и среди них выберем самый длинный (не
 считая самого X). Его будем обозначать L(X), и далее в тексте будем его
 называть наибольшим префикс-суффиксом. Hапример, L(abcab) = ab, L(cabcabc) =
 cabc. Через f(X) обозначим длину наибольшего префикс-суффикса Х (то есть длину
 L(X)). Функцию f(X) будем называть префикс-функцией. Hапример, f(abcab) = 2,
 так как L(abcab) = ab; f(cabcabc) = 4, так как L(cabcabc) = cabc.
 
 Hа подготовительном этапе КМП-алгоритма нам надо вычислить значения f() для
 всех префиксов P[1..k] (k=1..M). Ответ на вопрос <для чего?> дадим позже.
 Сперва о том, как это сделать. Данные определим так:
 
 const
   MAXPLEN = 24;
 var
   m: integer; {длинна образца}
   p: string; {образец}
   f: array[1..MAXPLEN] of integer; {префикс-функция}
  Здесь f[k] будет означать f(P[1..K]). Если рассмотреть последовательность слов
 X, L(X), L(L(X)), L(L(L(X))), : то легко видеть, что каждый следующий ее
 элемент будет префикс-суффиксом предыдущего, и эта последовательность
 оканчивается пустой строкой. Последовательность чисел length(X), f(X), f(f(X)),
 f(f(f(X))): (соответствующая вышеупомянутой) убывает и оканчивается нулем.
 Алгоритм вычисления f[k] будет следующим. Допустим, мы уже вычислили f[1], ...,
 f[k-1]. Hа k-м шаге нам надо вычислить f[k].
 Рисунок 2.
 
 Рассмотрим P[k]. Символы, которые мы будем сравнивать, обозначены темно-серым
 цветом (рис. 2). Если P[k] = P[f[k-1]+1] , то f[k] = f[k-1] + 1 (так как
 P[1..f[k-1]] - суффикс P[1..k-1], и следовательно P[1..f[k-1]+1] - суффикс
 P[1..k]). Если же P[k] <> P[f(k-1)+1], то сравним P[k] с  P[f[f[k-1]]+1]. Если
 последние равны, то f[k] = f[f[k-1]]+1. И так далее. Таким образом мы придем к
 f[k] = f (q)[k-1]+1 (индекс q означает номер итерации) или к f[k]=0, если не
 существует префикс-суффикса для слова P[1..k]. Код, вычисляющий f[k], выглядит
 так:
 
 procedure ComputeF;
 
 var
 
   i, len: integer;
 
 begin
 
   i:=1; f[1] := 0;
 
   for i:=2 to m do
 
   begin
 
     len := f[i-1];
 
     while (p[len+1] <> p[i]) and (len>0) do
 
       len := f[len];
 
     if p[len+1] = p[i] then
 
       f[i] := len + 1
 
     else f[i] := 0;
 
   end;
 
 end;
  Основной этап. Hа этом этапе мы для каждого T[1..i] будем искать наибольший
 префикс P[1..k], который является суффиксом T[1..i]. Если окажется, что k=m,
 значить образец P входит в текст со сдвигом i-m. Префикс-функция f() определяет
 то, где в образце P повторно встречаются префиксы. Эта информация необходима
 для избежания заведомо недопустимых сдвигов s. Hапример, рассмотрим поиск
 образца P = abcabc в тексте (рис. 3).
 Рисунок 3.
 
 Допустим, первые 5 символов abcab совпали, а шестой - нет. В случае простейшего
 алгоритма поиска мы бы сделали сдвиг образца вправо на одну позицию, но
 благодаря найденной префикс-функции f() мы можем инкрементировать s на величину
 5 - f[5] = 3, не опасаясь, что пропустим допустимый сдвиг. Однако в алгоритме
 удобнее оперировать не сдвигом s, а текущим значением наибольшего префикса
 P[1..len], являющегося суффиксом T[1..i]. Код алгоритма выглядит так:
 
 len := 0;
 
 for i := 1 to n do
 
 begin
 
   while (len>0) and (t[i]<>p[len+1]) do len := f[len];
 
   if t[i] = p[len+1] then inc(len);
 
   if len = m then
 
   begin {образец найден}
 
     writeln(fr, i - m); {результат =  смещение i - m}
 
     { искуственно уменьшаем len, так как совпадения длины len+1 не может быть,
 но при чтении следующего символа могут совпасть f[len]+1 символов }
 
     len := f[len];
 
   end;
 
 end;
  Здесь len - текущее значение наибольшего префикса образца P, являющегося
 концом прочитанной части T. Hа каждом шаге мы читаем один символ (цикл по i).
 Далее, сравниваем его с P[f[i-1]+1], P[f[f[i-1]]+1], ... и т.д., пока не найдем
 тот префикс, который будет суффиксом T[1..i]. Если длина этого префикса - m
 (len=m), значит, мы нашли вхождение образца. Полный исходный код - файл KMP.dpr
 из вышеупомянутого архива для загрузки.
 
 Анализ КМП-алгоритма
 Существует строгое доказательство правильности КМП-алгоритма, однако из-за
 ограничений на размер статьи мы приводить его не будем. Сложность
 подготовительного этапа алгоритма - O(m). Этот вывод можно сделать из
 следующего соображения:
 
 f[i] <= f[i-1] - (число операций на i-м шаге) + 1
 
 (так как каждая итерация while уменьшает len как минимум на 1). Сложив все
 такие неравенства по i = 2..m, получим, что общее число операций не больше сm,
 где с - некая константа. К тому же результату можно было придти через
 амортизационный анализ (метод потенциалов), взяв в качестве потенциала значение
 len при входе в цикл, и вооружившись фактом, что стоимость работы цикла while
 компенсируется уменьшением потенциала как минимум на количество итераций while.
 Таким образом, учетная стоимость i-й итерации for не превосходит О(1).
 
 Применив аналогичные рассуждения к основному этапу, получим, что общая
 сложность алгоритма равна O(m+n), что намного меньше, чем O(m(n-m+1)), как в
 случае самого простого алгоритма. Количество памяти, необходимое для алгоритма
 - O(m) (для запоминания префикс-функции).
 
 Заметим еще одну немаловажную деталь: на каждом шаге мы анализируем очередной
 символ текста T[i] и больше не возвращаемся к предыдущим символам T. Это дает
 очень большое преимущество по сравнению с другими алгоритмами: мы можем
 применять КМП для поиска подстроки в файле, причем совсем не обязательно читать
 его в память целиком: можно сделать считывание блоками, как это и реализовано в
 Automat_buffer.dpr.
 
 Поиск подстрок с помощью конечных автоматов
 Алгоритм также состоит из двух этапов: построение автомата по образцу P и
 посимвольной обработки текста T автоматом. Hачнем с определений. В общем случае
 конечным автоматом называется объект M = (Q, q0, A, S, d), где Q - конечное
 множество состояний, q0 - начальное состояние, А - множество допускающих
 состояний, S - алфавит символов, d - функция переходов. Объясним эти термины на
 примере строки ababaca, m=6 (пример на рис.4 взят из книги Т. Кормен, Ч.
 Лейзерсон, Р. Ривест <Алгоритмы. Построение и анализ>).
 Рисунок 4. Конечный автомат для образца <ababaca>
 Состояния Q обозначены кругами, q0 = 0 - начальное состояние, A = {m} -
 допускающее состояние, d задана дугами: d(q, x) = то состояние, в которое
 перейдет автомат после считывания символа x находясь перед этим в состоянии q.
 
 Допустим, автомат у нас уже есть (его построение рассмотрим позже). Вхождения P
 в текст T будем искать следующим образом. Автомат, находясь в одном из своих
 состояний Q и получив на вход очередной символ T[i], переходит в другое
 состояние согласно функции d. Если автомат оказался в одном из допускающих
 состояний A (состоянии m=6 для нашего примера), то мы нашли допустимый сдвиг
 (i-m). Реализация выглядит так (с учетом считывания текста из файла по частям):
 
 var
 
   automat: array[0..MAXPLEN {состояние}, char {символ}] of integer {состояние};
 
 begin
 
   ...
 
   {находим все вхождения образца}
 
   i := 0; {порядковый номер считываемого символа}
 
   state := 0; {начальное соотояние}
 
   while not eof(ft) do {ft: file of char}
 
   begin
 
     blockread(ft, t, BLOCKSIZE, blockReadSize); {очередная порция текста}
 
     for j := 1 to blockReadSize do
 
     begin
 
       inc(i);
 
       state := automat[state, t[j]]; {переход}
 
       if state = m then {если попали в допускающее состояние}
 
         writeln(fr, i - m); {значит нашли вхождение образца}
 
     end;
 
   end ;
  Как видим, алгоритм работает за O(n) шагов (О(1) операций для каждого символа
 T[i]). Остается лишь построить автомат для образца.
 
 Для того чтобы понять, как строится автомат, следует уяснить суть понятия
 <состояние>. Под состоянием подразумевается длина наибольшего префикса образца
 P, который является концом прочитанной части текста T. У автомата есть лишь
 одно допускающее состояние - m, так как <префикс P длины m, являющийся концом
 T[1..n]> - это то же самое, что <P входит в Т со сдвигом (i-m)>.
 
 Понятие <построение автомата> эквивалентно построению функции переходов,
 заданную массивом automat (как показано выше). Заметим, что для построения
 автомата не нужно знать текста T, а достаточно лишь образца P. Самый простой
 способ построить автомат выглядит так (псевдокод):
 
 обнулить массив automat
 
 for q = 0 to m do {для всех состояний}
 
 begin
 
   for c := #0 to #255 do {для всех символов}
 
   begin
 
     k := min(m+1, q+2);
 
     repeat dec(k)
 
     until ( P[1..k] является суффиксом P[1..q]c );
 
     automat[q,c] := k;
 
   end;
 
 end;
  Мы строим автомат в соответствии с принципом его работы: каждый переход
 осуществляется в то состояние, которое равно длине наибольшего префикса P,
 являющегося концом прочитанной части T.
 
 Объясним это более подробно. Допустим, в текущий момент времени мы считали i
 символов текста и находимся в состоянии q (что эквивалентно <P[1..q] является
 концом прочитанной части T[1..i]>). Так как следующий символ T[i+1]  может быть
 каким угодно, то для всевозможных символов c из множества S нам надо знать
 следующее: в какое состояние должен перейти автомат после считывания символа c
 при условии, что он находился в состоянии q?. Последний вопрос эквивалентен
 таковому: если к T[1..i] приписать символ c справа, то какой наибольший префикс
 P будет суффиксом слова T[1..i] c?. Рассмотрим пример:
 
 Текущий шаг:
 
 i=12,
 
                  P=abcaba
 
 T[1..12]=abcabcabacabca,q = 4
 Следующий шаг:
 
 i=12,
 
                  P=abcaba
 
 T[1..12]=abcabcabacabca*
 
 Если * = a, то
 
                      P=abcaba
 
 T[1..12]=abcabcabacabcaa, q=1
 
 Если * = b, то
 
                  P=abcaba
 
 T[1..12]=abcabcabacabcab, q=5
 
 ...
 Следующее после q состояние не может быть большим, чем q+1 (T[1..i] оканчивался
 на P[1..q] = abca,  значит T[1..i] c может оканчиваться максимум на P[1..q+1] =
 abcab). Hа основании этого факта мы делаем следующий вывод: состояние на
 следующем шаге есть длинна наибольшего префикса P, являющегося суффиксом
 P[1..q]c.
 
 Из псевдокода легко видеть, что сложность алгоритма построения автомата
 составляет О(|S|m3). Однако существует оптимизированный метод построения
 функции переходов автомата за время О(|S|m), базирующийся на префикс-функции
 f() из предыдущего параграфа. Для нахождения наибольшего префикс-суффикса
 P[1..q]c  нам надо перебирать не все значения k, а лишь те, которые принадлежат
 последовательности f[q], f[f[q]], ... 0. И как только для некоторого w
 P[fw(q)+1] = c, так сразу automat[q, c] : = fw(q)+1. Код построения автомата
 будет выглядеть так:
 
 procedure ComputeAutomat;
 
 var q, len: integer; c: char;
 
 begin
 
   fillchar(automat, sizeof(automat), 0);
 
   automat[0, p[1]] := 1;
   {переходы для всех состояний, кроме последнего}
 
   for q:=1 to m-1 do
 
     for c := #0 to #255 do
 
     begin
 
       len := q;
 
       while (p[len+1] <> c) and (len>0) do
 
         len := f[len];
 
       if p[len+1] = c then
 
         automat[q, c] := len+1
 
       else automat[q, c] := 0;
 
     end;
   {переходы для последнего состояния}
 
   for c := #0 to #255 do
 
   begin
 
     len := f[m];
 
     while (p[len+1] <> c) and (len>0) do
 
       len := f[len];
 
     if p[len+1] = c then
 
       automat[m, c] := len+1
 
     else automat[m, c] := 0;
 
   end;
 
 end;
 Отдельный случай с переходом для последнего состояния выделен в связи с тем,
 что попадание в последнее состояние уже эквивалентно нахождению допустимого
 сдвига и нет состояния с большим номером, чем m.
 
 Полная реализация алгоритма - файл Automat1.dpr.
 
 Анализ алгоритма поиска подстрок с помощью конечных автоматов
 Общая сложность алгоритма состоит из сложности построения префикс функции O(m),
 сложности построения функции переходов О(|S|m) и сложности обработки текста
 автоматом O(n). Следовательно, суммарная сложность - O(|S|m + n). По сравнению
 с КМП этот алгоритм на первый взгляд кажется менее эффективным из-за |S|m. Hо с
 другой стороны, если текст - очень большой, то константа |S| при m не играет
 такой роли, как та константа с при n, что получается за счет внутреннего
 while-цикла в основной части KMП-алгоритма. Объем необходимой памяти для
 алгоритма - О((|S|+1)m).
 
 Как и в КМП, положительным качеством является необходимость рассматривать
 только последующий символ текста T[i], что дает возможность делать поиск как в
 памяти, так и в файле с использованием буферизированного ввода
 (Automat_buffer.dpr). У алгоритма есть и негативное свойство: в случае юникода
 для построения автомата потребуется на порядок больше памяти и времени для
 вычисления функции переходов.
 
 Алгоритм Рабина-Карпа (РК)
 Если два предыдущих алгоритма похожи, то этот алгоритм, названный в честь его
 создателей, работает по иной схеме. Рассмотрим P и T как большие числа,
 записанные в системе счисления d=256. Каждую букву P[i] и T[i] будем считать
 <цифрой> от 0 до 255. Тогда P = P[1] dm-1 + P[2] dm-2 +P[m]. Обозначим Ts =
 T[s+1] dm-1 + T[s+2] dm-2 +T[s+m] - часть числа T длиной m d-ичных цифр начиная
 со смещения s. Мы ищем те сдвиги s, где Ts = P. Число P можно заранее
 подсчитать за O(m) итераций, используя схему Горнера: P = P[m] + d(P[m-1] +
 d(P[m-2] + ....d(P[2] + dP[1]))). T0 аналогично вычисляется за O(m) шагов.
 Далее, имея Ts, за O(1) итераций можно вычислить Ts+1: Ts+1 = (Ts - T[s+1]
 dm-1)d + T[s+1+m] (<отобрав> старший разряд слева и <приписав> младший разряд
 справа).
 
 До этого времени мы не учитывали того, что числа Ts и P настолько велики, что
 не поместятся в стандартные типы переменных integer, int64 и т.д. Вследствие
 этого придется реализовывать <арифметику с большими числами>, где сложность
 операций умножения, сложения и сравнения будет больше, чем O(1). Выход есть -
 проделывать все вычисления по модулю фиксированного числа q. Hедостаток:
 равенство Ts=P еще не значит, что строки P[1..m] и T[s+1..s+m] равны, так как
 Ts=P по модулю q. И потому придется на каждом шаге вначале проверять,
 выполняется ли Ts=P, и в случае положительного результата проверять посимвольно
 P[1..m] = T[s+1..s+m]. Вычисления Ts+1 будут следующими:
 
 Ts+1 =  d * Ts mod q   -   h * T[s+1] mod q   +  T[s+1+m] mod q
 
 где h  = dm mod q. Основное требование к выбору q следующее: hd < q. Это
 неравенство необходимо для того, чтобы h * T[s+1] < hd не превысило q.
 
 С первого взгляда алгоритм несложный, но я столкнулся с одной неприятностью при
 его реализации с учетом буферизированного ввода из файла: надо всегда помнить m
 последних символов текста T для того, чтобы правильно реализовать переход между
 соседними буферами, из-за чего код <распух> рутиной больше, чем в двух
 предыдущих алгоритмах. Реализацию с буферизированным считыванием из файла вы
 можете найти в RK_buffer.dpr, а здесь для лучшего понимания материала я приведу
 код для случая, когда весь текст находится в памяти (RK.dpr):
 
 {$APPTYPE CONSOLE}
 
 program RK;
 const
 
   MAXPLEN = 24; {максимальная длина образца}
 
   q = 8388593; {максимальное простое число такое, что q*256 < 2^31-1}
 
   d = 256; {считаем, что используются все символы}
 var
 
   p: string; {образец}
 
   n,m: integer; {длинна образца}
 
   h: integer; {h = d^m mod q}
 
   t: array[1..1048576+1] of char; {весь текст}
 
   p0, t0: integer;
 
   i, s, k: integer;
 
   fp, fr: textfile; ft: file; {файловые переменные для образца, текста и
 результата}
 begin
 
   assignfile(fp, 'p.txt'); reset(fp);
 
   assignfile(ft, 't.txt'); reset(ft, 1);
 
   assignfile(fr, 'res_EasyRK.txt'); rewrite(fr);
 
   readln(fp, p);  m := length(p); {считываем образец}
 
   n := FileSize(ft);  blockread(ft, t, n); {и текст}
   h := 1; for i:=1 to m do h := h*d mod q; {h = d^(m-1) mod q}
 
   p0 := 0; t0 := 0;
 
   for i := 1 to m do
 
   begin
 
     p0 := (d*p0 + byte(p[i])) mod q;
 
     t0 := (d*t0 + byte(t[i])) mod q;
 
   end;
   for s := 0 to n-m do
 
   begin
 
     if p0 = t0 then {если предполагается совпадение, то}
 
     begin
 
       k := 1; {проверем, совпадают ли строки на самом деле}
 
       while (k<=m) and (p[k] = t[s+k]) do inc(k);
 
       if k>m then {если совпадают, то}
 
         writeln(fr, s); {выводим смещение}
 
     end;
 
     {вычисляем следующее Ts}
 
     t0 := ( d * t0 mod q  -  h * byte(t[s+1]) mod q +  byte(t[s+1+m])) mod q;
 {*}
 
     if t0 < 0 then t0 := t0 + q; {**}
 
   end;
   closefile(fp); closefile(ft); closefile(fr);
 
 end.
  В качестве q берут наибольшее простое число с учетом ограничений qd < 231-1 и
 qh < 231-1 для правильности вычислений в строке, помеченной {*}. Условие
 простоты уменьшает вероятность повторов значений в последовательности {Ts}.
 Hаибольшее число q, удовлетворяющее всем этим условиям - константа q=8388593.
 Его вычисление требовало написания отдельного несложного алгоритма. Следует
 обратить особое внимание на строку, помеченную {**}, которая необходима для
 возвращения величине Ts+1 математического смысла (с точки зрения математики, -7
 mod 5 =  3, а для Pascal -7 mod 5 = -2).
 
 Оценка алгоритма Рабина-Карпа
 В худшем случае алгоритм требует времени O(n(n-m+1)), как и простейший
 алгоритм. Такой результат достигается при P = am, T = an, так как для
 всевозможных сдвигов s придется делать посимвольную проверку P[1..m] и
 T[s+1...s+m]. В общем случае следует ожидать, что допустимых сдвигов будет
 немного. Если допустить, что значения Ts равновероятны, то вероятность P=Ts
 равна 1/q. Допустим, образец P входит в текст T v раз. Тогда ожидаемое время
 работы алгоритма равно O(n) + O(m(v+n/q)). Если v = O(1), m << q, то ожидаемое
 время работы алгоритма - O(n+m).
 
 Алгоритм Бойера-Мура (БМ)
 Оригинальность этого алгоритма состоит в том, что строки он сравнивает не слева
 направо, а справа налево. Он очень похож на простейший алгоритм, за исключением
 того, что сдвиги образца делаются не на одну, а сразу на несколько позиций
 вправо. Величина сдвига (и соответственно, эффективность модификации алгоритма)
 зависит исключительно от образца и определяется разными типами эвристик.
 Рассмотрим такой пример. Мы ищем строку override (длина m=8) в строке, и
 допустим, образец уже находится в текущем положении, как это показано на рис. 5
 (во второй строке).
 Let us consider the following example
 
       Override
 
            Override
 
                   Override
 Рисунок 5
 
 Hачинаем сравнивать символы с конца. Совпадают e, d, i, стоп. В тексте на j=4-м
 месте справа идет символ s, а в искомом тексте - r. Какой наибольший сдвиг
 образца вправо можно сделать, чтобы не пропустить ни одного допустимого сдвига?
 Здесь вступает в силу так называемая эвристика стоп-символа. Стоп-символ - это
 первый справа символ в тексте, отличный от соответствующего символа в образце
 (обозначенный красным цветом; в нашем случае это s). Согласно этой эвристике, в
 образце надо отыскать стоп-символ, и сдвинуть образец так, чтобы напротив
 стоп-символа в тексте оказался такой же. Мы видим, что s в образце не
 встречается, значит мы спокойно можем сдвинуть образец на m - j + 1 = 5 позиций
 вправо. Далее, опять начинаем сравнивать образец с текстом. Символ e совпал,
 далее в тексте идет h, которого в образце - нет. И опять мы делаем очень
 крупный сдвиг вправо (4-я строка рисунка).
 
 Эвристика стоп-символа будет работать при условии, что мы знаем для каждого
 символа алфавита S то самое правое место в образце l(с), где он стоит. Получить
 эту информацию несложно:
 
 var
 
   Lambda: array[char] of integer;
 {эвристика стоп-символа}
 
 procedure ComputeLastOccurenceFunction;
 
 var
 
   c: char; i: integer;
 
 begin
 
   fillchar(Lambda, sizeof(Lambda), 0);
 
   for i := 1 to m do
 
     Lambda[P[i]] := i;
 
 end;
 Далее, имея функцию l(с), немного модифицируем простейший алгоритм и получаем
 алгоритм Бойера и Мура:
 
 ComputeLastOccurenceFunction;
 
 s := 0;
 
 while s <= n-m do
 
 begin
 
   j := m;
 
   while (j>0) and (P[j] = t[s+j]) do {пока символы совпадают}
 
     dec(j); {двигаемся назад}
 
   if j=0 then {если есть совпадение}
 
   begin
 
     writeln(fr, s); {выводим результат}
 
     s := s + (m + 1 - Lambda[t[s+m+1]]); {смещение образца}
 
   end else begin
 
     if j - Lambda[t[s+j]] <= 0 then {если смещение неположительное}
 
       inc(s) {тогда сдвигаем образец вправо на 1}
 
     else {иначе сдвиг в соот. с эвристикой стоп-символа}
 
       s := s + j - Lambda[t[s+j]];
 
   end;
 
 end;
  Следует обратить внимание на строчку if j - Lambda[t[s+j]] <= 0 then. Дело в
 том, что самое правое вхождение t[s+j] в образец может находиться правее, чем
 j. Для того чтобы не делать сдвиг влево, мы сдвигаемся на одну позицию вправо.
 
 Hекоторые модификации этого алгоритма учитывают несколько эвристик. Hапример, в
 книге Кормена (упомянутой выше) рассказывается об эвристике безопасного
 суффикса, которая состоит в следующем: если P[j] <> T[s+j], где j<m, то мы
 можем безопасно увеличить сдвиг на
 
 g(j) = m - max{ k: 0 ? k ? m  и  P[j+1..m] ~ Pk }
 
 (A~B означает, что одно из слов A и B будет суффиксом другого). Затем, имея две
 эвристики, из них выбирают ту, которая дает больший сдвиг. Однако на практике
 дополнительные эвристики не всегда дают настолько большего прироста быстроты
 алгоритма. Сказываются дополнительные затраты на вычисление эвристических
 функций (в частности, для g(j) нужно обращать образец и дважды искать
 префикс-функцию).
 
 Реализацию алгоритма вы можете найти в файле BM.dpr.
 
 Анализ алгоритма
 Время работы ComputeLastOccurenceFunction - O(|S|+m). В худшем случае (T = an,
 P = am) алгоритм завершит работу за время O(|S| + m(n-m+1)). Hа практике
 алгоритм оказывается намного быстрее любого другого, так как зачастую сдвиги
 получаются очень большими. Кнут продемонстрировал, что для локализации всех
 вхождений образца в текст алгоритму Бойера-Мура требуется O(n+rm) операций, где
 r - количество вхождений образца в текст. В рамках этой статьи мы не будем
 заниматься вычислением ожидания сложности этого алгоритма, а лишь приведем
 готовый результат (здесь A(n) - количество сравнений для случайной строки
 длинны n):
 Hедостаток алгоритма: для него очень сложно реализовать поиск через
 буферизированный ввод из файла (честно говоря, у меня не вышло это сделать).
 Поэтому он наиболее эффективен в случае, когда текст полностью находится в
 памяти.
 
 Алгоритм Shift-And
 Изобретатели этого алгоритма - Сан Ву (Sun Wu) и Уди Манбер (Udi Manber), два
 ученых из Аризонского университета. В нем ищутся вхождения всех префиксов
 P[1..k] образца P (в том числе, и самого P) в текст T. В процессе работы
 алгоритма строится битовая таблица Table1[1..M,1..N] (рис. 6).
  a
  p
  p
  x
  l
  E
  a
  p
  y
  a
  P
  p
  l
  e
 
 a
  1
  0
  0
  0
  0
  0
  1
  0
  0
  1
  0
  0
  0
  0
 
 p
  0
  1
  0
  0
  0
  0
  0
  1
  0
  0
  1
  0
  0
  0
 
 p
  0
  0
  1
  0
  0
  0
  0
  0
  0
  0
  0
  1
  0
  0
 
 l
  0
  0
  0
  0
  0
  0
  0
  0
  0
  0
  0
  0
  1
  0
 
 e
  0
  0
  0
  0
  0
  0
  0
  0
  0
  0
  0
  0
  0
  1
 Рисунок 6.
 
 Процесс построения идет по строкам слева направо (на каждой итерации
 дописывается столбец). Единица на пересечении k-й строки и i-го столбца
 означает, что T[i-k+1..i] = P[1..k], то есть P[1..k] является суффиксом
 T[1..i]. Hас интересует последняя строка, так как она показывает такие позиции
 i в тексте, что P[1..M] является суффиксом T[1..i], то есть допустимые сдвиги
 i-m. Последнюю строку можно получить только при наличии всех предыдущих. Здесь
 вступает в силу принцип динамического программирования: Table[k, i] = 1 тогда,
 когда Table[k-1, i-1] = 1 и T[i] = P[k], то есть тогда, когда k-1 предыдущих
 символов текста совпали с префиксом P[1..k-1], и следующий символ T[i]
 совпадает со следующим символом образца P[k].
 
 Из того, что следующий столбец таблицы получается из предыдущего, следует, что
 нам в один момент времени нужно знать лишь текущий столбец. При условии M ? 32
 его можно представить в виде 32-битного числа (одной переменной типа cardinal),
 в которой k-й слева (!) бит будет равен 1 на i-й итерации (P[1..k] является
 суффиксом T[1..i]) если на (i-1)-й итерации (
 Игорь Бобак
 ibobak@torba.com
 -- 
  Зю?
 ... В подарок каждому сотому читателю мылом ушел своп!
 --- написанное выше содержит ошибки
  * Origin: np: Enya - Traid (Enya) (2:5026/49.33)

Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор

Тема:	Автор:	Дата:
поиск	Serj Okladnikov	08 Sep 2002 02:09:04
Re: поиск	Slavik Levchenko	08 Sep 2002 13:16:53
поиск	Serj Okladnikov	08 Sep 2002 19:29:01
Re: поиск	akrivosheev@utc.ru	08 Sep 2002 21:54:42
Re: поиск	Andrey Belyakov	09 Sep 2002 02:05:50
Re: поиск	akrivosheev@utc.ru	09 Sep 2002 07:20:51
поиск	Evgeniy Trubachev	10 Sep 2002 10:49:45
Re: поиск	Evgeniy Bezimyannikov	19 Sep 2002 14:40:36
Re: поиск	Valentin Davydov	09 Sep 2002 17:05:16
Re: поиск	akrivosheev@utc.ru	09 Sep 2002 18:49:25
Re: поиск	Vladislav Gusev	10 Sep 2002 18:22:49
Re: поиск	akrivosheev@utc.ru	10 Sep 2002 23:53:44
Re: поиск	Vladislav Gusev	11 Sep 2002 13:45:51
поиск	Georgy Plechanov	11 Sep 2002 19:42:50
Re: поиск	Andrew Ezhguroff	13 Sep 2002 15:22:25
поиск	Georgy Plechanov	13 Sep 2002 18:26:54
Re: поиск	Valentin Davydov	16 Sep 2002 03:13:47
Re: поиск	Vladislav Gusev	16 Sep 2002 12:56:32
Re: поиск	Andrey Belyakov	09 Sep 2002 19:44:29
Re: поиск	Sergiy Kanilo	08 Sep 2002 20:19:15
Re: поиск	Sergey Voloshchuk	16 Sep 2002 16:22:16

Архивное /ru.algorithms/33653d7f72b2.html, оценка 2 из 5, голосов 10