Полезное для программистов:

Фриланс
Новости
Статьи
   
Рубрики:

Error. Page cannot be displayed. Please contact your service provider for more details. (11)


Алгоритм Бойера-Мура

Поиск:
Алгоритм Бойера-Мура поиска строки считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке. Был разработан Робертом Бойером (англ. Robert S. Boyer) и Джеем Муром (англ. J Strother Moore) в 1977 году. Преимущество этого алгоритма в том, что не нужно сравнивать шаблон (строка, которую хотим найти) с каждой буквой исходного текста, так как некоторые из них можно пропустить. Чем длиннее шаблон, тем быстрее работает алгоритм.


Описание алгоритма


Первым делом строится таблица смещений для искомого шаблона. Совмещается начало текста (строки) и шаблона, проверка начинается с последнего символа шаблона. Если последний символ шаблона и соответствующий ему при наложении символ строки не совпадают, то образец сдвигается относительно строки на величину, полученную из таблицы смещений. Причем берем символ из строки(а не шаблона) и смотрим соответствующий сдвиг в таблице. Сдвигаем и снова начинаем проверку с последнего символа. Если же символы совпадают, производится сравнение предпоследнего символа шаблона и т. д. Если все символы шаблона совпали с наложенными символами строки, значит мы нашли подстроку и поиск окончен. Если же какой-то (НЕ ПОСЛЕДНИЙ) символ шаблона не совпадает с соответствующим символом строки, мы сдвигаем шаблон на ОДИН символ вправо и снова начинаем проверку с последнего символа. Весь алгоритм выполняется до тех пор, пока либо не будет найдено вхождение искомого образца, либо не будет достигнут конец строки.

Построение таблицы

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

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

Пример

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

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

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

abeccacbadbabbad
abbad

Накладываем образец на строку. Литер "с" не содержится в образце. Сдвигаем образец вправо на 5 позиций:

abeccacbadbabbad
     abbad

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

abeccacbadbabbad
      abbad

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

abeccacbadbabbad
        abbad

Еще раз сдвигаем образец на 2 позиции:

abeccacbadbabbad
          abbad

Теперь, в соответствии с таблицей, сдвигаем образец на одну позицию, и получаем искомое вхождение образца:

abeccacbadbabbad
           abbad



Пример


Простой пример реализации алгоритма Бойера-Мура на языке Паскаль.

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

procedure boyer_moore(const haystack: string; const needle: string; var result: byte);
var
        i, j, k      : byte;
        needle_len   : byte;
        haystack_len : byte;
        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;







Просмотров: 15485

 

 

Новые статьи:


Популярные:
  1. Как сделать цикличным проигрывание MIDI-файла?
  2. Создание AVI файла из рисунков
  3. Как устройство "отключить в данной конфигурации"?
  4. Kто в данный момент присоединен через Сеть?
  5. Как узнать количество доступной памяти?
  6. Как реализовать в RichEdit разноцветный текст?
  7. Как скрыть свое приложение от ProcessViewer
  8. Как программно нажать/скрыть/показ кнопку "Start"?
  9. Модуль работы с ресурсами в PE файлах
10. Функции вызова диалоговых окон выбора
11. Проверка граматики средствами Word'а из Delphi.
12. Модуль для упрощенного вызова сообщений
13. Функции для записи и чтение своих данных в, ЕХЕ- файле
14. Рекурсивный просмотр директорий
15. Network Traffic Monitor
16. Разные модули
17. Универсальная функция для обращения к любым экспортируем функциям DLL
18. Библиотека от VladS
19. Протектор для UPX'а
20. Еще об ICQ, сообщения по контакт листу?
21. Использование открытых интерфейсов
22. Теория и практика использования RTTI
23. Работа с TApplication
24. Примеры использования Drag and Drop для различных визуальных компонентов
25. Что такое порт? Правила для работы с портами
26. Симфония на клавиатуре
27. Загрузка DLL
28. Исправление автоинкремента
29. Взаимодействие с чужими окнами
30. Проверить дубляжи в столбце


 

 

 
 
На главную