Центральный Дом Знаний - Алгоритм Бойера — Мура — Хорспула

Информационный центр "Центральный Дом Знаний"

Заказать учебную работу! Жми!



ЖМИ: ТУТ ТЫСЯЧИ КУРСОВЫХ РАБОТ ДЛЯ ТЕБЯ

      cendomzn@yandex.ru  

Наш опрос

Как Вы планируете отдохнуть летом?
Всего ответов: 922

Онлайн всего: 1
Гостей: 1
Пользователей: 0


Форма входа

Логин:
Пароль:

Алгоритм Бойера — Мура — Хорспула

Алгоритм Бойера — Мура — Хорспула  поиска строки, упрощённый вариант алгоритма Бойера — Мура. АБМХ работает лучше алгоритма Бойера — Мура на случайных текстах. К тому же, требующая многих предварительных вычислений эвристика совпавшего суффикса опускается.

Впрочем, оценка (в худшем случае на непериодических шаблонах) у АБМХ составляет |needle|·|haystack| (вместо 3|haystack| у Бойера-Мура). 

Сначала строится таблица смещений для искомого шаблона. Совмещается начало текста (строки) и шаблона, проверка начинается с последнего символа шаблона.

Если последний символ шаблона и соответствующий ему при наложении символ строки не совпадают, то образец сдвигается относительно строки на величину, полученную из таблицы смещений. Причём символ берется из строки (а не из шаблона), соответствующий сдвиг находится в таблице. Производится сдвиг и снова начинается проверка с последнего символа.

Если же символы совпадают, производится сравнение предпоследнего символа шаблона и т. д. Если все символы шаблона совпали с наложенными символами строки, значит, подстрока найдена, и поиск окончен. Если же какой-то (не последний) символ шаблона не совпадает с соответствующим символом строки, шаблон сдвигается на один символ вправо, и проверка снова начинается с последнего символа.

Весь алгоритм выполняется до тех пор, пока либо не будет найдено вхождение искомого образца, либо не будет достигнут конец строки. 

В таблице хранится величина сдвига для каждого символа в шаблоне. Величина сдвига определяется из тех соображений, что он должен быть максимально возможным, но таким, чтобы не пропустить вхождение искомого шаблона.

Таблица содержит список всех символов в шаблоне. В соответствие каждому символу ставится его порядковый номер, считая с конца строки. Если символ встречается несколько раз, то используется самое правое вхождение.

Пример:

Для шаблона «abbad» таблица имеет следующий вид.

a

b

d

1

2

5

Позиция последнего символа шаблона в алгоритме не рассматривается, то есть значение смещения для символа 'd' будет равно длине шаблона — 5.

В таблице соответствия символ — смещение, для всех символов, не вошедших в шаблон, величина смещения устанавливается равной длине шаблона — 5.

Пример работы алгоритма:

Искомый шаблон — «abbad» (таблица для этого шаблона построена выше).

abeccacbadbabbad

abbad

Накладываем образец на строку. Последний символ исходной строки «с» не содержится в образце. Сдвигаем образец вправо на 5 позиций в соответствии со значением смещения для «с»:

abeccacbadbabbad

abbad

Три символа образца совпали, а четвертый — нет. Сдвигаем образец вправо на 1:

abeccacbadbabbad

abbad

Последний символ строки b не совпадает с символом шаблона.Сдвигаем образец вправо на 2:

abeccacbadbabbad

abbad

И снова последний символ строки b не совпадает с символом шаблона.Сдвигаем на 2 позиции:

abeccacbadbabbad

abbad


Последний символ исходной строки «a» снова не совпадает с символом шаблона. В соответствии с таблицей смещений сдвигаем образец на 1 позицию и получаем искомое вхождение образца:

abeccacbadbabbad

abbad

Паскаль:

Процедура получает ссылки на три переменные: haystack и needle строкового типа и result целого типа, причём первые две для процедуры являются константами и не могут быть изменены. В haystack должна содержаться строка, в которой будет осуществлён поиск, а needle должна содержать подстроку, которую надо найти. В результате выполнения процедуры переменнаяresult будет содержать номер позиции, начиная с которого подстрока needle входит в строку haystack, или 0, если вхождения нет.

procedure boyer_moore(const haystack: string; const needle: string; var result: integer);
var
 i, j, k : integer;
 needle_len : integer;
 haystack_len : integer;
 needle_table : array[char] of byte;
begin
 
 needle_len := length(needle);
 haystack_len := length(haystack);
 
 if needle_len < haystack_len then
 begin
 for i := 0 to 255 do
 needle_table[chr(i)] := needle_len;
 for i := 1 to needle_len-1 do
 needle_table[needle[i]] := needle_len-i;
 
 i := needle_len;
 j := i;
 while (j > 0) and (i <= haystack_len) do
 begin
 j := needle_len; k := i;
 while (j > 0) and (haystack[k] = needle[j]) do
 begin
 dec(k);
 dec(j);
 end;
 i := i + needle_table[haystack[i]];
 end;
 
 if k > haystack_len - needle_len then
 result := 0
 else
 result := k + 1;
 
 end 
 else
 result := 0;
end;

Процедура получает ссылки на две переменные: haystack и needle строкового типа. В haystack должна содержаться строка, в которой будет осуществлён поиск, а needle должна содержать подстроку, которую надо найти. В результате выполнения процедуры переменная функция вернёт номер позиции (при нумерации с единицы), начиная с которого подстрока needle входит в строку haystack, или 0, если вхождения нет.

int BoyerMooreHorspool(char *haystack, char *needle)
{
 int i,j,k, needle_len = 0,haystack_len = 0;
 int needle_table[256];
 
 for (char *p = needle; *p; *p++)
 ++needle_len;
 for (char *p = haystack; *p; *p++)
 ++haystack_len;
 
 if (needle_len < haystack_len)
 {
 for (i = 0; i < 256; i++)
 needle_table[i] = needle_len;
 
 for (i = 1; i < needle_len; i++)
 needle_table[needle[i-1]] = needle_len-i;
 
 i = needle_len;
 j = i;
 
 while (j > 0 && i <= haystack_len)
 {
 j = needle_len;
 k = i;
 while (j > 0 && haystack[k-1] == needle[j-1])
 {
 --k;
 --j;
 }
 i+=needle_table[haystack[i-1]];
 }
 
 if (k > haystack_len - needle_len)
 return 0;
 else return k+1;
 }
 else return 0;
}
Лит.: Никлаус Вирт Алгоритмы и структуры данных. — М.: Невский Диалект, 2006. С. 352. ISBN 5-7940-0065-1

Loading

Календарь

«  Март 2024  »
ПнВтСрЧтПтСбВс
    123
45678910
11121314151617
18192021222324
25262728293031

Архив записей

Друзья сайта

  • Заказать курсовую работу!
  • Выполнение любых чертежей
  • Новый фриланс 24