В информатике , то алгоритм строк поиска Бойер-Мура является эффективным строковым поиском алгоритма , который является стандартным эталоном для практической строкового поиска литературы. [1] Он был разработан Робертом С. Бойером и Дж. Стротером Муром в 1977 году. [2] Исходный документ содержал статические таблицы для вычисления сдвигов паттернов без объяснения того, как их производить. Алгоритм создания таблиц был опубликован в следующей статье; Этот документ содержит ошибки , которые впоследствии были исправлены Войцех Rytter в 1980 году [3] [4] The алгоритм выполняет предварительную обработкустрока разыскивается (шаблон), но не строка разыскивается в (текст). Таким образом, он хорошо подходит для приложений, в которых шаблон намного короче текста или где он сохраняется при нескольких поисках. Алгоритм Бойера – Мура использует информацию, собранную на этапе предварительной обработки, для пропуска частей текста, что приводит к более низкому постоянному коэффициенту, чем многие другие алгоритмы поиска по строкам. Как правило, алгоритм работает быстрее с увеличением длины шаблона. Ключевыми особенностями алгоритма являются сопоставление по хвосту шаблона, а не по его заголовку, и пропуск по тексту скачками из нескольких символов, а не поиск каждого отдельного символа в тексте.
Класс | Строковый поиск |
---|---|
Структура данных | Нить |
Наихудшая производительность | Θ (m) предварительная обработка + O (mn) сопоставление [примечание 1] |
Лучшая производительность | Θ (m) предварительная обработка + Ω (n / m) согласование |
Сложность пространства в наихудшем случае | Θ (k) [примечание 2] |
Определения
А | N | п | А | N | M | А | N | - |
п | А | N | - | - | - | - | - | - |
- | п | А | N | - | - | - | - | - |
- | - | п | А | N | - | - | - | - |
- | - | - | п | А | N | - | - | - |
- | - | - | - | п | А | N | - | - |
- | - | - | - | - | п | А | N | - |
- T обозначает вводимый текст для поиска. Его длина равна n .
- P обозначает строку для поиска, называемую шаблоном . Его длина составляет м .
- S [ i ] обозначает символ в индексе i строки S , считая от 1.
- S [ i .. j ] обозначает подстроку строки S, начинающуюся с индекса i и заканчивающуюся j , включительно.
- Префикс из S является подстрока S [1 .. я ] для некоторого I в диапазоне [1, л ], где L является длиной S .
- Суффикс из S является подстроки S [ я .. л ] для некоторого I в диапазоне [1, л ], где L является длина S .
- Выравнивания из P в T является индексом к в Т таким образом, что последний символ P совмещен с индексом к из T .
- Совпадение или возникновение из P происходит при выравнивающей к , если Р эквивалентно Т [( к - м + 1) .. K ].
Описание
Алгоритм Бойера-Мура ищет вхождения P в T , выполняя явное сравнение символов при различных выравниваниях. Вместо перебора всех раскладов (из которых есть), Бойер-Мур использует информацию, полученную при предварительной обработке P, чтобы пропустить как можно больше выравниваний.
До введения этого алгоритма обычным способом поиска в тексте было изучение каждого символа текста на предмет первого символа шаблона. Как только это будет найдено, последующие символы текста будут сравниваться с символами шаблона. Если совпадения не было, текст снова будет проверяться посимвольно, чтобы найти совпадение. Таким образом, необходимо изучить почти каждый символ в тексте.
Ключевым моментом в этом алгоритме является то, что если конец шаблона сравнивается с текстом, то можно делать переходы по тексту, а не проверять каждый символ текста. Причина, по которой это работает, заключается в том, что при выравнивании шаблона по тексту последний символ шаблона сравнивается с символом в тексте. Если символы не совпадают, нет необходимости продолжать поиск в обратном направлении по тексту. Если символ в тексте не соответствует ни одному из символов в шаблоне, то следующий символ в тексте для проверки располагается на n символов дальше по тексту, где n - длина шаблона. Если символ в тексте находится в шаблоне, то выполняется частичный сдвиг шаблона по тексту, чтобы выровняться по совпадающему символу, и процесс повторяется. Переход по тексту для сравнения вместо проверки каждого символа в тексте уменьшает количество сравнений, которые необходимо выполнить, что является ключом к эффективности алгоритма.
Более формально алгоритм начинается с выравнивания , Так что начало P совмещен с началом Т . Затем символы в P и T сравниваются, начиная с индекса n в P и k в T , двигаясь назад. Строки сравниваются с конца Р до начала Р . Сравнение продолжается до тех пор, пока либо не будет достигнуто начало P (что означает совпадение), либо не произойдет несовпадение, при котором выравнивание сдвинется вперед (вправо) в соответствии с максимальным значением, разрешенным рядом правил. Сравнение выполняется снова при новом выравнивании, и процесс повторяется до тех пор, пока выравнивание не смещается за конец T , что означает, что дальнейшие совпадения не будут найдены.
Правила сдвига реализуется в виде постоянная время табличного поиска, используя таблицы , генерируемые во время предварительной обработки P .
Правила смены
Сдвиг рассчитывается с применением двух правил: правила плохого символа и правила хорошего суффикса. Фактическое смещение смещения - это максимальное смещение, рассчитанное по этим правилам.
Правило плохого характера
Описание
- | - | - | - | Икс | - | - | K | - | - | - |
А | N | п | А | N | M | А | N | А | M | - |
- | N | N | А | А | M | А | N | - | - | - |
- | - | - | N | N | А | А | M | А | N | - |
Правило недопустимых символов рассматривает символ в T, на котором произошел сбой процесса сравнения (при условии, что такая ошибка произошла). Следующее вхождение этого символа слева в P найдено, и сдвиг , который приносит , что появление в соответствии с несогласованным появлением в Т предлагается. Если несовпадающий символ не встречается слева в P , предлагается сдвиг, который перемещает всю P за точку несовпадения.
Предварительная обработка
Методы различаются в зависимости от точной формы, которую должна принимать таблица для правила плохого символа, но простое решение для поиска с постоянным временем выглядит следующим образом: создать 2D-таблицу, которая сначала индексируется индексом символа c в алфавите, а затем - индекс i в шаблоне. Этот поиск вернет вхождение c в P со следующим по величине индексомили -1, если такого не было. Предлагаемая смена тогда будет, с участием время поиска и пространство, предполагая конечный алфавит длины k .
Реализации C и Java ниже имеют сложность пространства (make_delta1, makeCharTable). Это то же самое, что и исходная delta1 и таблица недопустимых символов BMH . Эта таблица отображает символ в позиции сдвинуть , причем последний экземпляр - наименьшее количество сдвига - имеет приоритет. Все неиспользуемые символы устанавливаются как как контрольное значение.
Правило хорошего суффикса
Описание
- | - | - | - | Икс | - | - | K | - | - | - | - | - |
M | А | N | п | А | N | А | M | А | N | А | п | - |
А | N | А | M | п | N | А | M | - | - | - | - | - |
- | - | - | - | А | N | А | M | п | N | А | M | - |
Правило хорошего суффикса значительно сложнее как по концепции, так и по реализации, чем правило плохого символа. Подобно правилу плохого символа, оно также использует свойство алгоритма сравнения, начиная с конца шаблона и продвигаясь к началу шаблона. Его можно описать следующим образом: [5]
Предположим, что для данного выравнивания P и T подстрока t из T совпадает с суффиксом P , но при следующем сравнении слева возникает несоответствие. Тогда найти, если он существует, самый правый экземпляр т « о т в Р такой , что т» не является суффикс P и символ слева от т» в P отличается от символа слева от т в Р . Сдвиг Р вправо так , что подстроки т» в P совпадет с подстроки т в Т . Если т» не существует, то смещение левого конца P мимо левого конца т в Т наименьшим количеством , так что префикс сдвинутого шаблона соответствует суффикс т в Т . Если такой сдвиг невозможен, сдвиньте P на n позиций вправо. Если вхождение Р найдено, то сдвиг P наименьшим количеством , так что собственно префикс смещенная Р соответствует суффикс вхождения P в T . Если такой сдвиг невозможен, то сдвиньте P на n раз , то есть сдвиньте P за t .
Предварительная обработка
Правило хорошего суффикса требует двух таблиц: одну для использования в общем случае, а другую для использования, когда либо общий случай не возвращает значимого результата, либо происходит совпадение. Эти таблицы будут обозначены L и H соответственно. Их определения следующие: [5]
Для каждого i ,самая большая позиция меньше n такая, что строка совпадает с суффиксом и такой, что символ, предшествующий этому суффиксу, не равен . считается равным нулю, если нет позиции, удовлетворяющей условию.
Позволять обозначают длину наибольшего суффикса это также префикс P , если он существует. Если его нет, пусть быть нулевым.
Обе эти таблицы могут быть построены в время и использование космос. Сдвиг выравнивания для индекса i в P определяется выражением или же . H следует использовать только в том случае, если равен нулю или найдено совпадение.
Правило Галиля
Простая, но важная оптимизация Бойера-Мура была предложена Цви Галилом в 1979 году. [6] В отличие от смещения, правило Галиля имеет дело с ускорением фактических сравнений, выполняемых при каждом выравнивании, путем пропуска разделов, которые, как известно, совпадают. Предположим , что в выравнивающей к 1 , Р сравнивается с Т до символа с из T . Затем, если P сдвигается на k 2 , так что его левый конец находится между c и k 1 , на следующей фазе сравнения префикс P должен соответствовать подстроке T [( k 2 - n ) .. k 1 ] . Таким образом, если сравнения доходят до позиции k 1 из T , вхождение P может быть записано без явного сравнения прошедшего k 1 . Помимо повышения эффективности Бойера – Мура, правило Галиля требуется для доказательства линейного выполнения в наихудшем случае.
Правило Galil в его исходной версии действует только для версий, которые выводят несколько совпадений. Он обновляет диапазон подстроки только при c = 0 , т.е. при полном совпадении. Обобщенная версия для работы с подматчами была представлена в 1985 году как алгоритм Апостолико – Джанкарло . [7]
Представление
Алгоритм Бойера-Мура, представленный в исходной статье, имеет время работы в худшем случае, равное только если узор не появляется в тексте. Впервые это было доказано Кнутом , Моррисом и Праттом в 1977 г. [8], а затем Гибасом и Одлыжко в 1980 г. [9] с верхней границей 5 n сравнений в худшем случае. Ричард Коул дал доказательство с верхней границей 3 n сравнений в худшем случае в 1991 году [10].
Когда шаблон действительно встречается в тексте, время работы исходного алгоритма равнов худшем случае. Это легко увидеть, если и шаблон, и текст состоят исключительно из одного и того же повторяющегося символа. Однако включение правила Galil приводит к линейному времени выполнения во всех случаях. [6] [10]
Реализации
Существуют различные реализации на разных языках программирования. В C ++ он является частью стандартной библиотеки, начиная с C ++ 17, а также Boost предоставляет общую реализацию поиска Бойера – Мура в библиотеке алгоритмов . В Go (языке программирования) есть реализация в search.go . D (язык программирования) использует BoyerMooreFinder для сопоставления на основе предикатов в пределах диапазонов как часть библиотеки времени выполнения Phobos.
Алгоритм Бойер-Мур также используется в GNU «s Grep . [11]
Ниже приведены несколько простых реализаций.
от ввода import * # Эта версия чувствительна к английскому алфавиту в ASCII для сопоставления без учета регистра. # Чтобы удалить эту функцию, определите алфавитный_индекс как ord (c) и замените экземпляры «26» # на «256» или любую другую максимальную кодовую точку, которую вы хотите. Для Unicode вы можете захотеть сопоставить в байтах UTF-8 # вместо создания таблицы размером 0x10FFFF.ALPHABET_SIZE = 26def алфавит_index ( c : str ) -> int : "" "Возвращает индекс данного символа в английском алфавите, считая от 0." "" val = ord ( c . lower ()) - ord ( "a" ) assert val > = 0 и val < ALPHABET_SIZE return valdef match_length ( S : str , idx1 : int , idx2 : int ) -> int : "" "Возвращает длину совпадения подстрок S, начиная с idx1 и idx2." "" if idx1 == idx2 : return len ( S ) - idx1 match_count = 0, а idx1 < len ( S ) и idx2 < len ( S ) и S [ idx1 ] == S [ idx2 ]: match_count + = 1 idx1 + = 1 idx2 + = 1 return match_countdef basic_preprocess ( S : str ) -> List [ int ]: "" "Вернуть Z, фундаментальную предварительную обработку S. Z [i] - длина подстроки, начинающейся с i, которая также является префиксом S. Эта предварительная обработка выполняется за время O (n), где n - длина S. "" ", если len ( S ) == 0 : # Обрабатывает регистр пустой строки return [] if len ( S ) == 1 : # Обрабатывает регистр односимвольной строки return [ 1 ] z = [ 0 for x in S ] z [ 0 ] = len ( S ) z [ 1 ] = match_length ( S , 0 , 1 ) для i в диапазоне ( 2 , 1 + z [ 1 ]): # Оптимизация из упражнения 1–5 z [ i ] = z [ 1 ] - i + 1 # Определяет нижний и верхний пределы z-блока l = 0 r = 0 для i в диапазоне ( 2 + z [ 1 ], len ( S )): если i <= r : # i попадает в существующий z-блок k = i - l b = z [ k ] a = r - i + 1, если b < a : # b заканчивается внутри существующего z-блока z [ i ] = b else : # b заканчивается в конце z-блока или после него , нам нужно выполнить явное сопоставление справа от z-блока z [ i ] = a + match_length ( S , a , r + 1 ) l = i r = i + z [ i ] - 1 else : # i не находится в существующем z-блоке z [ i ] = match_length ( S , 0 , i ), если z [ i ] > 0 : l = i r = i + z [ i ] - 1 вернуть zdef bad_character_table ( S : str ) -> List [ List [ int ]]: "" " Создает R для S, который представляет собой массив, индексированный позицией некоторого символа c в английском алфавите. В этом индексе в R находится массив длины | S | +1, определяя для каждого индекса i в S (плюс индекс после S) следующее местоположение символа c, встречающегося при перемещении S справа налево, начиная с i. Это используется для поиска в постоянное время для плохое правило символов в алгоритме поиска строки Бойера-Муре, хотя он имеет гораздо больший размер , чем непостоянное время решение. «»» если Len ( S ) == 0 : возвращение [[] для более в диапазоне ( ALPHABET_SIZE )] R = [[ - 1 ] для более в диапазоне ( ALPHABET_SIZE )] альфа = [ - 1 для более в диапазоне ( ALPHABET_SIZE )] для I , с в перечисление , ( S ): альфа [ alphabet_index ( с )] = I для j , a в перечислении ( альфа ): R [ j ] . append ( a ) return Rdef good_suffix_table ( S : str ) -> List [ int ]: "" " Создает L для S, массива, используемого в реализации правила сильного хорошего суффикса. L [i] = k, самая большая позиция в S, такая что S [i:] (суффикс S, начинающийся с i) совпадает с суффиксом S [: k] (подстрока в S, заканчивающаяся на k). Используется в Boyer-Moore, L дает величину сдвига P относительно T, так что никакие экземпляры P в T не пропускаются, а суффикс P [: L [i]] соответствует подстроке T, сопоставленной суффиксом P в предыдущей попытке сопоставления. В частности, если несоответствие имело место в позиции i-1 в P величина сдвига определяется уравнением len (P) - L [i]. В случае, когда L [i] = -1, используется полная таблица сдвига. Поскольку важны только правильные суффиксы, L [0] = -1. "" " L = [ - 1 для c в S ] N = basic_preprocess ( S [:: - 1 ]) # S [:: - 1] меняет S N на противоположное . reverse () для j в диапазоне ( 0 , len ( S ) - 1 ): i = len ( S ) - N [ j ] if i ! = len ( S ): L [ i ] = j return Ldef full_shift_table ( S : str ) -> List [ int ]: "" " Создает F для S, массива, используемого в особом случае правила хорошего суффикса в алгоритме поиска строки Бойера-Мура . F [i] - длина самого длинного суффикса S [i:], который также является префиксом S. В тех случаях, когда он используется, величина сдвига шаблона P относительно текста T равна len (P) - F [i] для несоответствия встречается в i-1. "" " F = [ 0 для c в S ] Z = primary_preprocess ( S ) longest = 0 для i , zv в перечислении ( обратное ( Z )): longest = max ( zv , longest ), если zv == i + 1 еще самый длинный F [ - i - 1 ] = самый длинный возврат Fdef string_search ( P , T ) -> List [ int ]: "" " Реализация алгоритма поиска строки Бойера-Мура. Он находит все вхождения P в T и включает множество способов предварительной обработки шаблона для определения оптимального для сдвига строки и пропуска сравнений. На практике он выполняется за O (m) (и даже сублинейно) время, где m - длина T. Эта реализация выполняет поиск без учета регистра букв алфавитных символов ASCII, без пробелов. "" " если len ( P ) == 0 или len ( T ) == 0 или len ( T ) < len ( P ): return [] совпадения = [] # Предварительная обработка R = bad_character_table ( P ) L = good_suffix_table ( P ) F = full_shift_table ( P ) k = len ( P ) - 1 # Представляет выравнивание конца P относительно T previous_k = - 1 # Представляет выравнивание на предыдущей фазе (правило Галиля), в то время как k < len ( T ): i = len ( P ) - 1 # Символ для сравнения в P h = k # Символ для сравнения в T, пока i > = 0 и h > previous_k и P [ i ] == T [ h ]: # Соответствует, начиная с конца P i - = 1 h - = 1, если i == - 1 или h == previous_k : # Найдено совпадение (правило Галила) совпадений . append ( k - len ( P ) + 1 ) k + = len ( P ) - F [ 1 ] if len ( P ) > 1 else 1 else : # Нет совпадений, сдвиг на максимальное значение плохого символа и правила хорошего суффикса char_shift = i - R [ алфавитный_индекс ( T [ h ])] [ i ] if i + 1 == len ( P ): # Несоответствие произошло при первой попытке суффикс_shift = 1 elif L [ i + 1 ] == - 1 : # Соответствующий суффикс не появляется нигде в P суффикс_shift = len ( P ) - F [ i + 1 ] else : # Соответствующий суффикс появляется в P суффикс_shift = len ( P ) - 1 - L [ i + 1 ] shift = max ( char_shift , suffix_shift ) previous_k = k if shift > = i + 1 else previous_k # Правило Галиля k + = shift return соответствует
#include #include #include #include #define ALPHABET_LEN 256 #define max (a, b) ((a )?>// ПРАВИЛО ПЛОХОГО ХАРАКТЕРА. // таблица delta1: delta1 [c] содержит расстояние между последним // символом pat и крайним правым вхождением c в pat. // // Если c не встречается в pat, тогда delta1 [c] = patlen. // Если c находится в строке [i] и c! = Pat [patlen-1], мы можем безопасно сдвинуть i // на delta1 [c], которое является минимальным расстоянием, необходимым для сдвига // pat вперед, чтобы получить строку [i] совпал с каким-то персонажем в пат. // c == pat [patlen-1], возвращающий ноль, важен только для BMH, // который не имеет delta2. В таком случае BMH принимает значение patlen. // Мы следуем этому выбору вместо исходного 0, потому что // пропускает больше. (правильность?) // // Этот алгоритм работает в алфавитном порядке + время. void make_delta1 ( ptrdiff_t * delta1 , uint8_t * pat , size_t patlen ) { for ( int i = 0 ; i < ALPHABET_LEN ; i ++ ) { delta1 [ i ] = patlen ; } for ( int i = 0 ; i < patlen -2 ; i ++ ) { delta1 [ pat [ i ]] = patlen -1 - i ; } }// истина, если суффикс слова, начинающегося с слова [pos], является префиксом // слова bool is_prefix ( uint8_t * word , size_t wordlen , ptrdiff_t pos ) { int suffixlen = wordlen - pos ; // здесь также можно использовать библиотечную функцию strncmp () // return! strncmp (слово, & слово [позиция], суффикслен); for ( int i = 0 ; i < суффикслен ; i ++ ) { if ( word [ i ] ! = word [ pos + i ]) { return false ; } } return true ; }// длина самого длинного суффикса слова, оканчивающегося словом [pos]. // длина_суффикса ("dddbcabc", 8, 4) = 2 size_t суффикс_длина ( uint8_t * слово , size_t worddlen , ptrdiff_t pos ) { size_t i ; // увеличиваем длину суффикса i до первого несоответствия или начала // слова for ( i = 0 ; ( word [ pos - i ] == word [ wordlen -1 - i ]) && ( i < pos ); i + + ); вернуть я ; }// ПРАВИЛО ХОРОШЕГО СУФФИКСА. // таблица delta2: учитывая несоответствие в pat [pos], мы хотим выровнять // со следующим возможным полным соответствием. Это может быть основано на том, что мы // знаем о pat [pos + 1] и pat [patlen-1]. // // В случае, если 1: // pat [pos + 1] to pat [patlen-1] не встречается где-либо еще в pat, // следующее правдоподобное совпадение начинается с или после несоответствия. // Если в подстроке pat [pos + 1 .. patlen-1] находится префикс // слова pat, здесь будет следующее правдоподобное совпадение (если в подстроке несколько // префиксов, выберите самый длинный). В противном случае // следующее правдоподобное совпадение начинается после символа, выровненного с // pat [patlen-1]. // // В случае 2: // pat [pos + 1] to pat [patlen-1] действительно встречается в другом месте в pat. Несоответствие // говорит нам , что мы не ищем в конце матча. // Однако мы можем смотреть на середину матча. // // Первый цикл, который обрабатывает случай 1, аналогичен // таблице KMP, адаптированной для «обратного» порядка сканирования с // дополнительным ограничением, что все подстроки, которые он рассматривает как // потенциальные префиксы, являются всеми суффиксы. В худшем случае // pat состоит из одинаковых повторяющихся букв, поэтому каждый суффикс // является префиксом. Однако одного этого цикла недостаточно: // Предположим, что pat - это «ABYXCDBYX», а текст - «..... ABYXCDEYX». // Мы сопоставим X, Y и найдем B! = E. В суффиксе «YX» нет префикса pat //, поэтому первый цикл говорит нам пропустить вперед // на 9 символов. // Несмотря на внешнее сходство с таблицей KMP, таблица KMP // полагается на информацию о начале частичного совпадения, // которой алгоритм BM не имеет. // // Второй цикл обращается к случаю 2. Поскольку суффикс_длина не может быть // уникальным, мы хотим взять минимальное значение, // которое сообщит нам, // насколько далеко находится ближайшее потенциальное совпадение. void make_delta2 ( ptrdiff_t * delta2 , uint8_t * pat , size_t patlen ) { ssize_t p ; size_t last_prefix_index = patlen -1 ; // первый цикл for ( p = patlen -1 ; p > = 0 ; p - ) { if ( is_prefix ( pat , patlen , p + 1 )) { last_prefix_index = p + 1 ; } delta2 [ p ] = last_prefix_index + ( patlen -1 - p ); } // второй цикл for ( p = 0 ; p < patlen -1 ; p ++ ) { size_t slen = suffix_length ( pat , patlen , p ); if ( pat [ p - slen ] ! = pat [ patlen -1 - slen ]) { delta2 [ patlen -1 - slen ] = patlen -1 - p + slen ; } } }// Возвращает указатель на первое совпадение. // См. Также glibc memmem () (не BM) и std :: boyer_moore_searcher (первое совпадение). uint8_t * boyer_moore ( uint8_t * строка , size_t StringLen , uint8_t * погладить , size_t patlen ) { ptrdiff_t Delta1 [ ALPHABET_LEN ]; ptrdiff_t delta2 [ патлен ]; // C99 VLA make_delta1 ( delta1 , pat , patlen ); make_delta2 ( дельта2 , пат , патлен ); // Пустой шаблон нужно рассматривать особо if ( patlen == 0 ) { return string ; } size_t i = patlen - 1 ; // str-idx while ( i < stringlen ) { ptrdiff_t j = patlen - 1 ; // pat-idx while ( j > = 0 && ( string [ i ] == pat [ j ])) { - i ; - j ; } если ( j < 0 ) { возврат & строка [ я + 1 ]; } ptrdiff_t shift = max ( delta1 [ строка [ i ]], delta2 [ j ]); я + = сдвиг ; } return NULL ; }
/ ** * Возвращает в этой строке индекс первого вхождения указанной * подстроки. Если это не подстрока, верните -1. * * Galil не существует, потому что он генерирует только одно совпадение. * * @param haystack Строка для сканирования * @param Needle Целевая строка для поиска * @return Начальный индекс подстроки * / public static int indexOf ( char [] haystack , char [] Needle ) { if ( Needle . длина == 0 ) { возврат 0 ; } int charTable [] = makeCharTable ( игла ); int offsetTable [] = makeOffsetTable ( игла ); for ( int i = игла . длина - 1 , j ; i < стог сена . длина ;) { for ( j = игла . длина - 1 ; игла [ j ] == стог сена [ i ] ; - i , - j ) { если ( j == 0 ) { вернуть я ; } } // i + = Needle.length - j; // Для наивного метода i + = Math . max ( offsetTable [ игла . длина - 1 - j ] , charTable [ haystack [ i ]] ); } return - 1 ; } / ** * Делает таблицу переходов на основе информации о несовпадающих символах. * / Частные статические INT [] makeCharTable ( символ [] игла ) { конечная INT ALPHABET_SIZE = символы . MAX_VALUE + 1 ; // 65536 int [] table = new int [ ALPHABET_SIZE ] ; for ( int i = 0 ; i < table . length ; ++ i ) { table [ i ] = игла . длина ; } for ( int i = 0 ; i < игла . длина - 1 ; ++ i ) { таблица [ игла [ i ]] = игла . длина - 1 - i ; } таблица возврата ; } / ** * Создает таблицу переходов на основе смещения сканирования, при котором возникает несоответствие. * (правило плохого персонажа). * / Частные статические INT [] makeOffsetTable ( символ [] игла ) { INT [] таблица = новый INT [ игла . длина ] ; int lastPrefixPosition = игла . длина ; для ( int я = игла . длина ; я > 0 ; - я ) { если ( isPrefix ( игла , я )) { lastPrefixPosition = я ; } таблица [ игла . длина - i ] = lastPrefixPosition - i + игла . длина ; } для ( int я = 0 ; я < игла . длина - 1 ; ++ я ) { int slen = суффиксLength ( игла , я ); стол [ slen ] = игла . длина - 1 - i + slen ; } таблица возврата ; } / ** * Является ли игла [p: end] префиксом иглы? * / Частный статический логический isPrefix ( символ [] игла , ИНТ р ) { для ( Int я = р , J = 0 ; я < игле . Длины ; ++ I , ++ J ) { если ( игла [ я ] ! = игла [ j ] ) { return false ; } } return true ; } / ** * Возвращает максимальную длину подстроки, заканчивающейся на p и являющейся суффиксом. * (Хорошее правило суффикс) * / частный статический INT suffixLength ( символ [] игла , INT р ) { INT Len = 0 ; for ( int я = p , j = игла . длина - 1 ; я > = 0 && игла [ i ] == игла [ j ] ; - i , - j ) { len + = 1 ; } return len ; }
Варианты
Алгоритм Бойер-Мура-Horspool является упрощением алгоритма Бойера-Мура , используя только плохое правило символов.
Алгоритм Apostolico-Джанкарло ускоряет процесс проверки того, произошло ли совпадение на данном выравнивания путем пропуска явных сравнений символов. При этом используется информация, полученная во время предварительной обработки шаблона, в сочетании с длинами совпадений суффиксов, записанными при каждой попытке сопоставления. Для хранения длин совпадений суффиксов требуется дополнительная таблица, размер которой равен размеру искомого текста.
Алгоритм Райта повышает производительность алгоритма Бойера-Мура-Horspool. Шаблон поиска конкретной подстроки в данной строке отличается от алгоритма Бойера-Мура-Хорспула.
Заметки
- ^ m - это длина строки шаблона, которую мы ищем в тексте, которая имеет длину n . Эта среда выполнения предназначена для поиска всех вхождений шаблона без правила Galil.
- ^ k - размер алфавита
Рекомендации
- ^ Юм; Воскресенье (ноябрь 1991 г.). «Быстрый поиск строки». Программное обеспечение - практика и опыт . 21 (11): 1221–1248. DOI : 10.1002 / spe.4380211105 . S2CID 5902579 .
- ^ Бойер, Роберт С .; Мур, Дж. Стротер (октябрь 1977 г.). «Алгоритм быстрого поиска строки». Comm. ACM . Нью-Йорк: Ассоциация вычислительной техники. 20 (10): 762–772. DOI : 10.1145 / 359842.359859 . ISSN 0001-0782 . S2CID 15892987 .
- ^ Knuth, Donald E .; Моррис младший, Джеймс Х .; Пратт, Воан Р. (1977). «Быстрое сопоставление с образцом в строках». SIAM Journal on Computing . 6 (2): 323–350. DOI : 10.1137 / 0206024 . ISSN 0097-5397 .
- ^ Риттер, Войцех (1980). "Правильный алгоритм предварительной обработки для поиска строки Бойера – Мура". SIAM Journal on Computing . 9 (3): 509–512. DOI : 10.1137 / 0209037 . ISSN 0097-5397 .
- ^ а б Гасфилд, Дэн (1999) [1997], «Глава 2 - Точное соответствие: классические методы, основанные на сравнении», Алгоритмы на строках, деревьях и последовательностях (1-е изд.), Cambridge University Press, стр. 19–21, ISBN 0521585198
- ^ а б Галил, З. (сентябрь 1979 г.). «Об улучшении наихудшего времени работы алгоритма сопоставления строк Бойера – Мура». Comm. ACM . Нью-Йорк: Ассоциация вычислительной техники. 22 (9): 505–508. DOI : 10.1145 / 359146.359148 . ISSN 0001-0782 . S2CID 1333465 .
- ^ Апостолико, Альберто; Джанкарло, Рафаэле (февраль 1986 г.). «Новый взгляд на поисковые стратегии Бойера – Мура – Галила» . SIAM Journal on Computing . 15 : 98–105. DOI : 10.1137 / 0215007 .
- ^ Кнут, Дональд ; Моррис, Джеймс Х .; Пратт, Воан (1977). «Быстрое сопоставление с образцом в строках» . SIAM Journal on Computing . 6 (2): 323–350. CiteSeerX 10.1.1.93.8147 . DOI : 10.1137 / 0206024 .
- ^ Гибас, Леонид ; Одлызко, Андрей (1977). «Новое доказательство линейности алгоритма поиска строки Бойера – Мура» . Материалы 18-го ежегодного симпозиума по основам информатики . Вашингтон, округ Колумбия: Компьютерное общество IEEE: 189–195. DOI : 10,1109 / SFCS.1977.3 . S2CID 6470193 .
- ^ а б Коул, Ричард (сентябрь 1991 г.). «Жесткие границы сложности алгоритма сопоставления строк Бойера – Мура» . Труды 2-го ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . Филадельфия, Пенсильвания: Общество промышленной и прикладной математики: 224–233. ISBN 0-89791-376-0.
- ^ https://lists.freebsd.org/pipermail/freebsd-current/2010-August/019310.html
Внешние ссылки
- Оригинальная статья по алгоритму Бойера-Мура
- Пример алгоритма Бойера-Мура с домашней страницы Дж. Стротера Мура , соавтора алгоритма.
- Статья Ричарда Коула 1991 года, доказывающая линейность времени выполнения